- Flyver
- Nåede målet
- Styrtet ned
- Bedste flyvning i sidste generation
- Nåede målet
- Styrtet ned
Legeplads for genetiske algoritmer
En genetisk algoritme løser et problem på samme måde, som evolutionen former levende væsener: prøv mange tilfældige svar, behold de bedste, bland dem, ændr nogle få stykker tilfældigt, og gentag. Her er svarene raketter. Hver raket følger en liste af tilfældige skub og intet andet, og i starten tumler de formålsløst rundt. Tryk på Start, og se populationen blive bedre generation for generation, indtil de fleste af dem svinger uden om murene til målet, uden at nogen har fortalt dem, hvor de skal hen. Tryk på Start, og se en population af raketter forsøge at nå det grønne mål. Hver raket følger kun sine gener, en liste af små skub, ét for hvert øjeblik af flyvningen. Efter hver flyvning har de raketter, der kom tættest på, og frem for alt dem, der nåede frem, størst chance for at blive forældre til næste generation; deres gener blandes, og nogle få ændres tilfældigt. Næste generation springer resten af en flyvning over. Træk på feltet for at tegne en mur, og klik på en mur for at fjerne den.
Sådan virker det
- Vælg forhindringer, eller træk på feltet for at tegne dine egne mure, og indstil population, mutationsrate og levetid.
- Tryk på Start, og se hver generation flyve; Næste generation springer resten af en flyvning over.
- Følg andelen, der når målet, i felterne og diagrammet, og prøv andre mutationsrater og selektionsmetoder.
Sådan udvikler raketterne sig
Hver raket bærer gener: ét lille skub for hvert øjeblik af flyvningen. Den første generations gener er tilfældige. Efter flyvningen får hver raket en fitnessscore: højest for en tidlig ankomst, dernæst højere, jo tættere på målet den endte, og divideret med ti efter et styrt. Forældrene til næste generation vælges tilfældigt, men raketter med højere fitness har større chance for at blive valgt. Hvert barn tager den første del af sine gener fra den ene forælder og resten fra den anden, og nogle få gener erstattes af tilfældige skub: mutationer. Gennem generationerne spredes gode flyveplaner og bliver bedre.
Hvad indstillingerne ændrer
En større population udforsker flere flyveplaner på én gang og har mindre risiko for at sidde fast, men hver generation tager længere tid. Mutationsraten afbalancerer udforskning og bevarelse af det, der virker: uden mutation løber populationen hurtigt tør for nye idéer, med for meget glemmer den gode flyvninger hurtigere, end den kan finde dem. Roulettehjulselektion vælger forældre i forhold til deres fitness, mens en turnering tager den bedste af tre tilfældige raketter, hvilket er mindre følsomt over for, hvordan fitness er skaleret. Elitisme kopierer den bedste raket uændret over i næste generation, så det bedste resultat aldrig bliver dårligere.
Ofte stillede spørgsmål
Hvorfor sidder raketterne fast bag de forskudte mure?
Deres fitness måler den lige afstand til målet, så en raket, der flyver ind i muren under målet, scorer bedre end en, der flyver væk for at finde åbningen. Populationen hober sig op i den blindgyde, et lokalt optimum. Større populationer, mere mutation eller turneringsselektion hjælper den med at slippe ud, og en fitness, der målte den reelle rute uden om murene, ville undgå fælden. At vælge en god fitnessfunktion er den sværeste del af at bruge en genetisk algoritme.
Er det sådan, evolutionen virker i naturen?
I grove træk: variation fra mutation og rekombination, nedarvning af gener og selektion af de bedst egnede er Darwins ingredienser. Forskellene er dog store. Naturen har intet mål og ingen fitnessformel, kun overlevelse og formering, og rigtige genomer bygger kroppe gennem udvikling i stedet for at opremse handlinger.
Hvad bruges genetiske algoritmer til?
Til problemer med et enormt rum af mulige svar og en nem måde at bedømme en kandidat på: udformning af antenner, vinger og bildele, planlægning af skemaer, justering af andre algoritmers indstillinger, design af neurale netværk og skabelse af kunst og spilstrategier. NASA's evolverede antenne på ST5-satellitterne fra 2006 er et berømt eksempel.
Hvorfor flyver den bedste raket nogle gange dårligere i næste generation?
Uden elitisme bliver den bedste raket ikke kopieret: dens gener overlever kun blandet med andres og måske muteret, så næste generation kan miste dens præcise flyvning. Med elitisme slået til bevares den bedste raket uændret, og det bedste resultat bliver aldrig dårligere.
Bliver der sendt noget til en server?
Nej. Raketterne flyver og udvikler sig i din browser, og de mure, du tegner, bliver i denne browsers lokale lager.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Gå til Editor