Genetisk algoritme

Fra Wikipedia, den frie encyklopedi
Gå til: navigasjon, søk

En genetisk algoritme (GA) er en søkeheuristikk som etterligner prosessen ved naturlig evolusjon. Genetiske algoritmer tilhører den større klassen evolusjonære algoritmer (EA), som genererer løsninger på optimaliseringsproblemer ved hjelp av teknikker inspirert av naturlige evolusjon, slik som arv, mutasjon, utvalg, og rekombinasjon. Istedenfor å søke generelle til spesifikke heuristikker, eller fra enkle til komplekse, så genererer GA hypoteser ved å gjøre mutasjoner og rekobinere deler av de beste hypotesene som til enhver tid er kjent. Dette gjøres gjentatte ganger. Evolusjon er som kjent som en suksessfull og robust metode for tilpasning i biologiske systemer.[1]

Gjennomgang[rediger | rediger kilde]

Genetiske algoritmer begynner med et sett av k tilfeldig genererte tilstander kalt populasjon. Hver tilstand, eller individ, er representert som en tekststreng – mest vanlig er bruk av 0 og 1, men andre løsninger er også mulig. Evolusjonen starter med populasjonen og skjer i generasjoner. For hver generasjon blir hvert individ vurdert basert på en fitnessfunksjon. Fitnessfunksjonen bestemmer hvor bra eller nært et individ er i forhold til et mål. Hva målet er varierer fra problem til problem. Individer blir valgt fra populasjonen (basert på deres fitness) og modifisert for å lage en ny populasjon. Den nye populasjonen blir så brukt i neste iterasjon av algoritmen. Vanligvis avslutter algoritmen enten når den har nådd et gitt antall generasjoner har blitt produsert, eller en tilfredsstillende fitnessnivå har blitt oppnådd for populasjonen. Hvis algoritmen har avsluttet på grunn av et maksimum antall generasjoner, er det ikke sikkert at en tilfredsstillende løsning har blitt oppnådd.

Initialisering[rediger | rediger kilde]

I starten blir mange mulige individer generert for å danne en populasjon. Ofte nyttes en algoritme som lager helt tilfeldige individer. Størrelsen på populasjonen avhenger problemet, men typisk er det flere hundre eller tusenvis av mulige løsninger.

Utvalg[rediger | rediger kilde]

I hver etterfølgende generasjon blir en del av populasjonen valgt til å formere seg og danne en ny generasjon. Individene blir valgt gjennom en fitnessbasert prosess hvor gode løsninger (basert på fitnessfunksjonen) har størst sjanse for å bli valgt.

Reproduksjon[rediger | rediger kilde]

Det neste skrittet for å generere en ny generasjon av de utvalgte gjennom genetiske operasjoner: rekombinasjon ("crossover") og/eller mutasjon. For hver nye løsning som blir produsert, et sett av "foreldre"-individ er valgt for paring fra utvalget tidligere valgt. Ved å produsere et "barn" ved bruk av metodene rekombinasjon og mutasjon, vil den nye løsningen dele mange av de samme karakteristikkene som dens "foreldre". Nye foreldre er valgt for hvert barn og prosessen fortsetter helt til en ny populasjon med passende størrelse er generert. Selv om reproduksjonsmetodene som bruker to foreldre er mer biologisk inspirert, foreslår noen forskere[2][3] at mer enn to foreldre er bedre til å produsere avkom av god kvalitet.


Avslutning[rediger | rediger kilde]

Generering av nye generasjoner er gjentatt helt til et avslutningskriterium har blitt nådd. Vanlige avslutningskriterier er:

  • En løsning er funnet som tilfredsstiller et minimumskriterium.
  • Gitt antall generasjoner nådd.
  • Det gitte budsjettet (prosessortid / penger) er nådd).
  • Det individet med høyest rangering kommer til eller har har kommet til et platå slik at påfølgende iterasjoner ikke produserer bedre resultat.
  • Manuell inspeksjon.
  • Kombinasjon av de over.

Enkel genetisk algoritme pseudokode

  1. Velg den første populasjonen av individer.
  2. Evaluer fitness for hvert individ i den populasjonen.
  3. Gjenta på denne generasjonen til en er ferdig:
    1. Velg de beste individene til reproduksjon.
    2. Par nye individer ved hjelp av rekombinasjon og mutasjon for å lage nytt avkom.
    3. Evaluer den individuelle fitness til de nye individene.
    4. Erstatt de dårligste med nye individer.

Referanser[rediger | rediger kilde]

  1. ^ Mithcell, Tom. "Machine learning". McGraw-Hill Science/Engineering/Math, 1997. ISBN 9780070428072
  2. ^ Eiben, A. E. et al (1994). "Genetic algorithms with multi-parent recombination". PPSN III: Proceedings of the International Conference on Evolutionary Computation. The Third Conference on Parallel Problem Solving from Nature: 78–87. ISBN 3-540-58484-6.
  3. ^ Ting, Chuan-Kang (2005). "On the Mean Convergence Time of Multi-parent Genetic Algorithms Without Selection". Advances in Artificial Life: 403–412. ISBN 978-3-540-28848-0.