Het berekenen van de vouwing van een eiwit, het simuleren van kristalgroei, het ontwerpen van vliegtuigen; heel veel problemen zijn eigenlijk samen te vatten als de zoektocht naar een optimum. Hoewel computers tegenwoordig steeds sneller worden zijn er nog steeds problemen die zoveel parameters met zoveel vrijheid bevatten dat zelfs op de snelste computers het systematisch proberen van oplossingen letterlijk eeuwen zou duren. Om voor deze problemen toch goede oplossingen te vinden wordt de genetica gebruikt.

In de jaren zestig begon John H. Holland met het bestuderen van adaptieve systemen. Een typisch voorbeeld hiervan is natuurlijk het biologische evolutieproces, maar bijvoorbeeld economische planning en psychologische leerprocessen behoren hier ook toe. Holland onderkende dat dit, alhoewel de adaptieve systemen zeer uiteenlopend zijn, in feite allemaal zoektochten zijn naar de best passende oplossing voor de gegeven omgeving1; en de natuur had hiervoor al een universele methode van zowel beschrijven als oplossen ontwikkeld.

Het genetische algoritme

Het genetische algoritme is een rekenmethode die de voortplanting van organismen in de natuur nabootst. Als we naar organismen in de natuur kijken zien we dat elk primair gedefinieerd wordt door zijn genotype: zijn volledige verzameling genetisch materiaal. De insteek van de evolutieleer is het onderkennen dat elk organisme een voortplantingskans heeft die afhangt van hoe goed een organisme functioneert in zijn omgeving, zijn ‘fitheid’. Als we dit willen modelleren kan dit zo complex en natuurgetrouw als de rekentijd toestaat, maar de insteek is hier niet het simuleren van de bestaande natuur, het gaat ons hier niet om de details, maar om de fundamenten van het evolutieproces. Wij kijken dus naar een zo simpel mogelijk organisme. Een monochromosomaal en haploïd organisme heeft slechts één chromosoom bestaande uit enkelstrengs DNA. We beschrijven deze slechts als een genotype en de omgeving als de functionele evaluatie hiervan. Als we nu een populatie aan organismen definiëren kunnen we, in navolging van de natuur, genetisch materiaal veranderen en uitwisselen. Dit proces bestaat fundamenteel uit een drietal stappen. Voor de nabootsing definiëren we een drietal operatoren die we op onze populatie kunnen laten werken: selectie, overkruising en mutatie.

–selectie: we selecteren de ‘ouderparen’ voor onze volgende generatie aan de hand van hun fitheid. Dit kan bijvoorbeeld door een kansproces waarbij de kans van selectie evenredig is met de fitheidswaarde (roulettewheel selection), maar we kunnen dit ook selectief uitvoeren door bijvoorbeeld slechts de fitste organismen te nemen, dus dit niet af te laten hangen van een kansproces.

–overkruising: dit is het simpelste proces van het uitwisselen van genetisch materiaal voor de volgende generatie, in navolging van haploïde voortplanting. Hierbij worden een tweetal enkelvoudige DNA-strengen uit beide ouders samengevoegd waarbij ze een verwarde dubbele DNA-streng vormen. Vervolgens worden deze bij celdeling weer in twee strengen gescheiden (meiose). Door de verwarring van de strengen (overkruising) zijn de twee kindercellen nu anders dan die van de twee ouders. De simpelste manier van dit simuleren is het zogenaamde fixed point cross-over. Hierbij wordt een vaste plek op de virtuele DNA-streng gekozen en voor dit punt wordt voor kind 1 het ‘DNA’ van ouder 1 gebruikt en daarna het ‘DNA’ van ouder 2. Voor het tweede kind is dit omgekeerd.

–mutatie: in de natuur komt ook mutatie met een kleine kans voor. Bij de methode waarbij we de natuur willen nabootsen is het ook essentieel dat dit voorkomt, omdat een groot aantal DNA-reeksen niet door overkruising gevormd kan worden, maar wel door mutatie. Na het scheppen van de volgende generatie organismen passen we dus een kans op mutatie toe. Het simpelste is om hierbij elke ‘bit’ (nul of één) op de DNA-streng afzonderlijk te bekijken en met een bepaalde kans deze om te zetten in zijn tegengestelde (bit-flipping).

We hebben dus hierna een nieuwe generatie die deels bestaat uit de vorige generatie en deels bestaat uit nieuw gevormde organismen. We kunnen dan het evolutieproces simuleren door dit proces van selectie, overkruising en mutatie een aantal generaties lang toe te passen. We zien dan dat onze populatie zich gaat vormen aan de hand van de gekozen fitheidsfunctie.

Een eendimimensionaal voorbeeld

Als een populatie zich vormt naar de fitheidsfunctie, door toepassing van de evolutie-operatoren, kunnen we een willekeurige fitheidsfunctie nemen en onze populatie zich daarnaar laten vormen. Neem bijvoorbeeld de functie f(x) in (1).

(1) f(x) = -7,70 · 10-5 x4 + 8,65 · 10-3 x3 – 0,306 x2 + 4x + 10


Figuur 1. De grafiek van de fitheidsfunctie (1)

We kiezen als beginpopulatie een aantal mogelijke oplossingen (waarden voor x). Het is duidelijk dat we van tevoren het domein en de nauwkeurigheid (de oplossingsruimte) van de uiteindelijke oplossing zullen moeten kiezen, omdat de chromosoomgrootte hiervan afhangt. In dit geval kiezen we als domein 0 ≤ x ≤ 63 en als nauwkeurigheid nemen we op gehele getallen precies. Dit betekent dat we een chromosoom voor kunnen stellen als de binaire waarde voor x. Elk chromosoom bestaat dus uit een zestal nullen en enen. We beginnen door twintig van deze chromosoomstrengen willekeurig te kiezen. Om het proces zo simpel mogelijk te houden nemen we als selectieoperator ‘de fitste tien’, als overkruisingsoperator nemen we fixed point cross-over bij bits 3 en 4 en stellen we de kans op mutatie op nul. We krijgen dan bijvoorbeeld de onderstaande beginpopulatie (G0).


Tabel 1. Een beginpopulatie G0

Vervolgens selecteren we de fitste tien. In dit geval {13, 20, 15, 8, 10, 17, 5, 6, 9, 3}. Deze chromosomen, nu beschouwd als ouderparen, leveren na overkruising weer tien nieuwe kinderen: {13+20, 20+13, 15+8, 8+15, 10+17, 17+10, 5+6, 6+5, 9+3, 3+9}. De kans op mutatie is hier voor het gemak op nul gezet. 

We hebben nu de nieuwe generatie (G1) gevormd. Dit proces laten we een aantal generaties doorgaan. De uitkomst hiervan is gegeven in de onderstaande figuur, samen met de originele functie.


Figuur 2. Histogram van de populatieontwikkeling overlegd met de fitheidsfunctie (1)

We zien hier dat de populatie van achtereenvolgende generaties zich steeds meer gaat vormen naar de gekozen fitheidsfunctie (1), totdat bij generatie 6 de gehele bevolking hetzelfde genotype heeft: x = 48 (000011). Omdat we bij elke stap selecteren op hoogste fitheid loopt de bevolking steeds verder naar het maximum van de functie toe. We stellen met de fitheidsfunctie een te optimaliseren probleem en de populatie ‘zoekt’ vervolgens de beste oplossing.

Voor- en nadelen

Exploratie en exploitatie

Als we naar de beginpopulatie kijken zien we dat bij de eerste drie bits de combinatie 010 niet voorkomt, zo komt ook de combinatie 000 niet voor bij de laatste 3 bits. Dat betekent dat we bij de overkruising nooit oplossingen zullen vinden die beginnen met 010 of eindigen met 000, hiermee verkleinen we het aantal oplossingen dat we doorzoeken. Om ervoor te zorgen dat er geen oplossingen bij voorbaat uitgesloten worden moeten we de mutatie-operator toepassen, hetgeen we niet gedaan hebben bij het voorbeeld hierboven. Hiermee zorgen we dat het algoritme de gehele oplossingsruimte doorzoekt. Het nadeel dat we hebben is dat bij voldoende grote kans op mutatie de populatie niet langer naar één oplossing convergeert. De mutatiekans is dus een parameter voor de verbreding en verdieping van de zoektocht naar het optimum. Als de kans op muteren niet groot genoeg is dan hangt de gevonden eindoplossing te veel af van de beginpopulatie en is er een goede kans dat de gevonden oplossing een locaal maximum is, dat wil zeggen dat de functie links en rechts van dit punt afloopt, maar dit niet het hoogste punt van de functie is. Als de kans op muteren te groot is verspreidt de populatie zich te veel en zal deze geen maximum vinden.

Efficiëntie

Het aantal berekeningen dat gemaakt moet worden voordat we het maximum vinden is niet te zeggen, omdat we niet kunnen vaststellen dat we het maximum gevonden hebben. Ook is niet te zeggen hoe snel de populatie zal convergeren. Op het moment dat de populatie convergeert kunnen we concluderen dat we een maximum bereikt hebben, maar niet per se een globaal maximum. Dit blijven fundamentele nadelen van deze methode. De methode doorzoekt echter wel zeer snel grote hoeveelheden van de oplossingsruimte en convergeert meestal al na enkele tientallen generaties. De rekentijd die hierbij hoort is ongeveer evenredig met de populatiegrootte en evenredig met het aantal generaties dat we door blijven evolueren. Deze methode vindt niet met zekerheid de beste oplossing, maar kan wel betrekkelijk snel een goede oplossing vinden. Bij veel toepassingen is het ook niet noodzakelijk om de beste oplossing te vinden; een die boven een bepaalde kwaliteitseis zit is voldoende.

Probleemkennis

Bij het voorbeeld weten we hoe de oplossingsruimte eruitziet en zijn er ook veel efficiëntere en snellere methoden om het globale maximum te vinden. Het voordeel echter is dat deze methode ook klakkeloos op een ander probleem toegepast kan worden. Als er maar een fitheidsfunctie aan toegekend kan worden die naar een optimum toe loopt, zodat het onderscheid gemaakt kan worden tussen twee oplossingen door waar te nemen welk van de twee dichter bij het optimum zit. We kunnen dus eigenlijk zonder kennis van het probleem toch het probleem oplossen.

Het handelsreizigersprobleem

‘Gegeven een aantal steden (N), met bekende afstanden daartussen, wat is de kortste route waarlangs al deze steden worden bezocht met terugkeren naar de beginstad?’

Dit probleem betreft een variatie op de wiskundige problemen behandeld door de negentiende-eeuwse Ierse wiskundige sir William Rowan Hamilton. De cyclische route langs een aantal ‘steden’ heet dan ook een Hamilton-cykel. De simpelste methode voor de aanpak van dit probleem is door systematisch alle mogelijke oplossingen na te gaan en vervolgens de beste te kiezen. Het nadeel hiervan is dat het aantal mogelijke oplossingen zeer snel toeneemt als het aantal te bezoeken steden stijgt. 

Als aangenomen wordt dat de afstand van stad A naar stad B even groot is
als van B naar A dan is de formule voor het aantal oplossingen M afhankelijk van het aantal steden N gegeven door (2).

(2) M(N) = (N – 1)! / 2 

Dit houdt in dat er voor 5 steden er 12 mogelijke oplossingen zijn, maar voor 12 steden zijn het er al 19.958.400. Zelfs met een computer die elke 250 nanoseconden een oplossing kan proberen zou de oplossing voor slechts 20 steden 482 jaar op zich laten wachten.


Figuur 3. Geschatte rekentijden voor het handelsreizigersprobleem afhankelijk van het aantal te bezoeken steden

Via deze methode is het niet mogelijk om efficiënt en met zekerheid de beste oplossing van dit probleem te vinden, maar met behulp van een genetisch algoritme kunnen we wel snel een misschien minder optimale maar goede oplossing vinden. Gezien de oplossing dan bestaat uit een route van stad naar stad, waarbij vereist is dat we elke stad eenmaal aandoen, is de hierboven beschreven fixed point cross-over niet een goede manier van het combineren van twee chromosomen. De meeste kinderchromosomen die bij dit proces gevormd worden zullen niet voldoen aan deze eis. Wij lossen dat in dit geval op door wel de gewone overkruising te gebruiken, maar vervolgens in de twee oplossingen de tweemaal aangedane steden willekeurig te vervangen door steden die men nog niet aangedaan heeft.

We beginnen door twintig steden te nemen (A t/m T) en deze willekeurig coördinaten toe te wijzen tussen 0 ≤ x < 400 en 0 ≤ y < 300. Vervolgens gebruiken we een aangepaste versie van het programma GASalesman uit het pakket GAcode_JDK1.2 van Jeff Smith.2 GAcode_JDK1.2 is een programmapakket van Jeff Smith dat samen met de Java-broncode gratis beschikbaar is. Inmiddels is dit pakket opgegaan in GAlib.3 Dit pakket is gemaakt als illustratie van de werking van genetische algoritmen en levert een simpel kader waarbinnen een programma een genetisch algoritme kan gebruiken. Ook zit hierbij een voorbeeld waarmee het handelsreizigersprobleem is aan te pakken. Het meegeleverde programma genereert elke keer opnieuw twintig willekeurige steden in een eendimensionale ruimte, maar dit passen we dus eerst aan voor een set willekeurige, maar vaste locaties in een tweedimensionale ruimte door een paar kleine wijzigingen in de broncode. Omdat we hier op zoek zijn naar de kortste weg gebruiken we voor de fitheid van een oplossing de reciproque weglengte (1/lengte). Het programma genereert eerst vijfhonderd willekeurige oplossingen en laat deze vervolgens tweehonderd generaties lang ontwikkelen. Dit doen we tien maal en we slaan elke keer de beste oplossing op. De uitkomsten staan in de onderstaande tabel.


Tabel 2. De tien gevonden oplossingen voor een willekeurig 20-stads handelsreizigersprobleem na rekentijd van 278 seconden

We zien hier dat zowel #1 als #3 dezelfde kortste weglengte hebben, ondanks dat ze een ander genotype hebben. De paden zijn namelijk cyclisch en bidirectioneel, dus het maakt niet uit waar we beginnen en of we links of rechtsom gaan, daarmee definiëren een twintigtal verschillende chromosomen hetzelfde pad. We zien ook dat #5 en #10 dezelfde zijn. Om dit geheel te verduidelijken zijn alle gevonden beste paden hieronder weergegeven.


Figuur 4. De tien gevonden oplossingen voor een willekeurig 20-stads handelsreizigersprobleem na rekentijd van 278 seconden

Fitheid

Het duurde 278 seconden om dit geheel uit te voeren op een gewone pc (4,2 Ghz equivalent). Al na 27 seconden was een goede (#1, de beste) oplossing gevonden. Een grote verbetering ten opzichte van de schatting van 482 jaar voor de methode die alle mogelijkheden doorloopt. Bovendien duurt het om bij 21steden de kortste weg te zoeken bij de algoritmische methode naar schatting maar zo’n 5% langer, terwijl de precieze methoden dan 100% langer duren. We zien dus dat als we de methode van de natuur volgen we snel goede oplossingen kunnen vinden op zeer complexe problemen, zonder dat we precieze ‘kennis’ hoeven te hebben van het probleem en hoe het in elkaar zit. Het enige wat mogelijk moet zijn is dat we een fitheid kunnen toekennen aan een oplossing.