Dynamic co-evolutionary algorithms for dynamic, constrained optimisation problems

Pampara, Gary (2021-03)

Thesis (PhD)--Stellenbosch University, 2021.

Thesis

ENGLISH ABSTRACT: Dynamic, constrained optimisation problems (DCOPs) are a class of optimisa- tion problem where the problem landscape changes and problem constraints optionally change over time. Although DCOPs represent the super-set of op- timisation problems, relatively little is understood about these problems due to the complexity added to the optimisation process. However, unlike the available optimisation algorithms developed for changing problem landscapes, few algorithm variants exist for DCOPs. Optimisation algorithms for DCOPs are expected to not only adapt to the changing problem landscape but need to also consider the feasibility of solutions whilst adapting to any changes to the problem constraints over time. This thesis examines the constituent parts of the optimisation process by providing an in-depth review of the optimisation process. A substantial chal- lenge is created by DCOPs for optimisation algorithms and this thesis examines these problems in detail with a fitness landscape analysis (FLA), before propos- ing a DCOP benchmark generator capable of producing a truly comprehensive set of possible problem landscape and constraint combinations. Quantification of the performance of optimisation algorithms on these comprehensive DCOP instances is identified as being problematic. The behaviour of the algorithm during the entire optimisation process should provide a better indication of algorithm performance and this thesis proposes a new measurement capable of quantifying algorithm performance from the very beginning of the optimisation process. Generally, a constraint handling method is used to manage the optimisation problem constraints for the optimisation algorithm. The constraint handling method should also adapt to the changing optimisation problem. As a result, adaptive constraint handling methods are thought to be best. However, many of these methods introduce additional control parameters that require tuning which is not useful within DCOPs. This thesis provides evidence that a dy- namic co-evolutionary approach using the Lagrangian transformation of the optimisation problem can produce solutions to DCOPs. The co-evolutionary approach uses dynamic optimisation algorithms in order to adapt to both the changing problem landscape and changing problem constraints. This thesis also proposes a novel self-adaptive quantum particle swarm optimisation as one of these dynamic optimisation algorithms. Lastly, this thesis proposes a reproducible framework for computational intelligence allowing for the perfect replication of the experimental work of the aforementioned dynamic co-evolutionary algorithms.

AFRIKAANSE OPSOMMING: Dinamiese, beperkte optimeringsprobleme (DCOPs) is ’n klas optimeringsprob- leem waar die probleemlandskap verander en probleembeperkings opsioneel ve- rander met die verloop van tyd. As gevolg van die addisionele kompleksiteit wat hierdie klas van optimeringsprobleem by die optimeringsproses byvoeg, word daar huidiglik relatief min verstaan omtrent dié superstel van optimeringsprob- leme. Daar is ’n klein aantal optimeringsalgoritmes wat tans beskikbaar is vir veranderende probleemlandskappe soos DCOPs. Dit word van optimer- ingsalgoritmes vir DCOPs verwag om nie net by die veranderende probleem- landskap aan te pas nie, maar ook om die haalbaarheid van oplossings te oorweeg. Terselfdertyd moet optimeringsalgoritmes ook by enige verandering in die probleembeperkings aanpas met tyd. Hierdie proefskrif ondersoek die dele van die optimeringsproses deur ’n diepgaande oorsig van die optimeringsproses te gee. Die uitdagings wat deur DCOPs aan optimeringsalgoritmes gestel word is groot, en hierdie proefskrif ondersoek hierdie probleme deur “fiksheidlandskapanalise” (FLA). Nadat die eienskappe van die probleme ondersoek is, word ’n funksie voorgestel wat DCOP probleme kan genereer. Hierdie funksie kan ’n reeks van moontlike probleemlandskap en beperkingskombinasies lewer. Die kwantifisering van optimeringsalgoritme oplossings wat vir die reeks probleme gevind word, kan as problematies geïdentifiseer word. Die versameling van resultate na elke iterasie van ’n algoritme gee ’n beter aanduiding van die kwalitiet van oplossings wat deur ’n algoritme gevind kan word. In hierdie proefskrif word ’n nuwe metingsproses voorgestel wat die kwalitiet van algoritme oplossings kan bepaal, vanaf die begin van die optimeringsproses tot en met die einde daarvan. Oor die algemeen word ’n beperkingshanteringmetode gebruik om die probeem beperkings vir die optimeringsalgoritme te bestuur. Die beperkinghanter- ingsmetode moet ook aanpas by enige verandering van die optimeringsprobleem. As gevolg hiervan word aanpasbare metodes vir die hantering van probleem- beperkings as die beste beskou. Ongelukkig benodig baie van die probleem- beperking metodes addisionele beheerparameters wat ingestel moet word, maar die instel van beheerparameters maak geen sin binne DCOPs nie. Hierdie proefskrif lewer bewys dat ’n dinamiese ko-evolusionêre benader- ing wat die Lagrangiaanse transformasie van die optimeringsprobleem gebruik, oplossings vir DCOPs kan lewer. Die ko-evolusionêre benadering gebruik dinamiese optimeringsalgoritmes om aan te pas by die veranderende probleem- landskap en veranderende probleembeperkings. Hierdie proefskrif stel ook ’n nuwe selfaanpassende “kwantum deeltjieswerm optimeringsalgoritme” voor as een van hierdie dinamiese optimeringsalgoritmes. Laastens stel hierdie proefskrif ’n raamwerk voor vir rekenaarintelligensie paradigmas wat die perfekte replikasie van die eksperimentele werk van die bogenoemde dinamiese ko-evolusionêre algoritmes moontlik maak.

Please refer to this item in SUNScholar by using the following persistent URL: http://hdl.handle.net/10019.1/110453
This item appears in the following collections: