Genetiska algoritmer förklarade

Evolutionen har frambringat ögon, vingar och hjärnor utan någon formgivare, helt enkelt genom att behålla det som fungerar och variera det. En genetisk algoritm lånar den idén för att lösa problem på en dator. Den behöver inte förstå problemet, bara skilja ett bättre svar från ett sämre, och det gör den till ett kraftfullt verktyg när rummet av möjliga svar är för stort och för märkligt för att genomsökas på något annat sätt.

Raketer som flyger från botten av ett fält runt en vägg till ett grönt mål, med den bästa flygningen ritad som en streckad linje
Raketer som flyger från botten av ett fält runt en vägg till ett grönt mål, med den bästa flygningen ritad som en streckad linje

Idén

Under 1960- och 1970-talen gjorde John Holland vid University of Michigan om Darwins teori till en algoritm, beskriven i hans bok Adaptation in Natural and Artificial Systems från 1975. Ungefär samtidigt utvecklade Ingo Rechenberg och Hans-Paul Schwefel i Tyskland evolutionsstrategier för teknisk konstruktion. Det gemensamma receptet: håll en population av kandidatlösningar, poängsätt dem, låt de bättre fortplanta sig med variation och upprepa i många generationer.

John Holland, som beskrev genetiska algoritmer i sin bok Adaptation in Natural and Artificial Systems från 1975.
John Holland, som beskrev genetiska algoritmer i sin bok Adaptation in Natural and Artificial Systems från 1975.

Gener och populationen

Varje kandidat beskrivs av en kromosom, en lista med gener. På lekplatsen är en rakets gener dess knuffar, en för varje ögonblick av flygningen; i andra problem kan de vara bitarna i ett tal, ordningen på städer längs en rutt eller storleken på delar i en konstruktion. Den första generationen är slumpmässig, vilket betyder att den utforskar rummet av svar brett men nästan inte har några bra svar.

Fitnessfunktionen

Fitness är det enda tal som säger hur bra en kandidat är, och det är det enda algoritmen vet om problemet. För raketerna belönar den framför allt en tidig ankomst, därefter att sluta nära målet, och den bestraffar krascher. En välvald fitnessfunktion leder sökningen smidigt mot bra svar; en slarvig belönar fel sak, och algoritmen kommer att utnyttja varje kryphål den lämnar öppet.

Urval

Föräldrar väljs så att kandidater med högre fitness får fler barn, men svagare får ändå en chans, eftersom deras gener kan innehålla användbara bitar. Rouletthjulsurval ger varje kandidat en sektor av ett hjul i proportion till dess fitness; turneringsurval väljer några slumpmässigt och tar den bästa av dem. Starkare urval snabbar på framstegen men gör också populationen mer enhetlig, vilket kan avsluta sökningen för tidigt.

Korsning och mutation

Korsning kombinerar två föräldrar: här tar ett barn den första delen av sina gener från den ena föräldern och resten från den andra, så att en rakets tidiga manövrer kan mötas med en annans sena. Mutation ersätter några få gener slumpmässigt. Korsning kombinerar om det populationen redan har; mutation tillför det den aldrig har haft. Hollands schemasats beskriver hur korta byggstenar av bra gener sprids i populationen under denna blandning av urval och rekombination.

Elitism, utforskning och utnyttjande

Att kopiera de få bästa kandidaterna oförändrade till nästa generation, elitism, garanterar att det bästa svaret aldrig går förlorat. Varje genetisk algoritm måste balansera utforskning, att pröva nya delar av sökrummet, mot utnyttjande, att förfina det som redan är bra. För lite variation och populationen konvergerar mot ett enda medelmåttigt svar; för mycket och den stabiliseras aldrig. Populationsstorlek, mutationsgrad och urvalstryck är reglagen som ställer in balansen.

Lokala optima

En genetisk algoritm följer bara fitness, så den kan luras. När vägen till det bästa svaret först går genom sämre svar klättrar populationen upp på närmaste kulle och stannar där: ett lokalt optimum. Bakom de förskjutna väggarna på lekplatsen får raketer som kraschar under målet bättre värde än raketer som svänger bort för att hitta öppningen, så populationen hopar sig mot väggen. Botemedel är större populationer, högre mutation, att hålla populationen varierad och framför allt en bättre fitnessfunktion.

Utforska själv

Öppna lekplatsen för genetiska algoritmer för att låta raketer utvecklas runt en vägg, en öppning, pelare, förskjutna väggar eller väggar du ritar själv. Ändra population, mutationsgrad, livslängd och urvalsmetod, slå på och av elitism och följ i diagrammet hur snabbt andelen raketer som når målet växer, eller varför den inte gör det.

Ofta ställda frågor

Är en genetisk algoritm en sorts artificiell intelligens?

Den hör till det bredare området AI och maskininlärning, som en sök- och optimeringsmetod. Den lär sig inte av exempel som ett neuralt nätverk; den förbättrar kandidatlösningar genom försök och urval. De två kombineras ofta, till exempel genom att låta strukturen eller vikterna i neurala nätverk utvecklas, ett angreppssätt som kallas neuroevolution.

Hittar en genetisk algoritm alltid det bästa svaret?

Nej. Den är en heuristik: den hittar oftast bra svar på svåra problem, men ger ingen garanti för det bästa och inget bevis för hur nära det den är. För problem där en exakt metod är tillräckligt snabb är den metoden bättre.

Vad är skillnaden mellan en genetisk algoritm och evolutionsstrategier?

Båda är evolutionära algoritmer. Klassiska genetiska algoritmer betonar korsning av strängliknande kromosomer; evolutionsstrategier arbetar främst med mutation av reella tal och anpassar ofta sina egna mutationsstorlekar under tiden. Moderna metoder blandar idéer från båda.

Varför är raketerna så klumpiga i början?

Deras första gener är helt slumpmässiga knuffar, så i genomsnitt tar de ut varandra och raketerna driver omkring. Först när urvalet har behållit de sällsynta raketer som råkade knuffa ungefär åt rätt håll, och korsningen har kombinerat deras bra avsnitt, uppstår samordnade flygningar.

Redo att prova det?

Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.

Öppna lekplatsen för genetiska algoritmer