Genetisk algoritme

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). Det er derimot også mulig å vekte bestemte områder hvor man kan forvente å finne optimale løsninger.

Seleksjon

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-uttrykk; 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

For å generere den neste generasjonens populasjon av individ, blir de best egnede genene valgt gjennom en kombinasjon av operatorene: rekombinasjon, ogmutasjon.
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.
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.

Enkel genetisk algoritme pseudokode

initialize population p with random genesRepeat
  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’

Bruksområder

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

Historie

I 1950 foreslo Alan Turing en lærende maskin som kunne replisere prinsipper for evolusjon. 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.
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. 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. Andre pionerer inkluderer Richard Friedbergm Georg Friedman, og Micael Conrad. Mange av de tidlige artikklene er republisert av Fogel.
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 .
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.