A qualitative model of evolutionary algorithms
Date
2014-04
Authors
Fagan, Francois
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
ENGLISH ABSTRACT: Evolutionary Algorithms (EAs) are stochastic techniques, based on the idea of biological evolution,
for finding near-optimal solutions to optimisation problems. Due to their generality and
computational speed, they have been applied very successfully in a wide range of disciplines.
However, as a consequence of their stochasticity and generality, very little has been rigorously
established about their performance. Developing models for explaining and predicting algorithmic
performance is, in fact, one of the most important challenges facing the field of optimisation.
A qualitative version of such a model of EAs is developed in this thesis.
There are two paradigms for explaining why EAs are expected to converge toward an optimum.
The traditional explanation is that of Universal Darwinism, but an alternative explanation is
that they are hill climbing algorithms which utilise all possible escape strategies — restarting
local search, stochastic search and acceptance of non-improving solutions. The combination of
the hill climbing property and the above escape strategies leads to a fast algorithm that is able
to avoid premature convergence.
Due to the difficulty in mathematically or empirically explaining the performance of EAs, terms
such as exploitation, exploration, intensity and diversity are routinely employed for this purpose.
Six prevalent views on exploitation and exploration are identified in the literature, each expressing
a different facet of these notions. The coherence of these views is substantiated by their
deducibility from the proposed novel definitions of exploitation and exploration. This substantiation
is based on a novel hypothetical construct, namely that of a Probable Fitness Landscape
(PFL), which both unifies and clarifies the surrounding terminology and our understanding of
the performance of EAs.
The PFL is developed into a qualitative model of EAs by extending it to the notion of an Ideal
Probability Distribution (IPD). This notion, along with the criteria of diversity and computational
speed, forms a method for judging the performance of EA operators. It is used to explain
why the principal operators of EAs, namely mutation and selection, are effective.
There are three main types of EAs, namely Genetic Algorithms (GAs), Evolution Strategies
and Evolutionary Programming, each of which employ their own unique operators. Important
facets of the crossover operator (which is particular to GAs) are identified, such as: opposite
step vectors, genetic drift and ellipsoidal parent-centred probability distributions with variance
proportional to the distance between parents. The shape of the crossover probability distribution
motivates a comparison with a novel continuous approximation of mutation, which reveals very
similar underlying distributions, although for crossover the distribution is adaptive whereas for
mutation it is fixed. The PFL and IPD are used to analyse the crossover operator, the results
of which are contrasted with the traditional explanations of the Schema Theorem and Building
Block Hypothesis as well as the Evolutionary Progress Principle and Genetic Repair Hypothesis.
It emerges that the facetwise nature of the PFL extracts more sound conclusions than the other
explanations which, falsely, attempt to prove GAs to be superior.
AFRIKAANSE OPSOMMING: Evolusionere Algoritmes (EAs) is stogastiese tegnieke vir die bepaling van naby-optimale oplossings vir optimeringsprobleme wat gebaseer is op die beginsel van biologiese evolusie. As gevolg van hul algemene toepasbaarheid en hoe berekeningspoed, is hierdie algoritmes al met groot sukses in ’n wye verskeidenheid dissiplines toegepas. Die stogastiese aard en algemene toepasbaarheid van hierdie klas van algoritmes het egter tot gevolg dat baie min al oor hul werkverrigting formeel bewys is. Die ontwikkeling van modelle waarmee die doeltreffendheid van algoritmes verklaar en voorspel kan word, is trouens een van die grootste uitdagings in die studieveld van optimering. ’n Kwalitatiewe weergawe van so ’n model word in hierdie verhandeling vir EAs daargestel. Daar bestaan twee paradigmas vir die verklaring van waarom daar van EAs verwag word om na ’n optimum te konvergeer. Die tradisionele verklaring geskied aan die hand van Universele Darwinisme, maar ’n alternatiewe verklaring is dat hierdie algoritmes bergtop-soekend is en van alle moontlike ontsnapstrategiee gebruik maak — lokale soekstrategiee, stogastiese soekstrategiee en die aanvaarding van minderwaardige oplossings. Die kombinasie van die bergtop-soekende eienskap en die insluiting van die bogenoemde ontsnapstrategiee gee aanleiding tot vinnige algoritmes wat daartoe in staat is om voortydige konvergensie te vermy. Omdat dit moeilik is om die werkverrigting van EAs wiskundig of empiries te verklaar, word terminologie soos uitbuiting, verkenning, intensiteit en diversiteit roetinegewys vir hierdie doel ingespan. Ses heersende menings in die literatuur oor uitbuiting en verkenning word ge¨ıdentifiseer wat elkeen ’n ander faset van hierdie begrippe uitlig. Die samehang van hierdie menings word deur hul afleibaarheid uit nuwe definisies van uitbuiting en verkenning gedemonstreer. Hierdie demonstrasie is gebaseer op ’n nuwe hipotetiese konstruk, naamlik die van ’n Waarskynlike Fiksheidslandskap (WFL), wat beide die omliggende terminologie¨e en ons begrip van die werking van EAs enersyds verenig en andersyds verduidelik. Die begrip van ’n WFL word tot ’n kwantitatiewe model vir EAs ontwikkel deur dit tot die konstruk van ’n Ideale Waarskynlikheidsverdeling (IWV) uit te brei. Hierdie konsep word saam met die kriteria van diversiteit en berekeningspoed gebruik om ’n metode te ontwikkel waarmee die werkverrigting van EAs beoordeel kan word. Die IWV word gebruik om te verklaar waarom die hoofoperatore van EAs, naamlik mutasie en seleksie, doeltreffend is. Daar is drie tipes van EAs, naamlik Genetiese Algoritmes (GAs), Evolusionere Strategiee en Evolusionere Programmering, wat elk hul eie, unieke operatore bevat. Belangrike fasette van die oorgangsoperator (wat eie is aan GAs) word uitgelig, soos regoorstaande trapvektore, genetiese neiging en ellipsoıdale ouer-gesentreerde waarskynlikheidsverdelings met variansies wat eweredig is aan die afstand tussen ouers. Die vorm van die oorgangs-waarskynlikheidsverdeling gee aanleiding tot ’n vergelyking tussen die begrip van oorgang en ’n nuwe, kontinue benadering van mutasie. Daar word gevind dat die onderliggende verdelings baie soortgelyk is, alhoewel die oorgangsverdeling aanpasbaar is, terwyl die verdeling vir mutasie vas is. Die WFL en IWV word gebruik om die oorgangsoperator te analiseer en die resultate van hierdie analise word teenoor die tradisionele verklarings van die Skemastelling en Boublok-hipotese sowel as die Evolusionere Vooruitgangsbeginsel en die Genetiese Herstel-hipotese gekontrasteer. Dit blyk dat meer grondige gevolgtrekkings gemaak kan word uit die fasetgewyse aard van die WFL as uit ander verklarings wat valslik poog om die meer doeltreffende werkverrigting van GAs te demonstreer. Die gebruik van faset-gewyse en kwalitatiewe modelle word geregverdig deur hul sukses in terme van die verklaring van EA werkverrigting. Die argument word gemaak dat die beste rigting vir voortgesette navorsing oor EAs is om weg te bly van vergelykende studies en die afleiding van sogenaamde vergelykings van beweging, maar om eerder die ontwikkeling van wetenskaplikgefundeerde, faset-gewyse modelle vir algoritmiese werkverrigting na te streef.
AFRIKAANSE OPSOMMING: Evolusionere Algoritmes (EAs) is stogastiese tegnieke vir die bepaling van naby-optimale oplossings vir optimeringsprobleme wat gebaseer is op die beginsel van biologiese evolusie. As gevolg van hul algemene toepasbaarheid en hoe berekeningspoed, is hierdie algoritmes al met groot sukses in ’n wye verskeidenheid dissiplines toegepas. Die stogastiese aard en algemene toepasbaarheid van hierdie klas van algoritmes het egter tot gevolg dat baie min al oor hul werkverrigting formeel bewys is. Die ontwikkeling van modelle waarmee die doeltreffendheid van algoritmes verklaar en voorspel kan word, is trouens een van die grootste uitdagings in die studieveld van optimering. ’n Kwalitatiewe weergawe van so ’n model word in hierdie verhandeling vir EAs daargestel. Daar bestaan twee paradigmas vir die verklaring van waarom daar van EAs verwag word om na ’n optimum te konvergeer. Die tradisionele verklaring geskied aan die hand van Universele Darwinisme, maar ’n alternatiewe verklaring is dat hierdie algoritmes bergtop-soekend is en van alle moontlike ontsnapstrategiee gebruik maak — lokale soekstrategiee, stogastiese soekstrategiee en die aanvaarding van minderwaardige oplossings. Die kombinasie van die bergtop-soekende eienskap en die insluiting van die bogenoemde ontsnapstrategiee gee aanleiding tot vinnige algoritmes wat daartoe in staat is om voortydige konvergensie te vermy. Omdat dit moeilik is om die werkverrigting van EAs wiskundig of empiries te verklaar, word terminologie soos uitbuiting, verkenning, intensiteit en diversiteit roetinegewys vir hierdie doel ingespan. Ses heersende menings in die literatuur oor uitbuiting en verkenning word ge¨ıdentifiseer wat elkeen ’n ander faset van hierdie begrippe uitlig. Die samehang van hierdie menings word deur hul afleibaarheid uit nuwe definisies van uitbuiting en verkenning gedemonstreer. Hierdie demonstrasie is gebaseer op ’n nuwe hipotetiese konstruk, naamlik die van ’n Waarskynlike Fiksheidslandskap (WFL), wat beide die omliggende terminologie¨e en ons begrip van die werking van EAs enersyds verenig en andersyds verduidelik. Die begrip van ’n WFL word tot ’n kwantitatiewe model vir EAs ontwikkel deur dit tot die konstruk van ’n Ideale Waarskynlikheidsverdeling (IWV) uit te brei. Hierdie konsep word saam met die kriteria van diversiteit en berekeningspoed gebruik om ’n metode te ontwikkel waarmee die werkverrigting van EAs beoordeel kan word. Die IWV word gebruik om te verklaar waarom die hoofoperatore van EAs, naamlik mutasie en seleksie, doeltreffend is. Daar is drie tipes van EAs, naamlik Genetiese Algoritmes (GAs), Evolusionere Strategiee en Evolusionere Programmering, wat elk hul eie, unieke operatore bevat. Belangrike fasette van die oorgangsoperator (wat eie is aan GAs) word uitgelig, soos regoorstaande trapvektore, genetiese neiging en ellipsoıdale ouer-gesentreerde waarskynlikheidsverdelings met variansies wat eweredig is aan die afstand tussen ouers. Die vorm van die oorgangs-waarskynlikheidsverdeling gee aanleiding tot ’n vergelyking tussen die begrip van oorgang en ’n nuwe, kontinue benadering van mutasie. Daar word gevind dat die onderliggende verdelings baie soortgelyk is, alhoewel die oorgangsverdeling aanpasbaar is, terwyl die verdeling vir mutasie vas is. Die WFL en IWV word gebruik om die oorgangsoperator te analiseer en die resultate van hierdie analise word teenoor die tradisionele verklarings van die Skemastelling en Boublok-hipotese sowel as die Evolusionere Vooruitgangsbeginsel en die Genetiese Herstel-hipotese gekontrasteer. Dit blyk dat meer grondige gevolgtrekkings gemaak kan word uit die fasetgewyse aard van die WFL as uit ander verklarings wat valslik poog om die meer doeltreffende werkverrigting van GAs te demonstreer. Die gebruik van faset-gewyse en kwalitatiewe modelle word geregverdig deur hul sukses in terme van die verklaring van EA werkverrigting. Die argument word gemaak dat die beste rigting vir voortgesette navorsing oor EAs is om weg te bly van vergelykende studies en die afleiding van sogenaamde vergelykings van beweging, maar om eerder die ontwikkeling van wetenskaplikgefundeerde, faset-gewyse modelle vir algoritmiese werkverrigting na te streef.
Description
Thesis (MSc)--Stellenbosch University, 2014.
Keywords
Algorithms, Evolutionary, Optimization, Probable fitness landscape, Ideal probability distribution, Dissertations -- Industrial engineering, UCTD