Carsten Svaneborg
Natural selection saw to it that professional heroes who at a crucial moment tended to ask themselves questions like ``What is my purpose in life?'' very quickly lacked both.(Terry Pratchett; Interesting Times)
Genetiske algoritmer blev først opfundet af naturen, sidenhen af Darwin, og tilsidst John Holland i '75. John Holland fik ideen at implementere ``Survival of the fittest'' på en computer, og på den måde ``blev'' genetiske algoritmer (GA) til, der i dag er en paraplybetegnelse for de mange forskellige algoritmer, der er biologisk inspirerede.
Notationen fra ``Global Optimering 1'' [FAMøS, maj 1996 -
red.] transmogrifferes nu til en biologisk notation, n
tidsskridtet hedder nu generationen, tilstandsvektoren 
omfortolkes til et genom (=kromosom), en samling af genomer kaldes
en population, 
kaldes nu for ``fitness'',
fortegnskiftet skyldes, at i fysik er lave energier interessante
(grundtilstanden), men i biologi er høj tilpasningsgrad interessant.
Tilstandsvektoren er blevet til et genom, der er en (genotype-)repræsentation af tilstandsvektoren, som oftest en bitstreng, genomet har ikke nogen iboende mening eller realitet, men det er den information, der kan fortolkes eller afbildes til en phenotype, hvis fitness kan evalueres. Udtrykt biologisk: Hvis man har et dyrs DNA (genotype), kan man ikke fortælle om dyret er godt eller dårligt tilpasset, det kan man først når man har selve dyret (phenotypen), dvs. at DNA'et et blevet afbildet til dyret. På samme måde er et computerprogram genotypen, og bits i programmet har ikke nogen betydning, før programmet køres, og det, som brugeren ser, er phenotypen af programmet.
I ``travelling salesman problemet'' (TSP) er phenotypen den rute, som den
handelsrejsende følger, og genotypen er en streng af bits, der kan
repræsentere ruten. Hvis der er N byer, skal der mindst en
lang bitstreng til, for at repræsentere en
rute, men sådan en (minimal) repræsentation er ikke robust nok til at
anvendes i praksis, idet en vilkårlig bitstreng skal kunne tolkes som
en rute, og med det minimale antal bits, er der ikke nogen garanti for,
at en by ikke kommer flere gange i ruten, eller slet ikke er på ruten.
En meget mere robust repræsentation kan findes ved at byer, man allerede har besøgt, ignoreres og for det andet ved at gøre bitstrengen meget længere end nødvendigt og tage evt. manglende byer til sidst i tilfældig rækkefølge. Det er altså den algoritme med hvilke vi kan fortolke en vilkårlig bitstreng som en rigtig TSP rute.
Idéen ved en genetisk algoritme er nu at dele populationen op i phenotyper med god og dårligt fitness, de dårlige tilpassede genomer slettes, og fra gruppen med god fitness dannes nye genomer ved at blande eller mutere gode genomer (biologisk: et afkom af godt tilpasset forældre), derved holdes størrelsen af populationen konstant, og idet phenotyperne konkurrerer om at forblive i gruppen med god fitness, vil populationen som et hele drives mod optimal fitness.
Krydsning af genomer og mutation repræsenteres ved at definere et sæt af genetiske operatorer, der på passende vis ``rører rundt i suppen'', hver operator har en sandsynlighed for at blive valgt, og som input får den tilfældige valgte genomer, der er i fitnessgruppen, og som output leverer de genetiske operatorer nye genomer til populationen.
Mutationen kan ske ved at flippe en eller flere bits et sted i strengen med en passende sandsynlighedsfordeling. Krydsning kan ske ved at udvælge to stamfædre, og vælge et brudpunkt ved en tilfældigt bit j, og lade bits 1 til j i det nye genom stamme fra den ene stamfader og j+1 til N fra en anden stamfader.
Man kan også introducere mere eksotiske operatorer, fx inversion, der gør, at dele af genomet, der vekselvirker stærkt (coevolverer), bliver flyttet tættere på hinanden, så sandsynligheden for, at de bliver delt ved krydsning mindskes. Dette gøres, ved at man nummererer alle bits i strengen, så strengen består af par af (bit nummer,bit værdi), inversions operatoren kan så flytte rundt på disse par uden at ændre fortolkningen af strengen, og krydsning vil så operere på par som før. Eller man kunne bruge en meta-operator, ved at beskrive de genetiske operatorer som bitstrenge, og evolvere dem parallelt med populationen, og bruge konvergenshastigheden af algoritmen, som fitness mål for de genetiske operatorer.
En Genetisk Algoritme går som følger:
| 1: | n=0; Initialiser en population med N genomer bestående af tilfældige bits. |
| 2: | n=n+1; Næste Generation |
| 3: | Afbild genotyper til phenotyper, og evaluer deres fitness. |
| 4: | Udvælg M gode stamfædre fra populationen. |
| 5: | Slet de (N-M) resterende genomer. |
| 6: | Dan (N-M) nye genomer ved at operere med genetiske operatorer på de udvalgte stamfædre. |
| 7: | if not bored goto 2 |
Når M genomer skal udvælges, kan det i'te genom udvælges med
sandsynlighed 
, hvor 
er
phenotypes fitness for det i'te genom, og 
er
populationens fitness gennemsnit.
De genetiske operatorer er grunden til at afbildningen fra genotype til phenotype skal være defineret for en vilkårlig bitstreng, og grunden til genomets redundans, idet de genetiske operatorer ikke behøver at være skræddersyet, så resultatet opfylder en arbitrært valgt repræsentation, det giver en stor frihed i, hvad man kan gøre med en genetisk operator, og det flytter alle programmeringsproblemerne fra operatorerne til fortolkningen af genomer.
Et biologisk eksempel på redundansen er
cystisk fibrose-genet
,
der indeholder 250000 base par, men hvor kun 4440 ( 
) koder for
proteiner! Resten bliver filtreret bort, når DNA transkribres til
protein, og en redundansfaktor på 2% er ganske normal i eukaryote
celler.
GA kan bruges til meget forskelligt; hvis genomet fx er et computersprog, og fortolkningen er en fortolker af ``genom''-programmer (fx LISP-programmer), hvis output kan evalueres som fitness, kan man altså ``dyrke'' programmer (genetisk programmering). GA bruges også som udgangspunkt for kunstig liv, hvor man udvikler systemer af vekselvirkende populationer (fx planter/dyr/parasitter), der kan udvise evolverende handlingsmønstre (emergens), eller kan organisere sig i rummelige formationer (fx en model af et hvepsebo eller en myretue).
Ved at anvende GA på neurale net, kan man både undgå lokale minima samt optimere nettets struktur, og man kan også studere vekselvirkningen mellem evolution og indlæring, der virker på vidt forskellige tidsskalaer, men begge påvirker tilpassetheden af individer. Populært sagt er det et spørgsmål, om software- eller hardware-baseret viden er bedst (Baldwin effekt). Genetiske algoritmer med en specielt defineret krydsningsoperator, kan bruges ved fraktal billedkomprimering, genomet vil da bestå af et antal affine transformationer på blokke af pixels, og for hver par af transformationer i forældreparret vælger krydsningsoperatoren den bedste til afkommet.
Både genetiske algoritmer og simuleret udglødning er af typen guided random search, beregnet på at finde de globale minima af en ikke-differentiabel funktion, der afhænger af mange kontinuerte og/eller diskrete parametre, og de antager begge, at funktionen kun er kendt i punkter, så der ikke eksisterer nogle afledte.
I genetiske algoritmer spiller de genetiske operatorer den samme rolle som naboklassen, der foreslår nye og forhåbentlig bedre løsninger, og udvælgelsen er for simuleret udglødning givet ved fysiske årsager, så man opnår, at energitilstandene er Boltzmann fordelt. Analogt for genetiske algoritmer er der også en vis sandsynlighed for at et dårligt genom bliver udvalgt til reproduktion, hvorved begge algoritmer fokusere på minima, men samtidigt har en sandsynlighed for at forlade lokale minima.
En optimal simuleret udglødning er givet ved den ``udglødningsvej'' T(t), der minimere produktionen af entropi. Et optimalt valg af sandsynlighedsparametre i en genetisk algoritme med mutation og krydsning, er givet ved, at man undgår at krydsning driver population mod for stor korrelation mellem genomerne (i grænsen en population af identiske genomer), idet krydsning i så fald bliver meningsløst, og mutationssandsynligheden skal være så lille, at man undgår, at alle genomer bliver fuldstændigt tilfældige, i hvilket tilfælde GA degenererer til en tilfældig søgning. Et interessant spørgsmål er om disse to påstande om optimalitet er rigtige, og om de måske er identiske?.
Ved at udvælge genomer med en sandsynlighed 
, kan man lave en hybrid
simuleret udglødning GA, hvor temperaturen T virker som i simuleret
udglødning. Idéen er, at ved meget høj temperatur er sandsynligheden for
at blive valgt konstant for alle genomer, men som temperaturen sænkes,
bliver udvælgelsen mere fitness orienteret. Denne definition har også
nogle behagelige transformations egenskaber, idet P er invariant under
affine transformationer af E (hvis T også transformeres på pasende
vis).