Genetisk algoritm

Vad är det?

Den naturliga evolutionen kan modelleras som ett spel, där belöningen för en organism som spelar ett bra livsspel är att dess genetiska material överförs till dess efterföljare och att den fortsätter att överleva.^[2] I den naturliga evolutionen beror hur bra en individ presterar på vem den arbetar med och vem den konkurrerar med, samt på miljön. Genetiska algoritmer är en simulering av naturligt urval på en population av kandidatlösningar till ett optimeringsproblem (kromosomer, individer, varelser eller fenotyper).

Kandidater utvärderas och korsas i ett försök att hitta bra lösningar. Sådana lösningar kan ta mycket tid i anspråk och är inte uppenbara för en människa. En evolutionär fas inleds med en population av slumpmässigt genererade varelser. I varje generation utvärderas lämpligheten hos varje individ i populationen. Några väljs slumpmässigt ut från den aktuella populationen (baserat på deras lämplighet) och ändras (rekombineras och muteras eventuellt slumpmässigt) för att bilda en ny population. Cykeln upprepas med denna nya population. Algoritmen avslutas antingen efter att ett visst antal generationer har passerat eller efter att en god fitnessnivå har uppnåtts för populationen. Om algoritmen har avslutats på grund av att ett maximalt antal generationer har uppnåtts betyder det inte nödvändigtvis att en god fitnessnivå har uppnåtts.

Programmera detta på en dator

Pseudokoden är:

1. Initialisering: Ofta kommer dessa att ha slumpmässiga värden.
2. Utvärdering: En lämplighetsfunktion värderar varje lösning; värderingen är ett tal som anger hur väl lösningen löser problemet.
3. Följande steg utförs tills kravet på att stoppa är uppfyllt:
1. Urval: Välj lösningar/individer för nästa iteration.
2. Rekombination: Kombinera de valda lösningarna.
3. Mutation: Slumpmässigt ändra de nyss skapade lösningarna.
4. Utvärdering: Använd fitnessfunktionen, se steg 2.
5. Om kravet på stopp inte uppfylls, börja om med urvalssteget.

Exempel

Beskrivningen ovan är abstrakt. Ett konkret exempel är till hjälp.

Applikationer

I allmänhet

Genetiska algoritmer är bra på att lösa problem som omfattar schemaläggning och schemaläggning. De har också tillämpats inom ingenjörsvetenskapen. De används ofta för att lösa globala optimeringsproblem.

Som en allmän tumregel kan genetiska algoritmer vara användbara i problemområden som har ett komplext fitnesslandskap, eftersom blandningen är utformad för att flytta populationen bort från lokala optima som en traditionell hillclimbing-algoritm kan fastna i. Vanligt använda crossover-operatörer kan inte ändra någon enhetlig population. Enbart mutation kan ge ergodicitet åt den övergripande genetiska algoritmprocessen (som ses som en Markov-kedja).

Exempel på problem som löses med hjälp av genetiska algoritmer är: speglar som är utformade för att leda solljuset till en solfångare, antenner som är utformade för att fånga upp radiosignaler i rymden, gångmetoder för datorfigurer, optimal utformning av aerodynamiska kroppar i komplexa flödesfält.

I sin Algorithm Design Manual avråder Skiena från genetiska algoritmer för alla uppgifter: "Det är helt onaturligt att modellera tillämpningar i termer av genetiska operatorer som mutation och crossover på bitsträngar. Pseudobiologin lägger ytterligare en komplexitetsnivå mellan dig och ditt problem. För det andra tar genetiska algoritmer mycket lång tid på icke-triviala problem. [...] Analogin med evolutionen - där betydande framsteg kräver [sic] miljontals år - kan vara mycket lämplig. [...] Jag har aldrig stött på något problem där genetiska algoritmer förefaller mig vara det rätta sättet att angripa det. Vidare har jag aldrig sett några beräkningsresultat som rapporterats med hjälp av genetiska algoritmer och som har imponerat på mig. Håll dig till simulerad glödgning för dina heuristiska sökvoodoo behov."

Brädspel

Brädspel är en mycket relevant del av området genetiska algoritmer som tillämpas på spelteoretiska problem. Mycket av det tidiga arbetet med beräkningsintelligens och spel var inriktat på klassiska brädspel, t.ex. tic-tac-toe,^[3] schack och pjäser.^[4] Brädspel kan nu i de flesta fall spelas av en dator på en högre nivå än de bästa människorna, även med blinda uttömmande sökmetoder. Go är ett noterat undantag från denna tendens och har hittills stått emot maskinella attacker. De bästa datorspelarna i Go spelar nu på samma nivå som en god nybörjare.^[5][6] Go-strategin sägs i hög grad bygga på mönsterigenkänning, och inte bara på logisk analys som i schack och andra mer pjäsoberoende spel. Den enorma effektiva förgreningsfaktor som krävs för att hitta högkvalitativa lösningar begränsar kraftigt den tid som kan användas för att söka efter en dragsekvens.

Datorspel

Den genetiska algoritmen kan användas i dataspel för att skapa artificiell intelligens (datorn spelar mot dig). Om en mänsklig spelare kan hitta en sekvens av steg som alltid leder till framgång, även när de upprepas i olika spel, kan det inte finnas någon utmaning kvar. Omvänt, om en inlärningsteknik, t.ex. en genetisk algoritm för en strateg, kan undvika att upprepa tidigare misstag, kommer spelet att ha större spelbarhet.

Genetiska algoritmer består av följande delar:

• En metod för att representera utmaningen i form av lösningen (t.ex. dirigering av soldater i ett anfall i ett strategispel).
• En lämplighets- eller utvärderingsfunktion för att bestämma kvaliteten på en instans (t.ex. en mätning av den skada som en motståndare åsamkas vid ett sådant angrepp).

Fitness-funktionen accepterar en muterad instantiation av en enhet och mäter dess kvalitet. Funktionen anpassas till problemområdet. I många fall, särskilt när det gäller kodoptimering, kan lämplighetsfunktionen helt enkelt vara en systemtidsfunktion. När en genetisk representation och en fitnessfunktion har definierats kommer en genetisk algoritm att instantiera de första kandidaterna på det sätt som beskrivs ovan och sedan förbättra dem genom upprepad tillämpning av mutations-, crossover-, inversions- och selektionsoperatorer (enligt definitionerna för problemområdet).

Begränsningar

Det finns begränsningar i användningen av en genetisk algoritm jämfört med alternativa optimeringsalgoritmer:

• Upprepad utvärdering av fitnessfunktioner för komplexa problem är ofta det mest begränsande segmentet av artificiella evolutionära algoritmer. För att hitta den optimala lösningen på komplexa problem krävs ofta mycket dyra utvärderingar av lämplighetsfunktioner. I verkliga problem, t.ex. strukturella optimeringsproblem, kan en enda funktionsutvärdering kräva flera timmar till flera dagar av fullständig simulering. Typiska optimeringsmetoder kan inte hantera sådana typer av problem. Det är ofta nödvändigt att använda approximation, eftersom det tar för lång tid att beräkna den exakta lösningen. Genetiska algoritmer kombinerar ibland olika approximationsmodeller för att lösa komplexa verkliga problem.
• Genetiska algoritmer är inte skalbara. Om antalet element som utsätts för mutation är stort ökar ofta sökutrymmets storlek exponentiellt. Detta gör det mycket svårt att använda tekniken för problem som t.ex. att konstruera en motor, ett hus eller ett flygplan. För att kunna använda genetiska algoritmer för sådana problem måste de brytas ner till en så enkel representation som möjligt. Därför ser vi evolutionära algoritmer som kodar konstruktioner för fläktblad i stället för motorer, byggnadsformer i stället för detaljerade byggplaner och flygplansprofiler i stället för hela flygplanskonstruktioner. Det andra komplexitetsproblemet är frågan om hur man ska skydda delar som har utvecklats till att representera bra lösningar från ytterligare destruktiva mutationer, särskilt när deras lämplighetsbedömning kräver att de kombineras väl med andra delar.
• Den "bättre" lösningen finns bara i jämförelse med andra lösningar. Därför är stoppkriteriet inte tydligt i alla problem.
• I många problem har genetiska algoritmer en tendens att konvergera mot lokala optimum eller till och med godtyckliga punkter snarare än mot problemets globala optimum. Detta innebär att algoritmen inte "vet hur" den ska offra kortsiktig lämplighet för att få mer långsiktig lämplighet. Sannolikheten för att detta ska inträffa beror på fitnessfunktionens form: vissa problem gör det lätt att hitta det globala optimumet, andra kan göra det lättare för funktionen att hitta lokala optima. Detta problem kan minskas genom att använda en annan fitnessfunktion, öka mutationshastigheten eller genom att använda urvalstekniker som upprätthåller en varierad population av lösningar. En vanlig teknik för att bevara mångfalden är att använda en "nischstraff": varje grupp individer med tillräcklig likhet (nischradie) får en straffavgift som minskar representationen av den gruppen i de följande generationerna, vilket gör det möjligt att behålla andra (mindre likartade) individer i populationen. Detta trick kan dock vara ineffektivt, beroende på hur problemet ser ut. En annan möjlig teknik skulle vara att helt enkelt ersätta en del av populationen med slumpmässigt genererade individer, när större delen av populationen är alltför lik varandra. Mångfald är viktigt i genetiska algoritmer (och genetisk programmering) eftersom korsning av en homogen population inte ger nya lösningar. I evolutionära strategier och evolutionär programmering är mångfald inte viktigt eftersom man i högre grad förlitar sig på mutation.
• Det är svårt att arbeta med dynamiska datamängder, eftersom genomerna tidigt börjar konvergera mot lösningar som kanske inte längre är giltiga för senare data. Flera metoder har föreslagits för att åtgärda detta genom att på något sätt öka den genetiska mångfalden och förhindra tidig konvergens, antingen genom att öka sannolikheten för mutation när lösningens kvalitet sjunker (så kallad utlöst hypermutation) eller genom att ibland införa helt nya, slumpmässigt genererade element i genpoolen (så kallade slumpmässiga invandrare). Återigen kan evolutionsstrategier och evolutionär programmering genomföras med en så kallad "kommastrategi" där föräldrarna inte underhålls och nya föräldrar väljs endast från avkomman. Detta kan vara mer effektivt vid dynamiska problem.
• Genetiska algoritmer kan inte effektivt lösa problem där det enda måttet på lämplighet är ett enda rätt/fel-mått (som beslutsproblem), eftersom det inte finns något sätt att konvergera mot lösningen (ingen kulle att klättra uppför). I dessa fall kan en slumpmässig sökning hitta en lösning lika snabbt som en GA. Men om situationen gör det möjligt att upprepa ett försök med framgång eller misslyckande som ger (eventuellt) olika resultat, är förhållandet mellan framgång och misslyckande ett lämpligt mått på lämplighet.
• För specifika optimeringsproblem och probleminstanser kan andra optimeringsalgoritmer vara effektivare än genetiska algoritmer när det gäller konvergenshastighet. Alternativa och kompletterande algoritmer är bl.a. evolutionära strategier, evolutionär programmering, simulerad glödgning, Gaussisk anpassning, hill climbing, svärmintelligens (t.ex. myrkolonial optimering, partikel svärmoptimering) och metoder baserade på heltal linjär programmering. De genetiska algoritmernas lämplighet är beroende av hur mycket kunskap om problemet som finns; för välkända problem finns ofta bättre, mer specialiserade metoder.

Historia

1950 föreslog Alan Turing en "inlärningsmaskin" som skulle vara parallell med evolutionens principer. Datorsimulering av evolutionen började redan 1954 med Nils Aall Barricellis arbete, som använde datorn vid Institute for Advanced Study i Princeton, New Jersey. Hans publikation från 1954 uppmärksammades inte av någon större krets. Från och med 1957 publicerade den australiensiska kvantitativa genetikern Alex Fraser en serie artiklar om simulering av artificiellt urval av organismer med flera loci som kontrollerar en mätbar egenskap. Från denna början blev det vanligare att biologer simulerar evolutionen med hjälp av datorer i början av 1960-talet, och metoderna beskrevs i böcker av Fraser och Burnell (1970) och Crosby (1973). Frasers simuleringar innehöll alla väsentliga delar av moderna genetiska algoritmer. Dessutom publicerade Hans-Joachim Bremermann en serie artiklar på 1960-talet som också antog en population av lösningar på optimeringsproblem som genomgår rekombination, mutation och urval. Bremermanns forskning omfattade också de delar som ingår i moderna genetiska algoritmer. Andra anmärkningsvärda tidiga pionjärer är Richard Friedberg, George Friedman och Michael Conrad. Många av de tidiga artiklarna återges i Fogel (1998).

Även om Barricelli, i ett arbete som han rapporterade 1963, hade simulerat utvecklingen av förmågan att spela ett enkelt spel, blev artificiell evolution en allmänt erkänd optimeringsmetod som ett resultat av Ingo Rechenbergs och Hans-Paul Schwefels arbete på 1960-talet och i början av 1970-talet - Rechenbergs grupp kunde lösa komplexa tekniska problem med hjälp av evolutionära strategier. En annan metod var Lawrence J. Fogels teknik för evolutionär programmering, som föreslogs för att generera artificiell intelligens. Evolutionär programmering använde ursprungligen finita tillståndsmaskiner för att förutsäga miljöer, och använde variation och urval för att optimera de prediktiva logikerna. Genetiska algoritmer blev särskilt populära genom John Hollands arbete i början av 1970-talet, och särskilt hans bok Adaptation in Natural and Artificial Systems (1975). Hans arbete har sitt ursprung i studier av cellulära automater, som Holland och hans studenter genomförde vid University of Michigan. Holland introducerade ett formaliserat ramverk för att förutsäga kvaliteten på nästa generation, känt som Hollands schemateorem. Forskningen om genetiska algoritmer förblev till stor del teoretisk fram till mitten av 1980-talet, då den första internationella konferensen om genetiska algoritmer hölls i Pittsburgh, Pennsylvania.