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 wordt uitgegaan van een reeds eerder geplaatst artikel. Het grootste verschil zit in de codering van de chromosomen. Voor de duidelijkheid van het programma worden twee opties welke reeds in het eerdere artikel genoemd zijn, hiet weggelaten. Aan het eind worden een aantal 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. Er zijn reeds pogingen gedaan om een kortste route te bepalen door meer dan 13000 steden van Amerika.

Een meer praktische toepassing van het probleem treedt op bij de fabricage van printplaten. Daar moeten gaten gevoord 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 (= beter aangepaste) 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 (= beter aangepast) worden.

Er treedt daarbij nog het verschijnsel op van de mutaties. Dit is een willekeurige verandering van het 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 (= het best aangepast) 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. Bij kruising van verschillende chromosomen, kan het probleem ontstaan dat er wel twee dezelfde getallen voorkomen. Om dit probleem te omzeilen heeft Bean in (4) een methode beschreven die de Random Key Representation (RKP) genoemd wordt. Daarbij wordt iedere oplossing door een rij random getallen tussen de 0 en de 1 weergegeven. Dit is zo een indirecte methode.

Een mogelijk voorbeeld is de volgende rij getallen (bij 10 steden):

0.230.820.450.740.870.110.560.690.780.92

De bijbehorende volgorde van 10 steden is:

28369145710

Het laagste getal geeft daarbij de eerste stad weer. Een verdergaande vereenvoudiging is dat de random getallen liggen tussen de 0 en de 100. In dat geval kan met integers gewerkt worden.

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. Ieder 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.

Omdat in dit artikel de methode van de RKP gebruikt wordt, treedt het verschijnsel niet op. Immers er worden nu twee rijen random getallen gekruist. Een en ander wordt duidelijk aan het volgende voorbeeld.

chromosoom 1:
0.230.820.450.740.870.11
0.320.280.540.470.780.12
0.560.690.780.92
0.650.960.870.29
chromosoom 2:
Bijbehorende steden:
chromosoom 1:
283691 45710
426581 71093
chromosoom 2:
Kruising op gen 6:
chromosoom 1:
0.230.820.450.740.870.11
0.320.280.540.470.780.12
0.650.960.870.29
0.560.690.780.92
chromosoom 2:
Bijbehorende steden:
chromosoom 1:
274681 51093
325481 67910
chromosoom 2:

Duidelijk is te zien dat er geen dubbele steden voorkomen.

3.6. Keuze van het mutatiemechanisme.

In het klassieke 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 het chromosoom met behulp van een random getal gekeken of het 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 chromosomen 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 andere waarde krijgt. Het zal duidelijk zijn dat dit mechanisme zeer eenvoudig is.

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.

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 het eerste chromosoom. Dan wordt het 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 het 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 verder beschreven. De motivatie om deze methode te gebruiken 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 goed 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 chromosomen 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.

Deze methode werd in het vorige artikel besproken. Deze wordt vanwege de eenvoud van het programma hier weggelaten.

5.6. Methode van smoothing.

Deze methode werd eveneens in het vorige artikel besproken. Deze wordt hier weer weggelaten.

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 methode van het RKP levert een zeer eenvoudig programma op.

7. Literatuurlijst.

  1. Davis, L. (1991).
    Handbook of genetic algorithms.
    Van Nostrand Reinhold.
  2. Goldberg, D.E. (1989).
    Genetic algorithms in search, oprimization, and machine learning.
    Addison-Wesley.
  3. Michalewicz, Z. (1992).
    Genetic Algorithms + Data structures = Evolution programs.
    Springer-Verlag.
  4. Gen, M. en Cheng, R. (1994).
    Genetic algorithms and engineering design.
    John Wiley & Sons.

Bijlage: Totale listing van het programma.

Het programma is in TURBO Basic geschreven. Er is voor gezorgd dat de gebruikte instructies ook in andere dialecten voorkomen. Voor vragen hieromtrent kunt U bij de auteur terecht.

'Programma: TSP4
'Travelling salesman programma
'Er zijn maximaal 50 steden
'Cross-methode: Random, Gen en Cheng, blz.119
'Selektie methode: superras

DefInt A-D, G, I-K, M
Dim X(50)       'x coordinaat van de steden
Dim Y(50)       'y coordinaat van de steden
Dim A%(50,50)   'Oude generatie van maximaal 50 chromosomen en 50 genen
Dim AA%(50,50)  'Hulp array oude generatie
Dim B%(50,50)   'Nieuwe generatie
Dim C%(50,50)   'Hulp matrix voor display
Dim D%(50,50)   'Afstanden matrix
Dim DIS%(50)    'Totale afstand array

'Parameters instellen
10 CLS
INPUT "Aantal steden";GEN    'Aantal genen

INPUT "Generatie grootte";GENER  'Aantal chromosomen
INPUT "Mutatie percentage";M
INPUT "Steden: Cirkel, Random, Vierkant ";Z$

MPM=Fix(GEN * GENER * M / 100)

'Steden opzetten. Er mogen geen gelijke steden voorkomen.
If Z$="R" Then
  For I=1 To GEN: X(I)=Fix(100*Rnd): Y(I)=Fix(100*Rnd): Next
  For I=1 To GEN-1: For K=I+1 To GEN
    If X(I)=X(K) And Y(I)=Y(K) Then I=0: Y(K)=Y(K)+1
  Next K,I
ElseIf Z$="C" Then
  PI=4*Atn(1)
  For I=1 To GEN
    X(I)=Fix(50+45*Cos(2*I*PI/GEN)): Y(I)=Fix(50+45*Sin(2*I*PI/GEN))
  Next I
ElseIf Z$="V" Then
  For I=0 To 6: For J=1 To 7
    A(10)=I*7+J: X(A10)=14*J: Y(A10)=14*I: If A10=GEN Then J=7: I=6
  Next J,I
Else
  GoTo 10
End If

'Berekening van de afstanden matrix
Erase D
For J=1 To GEN: For I=1 To GEN
  D(J,I)=Sqrt((X(I)-X(J))*(X(I)-X(J))+(Y(I)-Y(J))*(Y(I)-Y(J)))
Next I,J

'Initiele generatie opbouwen.
'De chromosomen zijn random opgebouwd
For J=1 To GENER: For I=1 To GEN: A(J,I)=100*Rnd: C(J,I)=A(J,I):
Next I,J
For J=1 To GENER: For II=1 To GEN
  MINA=200: MINB=0
  For I=1 To GEN
    If C(J,I)<MINA Then MINA=C(J,I): MINB=I
  Next I
  AA(J,II)=MINB: C(J,MINB)=200
Next II,J
II&=1: FIT=10000

CLS: SCREEN 9: WINDOW (-1,-2)-(175,120)

'Fitness berekening: A10 is beste, A11 is de op een na beste.
100 FITMAX=10000: FITMAX1=10000: A10=1: A11=1
For J=1 To GENER
  DIS(J)=D(AA(J,1),AA(J,GEN))
  For I=2 To GEN: DIS(J)=DIS(J)+D(AA(J,I),AA(J,I-1)): Next
  If DIS(J)<FITMAX Then FITMAX=DIS(J): A10=J
Next J: DIS=DIS(A10)
For J=1 To GENER: If DIS(J)=DIS Then DIS(J)=0
  If DIS(J)<FITMAX1 And DIS(J)>0 Then FITMAX1=DIS(J): A11=J
Next J

'De beste chromosoom wordt als eerste gebruikt voor de nieuwe generatie
For J=1 To GENER Step 2: For I=1 To GEN: B(J,I)=A(A10,I): Next I,J
'De volgende beste wordt gebruikt voor de rest van de generatie
For J=2 To GENER Step 2: For I=1 To GEN: B(J,I)=A(A11,I): Next I,J

If FITMAX<FIT Then
  FIT=FITMAX: J=A10: GoSub DISPLAY
  LOCATE 1,1: Print "TRAVELLING SALESMAN PROBLEEM"
  Print "Aantal steden:  ";GEN;Tab(38);"Aantal generaties:  ";II&
  Print "Generatie grootte: "; GENER; Tab(38); "Minimale afstand:      "; Fix(FITMAX)
  Print "Mutatie percentage:"; M; Tab(38); "Bijbehorende generatie:"; II&;
End If
LOCATE 2,61: Print II&

'Cross-over
For J=3 To GENER Step 2
  P=1+Int(GEN*Rnd): For I=P To GEN: SWAP B(J+!,I),B(J,I): Next I
Next J

'Mutatie. Er krijgen random een aantal genen tot aan MPM een nieuwe waarde
TEL=0
While TEL<MPM
  I=1+Int(GEN*Rnd): J=1+Int(GENER*Rnd): B(J,I)=100*Rnd: INCR TEL
Wend

'Oude generatie wordt nieuwe generatie
For J=1 To GENER: For I=1 To GEN: A(J,I)=B(J,I): C(J,I)=B(J,I): Next I,J
For J=1 To GENER: For II=1 To GEN
  MINA=200: MINB=0
  For I=1 To GEN
    If C(J,I)<MINA Then MINA=C(I,J): MINB=I
  Next I
  AA(J,II)=MINB: C(J,MINB)=200
Next II,J

'Herhaal procedure
INCR II&: Y$=INKEY$: If Y$="" Then GoTo 100
If Y$="D" Then M=M-1: MPM=Fix(GEN*GENER*M/200): LOCATE 4,20: Print M;: GoTo100
If Y$="I" Then M=M+1: MPM=Fix(GEN*GENER*M/200): LOCATE 4,20: Print M;: GoTo100
BEEP: LOCATE 1,35: INPUT R: GOTO 10

DISPLAY:
  CLS: Circle(X(AA(J,1)),Y(AA(J,1))),0.4
  For I1=1 To GEN: Circle(X(AA(J,I1)),Y(AA(J,I1))),0.8: Next
  For I1=1 To GEN-1
    Line(X(AA(J,I1)),Y(AA(J,I1)))-(X(AA(J,I1+1)),Y(AA(J,I1+1)))
  Next I1
  Line (X(AA(J,GEN)),Y(AA(J,GEN))) - (X(AA(J,1)),Y(AA(J,1)))
Return

Waarschuwing: Een simpele copy en paste van deze code naar een (Turbo-)BASIC-editor zal niet werken. Omdat de karakters "<" en > een speciale betekenis hebben in HTML (de taal die de structuur en opmaak van websites beschrijft), zijn ze vervangen door HTML-karaktercodes.