Redigerer Genetisk algoritme (avsnitt)

== Metodologi ==
I en genetisk algoritme blir et sett (populasjon) av potensielle løsninger til et optimaliseringsproblem utviklet til bedre løsninger. Hver kandidat i populasjonen har et sett av verdier (sine kromosomer, gener eller genotype) som kan muteres og endres; tradisjonelt sett er løsninger oftest representert [[binær]]t, men andre kodingsformer er også mulige.<ref name="Whitley 1994 s.66">Whitley 1994 s.66</ref>
 
Utviklingen starter oftest fra tilfeldig genererte individer, og er en iterativ prosess, der hver populasjon kalles en generasjon. I hver generasjon blir alle individene i populasjonen evaluert av en [[fitness|fitness-funksjon]] som har til oppgave å beregne kvaliteten til hvert enkelt individ, og som helhet hvor nært optimaliseringsproblemet er til å bli løst. Individene med høyest fitness-verdi blir krysset med hverandre og utsatt for en mutasjonsprosess som tilfeldig endrer deler av genomet. Hvor ofte mutasjon skal forekomme blir bestemt av en mutasjonsrate To individer med høy fitness krysses og danner to nye individer som blir med på å forme en ny generasjon. Den nye generasjonen blir deretter brukt i den neste iterasjonen av algoritmen. Algoritmen avsluttes som regel enten etter et bestemt antall generasjoner, eller når en tilfredsstillende fitnessverdi for populasjonen er oppnådd.

En typisk genetisk algoritme krever
# Genetisk fremstilling av løsningsdomenet.
# Fitnessfunksjon som evaluerer løsningsdomenet.
 
En standard representasjon av hvert individ utgjøres av matrise av [[bit]]s.<ref name="Whitley 1994 s.66"/> Matriser av andre datastrukturer kan også bli brukt på en lignende måte. En av hovedegenskapene til genetiske algoritmer som gjør dem praktiske er at individer lett kan krysses med hverandre på grunn av den fastsatte størrelsen og de utskiftbare enkeltdelene  individet er satt sammen av. Representasjoner med varierende lengde kan også bli brukt, men gjør krysningsimplementasjon mer komplisert.
 
Etter at den genetiske fremstillingen og [[fitness]]-funksjonen er definert initialiserer den genetiske algoritmen en populasjon som den kan forbedre gjennom en iterativ prosess av [[Mutasjon (genetisk algoritme)|mutasjon]], rekombinasjon, inversjon og seleksjonsoperatorer.

=== Initialisering av genetiske algoritmer ===
Genetiske algoritmer starter oftest ved at tilfeldige løsninger 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 imidlertid også mulig å vekte bestemte områder hvor man kan forvente å finne optimale løsninger.

=== Seleksjon ===
I løpet av hver generasjon blir en del av den eksisterende populasjonen valgt for å avle en ny generasjon. Individuelle løsninger blir valgt gjennom en [[fitness|fitness-prosess]], hvor løsningene som er best egnet (bestemt fra en fitness-funksjon) blir valgt. Bestemte utvalgssmetoder rangerer fitnessverdiene 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 (genetisk algoritme)|rekombinasjon]] og [[Mutasjon (genetisk algoritme)|mutasjon]].

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 «avkom», 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 at bruken av mer enn to foreldre genererer høyere kvalitet på individene-<ref>Eiben, A. E. et al 1994</ref><ref>Ting 2004</ref>

Til slutt gjenstår 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 fitnessverdi. 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  mutasjonssannsynlighet, 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]]. En rekombinasjonsrate som er for høy kan føre til at den genetiske algoritmen når konvergens for tidlig. En høy mutasjonsrate kan føre til tap av potensielt gode løsninger, med mindre man bruke elitisme, en prosess hvor man lar de beste individene fra forrige generasjon krysse over til neste generasjon.

=== Termineringskriterier ===
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 (i prosessortid eller penger) er nådd.
* Individet med høyest rangering kommet til et platå, slik at påfølgende iterasjoner ikke produserer bedre resultat.
* Manuell inspeksjon.
* Kombinasjon av ovenstående resultater.