Tekst: Vegard Lillevoll | Illustrasjon: Bruno Calado
Vi er omgitt av problemer. Hele vårt teknologidrevne samfunn er stappfullt av problemer: Problemer som må løses. Men det finnes mange måter å løse disse på. En ganske ny og spennende metode kalles genetiske algoritmer.
En algoritme er en instruksjon man kan følge slavisk for å løse et problem. Hvis du skal sortere en kortstokk, kan du for eksempel gå gjennom stokken, finne alle essene og legge dem hver for seg. Så kan du gå gjennom stokken på nytt på utkikk etter toere, og legge hver toer oppå riktig ess. Slik kan du fortsette helt til du har kommet til kongen. Til slutt legger du alle fire bunkene oppå hverandre. Denne instruksjonen er en algoritme, og datamaskiner er fulle av dem.
Genetiske algoritmer finner sjelden den aller beste løsningen, men kan ofte finne en som er veldig god.
Å sortere en kortstokk er en relativt overkommelig oppgave, men noen regneoppgaver er så omfattende at det er umulig å løse dem fullstendig. De har ofte ikke bare én løsning, men svært mange løsninger av varierende kvalitet. Å finne den beste veien gjennom vanskelig terreng, å finne bevegelsesmønster for en robot og å gjenkjenne mønster i et bilde er oppgaver som er ekstremt vanskelig å løse helt nøyaktig. Heldigvis trenger man som regel ikke å finne den absolutt beste løsningen, det holder med en som er veldig god. Her kommer genetiske algoritmer, med kvasi-biologisk unøyaktighet og rot til sitt rette.
Teoretisk løsbare problemer
Store sjakkturneringer har enorme premiepotter, og tittelen «sjakkmester» er ærverdig og respektert. Man kan likevel si at sjakk er et kjedelig og forutsigbart spill – all informasjon er allerede kjent for begge spillerne, inkludert hvilke mulige trekk motstanderen vil kunne gjøre. Burde ikke en datamaskin kunne se på alle mulige trekk og velge det beste av dem?
Hvis alle mennesker i verden dannet par og spilte tusen parti sjakk per sekund døgnet rundt, ville vi ikke vært i nærheten av å ha spilt én prosent av alle mulige spill før jorden ble slukt av solen. Det vil i praksis være umulig for selv den kraftigste datamaskinen vi har i dag å tenke gjennom alle muligheter i et sjakkspill. Det finnes en mengde slike problemer, og hvis vi skal ha håp om å løse dem må vi se på andre metoder.
Akseptable løsninger
La oss gå tilbake til genetiske algoritmer. Som sagt tar de inspirasjon fra naturen for å løse problemer. Man tar utgangspunkt i oppskriften på et individ, altså et sett med data som inneholder all informasjonen man trenger for å kunne bygge akkurat det individet. Denne oppskriften kalles et genom, og i biologien er det som regel DNA.
Hvis alle mennesker i verden dannet par og spilte tusen parti sjakk per sekund døgnet rundt, ville vi ikke være i nærheten av å ha spilt én prosent av alle mulige spill før jorden ble slukket av solen.
Den viktigste egenskapen til et genom er at det lett kan klippes og limes i, rekkefølgen på dataen kan stokkes om på og varieres på utallige måter, og resultatet vil da bli et nytt individ. Da har man det man trenger for å kunne krysse forskjellige individer, og mutere et individ. Dette er viktige verktøy for å komme fram til gode løsninger.
Et genom leder altså til et individ, men i denne sammenhengen er ikke et individ et levende vesen. Et individ må være en potensiell løsning på problemet – en vei gjennom terrenget, et bevegelsesmønster for en robot eller en konfigurasjon av et mønstergjenkjenningssystem. Neste steg er å finne verdien til et gitt individ.
Vi parrer oppskrifter
Når vi vet hvor godt tilpasset hvert individ i en populasjon er, kommer evolusjonen inn for fullt. Vi lager par av et utvalg av de beste individene, og krysser dem. Vi får da nye genomer – avkom – som må prøves ut. Er vi heldig, vil en del av avkommet få de beste egenskapene fra foreldrene, slik at det blir enda bedre tilpasset. For eksempel er kanskje starten av en vei veldig bra, mens en annen har en bra slutt. En andel av avkommet muteres også, for å få inn nytt genetisk materiale som kan åpne for helt nye løsninger. Etter flere hundre generasjoner eller mer, vil gode løsninger komme til syne. Da kan vi si oss fornøyd, og ta i bruk den beste løsningen.
Genetiske algoritmer finner sjelden den aller beste løsningen, men kan ofte finne en som er veldig god. Det som gjør dem så forskjellig fra tradisjonelle metoder er den store graden av tilfeldighet brukt både for å velge mutasjoner og paringer. Man kan derfor ofte få uforutsette resultater, som både er den største styrken og den største svakheten til genetiske algoritmer, fordi de både kan utforske deler av løsningsrommet mennesker ikke har tenkt på og rote seg bort i et håpløst hjørne. Tilfeldighetene rår, og det er umulig å garantere hva som kommer til å skje.
Banebrytende nytenkning eller unødvendig abstrahering
Ikke alle er begeistret for genetiske algoritmer. De har blitt kalt både ineffektive og «pseudobiologisk voodoo». Hvorfor skal vi strebe etter en slags symmetri med hva man finner i naturens egne fremgangsmåter?
Metoden har åpenbart har fungert for naturen, siden så kompliserte individer som mennesker har utviklet seg på jorden. Men dette har skjedd gjennom en enormt langsom prosess, og naturen har også en ekstrem parallellitet. Milliarder av organismer i forskjellige økosystemer har utviklet seg parallelt og i vekselvirkning med hverandre, og de har utvekslet genetisk materiale seg imellom. Dette er en biologisk regnekraft vi ikke kan håpe på å etterligne med teknologien vi har i dag. En revolusjon på linje med kvantedatamaskiner må på banen før vi kan ha noe som helst håp om å kunne regne på samme nivå.
Sannheten ligger nok litt dypere. Metodene fungerer, men det finnes kanskje mindre kompliserte måter som kan oppnå samme resultater. Det at genetisk algoritmer har en slags elegant tilknytting til naturen er interessant, men er det bare en morsom kuriositet eller forteller det oss noe dypere om databehandlingens natur?
Vegard Lillevoll er en teknologientusiast som tar en mastergrad i robotikk.
