Labb 3 - design och implementation av genetisk algoritm.

Labb 3: OO design + implementation av GA from Jody Foo on Vimeo.

VIKTIGT: Läs dessa anvisningar innan ni börjar labben

Innehåll

Syfte med denna labb

Syftet med denna labb är att ni ska få öva er i objektorienterad modellering.

Ni ska själva för att implementera ett system som använder sig av genetiska algotimer för att hitta ett bra sätt att styra en spelare genom labyrintspelet.

Ni ska bestämma er för vilka klasser ni behöver och hur de ska hänga ihop. Kod som utvärderar en spelare i en labyrintvärld finns färdig och exempel på hur man kör det finns i labbskelettet.

Bakgrund

Genetiska algoritmer är inspirerade av biologisk evolution. Det är ett sätt att söka efter en lösning på ett problem genom att man låter olika lösningsförslag genomgå en evolutionär process. Nedan följer en väldigt kortfattad beskrivning av metoden.

Metoden innebär att man har ett antal individer vars beteende/presetation är beroende av deras digitala “DNA”. Detta digitala DNA kan bestå av olika saker, antingen parametrar till vissa funktioner eller annan kod som styr hur de agerar.

Individerna körs i någon form av simulering som resulterar i ett mått på deras prestation. De bästa individerna sparas och genomgår någon form av evolution. Deras avkomma får sedan genomgå samma process, och så fortsätter man så tills man eventuellt hittat en lösning på problemet.

Evolution

Den evolutionära processen i denna labbs labyrintvärld kan sammanfattas i följande steg:

  1. Individerna får prova sin lycka i labyrintvärlden. De får ett visst antal poäng.
  2. De två bästa individerna får föra sina gener vidare.
  3. De utvalda individerna parar sig och får fyra barn. Sedan muteras föräldrarna. Se nedan för mer detaljer om parandet och muterandet.
  4. Barnen och föräldrarna skickas tillbaka till labyrintvärlden och processen börjar om från punkt 1.

Crossover och mutation

Det finns olika sätt som individerna kan förändras/delta i evolutionen, antingen genom att två individer parar sig och deras DNA kombineras (Crossover), eller att en enskild individs DNA förändras av sig själv (mutation).

Beskrivning av systemet i denna labb

Nedan följer en beskrivning av systemet som ska skapas i denna labb: Individerna och deras DNA, Fortplantningfabriken och Labyrinten.

Individer och DNA i labbens labyrintdomän

I denna labb ska ni ta fram individer som ska prova sin lycka i labyrintvärlden. Ni kommer ha tillgång till ett labyrintprogram som tar in en lista av strängar (t.ex. ["n", "n", "p", "w"]) som bestämmer vad spelaren ska göra (t.ex. gå norr, gå norr, plocka upp något, gå väst. Det är den lista av strängar som kommer att utgöra individernas DNA. Längden på en DNA-sekvens kan variera.

Nedan finns de strängar som godtas som handlingar:

  • ‘n’ - gå norr
  • ‘e’ - gå öst
  • ’s’ - gå söder
  • ‘w’ - gå väst
  • ‘p’ - plocka upp eventuella mynt
  • ‘wait’ - gör ingenting

Förrutom att en individ har en DNA-sekvens, ett nummer. Varje individ ska också veta namnen på dess föräldrar (första generationen har dock inga föräldrar).

Varje individ ska också kunna komma ihåg hur många poäng den fick i den senaste labyrintomgången.

Varje generation består av 6 st individer.

Fortplantningsfabriken

I denna labb låter vi all fortplantning och mutation ske i en fortplantningsfabrik. Denna fabrik övervakar crossover och mutation.

Efter att alla individerna i en generation utvärderats i labyrintvärlden ska de två bästa (de två som fått flest poäng) skickas till fortplantningsfabriken.

Forplantningsfabriken ska producera fyra nya individer via crossover och mutera de två föräldrarna.

Crossover mellan två individer

Vid crossover skapas en ny individ med hjälp av två föräldrar. Föräldrarnas DNA blandas på följande sätt:

  1. En slumpmässig delningspunkt bestäms.Denna punkt används för att dela en individs DNA i två delar. Delningspunkten kan vara en viss procent av DNA-sekvensen. Om delningspunkten är 50% och en DNA-sekvens är 10 element lång, delas den i två delar på 5 element vardera. Om delningspunkten är 23% och DNA-sekvensen är 7 element lång, låter vi den ena delen vara 23% lång och den andra delen 77% lång. Avrundningen får ni bestämma själva.
  2. För individerna A och B får vi alltså fyra delar DNA. A1 och A2 från individ A och B1 och B2 från individ B. Två nya DNA-sekvenser kan skapas med hjälp av dessa delar: A1B2 och B1A2. En crossoverprocess resulterar alltså i två nya individer.

Mutation av en individ

En mutation av en individ kan ske på ett antal olika sätt:

  • Ett slumpmässigt element i DNA-sekvensen byter värde.
  • Ett slumpmässigt element i DNA-sekvensen tas bort.
  • Ett slumpmässigt element i DNA-sekvensen läggs till.

Antalet mutationer en förälder genomgår i fortplantningsfabriken bestämmer ni själva.

Poäng i labyrinten

Labyrintvärlden fungerar på följande sätt:

  • Spelaren börjar med 100 poäng.
  • Varje steg ('n', 'e', 's', 'w') som spelaren tar ger -10 poäng.
  • Om spelaren väntar ('wait') ger det spelaren -5 poäng.
  • Om spelaren hittar utgången ger det spelaren 200 poäng.
  • Varje mynt som spelaren plockar upp ger 10 poäng.

Krav på implementationen

  • Implementationen ska ha minst 2 klasser.
  • Koden ska följa PEP8. Denna gång behöver ni dock inte dokumentera get- och set-metoder.
  • Systemet ska ha koll på vilka en individs föräldrar är.
  • Systemet ska ha koll på hur många poäng en individ får.
  • Systemet ska ha koll på vad individerna heter.

Lägsta komplexitetskrav (Uppdaterat 2013-02-18)

  1. DNA-sekvensen är 10 element lång.
  2. Crossover sker alltid i mitten, dvs en DNA-sekvens delas i två delar på 5 element vardera.
  3. Endast “byt ut elemen” som mutationalgoritm behöver implementeras.
  4. 100 generationer körs.

Att lägga till (valfritt) för ökad komplexitet (Uppdaterad 2013-02-18)

  • Varierande längd på DNA-sekvensen.
  • Lägg-till och ta-bort som ytterligare mutationsmöjligheter.
  • Slumpat antal mutationer per generation (t.ex. att föräldrarna muteras 1-5 gånger i Förökningsfabriken).
  • Slumpad delningpunkt för crossover mellan två DNA-sekvenser.
  • Fler än 6 individer per generation
  • Fler än 2 som väljs ut för fortplantning mellan generationerna.
  • En annan karta (er egen från labb 6-8 i 729G04 kan användas)

Genomförande (Uppdaterat 2013-02-18)

Bra referenser till denna labb

Genomförandesteg

Uppdaterat 2013-02-18: Ni behöver inte använda getters och setters om ni jobbar med variabler som ligger innuti den egna instansen.

  1. Kopiera labbskelettet, filen labyrinth.py samt kartan (högerklicka och “Spara länk som…”).
  2. Exempel i labbskelett hur man skapar en värld, laddar en bana och kör en DNA-sekvens i labyrinten. Testa labbskelettet, och kontrollera att det fungerar. Om ni i ett terminalfönster ställer er i den katalog som alla filer finns i, bör ni kunna skriva python labbskelett3.py för att köra labbskelettet.
  3. Ta fram ett klassdiagram som beskriver vilka klasser ni behöver. Instansvariabler och instansmetoder ska finnas med. Se till att ni får med relationer som beskriver vilka klasser som innehåller vilka andra klasser, samt relationernas kardinalitet (1-1, 1-N, eller M-N). Viktigt är också att fundera på vilka parametrar konstruktorerna behöver.
  4. Implementationen kan sedan delas upp i följande steg:
    1. Skapa strukturen kring era klasser utan att de innehåller något. Se till att allt går att köra utan syntaxfel etc. Lägg till lite i taget till klasserna, testa med jämna mellanrum. Extra tips för att testa fil från prompt finns här i Pythonkompisen.
    2. Ordna så att ni kan ta en generation av individer och köra dem i labyrinten samt ta tillvara på deras prestationer.
    3. Ordna så att ni kan välja ut de två bästa individerna.
    4. Ordna så att ni kan skicka två individer till fortplantningsfabriken och att kloner skickas ut (tre av varje). Detta för att få till mekanismerna att spara nästa generation av individer.
    5. Implementerera mutationen.
    6. Implementera crossover.
  5. Den färdiga implementationen ska skriva ut namnet på den som var bäst i den sista generationen, dess DNA-sekvens, vilka dess föräldrar var, samt hur många poäng som den fick.

Redovisning

  • Labben redovisas genom att ni skickar alla filer (kod + eventuell egen karta), samt klassdiagram via e-post till er labbhandledare. Lägg till era liu-id:n i slutet av filerna. T.ex. labb3-liuid1-liud2.py och labb3-klassdiagram-liuid1-liuid2.png.
  • Se till att cc:a er labbpartner.
  • Använd följande ämnesrad: 729G06 Labb 3 abcde123 och qwert234 (där abcde123 och qwert234 ersätt med era liu-id:n). Genom att använda denna ämnesrad gör ni det lättare för er labbhandledare att hitta er inlämning! Vid komplettering, lägg till ett “kompl.” eller “komplettering”, och skicka inte in mer än en labb i samma e-post.

Sidansvarig: Jody Foo
Senast uppdaterad: 2013-01-16