Genetische algoritmen uitgelegd
De evolutie heeft ogen, vleugels en hersenen voortgebracht zonder ontwerper, simpelweg door te behouden wat werkt en het te variëren. Een genetisch algoritme leent dat idee om problemen op een computer op te lossen. Het hoeft het probleem niet te begrijpen, alleen een beter antwoord van een slechter te onderscheiden, en dat maakt het een krachtig hulpmiddel wanneer de ruimte van mogelijke antwoorden te groot en te vreemd is om op een andere manier te doorzoeken.
Het idee
In de jaren zestig en zeventig maakte John Holland aan de Universiteit van Michigan van Darwins theorie een algoritme, beschreven in zijn boek Adaptation in Natural and Artificial Systems uit 1975. Rond dezelfde tijd ontwikkelden Ingo Rechenberg en Hans-Paul Schwefel in Duitsland evolutiestrategieën voor technisch ontwerp. Het gemeenschappelijke recept: houd een populatie kandidaat-oplossingen bij, geef ze een score, laat de betere zich met variatie voortplanten en herhaal dat vele generaties lang.
Genen en de populatie
Elke kandidaat wordt beschreven door een chromosoom, een lijst genen. In de speeltuin zijn de genen van een raket zijn duwtjes, één voor elk moment van zijn vlucht; bij andere problemen kunnen het de bits van een getal zijn, de volgorde van steden op een route of de afmetingen van onderdelen in een ontwerp. De eerste generatie is willekeurig, wat betekent dat ze de ruimte van antwoorden breed verkent maar bijna geen goede antwoorden bevat.
De fitnessfunctie
Fitness is het ene getal dat zegt hoe goed een kandidaat is, en het is het enige wat het algoritme over het probleem weet. Bij de raketten beloont ze vooral een vroege aankomst, daarna eindigen dicht bij het doel, en ze bestraft neerstorten. Een goed gekozen fitnessfunctie leidt de zoektocht soepel naar goede antwoorden; een slordige beloont het verkeerde, en het algoritme zal elke maas in de wet die ze openlaat uitbuiten.
Selectie
Ouders worden zo gekozen dat fittere kandidaten meer kinderen krijgen, maar zwakkere krijgen nog steeds een kans, omdat hun genen bruikbare stukjes kunnen bevatten. Roulettewielselectie geeft elke kandidaat een stuk van een rad in verhouding tot zijn fitness; toernooiselectie kiest er willekeurig een paar en neemt de beste daarvan. Sterkere selectie versnelt de vooruitgang, maar maakt de populatie ook eenvormiger, waardoor de zoektocht te vroeg kan eindigen.
Crossover en mutatie
Crossover combineert twee ouders: hier neemt een kind het eerste deel van zijn genen van de ene ouder en de rest van de andere, zodat de vroege manoeuvres van de ene raket de late van een andere kunnen ontmoeten. Mutatie vervangt willekeurig een paar genen. Crossover combineert opnieuw wat de populatie al heeft; mutatie brengt binnen wat ze nooit heeft gehad. Hollands schematheorema beschrijft hoe korte bouwstenen van goede genen zich onder deze mix van selectie en recombinatie door de populatie verspreiden.
Elitisme, exploratie en exploitatie
Het ongewijzigd kopiëren van de beste paar kandidaten naar de volgende generatie, elitisme, garandeert dat het beste antwoord nooit verloren gaat. Elk genetisch algoritme moet een evenwicht vinden tussen exploratie, het uitproberen van nieuwe gebieden van de zoekruimte, en exploitatie, het verfijnen van wat al goed is. Te weinig variatie en de populatie convergeert naar één middelmatig antwoord; te veel en ze komt nooit tot rust. Populatiegrootte, mutatiegraad en selectiedruk zijn de knoppen waarmee dat evenwicht wordt ingesteld.
Lokale optima
Een genetisch algoritme volgt alleen de fitness, dus het kan om de tuin worden geleid. Wanneer de weg naar het beste antwoord eerst langs slechtere loopt, beklimt de populatie de dichtstbijzijnde heuvel en blijft daar: een lokaal optimum. Achter de verspringende muren in de speeltuin scoren raketten die onder het doel neerstorten beter dan raketten die afbuigen om de opening te zoeken, dus hoopt de populatie zich op tegen de muur. Remedies zijn grotere populaties, meer mutatie, de populatie divers houden en vooral een betere fitnessfunctie.
Probeer het zelf
Open de speeltuin voor genetische algoritmen om raketten te laten evolueren rond één muur, een opening, pilaren, verspringende muren of muren die je zelf tekent. Verander de populatie, de mutatiegraad, de levensduur en de selectiemethode, zet elitisme aan en uit, en volg in de grafiek hoe snel het aandeel raketten dat het doel bereikt groeit, of waarom het dat niet doet.
Veelgestelde vragen
Is een genetisch algoritme een vorm van kunstmatige intelligentie?
Het behoort tot het bredere vakgebied van AI en machine learning, als zoek- en optimalisatiemethode. Het leert niet van voorbeelden zoals een neuraal netwerk; het verbetert kandidaat-oplossingen door proberen en selecteren. De twee worden vaak gecombineerd, bijvoorbeeld door de structuur of de gewichten van neurale netwerken te laten evolueren, een aanpak die neuro-evolutie heet.
Vindt een genetisch algoritme altijd het beste antwoord?
Nee. Het is een heuristiek: het vindt meestal goede antwoorden op moeilijke problemen, maar het geeft geen garantie op het beste antwoord en geen bewijs van hoe dicht het erbij zit. Voor problemen waarvoor een exacte methode snel genoeg is, is die methode beter.
Wat is het verschil tussen een genetisch algoritme en evolutiestrategieën?
Beide zijn evolutionaire algoritmen. Klassieke genetische algoritmen leggen de nadruk op crossover van chromosomen die op tekenreeksen lijken; evolutiestrategieën werken vooral met mutatie op reële getallen en passen hun eigen mutatiegrootte vaak onderweg aan. Moderne methoden combineren ideeën uit beide.
Waarom zijn de raketten in het begin zo onhandig?
Hun eerste genen zijn volledig willekeurige duwtjes, die elkaar gemiddeld opheffen, dus de raketten drijven maar wat rond. Pas wanneer selectie de zeldzame raketten heeft behouden die toevallig ongeveer de goede kant op duwden, en crossover hun goede stukken heeft gecombineerd, verschijnen er gecoördineerde vluchten.
Klaar om het te proberen?
Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.
Open de speeltuin voor genetische algoritmen