Trofaste lesere vil sikkert huske at jeg skrev en artikkel om problemet med den omreisende handelsmannen for ikke så lenge siden. Nå har jeg prøvd å løse probelemet en gang til, denne gangen med det som kalles en genetisk algoritme. Jeg er ikke sikker på om den er helt god, men den finner i alle fall stadig bedre løsninger, og det er da noe. Men hva er egentlig en genetisk algoritme?

Som navnet tilsier er det en algoritme som etterligner måten evolusjon foregår, ved at de beste individene har større sannsynlighet for å gi sine gener videre til neste generasjon. Mutasjon kommer også inn i bildet, og så kjører man hele prosessen i en hel haug med generasjoner, og så blir det bra til slutt.

Man begynner med å generere mange tilfeldige løsninger. I problemet med den omreisende handelsmannen vil det si tilfeldige reiseruter. Disse løsningene kalles individer, og til sammen utgjør de en populasjon. Hver slik mulige løsning består da av en mulig rekkefølge, og denne rekkefølgen er på en måte genene til dette individet. Mange av disse rutene vil være crap, men noen av dem vil inneholde bra deler, og disse ønsker vi å ta vare på.

For å oppnå dette utfører man et utvalg. Da anvender man først en eller annen test på hvor bra løsningen er, og gir hvert individ et tall som representerer brahet (fitness). Deretter velger man ut de individene som skal danne neste generasjon. Dette kan skje ved at man sorterer dem etter brahet, og tar for eksempel den beste halvparten, eller man kan si at bedre løsningen har større sannsynlighet for å bli valgt, men ingen garanti. Det mest vanlige er nok en blanding av disse.

Neste skritt er å krysse de utvalgte løsningene. Det vil si at man tar en del av genene til en løsning, og setter sammen med en del av genene til en annen løsning, på en slik måte at det ferdige resultatet også utgjør en gyldig løsning. Det man ønsker å oppnå med dette er å skape nye løsninger som inneholder gode elementer fra de gamle løsningene. Noen løsninger vil naturligvis bli dårligere av denne prosessen, men de vi uansett bli utryddet ved neste utvalg. MUAHAHAHA!

Før krysning:
184952673
814973562

Etter krysning:
184973562
814952673

Man kan enten la hele neste generasjon fremkomme ved krysning, eller man kan la noen individer overleve og noen bli krysset. Jeg tror det kommer litt an på problemet man ser på. Her kan man også bestemme morsomme ting som incest, altså i hvilken grad «foreldre» skal kunne krysses med sine egne «barn», noe som kan være gunstig i denne sammenhengen. Antagelig på grunn av noe med manglende dobbel helix eller noe slikt.

Det siste leddet i prosessen er naturligvis mutasjon. Det kan nemlig hende at ingen av de opprinnelige løsningene inneholdt alt som skal til for å finne den beste løsningen. Derfor lar man mutasjoner dukke opp fra tid til annen, og idéen er at hvis en mutasjon er bra, vil den bli tatt vare på, og inngå i fremtidige generasjoner, mens hvis den er dårlig vil den bli slaktet ned.

Planen er så at etter at man har kjørt igjennom denne prosessen i mange nok generasjoner, vil etterhvert løsningene bli mer og mer like, og bedre og bedre. Her er resultatet jeg fant for 20 byer. Det tok rundt ti minutter eller noe slikt. Det er åpenbart ikke den beste løsningen, men hvis man hadde åpnet løkken hadde den nok ikke vært så langt unna. Når jeg tenker meg om ser jeg at denne typen problemer er en svakhet ved programmet mitt. Nuvel. For 20 byer finnes det i alle fall 2432902008180000000 mulige løsninger, så det er rimelig uaktuelt å sjekke alle. Og husk, 600.000 individer døde for å bringe oss denne informasjonen.



For de som er interessert ligger programmet her. pos.py lager en fil pos.txt, som inneholder koordinatene til byene. gen.py leser inn koordinatene, og setter i gang. Resultatet kommer ut i kart.txt.

-Tor Nordam