Artikkel

Den digitale evolusjonen

DNA teknologi
Evolusjon av informatikken har mange fellestrekk med tradisjonell evolusjonsteori og genetikken. Foto: Colourbox

Den digitale evolusjonen

Nye metoder utvikles for å prosessere kompleks data. Hva skjer når informatikk møter evolusjonsteori? Og hva er en genetisk algoritme?

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.

Vegard Knutsen Lillevoll
Artikkelforfatter Vegard Knutsen Lillevoll er student og tar formidlingskurset MNKOM.

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.

Å 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ønstre 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.

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.

sjakk
Verken mennesket eller den kraftigste datamaskinen vi har er i dag i stand til å tenke gjennom alle muligheter i sjakk. Foto: Colourbox

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.

Biologisk regnekraft og kvantedatamaskiner

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 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å et tilnærmet 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?

Les mer på Titan.uio.no:

Modellerer hjernen som en elektrokjemisk maskin: Vil vi i framtida bli i stand til å intervjue nevronene?

Fremtidens supermaskin: Kvantedatamaskinen kan være det neste store, men også noe ganske annet enn de datamaskinene vi er vant til.

Tenkemaskiner på opplæring: Vi har lært datamaskner å lære. Målet er å lære dem å tenke.

Flere artikler på bloggen til studentene som har tatt formidlingskurset MNKOM

Kontakt:

Avdelingsingeniør og student Vegard Knutsen Lillevoll

Kategori: 

Skriv ny kommentar

Verifiser deg (din epost-adresse vil ikke bli vist offentlig)

Les også

Teamet som har utviklet den nye elektrolysemodulen

Nye materialer produserer hydrogen mer effektivt og klimavennlig

Drømmen om å bruke en spesiell type keramiske materialer til elektrolyse ved høye temperaturer er snart 30 år gammel, men nå har professor Truls Norby og samarbeidspartnere fått det til. Metoden kan for eksempel omdanne en blanding av metan og vanndamp til hydrogengass og ren CO2, som kan deponeres offshore. 

Siri Bromander, Martin Eian, Vasileios Mavroeidis, Audun Jøsang og Laszlo Erdödi

De avslører hackere med smarte analyseverktøy

Med industrisamarbeid, «big data»-analyse, maskinlæring og matematisk logikk som våpen håper forskerne å komme de IT-kriminelle i forkjøpet.

– De som står bak cyberangrep blir stadig smartere.