Dynamic co-evolutionary algorithms for dynamic, constrained optimisation problems
Date
2021-03
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
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.
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.
Description
Thesis (PhD)--Stellenbosch University, 2021.
Keywords
Optimisation process, Automatic differentiation, Constrained optimization, Constrained dynamics