Genetisk algoritme

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. I stedenfor å 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

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 tilfredstillende fitness nivå har blitt oppnådd for populasjonen. Hvis algoritmen har avsluttet på grunn av et maksimum antall generasjoner, er det ikke sikkert at en tilfredstillende løsning har blitt oppnådd.

Initialisering

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

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

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

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

En løsning er funnet som tilfredstiller et minumumskriterie.
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

Velg den første populasjonen av individer.
Evaluer fitness for hvert individ i den populasjonen.
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 inviduelle fitness til de nye individene.
4. Erstatt de dårligste med nye individer.

Referanser

^ Mithcell, Tom. "Machine learning". McGraw-Hill Science/Engineering/Math, 1997. ISBN 9780070428072
^ 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.
^ 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.

[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.

[1]

[2]

[3]