Genetiske algoritmer forklaret
Evolutionen har frembragt øjne, vinger og hjerner uden en designer, blot ved at beholde det, der virker, og variere det. En genetisk algoritme låner den idé til at løse problemer på en computer. Den behøver ikke at forstå problemet, kun at kunne skelne et bedre svar fra et dårligere, og det gør den til et stærkt værktøj, når rummet af mulige svar er for stort og for underligt til at blive gennemsøgt på nogen anden måde.
Idéen
I 1960'erne og 1970'erne gjorde John Holland ved University of Michigan Darwins teori til en algoritme, beskrevet i hans bog Adaptation in Natural and Artificial Systems fra 1975. Omtrent samtidig udviklede Ingo Rechenberg og Hans-Paul Schwefel i Tyskland evolutionsstrategier til ingeniørmæssigt design. Den fælles opskrift: hold en population af kandidatløsninger, giv dem en score, lad de bedste formere sig med variation, og gentag i mange generationer.
Gener og populationen
Hver kandidat beskrives af et kromosom, en liste af gener. På legepladsen er en rakets gener dens skub, ét for hvert øjeblik af flyvningen; i andre problemer kan de være bittene i et tal, rækkefølgen af byer på en rute eller størrelserne på dele i et design. Den første generation er tilfældig, hvilket betyder, at den udforsker rummet af svar bredt, men næsten ikke har nogen gode svar.
Fitnessfunktionen
Fitness er det ene tal, der siger, hvor god en kandidat er, og det er det eneste, algoritmen ved om problemet. For raketterne belønner den mest en tidlig ankomst, dernæst at ende tæt på målet, og den straffer styrt. En velvalgt fitnessfunktion leder søgningen jævnt mod gode svar; en skødesløs belønner det forkerte, og algoritmen vil udnytte ethvert smuthul, den efterlader.
Selektion
Forældrene vælges, så kandidater med højere fitness får flere børn, men svagere kandidater får stadig en chance, fordi deres gener kan rumme nyttige stykker. Roulettehjulselektion giver hver kandidat et stykke af et hjul i forhold til dens fitness; turneringsselektion vælger nogle få tilfældigt og tager den bedste af dem. Stærkere selektion fremskynder fremskridtet, men gør også populationen mere ensartet, hvilket kan afslutte søgningen for tidligt.
Krydsning og mutation
Krydsning kombinerer to forældre: her tager et barn den første del af sine gener fra den ene forælder og resten fra den anden, så den ene rakets tidlige manøvrer kan møde en anden rakets sene. Mutation erstatter nogle få gener tilfældigt. Krydsning kombinerer det, populationen allerede har; mutation tilfører det, den aldrig har haft. Hollands skemasætning beskriver, hvordan korte byggesten af gode gener spredes i populationen under denne blanding af selektion og rekombination.
Elitisme, udforskning og udnyttelse
At kopiere de bedste få kandidater uændret over i næste generation, elitisme, garanterer, at det bedste svar aldrig går tabt. Enhver genetisk algoritme skal afbalancere udforskning, at afprøve nye områder af søgerummet, mod udnyttelse, at forfine det, der allerede er godt. For lidt variation, og populationen konvergerer mod ét middelmådigt svar; for meget, og den falder aldrig til ro. Populationsstørrelse, mutationsrate og selektionstryk er de knapper, der indstiller balancen.
Lokale optima
En genetisk algoritme følger kun fitness, så den kan narres. Når vejen til det bedste svar først går gennem dårligere svar, klatrer populationen op på den nærmeste bakke og bliver der: et lokalt optimum. Bag de forskudte mure på legepladsen scorer raketter, der styrter ned under målet, bedre end raketter, der drejer væk for at finde åbningen, så populationen hober sig op mod muren. Midlerne omfatter større populationer, højere mutation, at holde populationen varieret og frem for alt en bedre fitnessfunktion.
Udforsk det
Åbn legepladsen for genetiske algoritmer for at lade raketter udvikle sig uden om én mur, en åbning, søjler, forskudte mure eller mure, du selv tegner. Skift population, mutationsrate, levetid og selektionsmetode, slå elitisme til og fra, og følg i diagrammet, hvor hurtigt andelen af raketter, der når målet, vokser, eller hvorfor den ikke gør.
Ofte stillede spørgsmål
Er en genetisk algoritme en slags kunstig intelligens?
Den hører til det bredere felt AI og maskinlæring som en søge- og optimeringsmetode. Den lærer ikke af eksempler som et neuralt netværk; den forbedrer kandidatløsninger gennem forsøg og selektion. De to kombineres ofte, for eksempel ved at lade strukturen eller vægtene i neurale netværk udvikle sig, en tilgang der kaldes neuroevolution.
Finder en genetisk algoritme altid det bedste svar?
Nej. Den er en heuristik: den finder som regel gode svar på svære problemer, men giver ingen garanti for det bedste og intet bevis for, hvor tæt den er på. Til problemer, hvor en eksakt metode er hurtig nok, er den metode bedre.
Hvad er forskellen på en genetisk algoritme og evolutionsstrategier?
Begge er evolutionære algoritmer. Klassiske genetiske algoritmer lægger vægt på krydsning af strenglignende kromosomer; evolutionsstrategier arbejder hovedsageligt med mutation af reelle tal og tilpasser ofte selv deres mutationsstørrelser undervejs. Moderne metoder blander idéer fra begge.
Hvorfor er raketterne så klodsede i starten?
Deres første gener er helt tilfældige skub, så i gennemsnit udligner de hinanden, og raketterne driver rundt. Først når selektionen har beholdt de sjældne raketter, der tilfældigvis skubbede nogenlunde i den rigtige retning, og krydsningen har kombineret deres gode stykker, opstår der koordinerede flyvninger.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Åbn legepladsen for genetiske algoritmer