Over Methodes voor
Genetische Algoritmen

Deze memo is gebaseerd op een literatuuronderzoek dat ik heb uitgevoerd als onderdeel van mijn bachelorscriptie “Het Positioneren van Personen in een Genogram”. Dit onderzoek was voor het overgrote deel gebaseerd op het werk van Sivanandan en Deepa.¹ Mits niet anders vermeld zijn de methodes die in deze memo zijn opgesomd terug te vinden in hun werk.

Een Genetisch Algoritme (GA) werkt volgens het principe van de evolutietheorie: een probleem wordt opgelost door goede eigenschappen te selecteren voor een volgende generatie oplossingen en een beperkte hoeveelheid mutaties toe te staan.

Er zijn geen specifieke eisen aan het type probleem dat met een GA kan worden opgelost, wat het een krachtig instrument maakt voor het optimaliseren van oplossingen. Een GA evolueert een of meer generaties aan potentiële oplossingen door middel van selectie, kruising en mutatie om tot een optimaal resultaat te komen, zoals geïllustreerd in Figuur 1.

In deze memo illustreer ik de werking van verschillende GA-methodes aan de hand van een door mij ontwikkelde beeldtaal, zoals te zien in Figuur 1. In deze beeldtaal worden oplossingen weergegeven als gekleurde cirkels, waarbij de kleur een bepaalde fitnesswaarde vertegenwoordigt. De fitnesswaarde van de oplossingen wordt bepaald op basis van de kleur van de cirkel, die op zijn beurt wordt bepaald door drie eigenschappen: rood $\text{R}(X)$, groen $\text{G}(X)$ en blauw $\text{B}(X)$. Voor het gemak kunnen deze drie eigenschappen in één keer worden genoteerd als $\text{RGB}(X)=(\text{R}(X),\text{G}(X),\text{B}(X))$. De waarden van deze eigenschappen liggen allemaal binnen het bereik $[0,255]$, zoals geïllustreerd in Figuur 2. De fitnesswaarde $f(X)$ bereikt de maximumwaarde van $1$ wanneer $\text{RGB}(X)=(0,0,0)$ en de minimumwaarde van $0$ wanneer $\text{RGB}(X)=(255,255,255)$. Dit betekent dat oplossingen met verschillende kleurwaarden dezelfde fitnesswaarde kunnen hebben, maar dat vormt voor de hier opgenomen voorbeelden geen probleem. Formeel kan de fitnesswaarde als volgt worden bepaald op basis van de kleurwaarde:

In sommige gevallen is het wenselijk dat de verschillende eigenschappen (rood, groen en blauw) los van elkaar worden weergegeven. In dat geval worden ze in deze volgorde van boven naar beneden geplaatst en met een zwarte omlijning weergegeven. Een voorbeeld hiervan is te zien in Figuur 3.

Het probleem van het vinden van de kleur zwart is totaal niet complex genoeg om het gebruik van een ingewikkeld optimalisatiealgoritme als een GA te kunnen verantwoorden. In het geval van deze memo is hier natuurlijk voor gekozen om zo de werking van de verschillende methoden van het algoritme begrijpbaar te maken.

Selectie

Tijdens de selectiestap van een GA worden de oplossingen geselecteerd op basis van hun fitnesswaarde, waarna een volgende generatie oplossingen wordt gegenereerd. Hiervoor zijn verschillende methoden beschikbaar, elk met hun eigen voor- en nadelen.

Roulette Wheel Selection

Bij deze methode worden oplossingen willekeurig geselecteerd, waarbij de kans op selectie evenredig is aan de fitnesswaarde van de oplossing. De generatie aan oplossingen wordt voorgesteld als een roulettewiel, waarbij de vakjes verschillende groottes hebben afhankelijk van de fitnesswaarde. Deze methode kan als neveneffect hebben dat er te snel divergentie optreedt, waardoor het algoritme vastloopt in een lokaal optimum. Een visueel voorbeeld is te zien in Figuur 4.

Rank Selection

Oplossingen worden op volgorde van fitness geplaatst, van laag naar hoog. De selectie vindt vervolgens plaats via een Roulette Wheel Selection, gebaseerd op de positie in de gesorteerde lijst met oplossingen. Deze methode vermindert de kans op te vroege divergentie en zorgt voor een meer gebalanceerde selectiedruk. Een illustratie is opgenomen in Figuur 5.

Stochastic Universal Sampling

Een variant op Roulette Wheel Selection, waarbij oplossingen worden geselecteerd met gelijkmatig verdeelde “pointers.” Het resultaat is een uniforme selectieprocedure met minder afwijkingen en een hogere betrouwbaarheid van convergentie. Bij een selectiegrootte van $N$ worden de pointers op een afstand van $\frac{1}{N}$ van elkaar geplaatst. De eerste pointer wordt willekeurig geplaatst binnen het bereik $[0,\frac{1}{N}]$, zoals geïllustreerd in Figuur 6.

Tournament Selection

Een subset van de populatie wordt willekeurig samengesteld, waarbij de oplossing met de beste fitnesswaarde wordt opgenomen in de selectie. Door de grootte van de subset aan te passen, kan de selectiedruk worden beïnvloed. In Figuur 7 is een voorbeeld van deze selectiemethode opgenomen.

Boltzmann Selection

Deze methode is gebaseerd op “simulated annealing”, waarmee het afkoelen van temperatuur wordt gesimuleerd. Gedurende het verloop van het GA neemt de selectiedruk toe, waardoor er in de beginfase meer ruimte is om oplossingen te verkennen buiten een lokaal optimum. Per generatie $g$ wordt oplossing $X_g$ geselecteerd wanneer de fitnesswaarde $f(X_g)$ groter of gelijk is aan de hoogste fitnesswaarde uit de vorige generatie: $f(X_g)\ge max(f(X_{g-1}))$. Wanneer dit niet het geval is, bestaat er alsnog een kans $P$ dat $X_g$ wordt geselecteerd:

$G$ is de maximumwaarde van $g$, oftewel het maximaal aantal generaties. Door de parameter $\alpha$ in te stellen binnen het bereik $[0,1]$ en $T_0$ binnen het bereik $[5,100]$, kan deze selectiemethode worden geconfigureerd. Om te voorkomen dat een lokaal optimum, dat later een globaal optimum blijkt te zijn, verloren gaat, kan deze methode worden gecombineerd met “elitisme,” waarbij de beste resultaten bewaard blijven tot het einde van het GA.

Kruising

Bij kruising worden de eigenschappen van twee verschillende oplossingen gecombineerd om nieuwe oplossingen te genereren. Elke kruisingsmethode heeft een ander effect op de diversiteit en de volledigheid van de doorzochte oplossingsruimte.

Single Point Crossover

Bij deze methode worden beide oplossingen op hetzelfde punt gesplitst in twee delen. De nakomelingen worden samengesteld door één deel van de ene ouder en het andere deel van de andere ouder te combineren. Hoewel deze methode eenvoudig te implementeren is, beperkt het de mate waarin de zoekruimte wordt doorzocht aanzienlijk.² Een illustratie van deze methode is te zien in Figuur 8.

Multi-Point Crossover

Deze methode lijkt op Single Point Crossover, maar verschilt doordat de oplossingen op meerdere punten worden opgesplitst. Dit is ook te zien in Figuur 9. De nakomelingen worden samengesteld door afwisselend delen van beide ouders te nemen. Met meer splitsingspunten wordt een groter deel van de zoekruimte doorzocht.

Uniform Crossover

Bij Uniform Crossover wordt de kruising uitgevoerd op basis van een binair masker dat net zo groot is als het aantal eigenschappen van de oplossingen. Op basis van de binaire waarden in het masker wordt de eigenschap overgenomen van de ene ouder (0) of van de andere (1). Deze methode introduceert een hoge mate van willekeur, maar vergroot ook de kans op suboptimale oplossingen.

Three Parent Crossover

Bij deze methode worden de eigenschappen van twee oplossingen vergeleken en overgenomen door de nakomeling wanneer ze gelijk zijn. Bij ongelijke waarden wordt de eigenschap overgenomen van een derde ouder. Dit voorkomt het ontstaan van suboptimale combinaties van eigenschappen. In Figuur 10 is een illustratie opgenomen van deze methode.

Reduced Surrogate Crossover

Splitsingspunten worden geplaatst op posities waar de oplossingen van elkaar verschillen. Hierdoor wordt gegarandeerd dat de volgende generatie altijd uit unieke oplossingen bestaat.

Shuffle

Voordat Single Point Crossover wordt toegepast, worden de eigenschappen van de oplossingen willekeurig geschud. Dit voegt een extra laag van willekeur toe, die ervoor zorgt dat een groter deel van de zoekruimte wordt benut, maar ook de kans op suboptimale resultaten vergroot. Zie Figuur 11 voor een illustratie.

Mutatie

Bij mutatie worden willekeurige wijzigingen aangebracht in de nieuwe generatie oplossingen. Dit verhoogt de diversiteit en voorkomt dat het GA vastloopt in een lokaal optimum. Afhankelijk van het probleem dat wordt opgelost, zijn verschillende methoden beschikbaar.

Flipping

Deze methode is alleen toepasbaar op genen van een binair type, waarbij de waarde van willekeurige genen in het chromosoom wordt “geflipt”, d.w.z. een 0 wordt een 1 en vice versa.

Interchanging

Twee eigenschappen van een oplossing worden willekeurig geselecteerd en de waarden worden omgewisseld. Deze methode is vooral effectief in situaties waarin de volgorde van elementen belangrijk is, zoals bij het prioriteren van activiteiten of het optimaliseren van een route.

Reversing

De volgorde van de eigenschappen van een oplossing wordt volledig omgedraaid, waardoor de oplossing verandert, maar alle bestaande waarden behouden blijven. Deze methode is bijvoorbeeld effectief bij het “Travelling Salesman” probleem.

Gespecialiseerde Mutatie (Owais-Snasel Methode)

Deze methode is ontwikkeld door Owais en Snasel voor het optimaliseren van een lattice.² Hierbij wordt de $x$-coördinaat van knooppunten in de lattice gemuteerd, maar dit kan ook worden uitgebreid naar de $y$-coördinaat. Daarom is het zeer geschikt voor coördinaat-gebaseerde problemen.

Vervanging

Nadat de nakomelingen van de geselecteerde oplossingen zijn gegenereerd en gemuteerd, moeten zij oplossingen uit de vorige generatie vervangen. Hiervoor zijn verschillende benaderingen mogelijk, afhankelijk van de gewenste balans tussen vernieuwing en behoud van goede eigenschappen.

Generational Replacement

De gehele oudergeneratie wordt vervangen door de nakomelingen die eruit zijn voortgekomen. Dit zorgt voor volledige vernieuwing bij elke iteratie van het GA, wat een hoge mate van genetische diversiteit oplevert. Het risico is echter dat goede oplossingen verloren gaan.

Steady-State Replacement

Vervanging vindt plaats op basis van de fitnesswaarden van de oudergeneratie. Alleen oplossingen die slecht presteren worden vervangen door nakomelingen. Hierdoor blijven goede eigenschappen langer behouden en verloopt de evolutie geleidelijker. Door het aantal te vervangen oplossingen en de grenswaarde voor vervanging aan te passen, kan deze methode worden geconfigureerd.

Elitisme

De oplossingen met de hoogste fitnesswaarde worden bewaard. Bij het beëindigen van het GA kunnen deze als resultaat worden opgeleverd, mocht de laatste generatie geen betere oplossingen bevatten. Hierdoor gaan goede oplossingen nooit verloren en wordt het nemen van risico’s aangemoedigd bij kruising, mutatie en vervanging.

Random Immigrants

Tijdens de vervanging worden niet alleen nakomelingen van de vorige generatie toegevoegd, maar ook nieuwe, willekeurig gegenereerde oplossingen. Dit introduceert nieuwe genetische varianten die mogelijk niet zouden zijn ontstaan uit het bestaande genetische materiaal.

Terminatie

Om het GA te beëindigen, moet aan één of meerdere stopcriteria worden voldaan. Welke criteria worden gehanteerd, hangt af van de toepassing waarvoor het algoritme wordt ingezet. Hieronder zijn enkele veelgebruikte stopcriteria opgenomen.

1. Maximale Generaties
   Het algoritme stopt na een vooraf bepaald aantal generaties.
2. Voldoende Oplossingen
   Het algoritme stopt wanneer een oplossing is gevonden die voldoet aan een vooraf bepaalde minimale fitnesswaarde.
3. Convergentie
   Het algoritme stopt wanneer de populatie convergeert, d.w.z. wanneer de diversiteit onder de oplossingen afneemt en de individuen sterk op elkaar beginnen te lijken.
4. Geen verbetering
   Het algoritme stopt wanneer er gedurende een bepaald aantal generaties geen significante verbeteringen zijn waargenomen in de beste oplossing. Dit kan gebeuren wanneer de beste fitnesswaarde stabiel blijft of schommelt tussen bepaalde waarden.