- Vliegt
- Doel bereikt
- Neergestort
- Beste vlucht van de laatste generatie
- Doel bereikt
- Neergestort
Speeltuin voor genetische algoritmen
Een genetisch algoritme lost een probleem op zoals evolutie levende wezens vormt: probeer veel willekeurige antwoorden, houd de betere, meng ze, verander willekeurig een paar stukjes en herhaal. Hier zijn de antwoorden raketten. Elke raket volgt een lijst willekeurige duwtjes en verder niets, en in het begin tuimelen ze doelloos rond. Druk op Starten en kijk hoe de populatie generatie na generatie beter wordt, tot de meeste raketten in een boog om de muren heen naar het doel vliegen, zonder dat iemand ze vertelt waar ze heen moeten. Druk op Starten en kijk hoe een populatie raketten het groene doel probeert te bereiken. Elke raket volgt alleen zijn genen, een lijst kleine duwtjes, één per moment van zijn vlucht. Na elke vlucht hebben de raketten die het dichtst in de buurt kwamen, en vooral die welke aankwamen, de grootste kans om ouders van de volgende generatie te worden; hun genen worden gemengd en een paar worden willekeurig veranderd. Volgende generatie slaat de rest van een vlucht over. Sleep over het veld om een muur te tekenen, en klik op een muur om hem te verwijderen.
Hoe het werkt
- Kies obstakels, of sleep over het veld om je eigen muren te tekenen, en stel de populatie, de mutatiegraad en de levensduur in.
- Druk op Starten en kijk hoe elke generatie vliegt; Volgende generatie slaat de rest van een vlucht over.
- Volg in de tegels en de grafiek welk aandeel het doel bereikt, en probeer andere mutatiegraden en selectiemethoden.
Hoe de raketten evolueren
Elke raket draagt genen: één klein duwtje voor elk moment van zijn vlucht. De genen van de eerste generatie zijn willekeurig. Na de vlucht krijgt elke raket een fitnessscore: het hoogst voor een vroege aankomst, daarna hoger naarmate hij dichter bij het doel eindigde, en gedeeld door tien na een crash. Ouders voor de volgende generatie worden willekeurig gekozen, maar fittere raketten hebben meer kans om gekozen te worden. Elk kind neemt het eerste deel van zijn genen van de ene ouder en de rest van de andere, en een paar genen worden vervangen door willekeurige duwtjes: mutaties. In de loop van de generaties verspreiden goede vluchtplannen zich en worden ze beter.
Wat de instellingen veranderen
Een grotere populatie verkent meer vluchtplannen tegelijk en loopt minder kans vast te lopen, maar elke generatie duurt langer. De mutatiegraad zoekt het evenwicht tussen verkennen en behouden wat werkt: zonder mutatie raken de nieuwe ideeën van de populatie snel op, met te veel mutatie vergeet ze goede vluchten sneller dan ze die kan vinden. Rouletteselectie kiest ouders in verhouding tot hun fitness, terwijl een toernooi de beste van drie willekeurige raketten neemt, wat minder gevoelig is voor de schaal van de fitness. Elitisme kopieert de beste raket ongewijzigd naar de volgende generatie, zodat het beste resultaat nooit slechter wordt.
Veelgestelde vragen
Waarom blijven de raketten steken achter de verspringende muren?
Hun fitness meet de afstand in rechte lijn tot het doel, dus een raket die tegen de muur onder het doel vliegt, scoort beter dan een die wegvliegt om de opening te zoeken. De populatie hoopt zich op in die doodlopende weg, een lokaal optimum. Grotere populaties, meer mutatie of toernooiselectie helpen haar te ontsnappen, en een fitness die de echte route om de muren heen meet, zou de valkuil vermijden. Een goede fitnessfunctie kiezen is het moeilijkste deel van het gebruik van een genetisch algoritme.
Werkt evolutie in de natuur zo?
In grote lijnen wel: variatie door mutatie en recombinatie, overerving van genen en selectie van de sterksten zijn de ingrediënten van Darwin. De verschillen zijn echter groot. De natuur heeft geen doel en geen fitnessformule, alleen overleven en voortplanten, en echte genomen bouwen lichamen op via ontwikkeling in plaats van acties op te sommen.
Waarvoor worden genetische algoritmen gebruikt?
Voor problemen met een enorme ruimte van mogelijke antwoorden en een eenvoudige manier om een kandidaat te beoordelen: het vormgeven van antennes, vleugels en auto-onderdelen, het plannen van roosters, het afstellen van de instellingen van andere algoritmen, het ontwerpen van neurale netwerken en het maken van kunst en spelstrategieën. De geëvolueerde antenne van NASA op de ST5-satellieten uit 2006 is een beroemd voorbeeld.
Waarom vliegt de beste raket in de volgende generatie soms slechter?
Zonder elitisme wordt de beste raket niet gekopieerd: zijn genen overleven alleen gemengd met andere en mogelijk gemuteerd, dus kan de volgende generatie zijn exacte vlucht kwijtraken. Met elitisme aan blijft de beste raket ongewijzigd behouden en wordt het beste resultaat nooit slechter.
Wordt er iets naar een server gestuurd?
Nee. De raketten vliegen en evolueren in je browser, en de muren die je tekent blijven in de lokale opslag van deze browser.
Klaar om het te proberen?
Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.
Ga naar Editor