12    Evolutie / Revolutie

Materialisme en de seksuele teeltkeuze
Menno Wiegman

Gezocht: Kosmisch ontwerper
Iris Groen en Sjoert van Velzen
- 1 reactie

Genetische modificatie van planten: een duurzame revolutie?
Jeroen Melief
- 1 reactie

Een bron van inspiratie
Annemie Ploeger
- 1 reactie

De evolutie van taal
Jelle Zuidema
- 3 reacties

Meer van hetzelfde?
Mineke Schipper

De immer veranderende vampier
Sabrina Verbeek
- 5 reacties

Sinds the Sixties
Jetske van Heemstra
- 1 reactie

Che! Een commerciële revolutie
Maud Dahmen
- 2 reacties

Emergentie, evolutie en revolutie in Artificial life
Ella Keijzer

Genetische algoritmen en het handelsreizigersprobleem
Mark Kooijman
- 3 reacties

colofon  issn 1879-8144  2 juni 2007

Alle edities   Vakgebieden            
English   Over Blind       Vacatures
Volg ons:               
© 2004–2019 Blind    disclaimer   cookies

 

BLIND
12
 online interdisciplinair tijdschrift  
BLIND 12
alle edities      



zoeken + vakgebieden       



random editie       



vorige editie       



volgende editie       
naar boven       

Een negentiende-eeuwse Ierse wiskundige, sir William Rowan Hamilton, bedacht het volgende probleem: 'Gegeven een aantal steden (N), met bekende afstanden daartussen, wat is de kortste route waarlangs al deze steden worden bezocht met het terugkeren naar de beginstad?' Het probleem oogt op het eerste gezicht niet onoplosbaar, maar naarmate het aantal steden groeit, wordt de tijd dat het kost om de oplossing te vinden exponentieel langer. Een efficiëntere manier om een antwoord te berekenen is volgens het genetische algoritme. Deze methode heeft zijn oorsprong in de evolutie en geeft geen exacte oplossingen voor problemen maar benadert deze in grote mate. Hoe dit in de natuur werkt en kan worden toegepast op het handelsreizigersprobleem wordt nauwgezet uitgelegd in het volgende artikel van Mark Kooijman.

Mark Kooijman studeert momenteel af in scheikunde aan de Universiteit Utrecht.


Lees het artikel

BLIND 12 - Evolutie / Revolutie
sluiten

Hoofdredactie

Inge van der Bijl


Eindredactie

Inge van der Bijl


Redactie

Maud Dahmen
Iris Groen
Elisa Hermanides
Arno Verweij (webmaster)


Redactieraad

prof. dr. Johan van Benthem
drs. Kim van den Berg
dr. Casper de Groot
prof. dr. Michel Haring
prof. dr. Ed van den Heuvel
drs. Machiel Keestra
dr. Bernard Kruithof


klik hier voor huidige redactie


sluiten

Genetische algoritmen en het handelsreizigersprobleem

              
alle bijdragen van deze auteur
korte inleiding & meer over de auteur
all articles by this author
short intro & about the author
artikel door Mark Kooijman

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.

Noten

1. Holland, J.H., Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence, University of Michigan Press, 1975.
2. Smith, Jeff, Evolving a Better Solution, 13 maart 2007, http://www.dnjonline.com/articles/technology/GeneticAlgorithms_1.asp.
3. Java GAlib, genetic algorithm library, 23 mei 2007, https://sourceforge.net/projects/java-galib/.
4. Coley, David A., An Introduction to Genetic Algorithms for Scientists and Engineers, World Scientific, Covent Garden, 1999.

Lees nóg een artikel over

biologie

kunstmatige intelligentie


of lees verder in

of deel

                   

Reactie van Ot

Geplaatst op 10 juli 2007 om 17:24:16

Mark,Wat zeggen de bronnen over de toepasbaarheid van genetische algoritmen?Me dunkt dat er een meetbare waarde moet zijn die afhankelijk is van een aantal controleerbare en betrouwbaar kwantificeerbare variabelen. De variabelen moeten op automatiseerbare manier, al dan niet in een wiskundig model van de werkelijkheid, kunnen resulteren in de meetwaarde.Zijn er, naar jouw weten, nog meer beperkingen?


Reactie van Mark

Geplaatst op 12 juli 2007 om 09:43:04

Ot,Allereerst zal ik even verduidelijken dat het genetische algoritme slechts een rekenmethode is en niet een simulatiemethode, ondanks dat we wel spreken in de biologische termen. We hebben hier een fictief biologisch systeem om ons wiskundige optimalisatieprobleem heengebouwd om deze op te lossen. Uit de dynamica kunnen we dus geen informatie ontlenen.Dit neemt niet weg dat we wel degelijk aan fysische systemen zouden kunnen rekenen met deze methode. Hopelijk is wat wij berekenen experimenteel verifieerbaar, maar de methode zelf heeft geen fysische betekenis.De enige beperkingen aan deze methode is dat de fitheidsfunctie overal in de oplossingsruimte berekenbaar is (dus eindig) en dat de oplossingsruimte een eindige grootte en resolutie heeft (d.w.z. dat de oplossingsruimte opgedeeld is in een eindig aantal partities), maar deze beperkingen gelden voor elk computationeel rekenprobleem. Er moet wel nog bij gezegd worden dat ondanks het feit dat de fitheidsfunctie niet continu hoeft te zijn moeten oplossingen in de buurt van een optimum wel naar dit maximum toe neigen. De oplossing kan pas naar dit optimum toe evolueren als oplossingen 'in de buurt ervan' fitter bevonden worden dan oplossingen 'verder weg'.


Reactie van AT

Geplaatst op 1 februari 2011 om 11:52:46

Ik Snap Het Niet!!!


Reageren




De redactie behoudt zich het recht voor om reacties in te korten of te verwijderen indien daar reden toe is.


           


Lees nóg een artikel over

biologie

kunstmatige intelligentie



Alle edities   Vakgebieden  
             
Wilt u op de hoogte gehouden worden van nieuwe edities en activiteiten van Blind? Meldt u aan voor onze digitale nieuwsbrief:



Het e-mailadres wordt alleen gebruikt voor toezending van de e-mail met de links naar de nieuwe editie. Het adres staat opgeslagen bij MailChimp. MailChimp hanteert een eigen privacybeleid waarmee u instemt als u zich abonneert op onze nieuwsbrief. Elke nieuwsbrief toont een link waarmee toezending kan worden gestopt. Om uw adres eventueel nog te laten verwijderen uit het opzeggingenbestand stuurt u een e-mail aan redactie@ziedaar.nl.