Genetische algoritmen

Het was een beetje stil op deze blog. Ondertussen ben ik aan de gang gegaan met Coffeescript, een taal die het mogelijk maakt je programma’s voor webpagina’s heel compact en toch leesbaar op te schrijven. Als je geïnteresseerd bent kun je de broncode van het programma hieronder bekijken. In dat geval weet je vast ook hoe.

Ik heb coffeescript gebruikt om inzichtelijk te maken hoe genetische algoritmen werken. Dit zijn algoritmen die gebruikt worden om oplossingen te vinden voor problemen waarbij het aantal mogelijke oplossingen zeer groot is. Denk bijvoorbeeld aan het maken van een rooster voor een school. Als je -zeg- twintig klassen hebt, die elk les moeten krijgen in twaalf vakken verdeeld over achttien lokalen, in veertig mogelijke lesuren per week is het aantal mogelijkheden enorm groot. Wel kun je eenvoudig uitrekenen of een bepaalde oplossing aan alle voorwaarden voldoet, zoals geen lokaal of docent dubbel geboekt. Ook is het mogelijk iets te zeggen over de kwaliteit van een oplossing. Je kunt zo de voorkeur geven aan zo min mogelijk tussenuren voor klassen en docenten. Door het enorme aantal mogelijkheden is het vinden van de beste oplossing vrijwel onmogelijk, daarvoor zou je alle mogelijkheden moeten doorrekenen. Met genetische algoritmen kun je goede oplossingen vinden, hoewel die dus niet noodzakelijk de beste zijn.

Het werkt als volgt:

  1. Genereer een aantal willekeurige oplossingen
  2. Gebruik die oplossingen om nieuwe oplossingen te maken. Dat kan op twee manieren: combineer twee oplossingen tot één nieuwe (seksuele reproductie) of kopieer een oplossing en breng er een kleine wijziging in aan (aseksuele reproductie met mutatie)
  3. Bereken voor elke oplossing de kwaliteit.
  4. Houd de beste oplossingen (b.v. de beste 25%) en ga terug naar stap 2

Stappen 2-4 worden herhaald totdat je tevreden bent over de beste oplossing uit je verzameling oplossingen.

Screenshot 2013-10-22 14.42.42

Ik heb dit algoritme toegepast op het handelsreizigersprobleem. (Daar ben ik overigens niet origineel in). Dit probleem vraagt naar de kortste route voor een handelsreiziger die N steden precies één keer moet bezoeken en terugkeren naar zijn beginpunt. Het aantal mogelijke routes is N!, een aantal dat zeer snel oploopt met N, waardoor het onmogelijk wordt alle routes door te rekenen.

Hieronder kun je zien hoe een genetisch algoritme probeert een goede route te vinden. Klik in het witte vlak om steden te plaatsen. Als je minimaal twee steden hebt geplaatst kun je op start drukken om een route te vinden. Na elke generatie pauzeert het algoritme even en laat de tot dan toe beste oplossing zien. Als een generatie geen verbetering geeft stopt het. Als je nog niet tevreden bent, kun je met “Verder” het algoritme nog een schop geven om het nog wat langer te proberen. Soms helpt meerdere keren schoppen.

Voortplanting gebeurt op twee manieren: seksuele voortplanting gebeurt door het eerste deel van een oplossing te knippen, uit een andere de in dit deel al bezocht steden te verwijderen en de rest aan de nieuwe oplossing te plakken. Bij aseksuele voortplanting met mutatie wordt in de kopie één stad van plaats veranderd of worden twee steden verwisseld.

Mijn implementatie is niet ideaal, en stopt vaak te snel. Dat komt doordat ik relatief weinig “kinderen” laat genereren en doordat mijn mutaties misschien te conservatief zijn. Dat merk je vooral in situaties met veel steden. In onderstaand plaatje kreeg ik het algoritme niet meer verder ondanks het feit dat er op het oog zeker verbeteringen mogelijk zijn. Deze relatief zwakke implementatie laat denk ik juist goed de principes en beperkingen van genetische algoritmes zien.

Screenshot 2013-10-22 12.43.56

Ik hoop binnenkort een versie hier te plaatsen waarmee je met de parameters (aantal generaties, wijze van voortplanting) van het algoritme kunt stoeien en de effecten op het resultaat kunt zien.

 

Een gedachte over “Genetische algoritmen

Geef een reactie