Genetiske Algoritmer

Slik eit Nevralt Nett er ein enkel modell av eit biologisk nervesystem, så er ein Genetisk Algoritme (GA) er ein veldig forenkla modell for korleis evolusjonen virkar. Den har ein del av dei viktigaste kjennetegna, men på andre områder er modellen, som vi skal sjå, fjernt frå verkeligheten. For å forstå den Genetiske Algoritmen låner vi ein del basisbegrep frå biologien.

KROMOSOMET:

I verkelighetens verden inneheld krosomomene det arvestoffet som bestemmer korleis vi ser ut. (Her ser bort frå at miljøet har betydning, og om at det kan finnast arvestoff andre stader enn i kromosomet) Cella har ein måte å "pakka ut" den informasjonen som ligg i kromosoma og konstruera ein kropp. Kromosoma er altså ein datasekvens som på ein måte representerer ein kropp.

I ei modellverd kan vi ikkje byggja ein kropp. Dei dataene som ligg i kromosomet (vi forenklar og lar all informasjonen ligga i eit kromosom) kan egentlig representera kva vi vil. Det kan for eksempel vera forslag til løysinga på et problem, eller forslag til strukturen på et nevralt nett. Ordet "forslag" er viktig. Alle kromsom er forslag på den måten at vi anar ikkje om det virkar før vi har dekoda informasjonen og prøvd den ut i praksis.

Kromosomane til eit dyr kan vera "bra" eller "dårlige" i ein evolusjonær forstand. (Dette har ingenting med verdiar å gjera) Ein antilope som på grunn av "dårlige" gener blir treg, vil sannsynligvis bli et lett bytte for ein gepard eller eit anna rovdyr, og vil derfor ikkje kunna få barn. I ein evolusjonær forstand har genene lav verdi. I GA-språket seier vi at kromosomet har lav "fitness". Kromosomets fitness er altså eit mål for kor godt forslaget er.

EIT VELDIG ENKELT EKSEMPEL

La oss sei at vi har ein sekvens (eller streng) med 5 tall som skal vera forslag til problemet å finna kvadratroten av 2. For å testa forslaget er det bare å bestemma at det skal vera komma mellom første og andre siffer (det er dekodinga), og testa kor godt det stemmer. Anta at vi har et tilfeldig kromosom som er slik: 01382. For å testa dette er det bare å multiplisera det med seg sjølv: 0.1382*0.1382 = 0.019 Men det er jo eit stykke frå 2 som vi helst vil ha. Avstanden til 2 er 1.98 og den fortel oss kor godt godt forslaget er. Men vi vil gjerne ha eit tal som er positivt og som er større jo nærmare rett svar vi kjem. La oss derfor bare bestemma at f = 10 minus avstanden og kalla dette for fitness. I dette filfelle får vi f = 8.02.

Men vi vil jo nærmare. Vi kan då først prøva med andre tilfeldige kromosom. Somme av dei vil treffa betre og somme vil treffa dårligare. Sannsynligvis er vi ikkje fornøyd med nokon av dei. Korleis skal vi komma endå nærmare? Det er her biologien kjem oss til hjelp. For det fins måtar å kombinera to krosomom på og få eit (to) nye. Det heiter kryssing, og virkar slik at du spleiser saman starten på et kromsom og slutten på et anna. (Så kan du jo godt ta slutten på det første og starten på det andre og få endå ett om du vil)

KRYSNING:

Her er to "foreldre"kromosomer. Så bestemmer tilfeldighetene at vi skal kryssa dei mellom gene nr. 5 og 6. Då får vi altså eit avkom som er sett saman av dei fem første frå det blå kromosomet og dei tre siste frå det gule. Vi får altså eit barn som består av genene til "far" og "mor", men kombinert på ein ny måte, og som kan vera ganske langt frå begge to.

MUTASJON:

Men det fins ein annan måte å få nye kromosom på. Det er ein mutasjon. For vårt vedkommande kan vi då gå inn på eit tilfeldig gen (dvs. eit av tala i kromosomet) og endra det tilfeldig. Dette kallast mutasjon. Her tar vi utgansgpunkt i det gule kromosomet øverst og endrar på plass nr, fire. No får vi eit barn som er ein variant av eit foreldrekromosom, men som er veldig likt.

No har vi dei to måtane som ein GA produserer nye avkom. Men skal vi la alle kromosomene i poolen få avkom? Nei, vi lar bare et antal av dei beste gjera det, altså dei med høgast fitness. Dette kallast seleksjon. På denne måten får vi altså ein ny generasjon som også må evaluerast.

Og sannsynligvis vil eit eller fleire av dei nye kromosoma vera betre enn det beste av dei vi hadde frå før. Eller i det minste vil gjennomsnittet bli betre enn i forrige generasjon. Hvis resultatet er riktig bra, og vi er fornøyd så kan vi slutta. Hvis ikkje fortset algoritmen generasjon for generasjon.

Skjematisk kan vi framstilla ein Genetisk Algoritme slik:

No er vårt eksempel alt for enkelt og egentlig passar det dårlig for det fins jo andre metodar som kjem fortare til svaret. (Du kan jo feks bruka ein kalkulator!) Men det illustrerer korleis algoritmen fungerer. Her kan du sjå eit enkelt eksempel på ein Genetisk Algoritme med javascript.

EVOLUSJONEN:

Ein vanlig kjøring av ein Genetisk Algoritme kan sjå ut omtrent slik:

ANVENDELSAR:

Fordelen med ein Genetisk Algoritme er at den utfører eit såkalt Globalt søk. Det betyr at det leitar mange stader samtidig. Det fins såkalte lokale algoritmer som startar ein plass og leitar i nabolaget etter betre løysingar. Dette er for eksempel den såkalte hillclimbing (bakkeklatrings) algoritmar. Optimalisering betyr å finna det høgaste punktet på ein eller annan funksjon, i vårt tilfelle fitnessfunksjonen. Det slike hillclimbing-algoritmar gjer er å klatra oppover mot eit høgare punkt. Det blir akkurat som å finna ein fjelltopp med bind for augene, ved hjelp av ein (fortrinnsvis snakkande) høgdemålar. Du tar et skritt i den retningen som målaren gir best utslag på. Problemet er at du høgst sannsynlig vil havna på ein liten topp i nabolaget. Du vil ikkje finna det høgaste fjellet! lokale søk. Globale algoritmar unngår den fella, men kan ha andre problemer. Eg har brukt det til å finna optimale topologien for nevrale nett.

FITNESS I NATUREN:

Ein Genetisk Algoritme demonstrerer at vi ut frå "tilfeldigheter", skritt for skritt kjem nærare ei løysing. Og då er det jo det jo ikkje tilfeldig likevel når vi ser på sluttresultatet. Vi har jo designa algoritmen for å stadig komma nærmare målet, og målet har vi sett opp sjølv! Slik sett er ein GA ein dårlig modell for naturlig evolusjon. For evolusjon er ein open prosess uten forhåndsdefinert mål. Likevel skjer det ei utvikling i naturen også, men den har ingen bestemt retning. Naturen utviklar seg mot eit mål som stadig flyttar seg. Det er fordi "fitness" for eit levande vesen er bestemt av det miljøet det lever i, altså kva slags andre vesen som lever rundt det. Fitness i verkeligheten er mao. ein relativ størrelse. Det fins andre algoritmer som modellerer dette betre, som Evolusjonære Program, men det får vi sjå på ein annan gong!