Artikel uit Kennisgeving, jrg. 12, nr 1, september 1999, pp. 13-24

Een genetisch algoritme voor het Travelling Salesman Probleem.

Ir. E. Diekema

Samenvatting

In dit artikel wordt een beschrijving gegeven van een genetisch algoritme voor de toepassing op het Travelling Salesman Probleem. Er worden een aantal verbeteringen gegeven ten opzichte van het klassieke algoritme. Tevens worden twee aanpassingen gegeven welke geen betrekking hebben op het genetisch algoritme. Dit zijn de de-crossing methode en een smoothing methode. Aan het eind worden een aantal belangrijke conclusies getrokken.

Inhoudsopgave

  1. Inleiding in het Travelling Salesman Probleem.
  2. Principe van het genetisch algoritme.
  3. Toepassing van het genetisch algoritme.
  4. Beschrijving van het programma.
  5. Verbeteringen van het programma.
  6. Conclusies.
  7. Literatuurlijst.

1. Inleiding in het Travelling Salesman Probleem.

Het Travelling Salesman Probleem (TSP) wordt als volgt gedefinieerd. Een vertegenwoordiger moet een aantal steden bezoeken. Hij moet de kortste weg nemen. Daarbij mag hij elke stad maar een keer aandoen. Het probleem is om de kortste weg te vinden. Daarbij zijn er twee varianten. Bij de eerste variant moet de vertegenwoordiger eindigen in dezelfde stad waar hij begonnen is. Bij de tweede variant mag deze laatste eis vervallen.

Het TSP is een zogenaamd erkend NP probleem. Dit betekent dat de berekening van de kortste weg via de brute kracht-methode Niet Polynomisch is. De tijdsduur van de berekening neemt sterker dan polynomisch toe als functie van het aantal steden. In de praktijk betekent dit dat als het aantal steden groot is (bijvoorbeeld meer dan 500), de berekening niet meer te doen is op een eenvoudige computer.

Een meer praktische toepassing van het probleem treedt op bij de fabricage van printplaten. Daar moeten gaten geboord worden. Ieder gat hoeft maar een keer geboord te worden. Uit economisch oogpunt is het nodig dat de boorkop(pen) een zo kort mogelijke weg nemen.

Tegenwoordig pakt men het probleem aan met een genetisch algoritme. Een nadeel bij deze aanpak is dat men nooit zeker weet of men de kortste weg heeft gevonden. Bij de brute kracht-methode weet men dit wel.

2. Principe van het genetisch algoritme.

Het principe van het genetisch algoritme is afgeleid van de methode van de survival of the fittest in de biologie.

Dit principe werkt op een vereenvoudigde manier als volgt. Van een soort is op een bepaald moment een generatie aanwezig. Van deze generatie zullen een aantal individuen zich voortplanten. De eigenschappen van de soort liggen vast in de genen van de chromosomen van het individu. Tijdens de voortplanting worden de chromosomen gekopieerd. Daarmee krijgen de nakomelingen dezelfde eigenschappen als de ouders. Soms gaat dit kopiëren niet helemaal goed. Er treedt dan een variant op: de chromosomen worden gekruist. Daarbij worden wel alle genen overgenomen, maar de volgorde kan anders zijn. Een aantal eigenschappen worden daarmee wel overgenomen, maar een klein aantal eigenschappen veranderd. Het kan zijn dat de nieuwe eigenschappen sterkere nakomelingen geven dan de ouders. De nieuwe eigenschappen zullen daarom blijvend zijn. Het kan ook zijn dat de nieuwe nakomelingen zwakker zijn dan de ouders. Als deze maar zwak genoeg zijn, zal deze tak uitsterven. Door een min of meer toevallig proces zal de soort steeds sterker worden.

Er treedt daarbij nog het verschijnsel op van de mutaties. Dit is een willekeurige verandering van een gen onder invloed van externe factoren (bijvoorbeeld de kosmische straling). Ook dan kan een sterkere individu ontstaan. Als deze maar sterk genoeg is, zal de nieuwe eigenschap blijvend zijn.

Het hoofdprincipe van de voortplanting is, dat iedere nieuwe generatie gebruik maakt van de meest goede eigenschappen van de vorige generatie.

Het principe kan vertaald worden in een genetisch algoritme voor het oplossen van een optimalisatieprobleem. Het ontwikkelen van een soort kan namelijk gezien worden als een optimalisatieprobleem als gesteld wordt dat de soort zo sterk mogelijk moet zijn om te overleven. In feite kan ieder berekeningsprobleem als genetisch algoritme geprogrammeerd worden. Daar wordt hier verder niet op ingegaan.

Wordt bovenstaand principe informatietechnisch onderzocht, dan vallen een aantal zaken op.

Het algoritme kan op de volgende manier beschreven worden.

Er wordt begonnen met het opstellen van een startgeneratie. Deze generatie bevat een aantal chromosomen (oplossingen) van het optimalisatieprobleem. Deze zijn willekeurig gekozen.

Van deze chromosomen kan bepaald worden in hoeverre ze sterk of zwak zijn. Dit betekent dat er een maat gevonden moet worden om te bepalen of een oplossing van het optimalisatieprobleem beter of slechter is dan een andere oplossing. Dit wordt bepaald middels de fitness-functie. Van deze functie is bekend voor welke waarde er een optimale oplossing van het probleem is. Dit wordt de oplossingswaarde van de fitness-functie genoemd.

Uit deze generatie worden een aantal chromosomen gekozen die met elkaar mogen paren. De keuze wordt gemaakt middels een mechanisme waarbij een sterk chromosoom een voorkeur krijgt boven een zwak chromosoom (survival of the fittest). Als de keuze gemaakt is, gaan de betrokken paren kruisen. Bij deze kruising worden twee chromosomen op een willekeurige plaats in twee stukken gehakt. Daarna worden ze kruiselings weer aan elkaar geplakt. Op deze manier ontstaat er een nieuwe generatie. Van deze nieuwe generatie kan voor iedere chromosoom de fitness bepaald worden. Als van een chromosoom de fitness-functie de gevraagde oplossingswaarde heeft, dan stelt dit chromosoom de gevraagde oplossing van het probleem voor. Vaak is echter geen oplossingswaarde te vinden. Dan is niet zeker bekend of in de nieuwe generatie de beste oplossing aanwezig is. De oplossing zal wel steeds beter worden.

In de praktijk blijkt dat als het algoritme op een dergelijke manier gebouwd wordt, dit niet altijd tot de meest optimale oplossing voert. Het kan onder andere voorkomen dat alle chromosomen dezelfde waarde krijgen. In dat geval zal er geen betere oplossing gevonden worden. Om dit probleem te omzeilen, wordt gebruik gemaakt van het mechanisme van de mutatie. Dit kan op verschillende manieren. Het hoofdprincipe is dat er zo nu en dan op een willekeurige plaats een gen verandert van waarde. Daardoor zal er nooit een uniforme generatie ontstaan. Op deze manier wordt het bereiken van een eventueel lokaal optimum voorkomen. Middels mutatie blijkt het algoritme wel goed te werken.

Samengevat ken men voor het opstellen van een genetisch algoritme een aantal stappen onderscheiden. Deze zijn:

  1. Definitie van de chromosomen en zijn genen.
  2. Definitie van de fitness-functie van een chromosoom.
  3. Keuze van de begingeneratie.
  4. Keuze van de paren chromosomen welke mogen voortplanten.
  5. Keuze van het kruisingsmechanisme.
  6. Keuze van het mutatiemechanisme.
  7. Keuze van het stopmechanisme.
Deze stappen worden in de volgende paragraaf achtereenvolgens behandeld aan de hand van het TSP.

3. Toepassing van het genetisch algoritme.

Als het genetisch algoritme toegepast wordt op het TSP, dan moeten de genoemde zeven stappen gevolgd worden.

3.1. Definitie van de chromosomen en zijn genen.

Standaard bij het TSP krijgt iedere stad een nummer. Een chromosoom wordt gedefinieerd als een totale tour. Ieder chromosoom is opgebouwd uit genen. Ieder gen stelt een stad voor. Een chromosoom wordt dan voorgesteld als een rij met getallen waarbij de volgorde van die rij de route voorstelt welke de vertegenwoordiger moet nemen. Een mogelijke oplossing van een probleem met 10 steden ziet er bijvoorbeeld als volgt uit:

13579246810

Er mogen geen twee dezelfde getallen voorkomen.

3.2. Definitie van de fitness-functie van een chromosoom.

Het TSP is in feite een optimalisatieprobleem met meerdere variabelen. Ieder gen is een variabele. De variabele is het rangnummer van een stad. Het gaat om de kortste afstand. Deze afstand wordt berekend door de onderlinge afstanden op te tellen. De onderlinge afstanden kunnen in een afstandentabel gegeven worden. Dit betekent dat de fitness-functie niets anders is dan een optelling van een aantal getallen. Dit gaat vrij snel.

3.3. Keuze van een begingeneratie.

Bij de keuze van de begingeneratie moet tevens de grootte van de generatie bepaald worden. In de praktijk is dit een even getal. Vaak wordt een generatiegrootte genomen van 30. Dit betekent dat er 30 oplossingen tegelijk meegenomen worden in het algoritme.

3.4. Keuze van de paren chromosomen welke mogen voortplanten.

Voor de reproductie van de chromosomen wordt een nieuwe generatie opgezet. Deze wordt gevuld met chromosomen uit de oude generatie. Voor de keuze van de chromosomen welke naar de nieuwe generatie gaan, zijn verschillende manieren in gebruik. Voor het klassieke algoritme wordt gebruik gemaakt van de zogenaamde fitness-balk. Deze methode wordt ook wel de roulettewiel-methode genoemd. Het principe werkt als volgt.

Iedere chromosoom heeft een bepaalde fitness-waarde. Deze kunnen als een cumulatieve balk weergegeven worden. Er wordt een voorbeeld weergegeven met fictieve fitness-waarden.

chromosoom nr.123456789101112
fitness:2536381027416
fitnessbalk:2710161927373946505157

De keuze kan gemaakt worden met een random generator die van 0 tot en met 57 loopt. Stel dat bijvoorbeeld het getal 25 uit de random generator komt. Dan wordt chromosoom 5 gekozen om naar de volgende generatie over te gaan. De chromosomen met de grootste fitness hebben zo de meeste kans op de verplaatsing naar de nieuwe generatie. Bij deze methode wordt gekeken naar de grootste fitness-functie. Een uitbreiding hiervan is om de fitness-functie tot een bepaalde macht te verheffen. De chromosomen met de grootste fitness worden op deze manier nog meer bevoordeeld.

Bij het mechanisme hoort een kans gegeven te zijn. Er wordt dan door een random-generator een getal bepaald. Is dit getal kleiner dan de gegeven kans, dan zal een kruising optreden. Is het getal groter dan de gegeven kans, dan zal geen kruising optreden.

3.5. Keuze van het kruisingsmechanisme.

Om de chromosomen te laten kruisen, zijn een aantal mogelijkheden bekend. In het klassieke algoritme worden de kruisingen gewoon paarsgewijs uitgevoerd. Er wordt met een random generator een punt gezocht. Met behulp van dit punt worden twee chromosomen gekruist. Dit wordt aan de hand van de volgende figuur uitgelegd.

Voor de kruising
chromosoom 1:
12345
246810
678910
13579
chromosoom 2:

Na de kruising
chromosoom 1:
12345
246810
13579
678910
chromosoom 2:

Duidelijk is te zien dat deze manier van kruisen voor het TSP niet een geschikte manier is. In de chromosomen komen dezelfde waarden van de genen voor. Dat betekent dat een stad meerdere malen bezocht wordt en een andere geen enkele maal. Dit mag niet.

Daarom wordt voor de kruising een andere methode gebruikt. Deze methode wordt beschreven in Goldberg en wordt aangeduid met de term Partially Matched Crossover (PMX). De methode werkt als volgt: Er worden bij deze methode twee kruispunten gebruikt. Deze punten geven de zogenaamde matching section weer. De methode wordt uitgelegd aan de hand van een voorbeeld.

chromosoom 1:
123
246
4567
81013
8910
579
chromosoom 2:

Zet het eerste gen van chromosoom 2 in de matching section naar die van chromosoom 1. De 8 moet op de plaats van de 4 komen. Dan moet de 4 van chromosoom 1 gaan naar de plaats waar de 8 staat.

chromosoom 1:
123
8567
4910

Dit moet op dezelfde manier gebeuren met het eerste gen van chromosoom 1 naar chromosoom 2. De 4 moet op de plaats van de 8 komen. De 8 gaat naar de plaats van de 4.

chromosoom 2:
286
41013
579

Dit mechanisme wordt ook voor de volgende genen uitgevoerd. Het eindresultaat ziet er dan als volgt uit:

chromosoom 1:
627
281
81013
4567
495
1039
chromosoom 2:

Duidelijk is te zien dat de genen in de matching section verwisseld zijn. De genen buiten deze sectie zijn aangepast met informatie van de genen binnen de sectie. Dit is een essentieel feit van een kruisingsmechanisme. Er moet altijd informatie van de oude generatie doorgegeven worden naar de nieuwe generatie.

Er zijn andere kruisingsmethoden bekend. Hier is arbitrair voor deze gekozen.

3.6. Keuze van het mutatiemechanisme.

In het klassiek mechanisme wordt het mutatiemechanisme gecombineerd met het mechanisme voor de keuze van de reproductieparen. Dit gaat door van tevoren een mutatiekans te bepalen. Dan wordt bij de keuze van de chromosoom met behulp van een random getal gekeken of de chromosoom eventueel nog gemuteerd wordt. Is het random getal kleiner dan de mutatiekans, dan wordt er gemuteerd, anders niet.

Dit muteren kan ook achteraf gebeuren. Na de keuze van de nieuwe generatie kan met een random generatie gekeken worden welke chromosoom nog gemuteerd moeten worden.

In dit voorbeeld wordt een principieel andere methode gebruikt. Ook bij deze methode wordt gebruik gemaakt van een mutatiekans. Daarmee wordt het aantal genen uitgerekend dat gemuteerd moet worden. Dit betekent dat er altijd gemuteerd wordt. Bij de klassieke methode is er een kans dat er in een bepaalde generatie geen mutaties optreden.

De mutatie bestaat daarin dat van een random gekozen chromosoom vanaf een random gekozen plaats een random gekozen aantal genen 1 plaats naar rechts opgeschoven wordt. Voor deze methode is gekozen omdat dan een "stukje" route behouden blijft. Tevens speelt de eenvoud van dit mechanisme een belangrijke rol.

3.7. Keuze van het stopmechanisme.

Het algoritme is te stoppen als er een criterium gevonden kan worden waarmee aangegeven wordt dat de oplossing optimaal is. Er zijn een aantal problemen bekend die deze eigenschap hebben. Bij dit probleem is geen algemene optimale oplossing bekend. Daarom is er ook geen stopmechanisme te vinden. Dit wordt dan ook niet gebruikt.

4. Beschrijving van het programma.

Bij de beschrijving van het programma kan men de stappen onderscheiden van hoofdstuk 2. Daaromheen zijn nog enkele instellingen en weergave-instructies nodig. Het volledige programma staat in de bijlage.
Noot van de redactie: de bijlage met BASIC-programmacode is om onbekende redenen niet in deze editie van Kennisgeving afgedrukt.

Het programma begint met het schoonmaken van een aantal array's. De betekenis staat in de kop van het programma. Verder kent het programma drie mogelijkheden om de steden te configureren. De steden kunnen op een cirkel liggen, in een matrix liggen of random bepaald worden. Het maximum aantal steden is gesteld op 50, maar dit kan eenvoudig uitgebreid worden. Er kan ingesteld worden of de de-crossing methode en de smoothing methode wel of niet gebruikt zullen worden. Na de keuze van de stedenconfiguratie wordt de afstandenmatrix berekend.

Dan wordt de begingeneratie opgebouwd. Daarna wordt eventueel getoond hoe de de-crossingmethode werkt op de eerste chromosoom. Dan wordt de beste chromosoom bepaald. Deze wordt op het scherm getoond als zijnde de beste oplossing tot dan. De minimale afstand wordt weergegeven.

Met deze beste oplossing wordt vervolgens de cross-over gedaan. Daarna de mutaties. Dan wordt de nieuwe generatie die in array B staat overgezet in array A van de oude generatie. De cyclus begint dan opnieuw.

Het programma wijst zich verder vanzelf. Afwijkend is de INCR functie. Deze heeft de volgende betekenis:
INCR A, B betekent: A = A + B

5. Verbeteringen van het programma.

In het algoritme zijn een aantal verbeteringen aan te brengen. Daartoe moet eerst een criterium opgesteld worden waaraan men kan zien of het ene algoritme beter is dan het andere.

Als criterium worden de snelheid en de minimale afstand genomen. Een gebruiker is voornamelijk geïnteresseerd in het feit hoe snel de routine werkt.

De moeilijkheid van het tijdscriterium ligt daarin, dat deze moeilijk te meten is. De ene testrun kan veel langer of korter zijn dan de volgende. Dit komt vanwege het random karakter van het algoritme.

Dit is op te lossen door een testomgeving te creëren waarbij een aantal testruns gedraaid worden. Op deze manier wordt een soort gemiddelde verkregen. Deze tijden zeggen dus absoluut niets over de werkelijke draaitijd van 1 run.

Er zijn drie instelbare variabelen. Dit zijn:

De instelling van deze variabelen is nog steeds een onderwerp van onderzoek. Het verlossende woord is daarover nog niet uitgesproken.

Wel is bekend dat als de generatie klein is, dat dan de kans dat er in de generatie een optimale oplossing zit, eveneens klein is. Er zijn dan veel generaties nodig. Dit maakt het zoekproces trager. Als de generatiegrootte groot is, dan kost het veel tijd om de hele generatie door te rekenen. Hier zal ergens een optimum liggen.

Hetzelfde geldt voor de mutatiekans. Als deze groot is, duurt het zoeken lang. Het wordt dan als het ware een zuiver random zoekproces. Als de mutatiekans klein is, dan is de kans groot dat er veel dezelfde chromosomen ontstaan. Dan duurt het zeker langer voordat een optimum gevonden is. Ergens tussen de twee uitersten ligt een optimale instelling van de mutatiekans.

Verder blijkt het optimum van de generatiegrootte en de mutatiekans sterk af te hangen van de lengte van de chromosomen in casu het aantal steden.

5.1. Methode van het elitisme.

Dit is een bekende methode. Er wordt voor gezorgd dat de beste chromosoom altijd meegenomen wordt naar de volgende generatie.

5.2. Methode van het superras met randomgenerator.

Deze methode maakt gebruik van het superras en is voor zover nagegaan nog niet eerder beschreven. De motivatie om deze methode te gbruiken is de volgende. Als het selectiemechanisme voor de reproductie wordt bekeken, dan ziet men dat men er bij de verschillende methoden voor zorgt dat de kans groot wordt om een goede chromosoom te nemen. Elitisme, machtverheffen van de fitnessfunctie, enz.

Waarom dan niet gewoon de twee beste chromosomen genomen en deze in de nieuwe generatie gebruiken voor de reproductie. Uitgaande van de eerste twee chromosomen (steeds de beste, vandaar de naam superras) kan men met een random generator de kruisingpunten bepalen. Door te kruisen ontstaan de volgende chromosomen van de nieuwe generatie. De nieuwe generatie bestaat zo volledig uit kruisingen van de beste twee chromosomen van de oude generatie.

Deze methode werkt uitstekend. Een voordeel is dat het programma zeer simpel wordt. Er hoeft geen survivalbalk uitgerekend te worden. Er hoeft geen moeilijke fitnessfunctie met schaalfactor bepaald te worden. Er kan direct naar een minimum van de fitnessfunctie gezocht worden. De tijdwinst is spectaculair.

5.3. Methode van het superras zonder randomgenerator.

Uitgaande van de vorige methode is het mogelijk om nog een randomgenerator weg te laten. Het gaat dan om die welke gebruikt wordt om bij de reproductie van de chtomosomen de kruisingpunten te bepalen.

Bij deze methode wordt deze weggelaten. Er wordt geen selectiemechanisme meer toegepast. De nieuwe chromosomen ontstaan door de twee beste beginchromosomen op alle mogelijke manieren te kruisen. Zijn er dan nog niet genoeg chromosomen, dan worden de beste en de op twee na beste chromosomen gekruist op alle mogelijke manieren. Dit gaat zolang door totdat de hele nieuwe generatie gevuld is.

Ook deze methode werkt goed. In snelheid ontlopen de twee methodes van het superras elkaar niet veel.

5.4. Keuze van een geschikte begingeneratie.

De klassieke methode gaat er vanuit dat er een willekeurige begingeneratie gekozen wordt. Deze keuze is echter arbitrair. Het blijkt dat bij een geschikte keuze de snelheid van het algoritme wederom spectaculair toeneemt.

De eerste methode welke gebruikt wordt, is die waarbij men er voor zorgt dat er geen dezelfde chromosomen in de begingeneratie voorkomen. De snelheidswinst is alleen van belang als het zoekproces kort duurt. Bij zeer lange zoekprocessen is de winst minimaal.

De tweede methode gaat er vanuit dat men probeert een zo optimaal mogelijke oplossing te gebruiken. Daartoe begint men bij de eerste stad. Vanuit deze stad zoekt men de dichtstbijgelegen stad. Vervolgens weer de dichtstbijgelegen stad, enzovoort. Alleen het gaan van de laatste stad naar de beginstad zal geen optimale oplossing zijn. Toch blijkt op deze manier een grote snelheidswinst te behalen, vooral als men niet teveel steden neemt.

5.5. Gebruik van een de-crossing mechanisme.

Dit mechanisme maakt gebruik van een eenvoudige meetkundige eigenschap. Deze eigenschap luidt dat de som van twee zijden van een vierhoek altijd kleiner is dan de som van de twee diagonalen. Dat betekent dat als twee wegen elkaar kruisen er altijd een kortere weg aan te geven is. Dit principe wordt het de-crossingmechanisme genoemd. Het heeft dus niets te maken met een genetisch algoritme. Het wordt ingebouwd nadat de nieuwe generatie is gemaakt. In de volgende figuur wordt een en ander duidelijk gemaakt.


De weg van A naar B plus de weg van C naar D is altijd langer dan de weg van A naar D plus de weg van B naar C.

Wordt het mechanisme gebruikt bij de test van de stedenring, dan wordt meteen de optimale oplossing gevonden. Daarom blijven alleen de stedenmatrix en de random stedenwolk over voor het testen van dit mechanisme.

De winst in het aantal te doorlopen generaties is spectaculair. De tijdwinst niet zo. Dit is gelegen in het feit dat het mechanisme zeer tijdrovend is. Elk kruispunt van wegen moet opgezocht worden. De vraag is of dit mechanisme zelf niet NP is. In dat geval zal er geen tijdwinst optreden. De praktijk geeft aan dat er wel degelijk een grote tijdwinst te behalen is.

5.6. Methode van smoothing.

Bij deze methode wordt een smoothing toegepast. Dit betekent dat een bepaald stuk route glad getrokken wordt. Stel daarbij de volgende route:

De normale route loopt van A naar B, naar C, naar D. De routine zorgt ervoor dat de route in ieder geval loopt van A naar C, naaar B, naar D. Het effect van deze routine is wel aanwezig, maar of de winst in tijd opweegt tegen de extra benodigde rekentijd is niet uitgebreid nagegaan.

6. Conclusies.

Er kunnen voor de oplossing van het TSP met behulp van een genetisch algoritme de volgende conclusies getrokken worden.

  1. Optimale instelling.
    Om een optimale instelling van het algoritme te vinden, is het nodig om niet alleen een optimale generatiegrootte te bepalen. Het blijkt dat ook de mutatiekans van belang is.
  2. Mutatiekans.
    De gebruikte methode, waarbij een vast aantal genen per generatie gemuteerd wordt, blijkt goede resultaten op te leveren. Het programma wordt veel overzichtelijker. De praktijkwaarde voor de mutatiekans blijkt wat hoger te liggen dan die van het klassieke algoritme (10% kans tegen ca. 6%).
  3. Selectiemechanisme.
    Het selectiemechanisme met behulp van de fitnessbalk blijkt voor dit probleem niet de meest snelle oplossing te geven. Dit komt omdat dit mechanisme traag is omdat er relatief veel gerekend moet worden.
  4. Methode van het superras.
    Deze methode blijkt een zeer snel algoritme op te leveren. De verdere voordelen zijn dat het programma zeer eenvoudig wordt.
  5. De-crossing mechanisme.
    Het gebruik van het de-crossing mechanisme levert een vermindering op van het aantal generaties om een bepaalde minimale afstand te halen. Het kost echter meer tijd omdat er nogal wat gerekend moet worden. De indruk bestaat dat het meer generaties kost om tot de optimale oplossing te komen. Dit is nog niet hard gemaakt. In zijn totaliteit wordt echter wel een winst geboekt. Nadere testen zullen dit moeten aantonen.

7. Literatuurlijst.

  1. Davis, L. (1991).
    Handbook of genetic algorithms.
    Van Nostrand Reinhold.
  2. Goldberg, O.E. (1989).
    Genetic algorithms in search, oprimization, and machine learning.
    Addison-Wesley.
  3. Michalewicz, Z. (1992).
    Genetic Algorithms + Data structures = Evolution programs.
    Springer-Verlag.