Genetisk algoritme

Hvad er det?

Den naturlige evolution kan modelleres som et spil, hvor belønningen for en organisme, der spiller et godt spil om livet, er, at dens genetiske materiale videregives til dens efterfølgere og at den fortsat overlever.^[2] I den naturlige evolution afhænger det af, hvem et individ klarer sig godt, hvem det arbejder sammen med, hvem det konkurrerer med, samt af miljøet. Genetiske algoritmer er en simulering af naturlig udvælgelse på en population af løsningsmuligheder til et optimeringsproblem (kromosomer, individer, væsener eller fænotyper).

Kandidaterne vurderes og krydses i et forsøg på at finde gode løsninger. Sådanne løsninger kan tage meget tid og er ikke indlysende for et menneske. En evolutionær fase startes med en population af tilfældigt genererede væsener. I hver generation vurderes fitnessen for hvert individ i populationen. Nogle af dem udvælges tilfældigt fra den aktuelle population (på grundlag af deres fitness) og ændres (rekombineres og muteres eventuelt tilfældigt) for at danne en ny population. Cyklussen gentages med denne nye population. Algoritmen slutter enten efter et bestemt antal generationer, eller når populationen har nået et godt fitnessniveau. Hvis algoritmen er afsluttet, fordi der er nået et maksimalt antal generationer, betyder det ikke nødvendigvis, at der er opnået et godt fitnessniveau.

Programmering af dette på en computer

Pseudokoden er:

1. Initialisering: Nogle mulige løsninger oprettes; meget ofte vil disse have tilfældige værdier.
2. Evaluering: En fitnessfunktion vurderer hver løsning; scoren vil være et tal, der fortæller, hvor godt løsningen løser problemet.
3. De følgende trin udføres, indtil kravet om at stoppe er opfyldt:
1. Udvælgelse: Udvælg løsninger/individer til den næste iteration
2. Rekombination: Kombiner de valgte løsninger
3. Mutation: Tilfældige ændringer i de nyoprettede løsninger
4. Evaluering: Anvend fitnessfunktionen, se trin 2.
5. Hvis kravet om at stoppe ikke er opfyldt, skal du starte forfra med udvælgelsestrinet.

Eksempel

Ovenstående beskrivelse er abstrakt. Et konkret eksempel hjælper.

Applikationer

Generelt

Genetiske algoritmer er gode til at løse problemer som f.eks. tidsplanlægning og skemalægning. De er også blevet anvendt inden for ingeniørvidenskab. De bruges ofte til at løse globale optimeringsproblemer.

Som en generel tommelfingerregel kan genetiske algoritmer være nyttige i problemdomæner med et komplekst fitnesslandskab, da blandingen er designet til at flytte populationen væk fra lokale optima, som en traditionel hill climbing-algoritme kan sidde fast i. Almindeligt anvendte crossover-operatører kan ikke ændre en ensartet population. Mutation alene kan sikre ergodicitet i den samlede genetiske algoritmeproces (set som en Markov-kæde).

Eksempler på problemer, der er løst ved hjælp af genetiske algoritmer, omfatter: spejle, der er designet til at lede sollyset til en solfanger, antenner, der er designet til at opfange radiosignaler i rummet, gåmetoder til computerfigurer, optimal udformning af aerodynamiske kroppe i komplekse strømningsfelter.

I sin Algorithm Design Manual fraråder Skiena genetiske algoritmer til enhver opgave: "Det er helt unaturligt at modellere applikationer i form af genetiske operatorer som mutation og crossover på bitstrenge. Pseudobiologien tilføjer endnu et niveau af kompleksitet mellem dig og dit problem. For det andet tager genetiske algoritmer meget lang tid på ikke-trivielle problemer. [...] Analogien med evolutionen - hvor betydelige fremskridt kræver [sic] millioner af år - kan være ganske passende. [...] Jeg er aldrig stødt på et problem, hvor genetiske algoritmer forekom mig at være den rigtige måde at angribe det på. Desuden har jeg aldrig set nogen beregningsresultater, der er rapporteret ved hjælp af genetiske algoritmer, som har gjort positivt indtryk på mig. Hold dig til simuleret udglødning for dine heuristiske søgevoodoo behov."

Brætspil

Brætspil er en meget relevant del af området genetiske algoritmer anvendt på spilteoretiske problemer. En stor del af det tidlige arbejde om computerintelligens og spil var rettet mod klassiske brætspil som f.eks. tic-tac-toe,^[3] skak og brikker.^[4] Brætspil kan nu i de fleste tilfælde spilles af en computer på et højere niveau end de bedste mennesker, selv med blinde udtømmende søgeteknikker. Go er en bemærkelsesværdig undtagelse fra denne tendens og har indtil nu modstået maskinelle angreb. De bedste Go-computerspillere spiller nu på samme niveau som en god nybegynder.^[5][6] Go-strategien siges at være stærkt afhængig af mønstergenkendelse og ikke kun af logisk analyse som i skak og andre mere brik-uafhængige spil. Den enorme effektive forgreningsfaktor, der er nødvendig for at finde løsninger af høj kvalitet, begrænser i høj grad det "look-ahead", der kan anvendes i en træksekvenssøgning.

Computerspil

Den genetiske algoritme kan bruges i computerspil til at skabe kunstig intelligens (computeren spiller mod dig). Dette giver mulighed for en mere realistisk spiloplevelse; hvis en menneskelig spiller kan finde en sekvens af trin, der altid fører til succes, selv når de gentages i forskellige spil, kan der ikke være nogen udfordring tilbage. Omvendt, hvis en læringsteknik som f.eks. en genetisk algoritme til en strateg kan undgå at gentage tidligere fejl, vil spillet have større spilbarhed.

Genetiske algoritmer kræver følgende dele:

• En metode til at repræsentere udfordringen i form af løsningen (f.eks. dirigering af soldater i et angreb i et strategispil)
• En egnetheds- eller evalueringsfunktion til bestemmelse af kvaliteten af en instans (f.eks. en måling af den skade, der er forvoldt en modstander i et sådant angreb).

Fitnessfunktionen accepterer en muteret instantiering af en enhed og måler dens kvalitet. Denne funktion tilpasses til problemdomænet. I mange tilfælde, især når der er tale om kodeoptimering, kan fitnessfunktionen blot være en systemtidsfunktion. Når en genetisk repræsentation og en fitnessfunktion er defineret, vil en genetisk algoritme instantiere indledende kandidater som beskrevet ovenfor og derefter forbedre dem ved gentagne anvendelser af mutation, crossover, inversion og udvælgelse (som defineret i overensstemmelse med problemdomænet).

Begrænsninger

Der er begrænsninger ved brugen af en genetisk algoritme i forhold til alternative optimeringsalgoritmer:

• Gentagen evaluering af fitnessfunktioner til komplekse problemer er ofte den mest begrænsende del af kunstige evolutionære algoritmer. At finde den optimale løsning på komplekse problemer kræver ofte meget dyre fitnessfunktionsvurderinger. I virkelige problemer som f.eks. strukturoptimeringsproblemer kan en enkelt funktionsevaluering kræve flere timer til flere dage af en komplet simulering. Typiske optimeringsmetoder kan ikke håndtere sådanne typer problemer. Det er ofte nødvendigt at anvende tilnærmelser, da det tager for lang tid at beregne den nøjagtige løsning. Genetiske algoritmer kombinerer undertiden forskellige tilnærmelsesmodeller for at løse komplekse virkelige problemer.
• Genetiske algoritmer er ikke gode til at skalere. Det vil sige, at når antallet af elementer, der er udsat for mutation, er stort, sker der ofte en eksponentiel stigning i størrelsen af søgeområdet. Dette gør det yderst vanskeligt at anvende teknikken på problemer som f.eks. design af en motor, et hus eller et fly. For at kunne anvende genetiske algoritmer til sådanne problemer skal de nedbrydes til den enkleste repræsentation, der er mulig. Derfor ser vi evolutionære algoritmer, der koder design af ventilatorblade i stedet for motorer, bygningsformer i stedet for detaljerede byggeplaner og flyprofiler i stedet for hele flydesigns. Det andet kompleksitetsproblem er spørgsmålet om, hvordan man beskytter dele, der har udviklet sig til at repræsentere gode løsninger, mod yderligere destruktiv mutation, især når deres fitnessvurdering kræver, at de skal kombineres godt med andre dele.
• Den "bedre" løsning er kun i forhold til andre løsninger. Som følge heraf er stopkriteriet ikke klart i alle problemer.
• I mange problemer har genetiske algoritmer en tendens til at konvergere mod lokale optima eller endog vilkårlige punkter snarere end mod problemets globale optimum. Det betyder, at algoritmen ikke "ved, hvordan" den skal ofre kortsigtet fitness for at opnå langsigtet fitness. Sandsynligheden for, at dette sker, afhænger af fitnessfunktionens form: visse problemer gør det let at finde det globale optimum, mens andre kan gøre det lettere for funktionen at finde de lokale optima. Dette problem kan mindskes ved at anvende en anden fitnessfunktion, ved at øge mutationsraten eller ved at anvende udvælgelsesteknikker, der opretholder en forskelligartet population af løsninger. En almindelig teknik til at bevare mangfoldigheden er at anvende en "nichestraf": enhver gruppe af individer med tilstrækkelig stor lighed (nicheradius) får tilføjet en straf, som reducerer repræsentationen af denne gruppe i de følgende generationer, så andre (mindre ens) individer kan blive bevaret i populationen. Dette trick er dog ikke nødvendigvis effektivt, afhængigt af problemets karakteristika. En anden mulig teknik ville være simpelthen at erstatte en del af populationen med tilfældigt genererede individer, når størstedelen af populationen ligner hinanden for meget. Mangfoldighed er vigtig i genetiske algoritmer (og genetisk programmering), fordi krydsning af en homogen population ikke giver nye løsninger. I udviklingsstrategier og evolutionær programmering er mangfoldighed ikke afgørende, fordi man i højere grad er afhængig af mutation.
• Det er vanskeligt at arbejde med dynamiske datasæt, da genomerne tidligt begynder at konvergere mod løsninger, som måske ikke længere er gyldige for senere data. Der er blevet foreslået flere metoder til at løse dette problem ved at øge den genetiske diversitet på en eller anden måde og forhindre tidlig konvergens, enten ved at øge sandsynligheden for mutation, når løsningens kvalitet falder (kaldet udløst hypermutation), eller ved lejlighedsvis at indføre helt nye, tilfældigt genererede elementer i genpuljen (kaldet tilfældige indvandrere). Igen kan evolutionsstrategier og evolutionær programmering gennemføres med en såkaldt "kommastrategi", hvor forældre ikke vedligeholdes, og nye forældre kun udvælges fra afkom. Dette kan være mere effektivt ved dynamiske problemer.
• Genetiske algoritmer kan ikke effektivt løse problemer, hvor det eneste mål for egnethed er et enkelt rigtigt/forkert mål (som f.eks. beslutningsproblemer), da der ikke er nogen måde at konvergere mod løsningen på (ingen bakke at bestige). I disse tilfælde kan en tilfældig søgning finde en løsning lige så hurtigt som en GA. Hvis situationen imidlertid gør det muligt at gentage et forsøg med succes/fiasko med (muligvis) forskellige resultater, er forholdet mellem succeser og fiaskoer et passende fitnessmål.
• For specifikke optimeringsproblemer og probleminstanser kan andre optimeringsalgoritmer være mere effektive end genetiske algoritmer med hensyn til konvergenshastighed. Alternative og supplerende algoritmer omfatter udviklingsstrategier, evolutionær programmering, simuleret udglødning, Gaussisk tilpasning, hill climbing og sværmintelligens (f.eks. myrekolonioptimering, partikel-sværmoptimering) og metoder baseret på heltals-lineær programmering. Hvor velegnede genetiske algoritmer er, afhænger af mængden af viden om problemet; velkendte problemer har ofte bedre, mere specialiserede metoder.

Historie

I 1950 foreslog Alan Turing en "indlæringsmaskine", som skulle være parallel til evolutionens principper. Computersimulering af evolutionen begyndte allerede i 1954 med Nils Aall Barricellis arbejde, som brugte computeren på Institute for Advanced Study i Princeton, New Jersey. Hans publikation fra 1954 blev ikke bredt bemærket. Fra 1957 offentliggjorde den australske kvantitative genetiker Alex Fraser en række artikler om simulering af kunstig udvælgelse af organismer med flere loci, der kontrollerer en målbar egenskab. Fra denne begyndelse blev computersimulering af evolution blandt biologer mere almindelig i begyndelsen af 1960'erne, og metoderne blev beskrevet i bøger af Fraser og Burnell (1970) og Crosby (1973). Frasers simuleringer omfattede alle de væsentlige elementer i moderne genetiske algoritmer. Desuden udgav Hans-Joachim Bremermann en række artikler i 1960'erne, som også antog en population af løsninger på optimeringsproblemer, der gennemgik rekombination, mutation og selektion. Bremermanns forskning omfattede også elementerne i de moderne genetiske algoritmer. Andre bemærkelsesværdige tidlige pionerer omfatter Richard Friedberg, George Friedman og Michael Conrad. Mange af de tidlige artikler er genoptrykt af Fogel (1998).

Selv om Barricelli i sit arbejde fra 1963 havde simuleret udviklingen af evnen til at spille et simpelt spil, blev kunstig evolution en bredt anerkendt optimeringsmetode som følge af Ingo Rechenbergs og Hans-Paul Schwefel's arbejde i 1960'erne og begyndelsen af 1970'erne - Rechenbergs gruppe var i stand til at løse komplekse tekniske problemer ved hjælp af evolutionære strategier. En anden tilgang var Lawrence J. Fogels evolutionære programmeringsteknik, som blev foreslået til at generere kunstig intelligens. Evolutionær programmering anvendte oprindeligt finite state machines til at forudsige miljøer og brugte variation og udvælgelse til at optimere de forudsigelige logikker. Genetiske algoritmer blev især populære gennem John Hollands arbejde i begyndelsen af 1970'erne og især hans bog Adaptation in Natural and Artificial Systems (1975). Hans arbejde havde sin oprindelse i studier af celleautomater, som Holland og hans studerende gennemførte på University of Michigan. Holland introducerede en formaliseret ramme for forudsigelse af kvaliteten af den næste generation, kendt som Hollands skemateorem. Forskningen i GA'er forblev overvejende teoretisk indtil midten af 1980'erne, hvor den første internationale konference om genetiske algoritmer blev afholdt i Pittsburgh, Pennsylvania.