Evolutietheorie en theoretische probleemoplossing
Voor mensen die geen zin hebben door te scrollen naar het einde van dit stukje, mijn programma is hier te vinden.Dit klinkt helemaal niet gerelateerd, maar het is het wel. Recentelijk ben ik gestuit op een techniek die "genetisch algoritme" heet. Het gegeven fascineerde me.
Me helemaal inlezen in zoiets is helaas mijn stijl niet, dus heb ik maar geprobeerd er een praktisch voorbeeld van te maken. Hiervoor heb ik geprobeerd om het klassieke probleem van de handelsreiziger op te lossen.
Het probleem
Stel je bent een handelsreiziger, die naar een aantal steden in een land moet. Dit doet hij met het vliegtuig. Echter, er zijn vele verschillende volgorden die hij hierbij kan nemen. Hij wil hierbij natuurlijk een zo kort mogelijke route nemen. Hoe moet hij vliegen?
Dit probleem kan niet direct, volgens een formule etc., worden opgelost. Een aanpak zou zijn om het dan maar te brute forcen, om dan gewoon iedere mogelijkheid te proberen en te kijken welke de kortste is, maar dat levert ook problemen op. Immers, voor een n aantal punten, zijn er (n-1)!, dus n-1 faculteit, oplossingen. Dit valt nog wel mee voor 6 punten (120 oplossingen), maar met 20 punten levert dat 19! = 121.645.100.408.832.000 of grofweg 2^58 mogelijkheden. Dat zijn veel te veel oplossingen om te proberen. Iets anders dus maar.
De oplossing
Hierbij komt die titel dus kijken. Hoe heeft de natuur het probleem "Het organisme moet overleven" opgelost? Door te kijken wie het beste overleefde, en met die selecte groep verder te gaan om dat generatie na generatie te herhalen. De nieuwe groepen muteerden lichtjes en er werden genen uitgewisseld. En zo verder.
Dat was het voor het lesje biologie. De kern hieruit is dat je begint met wat probeersels, de best gelukten eruit pakt, daar een nieuwe groep probeersels van maakt die allemaal een beetje verschillend zijn, en van de nieuwe probeersels weer kijkt wie de besten zijn. Hiermee is het mogelijk om met het voorbeeld van de 20 punten de snelste weg al met 20.000 pogingen te vinden. Een besparing van 99,99999999999984661275 (dus bijna 100) procent! Toegegeven, het algoritme zelf levert iets meer overhead dus het bespaar iets minder, maar nog steeds veel. De naam van het beestje? Genetisch Algoritme.
Hoe het werkt
Stel je de volgorde van de punten voor. Dat is een chromosoom. Hiervan begin je met een aantal willekeurig gegenereerde exemplaren. In iedere generatie neem je de beste, de beste 20% in mijn applicatie. Daarmee ga je een nieuwe generatie proberen te maken.
Dit doe je door eerst natuurlijk twee ouders uit je huidige generatie te kiezen. Deze kruis je. In het echt kan je 1 chromosoom alleen in bijzondere omstandigheden kruisen, maar dat doet er niet toe. Het proces is exact hetzelfde als hoe het in de natuur gebeurt, je neemt een stukje van ouder 1 en je vult dat aan met ouder 2. Hier moet je, afhankelijk van de data waar je het over hebt, een of andere methode gebruiken om dat te doen. Op deze website staan een aantal voorbeelden. Kind kan de was doen.
Daarnaast vind er over de eeuwen heen mutaties plaats in het DNA. Deze hebben we ook nodig, om onze kansen de goede oplossing te vinden te vergroten. Hiervoor verwisselen we per generatie een paar punten van plek in de volgorde. Heel toevallig ook volgens hetzelfde algoritme waarmee je normaal gesproken kaarten zou schudden. Het resultaat is hetzelfde.
De applicatie
Geheel geschreven met gebruikmaking van de standaarden voor HTML5 Canvas en JavaScript heb ik hiervan hier een werkend voorbeeldje gemaakt. Deze poogt de kortste route te vinden door een set punten. Ik heb aardige resultaten gekregen tot wel 100 punten, hoewel ze niet altijd even goed zijn. De demo is succesvol getest in Google Chrome 8 en Apple Safari 5. Mozilla Firefox 3.6 werkt half, maar er zit een bug in de implementatie van Canvas die volledig functioneren tegengaat. Internet Explorer 8 werkt niet. Dit alles onder Windows Vista. Andere browsers en besturingssystemen zouden kunnen werken maar dit is niet getest.
Dan nog een afsluitend verhaaltje. Het algoritme levert namelijk niet de beste route. Het levert een goede route, die naar alle waarschijnlijkheid niet heel veel verschilt van de daadwerkelijke. Het is echter, net als evolutie, een toevalsspel. Dezelfde puntenwolk kan namelijk best een paar oplossingen hebben die helemaal niet op elkaar lijken. Mensen lijken immers ook niet op haaien.