Investigating hyperheuristics for solving bi-objective simulation optimisation problems

Simple item page
dc.contributor.advisorBekker, JFen_ZA
dc.contributor.advisorNel, GSen_ZA
dc.contributor.authorNigrini, Leanneen_ZA
dc.contributor.otherStellenbosch University. Faculty of Engineering. Dept. of Industrial Engineering.en_ZA
dc.date.accessioned2023-02-10T17:11:33Zen_ZA
dc.date.accessioned2023-05-18T07:02:19Zen_ZA
dc.date.available2023-02-10T17:11:33Zen_ZA
dc.date.available2023-05-18T07:02:19Zen_ZA
dc.date.issued2023-02-10en_ZA
dc.descriptionThesis (MEng)--Stellenbosch University, 2023.en_ZA
dc.description.abstractENGLISH ABSTRACT: The investigation and exploration of search and optimisation methodologies are crucial research areas. Take for example the potential impact of an effective and computationally efficient decision support methodology, it could be the difference between life and death in healthcare scheduling. Schedule too few doctors and patients could die; schedule long work-hours and doctors could make fatal mistakes due to fatigue. Simulation optimisation is typically used to approximately solve large and complex problems that cannot be solved by exact methods. In addition, the need for better simulation optimisation approaches are further motivated by the combinatorial relationship that results in significant search spaces. One of the biggest problems that researchers face with metaheuristic approaches is the lack of general applicability and the high number of hyperparameter combinations that algorithms have and a lack of insight on how to choose them. This is due to the fact that the performance of metaheuristics greatly depends on the type of problem being optimised, as supported by the no free lunch (NFL) theorem. Accordingly, each optimisation algorithm has its strengths and weaknesses when it comes to exploring the search space. Hyperheuristics propose to compensate, to some extent, for the weaknesses of the individual low-level heuristics (LLHs) by method of algorithmic cooperation, creating ensemble algorithms that are more generally applicable, i.e. can solve a larger range of problems than the individual LLHs are capable of solving. In this study, two hyperheuristic approaches are developed, one for population-based search and the second for single-solution based search, and are assessed using five discete-event dynamic stochastic bi-objective simulation optimisation problems. The hyperheuristics as well as their individual LLHs are implemented and assessed in Tecnomatix Plant Simulation. In addition, an algorithmic parameter study is presented for the respective LLHs to determine good hyperparameter combinations and possibly infer insights from the complex interaction. Furthermore, due to the dynamic and stochastic nature of simulation models, there exists a sufficient number of observations per solution that need to be evaluated to be able to construct suitable narrow confidence intervals. This renders simulation optimisation computationally expensive and for that reason a pilot study is conducted to determine the feasibility of an ANN as metamodel to screen out solutions that are predicted to be of low-quality, thereby reducing the number of computationally expensive evaluations that need to be made by the simulation model. The statement that hyperheuristics perform better (or at least similar) to its individual LLHs does not hold true for the population-based hyperheuristic. The statement, however, holds true for the single-solution based hyperheuristic. It can be concluded that both hyperheuristics failed to exhibit superior performance and did not indicate favourable performance improvements relative to all the individual applications of the LLHs. Furthermore, the novel pilot study provided valuable insights pertaining to the complex interaction within an ANN, however, the study could not conclude whether or not an ANN metamodel is a feasible solution to enhance the simulation optimisation process. The study does provide valuable insights which could inspire further research. en_ZA
dc.description.abstractAFRIKAANS OPSOMMING: Die ondersoek en verkenning van optimeringmetodes word beskou as ’n kritieke navorsings gebied. Simulasie-optimeringsmetodes word dikwels gebruik om benaderde oplossings te vind vir komplekse probleme wat onoplosbaar is deur presiese metodes. Die behoefte vir beter optimeringsmetodes word verder gemotiveer deur kombinatoriese verwantskappe wat lei tot beduidende groot besluitnemingsruimtes. Een van die grootste tekortkominge in navorsing in hierdie gebied is die gebrek aan metaheuristieke wat oor die algemeen toepaslik is asook die groot aantal algoritme parameters wat kundigheid verg om van te kies. Dit is as gevolg van die metaheuristieke se sterk en swakpunte, in terme van die besluitnemingsruimte verken, wat lei tot die metaheuristiek se vermo¨e om sekere probleme goed te kan benader en ander nie. Hiperheuristieke is voorgestel met die doel om vir die swakpunte van die enkele metaheuristieke of heuristieke komponente te kompenseer deur middel van algoritme samewerking om gevolglik ’n groter verskeidenheid van optimeringsprobleme te kan benader as voorheen. Twee hiperheuristieke was voorgestel en ontwikkel in hierdie studie. Die een volg ’n enkel-oplossing benadering, terwyl die ander ’n populasie-oplossing benadering volg. Die uitvoer van die voorgestelde hiperheuristieke was in Tecnomatix Plant Simulation verrig en geevalueer op vyf tweedoelige stogastiese en dinamies simulasie optimeringsprobleme. Daarby, was ’n omvattende parameterevaluarings studie uitgevoer met die doel om afleidings te kan maak oor die komplekse interaksies wat plaasvind tussen die parameters. As gevolg van die stogastiese en dinamies aard van die simulasie-optimeringsprobleme moet daar ’n sekere aantal observasies per oplossing geevalueer word om sodoende nou vertrouensintervalle te bewerkstellig. Dit is as gevolg van die statistiese steekproefneming dat die produksielopies tydrowend is. Gevolglik is ’n ondersoek ingestel om te bepaal of ’n kunsmatige neurale netwerk as ’n metamodel die simulasie optimeringsoekproses kan ondersteun. Die opvatting dat hiperheuristieke se prestasie beter of ten minste dieselfde is as sy individuele algoritmes, geld nie vir die populasie-oplossing hiperheuristiek nie. Die verklaring geld wel vir die enkel-oplossing hiperheuristiek wat ten minste so goed gedoen het of beter as al sy individuele heuristieke. Om af te sluit, die beslissing wat gevind was in die studie is dat die hiperheuristieke nie beter presteer het in vergelyking met al hulle individuele algoritmes nie. Die uiteinde van die ondersoek kon nie oortuigend tot ’n beslissing kom nie en daarom moet verdere ondersoek ingestel word. Waardevolle insigte is wel verkry uit die studie en kan gebruik work om verdere navorsing te inspireer. en_ZA
dc.description.versionMastersen_ZA
dc.format.extentxxxiv, 289 pages : illustrations.en_ZA
dc.identifier.urihttp://hdl.handle.net/10019.1/127060en_ZA
dc.language.isoen_ZAen_ZA
dc.language.isoen_ZAen_ZA
dc.publisherStellenbosch : Stellenbosch Universityen_ZA
dc.rights.licenseStellenbosch Universityen_ZA
dc.subject.lcshLithium ion batteriesen_ZA
dc.subject.lcshRecycling (Waste, etc.)en_ZA
dc.subject.lcshValue analysis (Cost control)en_ZA
dc.subject.lcshHeuristic algorithmsen_ZA
dc.subject.lcshMachine Learningen_ZA
dc.subject.lcshOptimization -- Simulation methodsen_ZA
dc.titleInvestigating hyperheuristics for solving bi-objective simulation optimisation problemsen_ZA
dc.typeThesisen_ZA
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
nigrini_investigating_2023.pdf
Size:
4.12 MB
Format:
Adobe Portable Document Format
Description:
Download
Collections
Masters Degrees (Industrial Engineering)