Genetisk algoritme

Fra Wikipedia, den frie encyklopedi
Gå til: navigasjon, søk
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]

Noen felt genetiske algoritmer blir brukt innenfor er: bioinformatikk, fylogenetikk, informatikk, ingeniørvitenskap, økonomi, kjemi, industriteknikk, matematikk og fysikk.

Metodologi[rediger | rediger kilde]

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 (dens kromosomer, gener eller genotype) som kan muteres og endres; tradisjonelt sett er løsninger oftest representert i binær som en streng av 0er og 1ere, 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; fitness-funksjonen har som oppgave å beregne kvaliteten til hvert enkelt individ, og som helhet hvor nært optimaliseringsproblemet er til å bli løst. De individene med høyest fitness verdi blir krysset med hverandre og blir utsatt for en muteringsprosess som tilfeldig endrer deler av genomet. Hvor ofte mutasjon skal forekomme er bestemt av en muterings-rate 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 nummer av generasjoner, eller når en tilfredsstillende fitness verdi for populasjonen er nådd.

En typisk Genetisk Algoritme krever:

  1. Genetisk fremstillelse av løsningsdomenet.
  2. Fitness funksjon som evaluerer løsningsdomenet.

En standard representasjon av hvert individ en matrise av bits.[3] 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 utbyttbare enkeltdelene som individet er satt sammen av. Representasjoner med varierende lengde kan også bli brukt men gjør kryssningsimplementasjon 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[rediger | rediger kilde]

Genetiske algoritmer starter oftest ved at løsninger tilfeldig 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 derimot også mulig å vekte bestemte områder hvor man kan forvente å finne optimale løsninger.

Seleksjon[rediger | rediger kilde]

Under 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 i best egnet (bestemt fra en fitness-funksjon) blir valgt. Bestemte utvelgelsesmetoder rangerer fitness verdiene 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-utrykk; 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[rediger | rediger kilde]

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 "barn", 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 på at bruken av mer enn to foreldre genererer høyere kvalitet på individene[4][5]. Til slutt vil vi stå igjen med 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 fitness verdi. 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 mutasjonssannsynilighet, 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. Mens en rekombinasjonsrate som er for høy kan føre til at den genetiske algoritmen når konvergens for tidlig. Og en høy mutasjonsrate kan føre til tap av potensielt gode løsninger, med mindre man bruke elitisme - en praksis hvor man lar de beste individene fra forrige generasjon krysse over til neste generasjon.

Termineringskriterier[rediger | rediger kilde]

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.
  • Det individet med høyest rangering kommet til et platå slik at påfølgende iterasjoner ikke produserer bedre resultat.
  • Manuell inspeksjon.
  • Kombinasjon av de over.

Eksempelkode[rediger | rediger kilde]

Enkel genetisk algoritme pseudokode[rediger | rediger kilde]

 
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[rediger | rediger kilde]

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[rediger | rediger kilde]

Genetiske algoritmer er passende til å løse oppgaver innenfor ingeniørvitenskap[6], 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[7], antenne designet for å plukke opp radiosignaler i verdensrommet [8], og simulasjoner av bevegelsesmønster på tobente datafigurer.[9]

Historie[rediger | rediger kilde]

I 1950 foreslo Alan Turing en lærende maskin som kunne replisere prinsipper for evolusjon[10]. 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[11][12]. 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[13][14]. 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[15]. Andre pionerer inkluderer Richard Friedbergm Georg Friedman, og Micael Conrad. Mange av de tidlige artikklene er republisert av Fogel[16]. 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 [17] [18] [19] [20]. 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[21].

Relaterte områder[rediger | rediger kilde]

Overområder[rediger | rediger kilde]

Genetiske algoritmer er en underklasse av blant annet:

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

Referanser[rediger | rediger kilde]

  1. ^ Mitchell (1996), s. 2.
  2. ^ Whitley 1994 s.66
  3. ^ Whitley 1994 s.66
  4. ^ Eiben, A. E. et al 1994
  5. ^ Ting 2004
  6. ^ Tomoiagă 2013
  7. ^ Gross 2013
  8. ^ Homby, Linden, Lohn Automated Antenna Design with evolutionary algorithms
  9. ^ http://goatstream.com/research/papers/SA2013/index.html
  10. ^ Turing, A. M. Computing Machinery and Intelligence. s.433-460
  11. ^ Barricelli, N. A. Esempi Numerici di Processi di Evoluzione. 1954 s.45-68
  12. ^ Barricelli, N. A, Symbiogenetic Evolution Processes realized by Artificial Methods. 1957 s143-182
  13. ^ Fraser, A., Burnell, D. Computer Models in Genetics. 1970 ISBN=0-07-021904-4.
  14. ^ Crosby, J. L. Computer Simulation in Genetics. ISBN=0-471-18880-8.
  15. ^ 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
  16. ^ Fogel D. B. Evolutionary Computation: The Fossil Record. 1998 ISBN=0-7803-3481-7.
  17. ^ Rechenberg, Ingo (1973). Evolutionsstrategie. Stuttgart: Holzmann-Froboog. ISBN 3-7728-0373-3.
  18. ^ Schwefel, Hans-Paul (1974). Numerische Optimierung von Computer-Modellen (PhD thesis).
  19. ^ 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.
  20. ^ 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.
  21. ^ Evolver: Sophisticated Optimization for Spreadsheets. Palisade. Hentet den 07/11-14.