Genetisk algoritme

Representasjon av reproduksjonssyklusen til en genetisk algoritme.

En genetisk algoritme (GA) er en søkeheuristikk innenfor kunstig intelligens, som har som mål å etterligne den naturlige evolusjonsprosessen. Den inneholder derfor evolusjonselementer som arv, mutasjon, utvalg, og rekombinasjon. Genetiske algoritmer er en underklasse av evolusjonære algoritmer, og blir ofte brukt til å generere optimaliseringer og innen søkeproblemer.^[1]

Genetiske algoritmer blir blant annet brukt innenfor områdene bioinformatikk, fylogenetikk, informatikk, ingeniørvitenskap, økonomi, kjemi, industriteknikk, matematikk og fysikk.

Metodologi

I en genetisk algoritme blir et sett (populasjon) av potensielle løsninger til et optimaliseringsproblem utviklet til bedre løsninger. Hver kandidat i populasjonen har et sett av verdier (sine kromosomer, gener eller genotype) som kan muteres og endres; tradisjonelt sett er løsninger oftest representert binært, men andre kodingsformer er også mulige.^[2]

Utviklingen starter oftest fra tilfeldig genererte individer, og er en iterativ prosess, der hver populasjon kalles en generasjon. I hver generasjon blir alle individene i populasjonen evaluert av en fitness-funksjon som har til oppgave å beregne kvaliteten til hvert enkelt individ, og som helhet hvor nært optimaliseringsproblemet er til å bli løst. Individene med høyest fitness-verdi blir krysset med hverandre og utsatt for en mutasjonsprosess som tilfeldig endrer deler av genomet. Hvor ofte mutasjon skal forekomme blir bestemt av en mutasjonsrate To individer med høy fitness krysses og danner to nye individer som blir med på å forme en ny generasjon. Den nye generasjonen blir deretter brukt i den neste iterasjonen av algoritmen. Algoritmen avsluttes som regel enten etter et bestemt antall generasjoner, eller når en tilfredsstillende fitnessverdi for populasjonen er oppnådd.

En typisk genetisk algoritme krever

1. Genetisk fremstilling av løsningsdomenet.
2. Fitnessfunksjon som evaluerer løsningsdomenet.

En standard representasjon av hvert individ utgjøres av matrise av bits.^[2] Matriser av andre datastrukturer kan også bli brukt på en lignende måte. En av hovedegenskapene til genetiske algoritmer som gjør dem praktiske er at individer lett kan krysses med hverandre på grunn av den fastsatte størrelsen og de utskiftbare enkeltdelene individet er satt sammen av. Representasjoner med varierende lengde kan også bli brukt, men gjør krysningsimplementasjon mer komplisert.

Etter at den genetiske fremstillingen og fitness-funksjonen er definert initialiserer den genetiske algoritmen en populasjon som den kan forbedre gjennom en iterativ prosess av mutasjon, rekombinasjon, inversjon og seleksjonsoperatorer.

Initialisering av genetiske algoritmer

Genetiske algoritmer starter oftest ved at tilfeldige løsninger genereres for å skape en innledende populasjon. Størrelsen på populasjonen varierer ut i fra problemet som skal løses, men inneholder oftest flere hundre eller tusener av mulige løsninger. Populasjonen blir tradisjonelt generert tilfeldig, og tillater derfor alle potensielle løsninger (også kalt et søkerom). Det er imidlertid også mulig å vekte bestemte områder hvor man kan forvente å finne optimale løsninger.

Seleksjon

I løpet av hver generasjon blir en del av den eksisterende populasjonen valgt for å avle en ny generasjon. Individuelle løsninger blir valgt gjennom en fitness-prosess, hvor løsningene som er best egnet (bestemt fra en fitness-funksjon) blir valgt. Bestemte utvalgssmetoder rangerer fitnessverdiene til alle individene og velger ut de beste. Andre metoder kan ta et tilfeldig utvalg fra populasjonen, da førstnevnte prosessen kan være veldig tidskrevende.

Fitness-funksjonen måler kvaliteten av den representerte løsningen. Hva fitness-funksjonen er, er alltid avhengig av hva problemet er.

For noen problemer er det svært vanskelig eller umulig å definer ett fitness-uttrykk; i disse situasjonene kan en simulering bli brukt for å avgjøre fitness-funksjonsverdien av en fenotype, eller potensielt også en interaktiv genetisk algoritme.

Genetiske operatorer

For å generere den neste generasjonens populasjon av individ blir de best egnede genene valgt gjennom en kombinasjon av operatorene rekombinasjon og mutasjon.

For hvert nye individ som blir produsert, eksisterer et par «foreldre» som har blir valgt fra samlingen av individ i den første generasjon. Et nytt individ er skapt ved bruk av operatorene rekombinasjon og mutasjon, og deler typisk mange av karakteristikkene til sine foreldre. Nye foreldre blir valgt til hvert nye «avkom», og prosessen fortsetter helt til den nye populasjonen når en tilstrekkelig størrelse.

Selv om reproduksjonsmetodene med to foreldre er inspirert av biologien, antyder forskning at bruken av mer enn to foreldre genererer høyere kvalitet på individene-^[3][4]

Til slutt gjenstår en populasjon av individer som er forskjellig fra forrige generasjon. Denne nye generasjonen vil vanligvis ha en forbedret fitnessverdi, da bare individene av høyest kvalitet fra forrige generasjon blir valgt for krysning, sammen med en liten andel med individer som har lavere fitnessverdi. Disse individene med lavere fitness sørger for et større mangfold innenfor populasjonen av foreldre og sørger derfor genetisk mangfold i de følgende generasjonene av barn.

Selv om krysning og mutasjon er hovedoperatorene for genetiske algoritmer, er det også mulig å bruke andre operatorer.

Det er anbefalt å tilpasse parametre som mutasjonssannsynlighet, rekombinasjonssannsynlighet og populasjonsstørrelse for å finne fornuftige innstillinger for det bestemte problemet som skal løses. En for liten mutasjonsrate kan føre til genetisk drift. En rekombinasjonsrate som er for høy kan føre til at den genetiske algoritmen når konvergens for tidlig. En høy mutasjonsrate kan føre til tap av potensielt gode løsninger, med mindre man bruke elitisme, en prosess hvor man lar de beste individene fra forrige generasjon krysse over til neste generasjon.

Termineringskriterier

Iterasjonsprosessen repeteres helt til krav for fullførelse blir nådd. Vanlige krav er

• En løsning er funnet som tilfredsstiller et minimumskriterium.
• Gitt antall generasjoner nådd.
• Det gitte budsjettet (i prosessortid eller penger) er nådd.
• Individet med høyest rangering kommet til et platå, slik at påfølgende iterasjoner ikke produserer bedre resultat.
• Manuell inspeksjon.
• Kombinasjon av ovenstående resultater.

Eksempelkode

Enkel genetisk algoritme pseudokode

    
initialize population p with random genes
Repeat
  foreach pi in p
     fi = fitness(pi)
  repeat
     parent1 = select(p,f)
     parent2 = select(p,f)
     child1, child2 = crossover(parent1,parent2)
     if (random < mutate_probability)
         child1 = mutate(child1)
     if (random < mutate_probability)
         child2 = mutate(child2)
     add child1, child2 to p’
   until p’ is full
   p = p’

Begrensninger

Det er begrensninger på bruken av genetiske algoritmer sammenlignet med andre alternative optimaliseringsalgoritmer.

• Gjentatt fitness-funksjonsevaluering for komplekse problemer er ofte det mest uoverkommelige og begrensende området av kunstig evolusjonære algoritmer. Å finne optimale løsninger på komplekse fler-dimensjonale, multimodale problemer krever ofte veldig dyre fitness-funksjonsevalueringer. I den reelle verden kan enkelte funksjonsevalueringer kreve alt fra flere timer til dager for å fullføre. Typiske optimaliseringsmetoder kan ikke takle slike problemer, og det er derfor nødvendig å bruke tilnærmet fitness som er mer effektiv for databehandlig. Den mest lovende løsningen for å bruke genetiske algoritmer til komplekse problemer i den reelle verden er så langt sammenslåing av tilnærmingsmodeller.
• Genetiske algoritmer skalerer dårlig når kompleksiteten stiger. Det vil si at når mengden elementer som er utsatt for mutasjon er stor blir det ofte en eksponentiell økning i søkestørrelse. Dette gjør det svært vanskelig å bruke teknikken på problemer som er for eksempel design av en motor, et hus eller et fly. For at slike problemer skal kunne benytte seg av genetiske algoritmer må de først bli brutt ned i den enkleste representasjonen som er mulig. Derfor vil typisk evolusjonære algoritmer bli brukt til propeller istedenfor motorer, design av formen på bygninger istedenfor detaljerte byggeplaner, vingeprofil istedenfor hele luftfartøy design.

Det andre problemet ved kompleksitet er, hvordan skal en hindre enkelte parter eller kromosomer som har blitt avlet frem til potensielt gode løsninger fra å bli ødelagt av videre mutasjon, spesielt når fitness vurderingen krever at de må kombineres med andre parter.

• Den «beste» løsningen er bare best sammenlignet med andre løsninger, noe som fører til at stoppkriteriet ofte er uklart for noen problem.
• For spesifikke optimaliseringsoppgaver kan andre algoritmer være mer effektive enn genetiske algoritmer.

Bærekraften til genetiske algoritmer er avhengig av kunnskapen som er kjent om oppgaven; velkjente oppgaver har ofte bedre, mer spesialiserte tilnærminger.

Bruksområder

Genetiske algoritmer er passende til å løse oppgaver innenfor ingeniørvitenskap^[5], men er også bruk som en tilnærming for å løse globale optimaliseringsproblemer.

Eksempler på oppgaver løst av genetiske algoritmer inkluderer: speil som er designet til å samle sollys i en solfanger^[6], antenne designet for å plukke opp radiosignaler i verdensrommet^[7], og simulasjoner av bevegelsesmønster på tobente datafigurer.^[8]

Historie

I 1950 foreslo Alan Turing en lærende maskin som kunne replikere prinsipper for evolusjon^[9]. Datasimulering av evolusjon startet så tidlig som 1954 med arbeid gjort av Nils Aall Barricelli, som brukte computeren på instituttet for avansert studie på Princeton i New Jersey^[10][11]. I 1957 publiserte kvantegenetiker Alex Fraser en rekke saksutredelser om simulering av kunstig seleksjon av organismer med flere locus som styrte en målbar egenskap. Fra disse startpunktene ble data simulering av evolusjon mer vanlig hos biologer på tidlig 60-tallet, og beskrevet i bøker av Fraser og Burnell^[12][13]. Fraser sine simulasjoner inkluderte alle de essensielle områdene for moderne genetiske algoritmer. Videre publiserte også Hans-Joachim Bremermann en rekke artikler på 60-tallet som presenterte løsninger for optimaliseringsproblemer, rekombinering, mutasjon og seleksjon. Bremermann sin forsking inkluderte også elementer av moderne genetiske algoritmer^[14]. Andre pionerer inkluderer Richard Friedbergm Georg Friedman, og Micael Conrad. Mange av de tidlige artiklene er republisert av Fogel^[15]. Grunnet arbeidet til Ingo Rechenberg og Hans-Paul Schwefel på 60-tallet og tidlig 70 tall kunne Recenberg gruppen å løse komplekse ingeniørvitenskaps problemer ved bruk av evolusjonsstrategier^{[16][17][18][19]}. En annen tilnærming for evolusjonære programmeringsteknikker var foreslått av Lawrence J. Fogel, som formål å generere kunstig intelligens. Evolusjonær programmering brukte originalt endelig tilstandmaskin som brukte variasjon og seleksjon til å optimalisere predikat logikk. Genetiske algoritmer ble spesielt populært på grunn av arbeidet til John Holland tidlig på 70-tallet - spesielt boken hans "Adaptation in Natural and Artificial Systems" (1975). Holland introduserte et formalisert rammeverk for å forutsi kvaliteten på den neste generasjonen, kjent som Holland’s Schema Theorem. Forskning på genetiske algoritmer forble hovedsakelig teoretisk frem til midten av 80-tallet, da den første internasjonale konferansen på genetiske algoritmer ble hold i Pittsburgh, Pennsylvania, USA.

Akademisk interesse steg samtidig som databehandlingskraft steg, og tillot derfor praktisk applikasjon av teknikken. På slutten av 80-tallet lanserte General Electric verdens første produkt laget med genetisk algoritme - et stormaskin-basert verktøysett utviklet for industrielle prosesser. I 1989 lanserte Axcelis, Inc. Evolver, verdens første kommersielle genetisk algoritme produkt for stasjonære datamaskiner. Evolver ble solgt til Palisade i 1997, og er for øyeblikket i sin 6. versjon^[20].

Relaterte områder

Overområder

Genetiske algoritmer er en underklasse av blant annet:

• Evolusjonære algoritmer
• Evolusjonær databehandling
• Metaheuristikk
• Stokastisk optimalisering
• Optimalisering

Referanser

1. Mitchell (1996), s. 2.
2. ^ Whitley 1994 s.66
3. Eiben, A. E. et al 1994
4. Ting 2004
5. Tomoiagă 2013
6. Gross 2013
7. Homby, Linden, Lohn Automated Antenna Design with evolutionary algorithms
8. http://goatstream.com/research/papers/SA2013/index.html
9. Turing, A. M. Computing Machinery and Intelligence. s.433-460
10. Barricelli, N. A. Esempi Numerici di Processi di Evoluzione. 1954 s.45-68
11. Barricelli, N. A, Symbiogenetic Evolution Processes realized by Artificial Methods. 1957 s143-182
12. Fraser, A., Burnell, D. Computer Models in Genetics. 1970 ISBN=0-07-021904-4.
13. Crosby, J. L. Computer Simulation in Genetics. ISBN=0-471-18880-8.
14. UC Berkeley's Hans Bremermann, professor emeritus and pioneer in mathematical biology, has died at 69 - http://berkeley.edu/news/media/releases/96legacy/releases.96/14319.html. 1996
15. Fogel D. B. Evolutionary Computation: The Fossil Record. 1998 ISBN=0-7803-3481-7.
16. Rechenberg, Ingo (1973). Evolutionsstrategie. Stuttgart: Holzmann-Froboog. ISBN 3-7728-0373-3.
17. Schwefel, Hans-Paul (1974). Numerische Optimierung von Computer-Modellen (PhD thesis).
18. Schwefel, Hans-Paul (1977). Numerische Optimierung von Computor-Modellen mittels der Evolutionsstrategie : mit einer vergleichenden Einführung in die Hill-Climbing- und Zufallsstrategie. Basel; Stuttgart: Birkhäuser. ISBN 3-7643-0876-1.
19. Schwefel, Hans-Paul (1981). Numerical optimization of computer models (Translation of 1977 Numerische Optimierung von Computor-Modellen mittels der Evolutionsstrategie. Chichester ; New York: Wiley. ISBN 0-471-09988-0.
20. Evolver: Sophisticated Optimization for Spreadsheets. Palisade. Hentet den 07/11-14.