Genetisk algoritme
Innenfor informatikk feltet kunstig intelligens, er en ""genetisk algoritme"" en søkeheuristikk som etterligner den naturlige evolusjonsprosessen. Slik som arv, Mutasjon (genetisk algoritme), utvalg, og rekombinasjon. Denne heuristikken (også kjent som metaheuristikk) er ofte brukt for å generere løsninger for optimalisering/matematisk programmering og søkeproblemer [1]. Isteden for å søke generelle til spesifikke heuristikker, eller fra enkle til komplekse, så genererer genetiske algoritmer hypoteser ved å gjøre mutasjoner og rekombinere deler av de beste hypotesene som til en hver tid er kjent. Dette gjøres gjentatte ganger. Evolusjon er som kjent en suksessfull og robust metode for tilpasning i biologiske systemer.[2] Genetiske Algoritmer hører til området Evololusjonsalgoritmer som genererer løsninger for optimaliseringsproblemer ved bruk av teknikker som tar inspirasjon fra evolusjon, som f. eks. Arv, Mutasjon, Valg (Selection), og Crossover/rekombinasjon.
Genetiske Algoritmer er brukt innenfor: Bioinformatikk, Fylogenetikk, Informatikk, Ingeniørvitenskap, Økonomi, Kjemi, Industriteknikk, Matematikk, Fysikk, Pharmacometrics, og andre felt.
Metodologi
I en genetisk algoritme blir en populasjon av kandidat løsninger (ofte kalt individer, skapninger eller fenotyper) til et optimaliseringsproblem utviklet til bedre løsninger. Hver kandidat løsning 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 kodinger er mulige[3].
Utviklingen starter oftest fra tilfeldig genererte individer, og er en iterativ prosess, mens hver populasjon kalles en generasjon. I hver generasjon er alle individene i populasjonen sin fitness evaluert; fitness er oftest beregnet ut i fra hvor nært optimaliseringsproblemt er til å bli løst. De individene med høyest fitness verdi blir valgt, i tillegg til at genomet blir modifisert (rekombinert og potensielt tilfeldig mutert) og former deretter en ny generasjon. Den nye generasjonen blir deretter brukt i den nye neste iterasjonen av algoritmen. Algoritmen avsluttes/termineres oftest når enten et maksimum nummer av generasjoner har blitt produsert, eller en tilfredsstillende fitness verdi har blitt nådd for populasjonen.
En typisk Genetisk Algoritme krever:
- Genetisk representasjon av løsningsdomenet.
- Fitness funksjon som evaluerer løsningsdomenet.
En standard representasjon av hver kandidatløsning er en array (matrise) av bits.[4] Arrayer av andre datastrukturer kan oftest bli brukt på omtrent samme måte. Hovedegenskapen som gjør genetiske representasjoner praktisk er at dens deler er enkelt koblet opp mot hverandre grunnet dens satt størrelse, som tilrettelegger for enkle rekombineringsoperasjoner. Representasjoner med varierende lengde kan også bli brukt men gjør rekombinasjonsimplementasjon mer komplisert.
Etter at den genetiske representasjonen og fitness funksjonen er definert, initialiserer den genetiske algoritmen en populasjon av løsninger som den kan forbedre gjennom en iterativ prosess av mutasjon, rekombinasjon, inversion/invertering og selection/utvalg operatører.
Initialisering av genetiske algoritmer
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/search space). Det er derimot også mulig å Vekte bestemte områder hvor man kan forvente å finne optimale løsninger.
Selection/utvalg
Under hver etterfølgende generasjon, blir en andel 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 egnede løsninger (ut i fra en fitness funksjon) blir valgt. Bestemte utvalgs/selection metoder rangerer fitness verdiene til alle løsningene og velger ut de beste løsningene. Andre metoder kan ta et tilfeldig utvalg av populasjonen, da førstnevnte prosessen kan være veldig tidskrevende.
Fitness funksjonen måler kvaliteten av den representerte løsningen. Fitness funksjonen er alltid bestemt ut i fra problemet. I noen problemer er det svært vanskelig eller umulig å definer ett fitness utrykk; i disse situasjonene kan en simulering/simulation bli brukt for å avgjøre fitness funksjonsverdien av en fenotype, eller potensielt også en interaktiv genetisk algoritme.
Genetiske Operatører
For å generere den neste generasjonens populasjon med løsninger, blir de best egnede genene valgt gjennom en kombinasjon av operatørene: rekombinasjon, og mutasjon. For hver ny løsning som blir produsert, eksisterer et par foreldre løsninger som har blir valgt fra samlingen av løsninger i første generasjon. En ny løsning er skapt ved bruk av operatørene rekombinasjon og mutasjon, og deler typisk mange av karakteristikkene til sine foreldre. Nye foreldre blir valgt til hvert nytt barn, og prosessen fortsetter helt til populasjonen av løsninger som blir generert, når den satte størrelsen. Selv om reproduksjonsmetodene er mer biologi inspirert viser forskning at bruken av mer enn to foreldre genererer høyere kvalitet på kromosomene[5][6]. Tilslutt vil vi stå igjen med en populasjon av kromosomer som er forskjellig fra forrige generasjon. Denne nye generasjonen vil vanligvis ha en forbedret fitness verdi, da bare de beste organismene fra forrige generasjon blir valgt for avling, sammen med en liten andel med løsninger som har lavere fitness verdi. Disse la-fitness løsningene sørger for et større mangfold innenfor gensamlingen/genpool av foreldre og sørger derfor genetisk mangfold i de følgende generasjonene av barn. Selv om rekombinasjon og mutasjon er hoved operatørene for genetiske algoritmer er det også mulig å bruke andre operatører som regrouping, colonization-extinction, eller migration i genetiske algoritmer[7].
Det er anbefalt å tilpasse parametrene, som mutasjons og rekombinasjonssannsynlighet og populasjonsstørrelse for å finne logiske instillinger for det bestemte problemet som skal løses. En for liten mutasjonsrate kan føre til genetisk drift(som er av natur non-ergodic). Mens en rekombinasjonsrate som er for høy kan fort føre til tap av potensielt gode løsninger, hvis en ikke bruker elitism - praksis hvor man lar de beste organismene fra en populasjon krysse over til neste generasjon, uten endring.
Terminering/fullføring
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 (prosessortid / 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.
Eksempel kode
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 bestemte begrensninger på bruken av genetiske algoritmer sammenlignet med andre alternative optimaliserings algoritmer:
- Gjentatt fitness funksjonsevaluering for komplekse problemer er ofte det mest uoverkommelige og limiterende området av kunstig evolusjonære alogoritmer. Å finne optimale løsninger på komplekse flere-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 behandle slike problemer, og det er derfor nødvendig å bruke tilnærmet fitness som er databehandligseffektivt. 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økeområdet. Dette gjør det svært vanskelig å bruke teknikken på problemer som f. eks designet av en motor, et hus eller et fly.
For at slike problemer kan 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 vifte blader istedenfor motorer, design av formen på bygninger over 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 bedre løsningen er bare sammenlignet med andre løsninger, noe som fører til at kriterier for terminering/fullføring ofte ikke er veldig klart.
- 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[8], og er også bruk som en tilnærming for å løse globaleoptimaliseringsproblemer. En generell tommelregel er at genetiske algoritmer kan være hjelpsomme innenfor bruksområder som har et komplekst fitness landskap, fordi miksing, altså mutasjon i kombinasjon med rekombinasjon er designet for å flytte populasjon bort fra lokal optima som en tradisjonell hill climbing algoritme kan sette seg fast i. mutasjon alene kan tilby ergodisitet over den helhetlige genetisk algoritme prosessen (sett som en Markov kjede).
Eksempler på oppgaver løst av genetiske alogritmer inkluderer: speil designet til å samle sollys i en solcelle samler[9], antenne designet for å plukke opp radiosignaler i verdensrommet [10], og simulasjoner av bevegelsesmønster på tobente datafigurer[11].
I Skiena sin Algorithm Design Manual anbefaler han å ikke bruke genetiske algoritmer for noen oppgaver:
[I]t is quite unnatural to model applications in terms of genetic operators like mutation and crossover on bit strings. The pseudobiology adds another level of complexity between you and your problem. Second, genetic algorithms take a very long time on nontrivial problems. [...] [T]he analogy with evolution—where significant progress require millions of years—can be quite appropriate.
[...] I have never encountered any problem where genetic algorithms seemed to me the right way to attack it. Further, I have never seen any computational results reported using genetic algorithms that have favorably impressed me. Stick to simulated annealing for your heuristic search voodoo needs.
Steven Skiena[12]
Historie
I 1950 foreslo Alan Turing en lærende maskin som kunne replisere prinsipper for evolusjon[13]. Datasimulering av evolusjon startet så tidlig som 1954 med arbeid gjort av Nils Aall Barricelli, som brukte datamaskinen på instituttet for avansert studie på Princeton i New Jersey[14][15]. I 1957 publiserte kvantegenetiker Alex Fraser en rekke papirer på simulering av kunstig seleksjon av organismer med flere locust gresshopper med en sammenlignbar egenskap. Fra disse startpunktene ble data simulering av evolusjon mer vanlig hos biolger på tidlig 60-tallet, og beskrevet i bøker av Fraser og Burnell[16][17]. 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 optimaliserings problemer, rekombinering, mutasjon og selection. Bremermann sin forsking inkluderte også elementer av moderne genetiske algoritmer[18]. Andre pionerer inkluderer Richard Friedbergm Georg Friedman, og Micael Conrad. Mange av de tidlige artikklene er republisert av Fogel[19]. 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 [20] [21] [22] [23]. En annen tilnærming for evolusjonære programmerings teknikker var foreslått av Lawrence J. Fogel, som formål å generere kunstig intelligens. Evolusjonær programmering brukte originalt finite state machines som brukte variasjon og selection for å optimalisere predictive logics. 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 for 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 derfor tillatte praktisk applikasjon av teknikken. På slutten av 80-tallet lanserte General Electric verdens første genetiske algoritme produkt - et mainframe-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[24].
Relaterte Områder
Over områder
Genetiske algoritmer er et under felt av:
- Evolusjonære algoritmer
- Evolusjonær databehandling
- Metaheurestikk
- Stockastic optimalisering
- Optimalisering
Referanser
- ^ Mitchell 1996. s.2.
- ^ Mitchell,Tom.”Machine Learning”. McGraw-Hill Science/Engineering/Math, 1997.ISBN 9780070428072
- ^ Whitley 1994 s.66
- ^ Whitley 1994 s.66
- ^ Eiben, A. E. et al 1994
- ^ Ting 2004
- ^ Akibari 2010
- ^ Tomoiagă 2013
- ^ Gross 2013
- ^ Homby, Linden, Lohn Automated Antenna Design with evolutionary algorithms
- ^ http://goatstream.com/research/papers/SA2013/index.html
- ^ Skiena, S. The Algorithm Design Manual, 2010. ISBN=1-849-96720-2
- ^ Turing, A. M. Computing Machinery and Intelligence. s.433-460
- ^ Barricelli, N. A. Esempi Numerici di Processi di Evoluzione. 1954 s.45-68
- ^ Barricelli, N. A, Symbiogenetic Evolution Processes realized by Artificial Methods. 1957 s143-182
- ^ Fraser, A., Burnell, D. Computer Models in Genetics. 1970 ISBN=0-07-021904-4.
- ^ Crosby, J. L. Computer Simulation in Genetics. ISBN=0-471-18880-8.
- ^ 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
- ^ Fogel D. B. Evolutionary Computation: The Fossil Record. 1998 ISBN=0-7803-3481-7.
- ^ Rechenberg, Ingo (1973). Evolutionsstrategie. Stuttgart: Holzmann-Froboog. ISBN 3-7728-0373-3.
- ^ Schwefel, Hans-Paul (1974). Numerische Optimierung von Computer-Modellen (PhD thesis).
- ^ 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.
- ^ 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.
- ^ Evolver: Sophisticated Optimization for Spreadsheets. Palisade. Hentet den 07/11-14.