Evolutionary search strategies in constraint programming
Date
2020-03
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
ENGLISH ABSTRACT: Successful approaches towards solving complex combinatorial optimisation problems straddle a boundary between art and science. Discrete search spaces are typically notoriously large, contain
high-dimensional dependencies and usually remain intractable for large instances. Generalised
mathematical relaxations that allow discrete problems to be solved in a near-trivial manner are not known. As such, researchers have focussed on approximate solution techniques, heuristics and metaheuristics for solving classes of such complex problems. Many of these techniques have forgone mathematical guarantees in favour of bio-inspired mechanisms which can produce good solutions.
Constraint Programming (CP) is a discrete optimisation technique which, historically, has not received as much attention as its linear and mixed integer counterparts in the literature. CP has, however, gained popularity in recent years due to its direct modelling approach, its ability to solve a large range of medium-sized optimisation problems with complex constraints, and the
maturity of the modelling language.
It is advocated in this dissertation that a best-of-breed approach to combinatorial optimisation be adopted which leverages the modelling exibility of CP and evolutionary processes for searchpolicy generation as a function of the underlying abstract problem representation. Research
into the algorithm selection problem which simultaneously solves the problem of generating new
algorithms while allowing for selecting from an existing corpus of algorithms is limited. A literature review of the relevant solution components is provided. An incremental approach to testing these components is employed where the merits of the various algorithmic components
are demonstrated, highlighting novelties in the methodology applied. Commentary on the computational performance and quality of results achieved is also provided. It is concluded that evolutionary algorithms serve as a suitable metaheuristic paradigm, capable of finding high-quality branching schemes for resolving constraint satisfaction problems more effectively
than those of a benchmark algorithm. A single-objective and a multi-objective optimisation approach are tested, and it is found that the multi-objective approach facilitates the formation of higher-quality strategies during the evolutionary search process.
It is further demonstrated that the search strategies uncovered not only extend their performance
characteristics to unseen problem instances of the same class, but also that a deep learning model
may be employed as a predictor of performance when selecting a strategy for an unseen problem instance. A commentary is provided as to likely areas of potential future work as a result of the methodology and findings of this dissertation.
AFRIKAANSE OPSOMMING: Suksesvolle benaderings tot die oplossing van komplekse kombinatoriese optimeringsprobleme oorspan 'n grens tussen kuns en wetenskap. Diskrete soekruimtes is tipies problematies groot, bevat hoe-dimensionele afhanklikhede en groot gevalle bly normaalweg onoplosbaar. Veralgemene wiskundige verslappings waarvolgens diskrete probleme byna triviaal oplosbaar word, is nie bekend nie. As sulks, het navorsers gefokus op benaderde oplossingstegnieke, heuristieke en meta-heuristieke om klasse van sulke ingewikkelde probleme mee op te los. Baie van hierdie tegnieke het wiskundige waarborge ten gunste van bio-geinspireerde meganismes wat goeie oplossings kan lewer, versaak. Beperkingsprogrammering (BP) is 'n diskrete optimeringstegniek wat histories nie soveel aandag soos lineêre en gemengde heelgetalligeprogrammering, in die literatuur geniet het nie. BP het egter die afgelope paar jaar gewildheid verwerf vanwee die direkte modelleringsbenadering daarvan, die vermoë om 'n groot verskeidenheid medium-grootte optimeringsprobleme met ingewikkelde beperkings op te los, en die volwassenheid van die gepaardgaande modelleringstaal. In hierdie proefskrif word daar voorgestel dat 'n beste-van-telingsbenadering tot kombinatoriese optimering in gebruik geneem word wat die modelleringsvryheid van BP en evolusionêre prosesse vir soekbeleidgenerering as 'n funksie van die onderliggende abstrakte probleemvoorstelling benut. Navorsing oor die algoritme-seleksieprobleem wat tegelykertyd die probleem van die ontwerp van nuwe algoritmes oplos en ook 'n keuse uit 'n bestaande groep algoritmes toelaat, is beperk. 'n Literatuuroorsig van die toepaslike oplossingskomponente word aangebied. Daar word gebruik gemaak van 'n inkrementele benadering tot die toetsing van hierdie komponente waartydens die meriete van die verskillende algoritmiese komponente gedemonstreer word, wat nuwe elemente in die toegepaste metodologie beklemtoon. Kommentaar oor die berekeningsprestasie en die kwaliteit van die resultate bereik, word ook gelewer. Daar word tot die gevolgtrekking gekom dat evolusionêre algoritmes as 'n geskikte meta-heuristiese paradigma dien en daartoe in staat is om hoe-kwaliteit vertakkingskemas vir die oplossing van beperkingvoldoeningsprobleme te vind wat meer doeltreffend is as die van 'n maatstafalgoritme. 'n Enkeldoelige en 'n meerdoelige optimeringsbenadering word getoets, en daar word bevind dat die meerdoelige benadering die vorming van strategiee van hoer gehalte tydens die evolusionêre soekproses fasiliteer. Daar word verder gedemonstreer dat die ontdekte soekstrategiee nie net hul toepaslikheid uitbrei na ongekende probleemgevalle van dieselfde klas nie, maar ook dat 'n diepleermodel, as 'n voorspeller van prestasie by die keuse van 'n strategie vir 'n ongesiene probleemgeval gebruik kan word. Kommentaar word gelewer oor waarskynlike gebiede van moontlike toekomstige werk wat uit die metodologie en bevindings in hierdie proefskrif voortvloei.
AFRIKAANSE OPSOMMING: Suksesvolle benaderings tot die oplossing van komplekse kombinatoriese optimeringsprobleme oorspan 'n grens tussen kuns en wetenskap. Diskrete soekruimtes is tipies problematies groot, bevat hoe-dimensionele afhanklikhede en groot gevalle bly normaalweg onoplosbaar. Veralgemene wiskundige verslappings waarvolgens diskrete probleme byna triviaal oplosbaar word, is nie bekend nie. As sulks, het navorsers gefokus op benaderde oplossingstegnieke, heuristieke en meta-heuristieke om klasse van sulke ingewikkelde probleme mee op te los. Baie van hierdie tegnieke het wiskundige waarborge ten gunste van bio-geinspireerde meganismes wat goeie oplossings kan lewer, versaak. Beperkingsprogrammering (BP) is 'n diskrete optimeringstegniek wat histories nie soveel aandag soos lineêre en gemengde heelgetalligeprogrammering, in die literatuur geniet het nie. BP het egter die afgelope paar jaar gewildheid verwerf vanwee die direkte modelleringsbenadering daarvan, die vermoë om 'n groot verskeidenheid medium-grootte optimeringsprobleme met ingewikkelde beperkings op te los, en die volwassenheid van die gepaardgaande modelleringstaal. In hierdie proefskrif word daar voorgestel dat 'n beste-van-telingsbenadering tot kombinatoriese optimering in gebruik geneem word wat die modelleringsvryheid van BP en evolusionêre prosesse vir soekbeleidgenerering as 'n funksie van die onderliggende abstrakte probleemvoorstelling benut. Navorsing oor die algoritme-seleksieprobleem wat tegelykertyd die probleem van die ontwerp van nuwe algoritmes oplos en ook 'n keuse uit 'n bestaande groep algoritmes toelaat, is beperk. 'n Literatuuroorsig van die toepaslike oplossingskomponente word aangebied. Daar word gebruik gemaak van 'n inkrementele benadering tot die toetsing van hierdie komponente waartydens die meriete van die verskillende algoritmiese komponente gedemonstreer word, wat nuwe elemente in die toegepaste metodologie beklemtoon. Kommentaar oor die berekeningsprestasie en die kwaliteit van die resultate bereik, word ook gelewer. Daar word tot die gevolgtrekking gekom dat evolusionêre algoritmes as 'n geskikte meta-heuristiese paradigma dien en daartoe in staat is om hoe-kwaliteit vertakkingskemas vir die oplossing van beperkingvoldoeningsprobleme te vind wat meer doeltreffend is as die van 'n maatstafalgoritme. 'n Enkeldoelige en 'n meerdoelige optimeringsbenadering word getoets, en daar word bevind dat die meerdoelige benadering die vorming van strategiee van hoer gehalte tydens die evolusionêre soekproses fasiliteer. Daar word verder gedemonstreer dat die ontdekte soekstrategiee nie net hul toepaslikheid uitbrei na ongekende probleemgevalle van dieselfde klas nie, maar ook dat 'n diepleermodel, as 'n voorspeller van prestasie by die keuse van 'n strategie vir 'n ongesiene probleemgeval gebruik kan word. Kommentaar word gelewer oor waarskynlike gebiede van moontlike toekomstige werk wat uit die metodologie en bevindings in hierdie proefskrif voortvloei.
Description
Thesis (PhD)--Stellenbosch University, 2020.
Keywords
Machine learning -- Decision making, Combinatorial optimization, Constraint programming (Computer Science), Genetic algorithms, Database searching, Evolutionary programming (Computer Science), UCTD