- Flyger
- Nådde målet
- Kraschade
- Bästa flygningen i senaste generationen
- Nådde målet
- Kraschade
Lekplats för genetiska algoritmer
En genetisk algoritm löser ett problem på samma sätt som evolutionen formar levande varelser: pröva många slumpmässiga svar, behåll de bättre, blanda dem, ändra några bitar slumpmässigt och upprepa. Här är svaren raketer. Varje raket följer en lista med slumpmässiga knuffar och inget annat, och i början tumlar de omkring planlöst. Tryck på Kör och se populationen bli bättre generation för generation, tills de flesta av dem svänger runt väggarna till målet, utan att någon har talat om för dem vart de ska. Tryck på Kör och se en population raketer försöka nå det gröna målet. Varje raket följer bara sina gener, en lista med små knuffar, en för varje ögonblick av flygningen. Efter varje flygning har de raketer som kom närmast, och framför allt de som kom fram, störst chans att bli föräldrar till nästa generation; deras gener blandas och några få ändras slumpmässigt. Nästa generation hoppar över resten av en flygning. Dra på fältet för att rita en vägg, och klicka på en vägg för att ta bort den.
Hur det fungerar
- Välj hinder, eller dra på fältet för att rita egna väggar, och ställ in population, mutationsgrad och livslängd.
- Tryck på Kör och se varje generation flyga; Nästa generation hoppar över resten av en flygning.
- Följ andelen som når målet i rutorna och diagrammet, och pröva andra mutationsgrader och urvalsmetoder.
Så utvecklas raketerna
Varje raket bär gener: en liten knuff för varje ögonblick av flygningen. Den första generationens gener är slumpmässiga. Efter flygningen får varje raket ett fitnessvärde: högst för en tidig ankomst, sedan högre ju närmare målet den slutade, och delat med tio efter en krasch. Föräldrar till nästa generation väljs slumpmässigt, men raketer med högre fitness har större chans att bli valda. Varje barn tar den första delen av sina gener från den ena föräldern och resten från den andra, och några få gener ersätts med slumpmässiga knuffar: mutationer. Under generationernas gång sprids bra flygplaner och blir bättre.
Vad inställningarna ändrar
En större population utforskar fler flygplaner på en gång och fastnar mindre lätt, men varje generation tar längre tid. Mutationsgraden balanserar utforskande mot att behålla det som fungerar: utan mutation får populationen snabbt slut på nya idéer, med för mycket glömmer den bra flygningar snabbare än den hittar dem. Rouletteurval väljer föräldrar i proportion till fitness, medan en turnering tar den bästa av tre slumpmässiga raketer, vilket är mindre känsligt för hur fitness är skalad. Elitism kopierar den bästa raketen oförändrad till nästa generation, så att det bästa resultatet aldrig blir sämre.
Ofta ställda frågor
Varför fastnar raketerna bakom de förskjutna väggarna?
Deras fitness mäter fågelvägen till målet, så en raket som flyger in i väggen under målet får bättre värde än en som flyger bort för att hitta öppningen. Populationen hopar sig i den återvändsgränden, ett lokalt optimum. Större populationer, mer mutation eller turneringsurval hjälper den att ta sig ur, och en fitness som mätte den verkliga vägen runt väggarna skulle undvika fällan. Att välja en bra fitnessfunktion är den svåraste delen av att använda en genetisk algoritm.
Är det så här evolutionen fungerar i naturen?
I stora drag: variation genom mutation och rekombination, nedärvning av gener och urval av de bäst anpassade är Darwins ingredienser. Skillnaderna är dock stora. Naturen har inget mål och ingen fitnessformel, bara överlevnad och fortplantning, och verkliga genom bygger kroppar genom utveckling i stället för att räkna upp handlingar.
Vad används genetiska algoritmer till?
Till problem med ett enormt rum av möjliga svar och ett enkelt sätt att bedöma en kandidat: att forma antenner, vingar och bildelar, lägga scheman, ställa in andra algoritmers inställningar, utforma neurala nätverk och skapa konst och spelstrategier. NASA:s evolverade antenn på ST5-satelliterna från 2006 är ett berömt exempel.
Varför flyger den bästa raketen ibland sämre i nästa generation?
Utan elitism kopieras inte den bästa raketen: dess gener överlever bara blandade med andras och kanske muterade, så nästa generation kan förlora just dess flygning. Med elitism påslagen behålls den bästa raketen oförändrad och det bästa resultatet blir aldrig sämre.
Skickas något till en server?
Nej. Raketerna flyger och utvecklas i din webbläsare, och väggarna du ritar sparas i den här webbläsarens lokala lagring.
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Gå till Editor