Most recent comments
Liveblogg nyttårsaften 2017
Tor, 11 months, 2 weeks
Jogging og blogging
Are, 1 year, 11 months
Liveblogg nyttårsaften 2016
Are, 1 year, 11 months
Reading in dark times
Are, 2 years
Moldejazz 2016
Camilla, 2 years, 4 months
Dørskilt
Karoline, 2 years, 5 months
Halifax
Tor, 2 years, 5 months
Sony Smartwatch 3 review
Tor, 2 years, 6 months
Numerikk, takk
Tor, 2 years, 6 months
Topp tur
Camilla, 2 years, 8 months
50 book challenge
Camilla, 11 months, 2 weeks
Ten years ago
Kurs for brukere
Tor
Controls
Register

Genetisk algoritme

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

Comments

Camilla,  15.04.08 16:23

600.000 individer, kanskje, men ikke 600.000 Bothans. Og det er jo bra.

Camilla,  15.04.08 16:24

For å forklare, for det går jo ikke an å redigere: Det er bra at det ikke var Bothanere, for de tok jo bare opp informasjon som keiseren hadde plantet.

Are,  15.04.08 17:29

Cred! Jeg digger algoritmeartiklene dine, Tor!
Tor,  16.04.08 14:31

Jeg flikket litt på koden min akkurat nå. Før jeg setter sammen to strenger til et nytt individ, la jeg inn en mulighet for at den ene strengen blir snudd. Dette vil i en del tilfeller kunne åpne løkker, noe som vil være gunstig i alle tilfeller, tror jeg. Foreløpig testing later til å indikere at programmet ble mye mer effektivt etter denne forandringen.

Forøvrig, jeg noe en fyr hadde skrevet om genetiske algoritmer, og det var jaggu ikke lite han hadde å si. Han mener blant annet at konseptet langt på vei beviser at det er evolusjon som er tingen i naturen også.

Forøvrig lister han opp en den interessant eksempler, særlig det med prediksjon av aksjekurser, og det med sjakk-programmet.

Kristian,  17.04.08 08:29

Fin artikkel Tor. Poenget at sånne algoritmer beviser evolusjon er kanskje litt drøyt, men det føyer seg pent inn i rekken av ting som taler for.

B,  17.04.08 22:04

hva med å outputte til gnuplott istedenfor den kjedelige tekstfila?

B,  17.04.08 22:51

gen.py
Her er versjon jeg har moddet sånn at den ble litt finere. pos.py er nå en del av gen.py og dermed fullstendig unødvendig å legge ved.

Koden din er egentlig litt som håndskriften din Tor... :D

Kan du forklare litt mer i detalj hvordan du tenker/tenkte at funksjonene skulle oppføre seg?

Tor,  17.04.08 23:37

Jeg bruker naturligvis gnuplot, men jeg får ikke til å plotte direkte fra python, fordi gnuplot.py krever Scipy, som jeg aldri fikk til å installere.

Og det at jeg lagde pos.py som et eget program var for å kunne teste forskjellige instillinger på samme problem.

Men jeg ser at det er en del ting jeg skal få deg til å forklar meg, når jeg har lest igjennom det du har fikset på.

Og kanskje du kan sende meg noe du har kodet, eller en link til en oppskrift på god skikk og bruk når det gjelder koding?

B,  18.04.08 09:20

Du kan jo skrive til tekstfilen din og så kan du bruke import os og så skriver du;
gnustr = "gnuplot -option ..."
os.system(gnustr)

B,  18.04.08 09:33

hvis du vil kjøre et program fra terminal og ønsker å ha tilbake informasjonen som er output kan du
skrive
ab[ ]
cmd_str = os.popen(ps au | grep nordam)
ab.append(cmd_str.readlines() )
cmd_str.close()
for line in ab:
print line

Tor,  18.04.08 23:39

Jeg fikk det ikke til å funke med os.system, men dette fungerte:

g = os.popen("gnuplot", "w")
print>> g, "load '/users/tor/python/bounce.p'"

Så nå kan jeg plotte i vilden sky. Woho!