Göm meny

Temauppgift 3

I Temauppgift 3 ska ni på ett objektorienterat sätt jobba med ett exempel där genetiska algoritmer används. Domänen är en modellvärld där virtuella varelser går runt, äter och ska försöka överleva så länge som möjligt.

Uppdatrerad inför VT18!

Allmänt

Uppgifter: Brons, Silver, Guld

  • Alla uppgifter göras av alla på bronsnivå.
  • För att få Silver på temauppgiften måste du göra alla brons- och silver-delar
  • För att få Guld på temauppgiften måste du göra alla brons-, silver- och guld-delar

Se även examination för information om hur brons, silver och guld påverkar moment- och kursbetyg.

Kodstandard

Er kod ska följa standarderna PEP 8 och PEP 257. Kontrollera detta genom att köra koden genom pep8 och pep257 programmen. pep8 finns installerad för alla, men ni behöver skapa en virtuell miljö (virtualenv) och installera pep257.

Redovisning och komplettering

Uppgiften redovisas på schemalagt redovisningstillfälle. Vid redovisningen visar ni att er kod fungerar korrekt, att den går igenom kontroll för PEP8 och PEP257 samt att ni förstår den kod ni skrivit.

  • Efter redovisningen kommer handledaren bedömma hur väl varje enskild gruppmedlem uppnått kunskapsmålen kopplade till denna uppgift (se ovan).
  • Varje pargrupp har en begränsad tid (ca 10 minuter) att redovisa och diskutera med handledaren.

Anvisad komplettering

Vid behov kommer er redovisningshandledare anvisa om att ni ska lämna in komplettering enligt kompletteringsinstruktionerna ovan. Inga kompletteringar kommer kunna göras under själva redovisningstiden.

Komplettering vid missat redovisningstillfälle

Missat redovisningstillfälle kompletteras genom att skicka in en screencast där ni demonstrerar ovanstående. Screencastkomplettering kan skickas in individuellt eller som par.

Komplettering upp till Silver eller Guld

Om man fått brons och vill få silver eller guld, eller om man fått silver och vill få guld, så kommer ett specifikt tillfälle för kompletteringsredovisningar för att få Silver eller Guld på temauppgiften kommer att hållas i slutet av kursen.

Lärandemål vid redovisning

Precis som alla uppgifter i kursen är det inte att lösa uppgiften i sig som är målet. Uppgiften är konstruerad för att hjälpa er behärska mer generella färdigheter och begrepp och det är dessa som kommer att bockas av vid redovisning.

Lärandemål: Brons

  • förstå grunderna för genetiska algoritmer (urval, crossover, mutation)
  • på ett objektorienterat sätt kunna dela upp funktionalitet för en tillämpning av genetiska algoritmer mellan en klass som representerar DNA och en klass som skapar nästa generations DNA-instanser.
  • kunna beskriva klasserna för ovan nämnda uppdelning med hjälp av ett klassdiagram
  • kunna implementera ovan nämnda uppdelning i programmeringsspråket Python, där metoder från de olika klasserna används på lämpligt sätt (se nedan för detaljer)
  • kunna att kunna använda beskrivande variabelnamn i programkod
  • kunna beskriva egenskriven kod på olika nivåer (t.ex. “den här raden lägger till ett element till listan”, jmf med “den här loopen används för att hitta antalet element som har samma värde som variablen söksträng

Lärandemål: Silver

  • kunna att använda variabler istället för hårdkodade värden i kod för att underlätta både underhåll och utveckling

Lärandemål: Guld

  • kunna dela upp en metod i flera mindre metoder inom en klass och redogöra för hur de används tillsammans

Uppgift

2018-04-27 Hungersnöd avvärjd: Iliyas upptäckte en bugg i lifesimulator.py som orsakat svår hungersnöd i världen eftersom den gjorde det omöjligt för mat att växa i världen. En uppdaterad version finns i kurskatalogen, men ni kan själva rätta till buggen som förmodligen uppstod när raderna skulle PEP8-förkortas. Rad 853-854 i lifesimulator.py ska ändras från

if cell_type == (WorldMap.EMPTY and
                 self.lookup_spawn_food_now()):

till

if (cell_type == WorldMap.EMPTY
                 and self.lookup_spawn_food_now()):

Det är alltså en parentes som grupperar fel. Värt att tänka på när man använder parenteser för att kunna bryta rader! PEP8 rekommenderar också att rader bryts innan den binära operatorn (som t.ex. +, *, and, or) för bättre läsbarhet.

Instruktionerna är också uppdaterade med ett till tips och förklaring kring siffror i kartan. Se text under avsnitten “Tips” och “Simuleringen”.

I Temauppgift 3 kommer ni få jobba med en simulerad värld som bebos av ett antal virtuella agenter. Agenternas beteende baseras på en DNA-sekvens som ni skapar och skickar till simuleringen som i sin tur skapar agenterna. Agenterna deltar i en simuleringsomgång som består av ett antal rundor.

Er uppgift (se detaljer längre ner på sidan) är är att strukturera och implementera den del av systemet som

  1. levererar DNA-sekvenser som används för att skapa agenterna i simuleringen
  2. tittar på poängen från en generation agenter och väljer ut de som ska bli “föräldrar” till nästa generation
  3. korsbefrukar och muterar dna från en generation för att skapa nästa generation.

I praktiken innebär detta att ni ska

  • implementera klassen BreedingFacility
  • implementera en DNA-klass
  • implementera algoritmer för crossover och mutation

OBS! Systemet i denna temauppgift ska inte ses som ett “riktigt” system för att tillämpa genetiska algoritmer eftersom modellen som används för hur dna-sekvensens genotyp översätts till en fenotyp har för många begränsningar.

Video från föreläsningen: https://www.youtube.com/watch?v=z9ptOeByLA4

Kodskelett

  • Filerna till uppgiften hittar ni i katalogen ~729G75/kursmaterial/tema3/temauppgift3. Filen lifesimulator.py innehåller koden till simuleringsmiljön. Filen temauppg3_skelett.py innehåller ett kodskelett som ni kan utgå ifrån när ni ska lösa uppgiften.

  • Ni kan testköra uppgiften genom att köra temauppg3_skelett.py. Tekniska begänsningar i simuleringsmiljön gör att det terminalfönster som ni kör programmet i tyvärr kraschar om fönstret är för litet! Om programmet kraschar, prova därför att göra terminalfönstret större!

Simuleringen

När ni kör igång ert program (utgå från temauppg3_skelett.py), kommer ett antal simuleringsomgångar som i sin tur består av ett antal rundor.

  • Agenternas uppgift är att överleva. En agent överlever genom att äta mat. När den blir för hungrig börjar den förlora hälsopoäng.
  • Simuleringen (lifesimulator.Simulator) består av en diskret modell som beskriver världen. Tiden i simuleringen är uppdelad i diskreta rundor, där varje agent utför en handling varje runda (ungefär som i ett brädspel).
  • Uppatering 2018-04-27: Siffrorna i simuleringsvyn är antalet agenter i en ruta. Om cellen innehåller mat är den gul. En cell utan mat är grön.
  • Simulerigen använder sig av metoden get_next_generation_dna_sequences() i klassen BreedingFacility för att få nästa generation DNA-sekvenser. Dessa är listor som följer specifikationen för dna_sequence som beskrivs i ett eget avsnitt nedan.
  • För varje runda som i simuleringen kan en agent antingen få poäng, eller förlora poäng. Om agenten mår bra får den poäng. Om den mår dåligt, förlorar den poäng.
  • Efter ett förutbestämt antal rundor är avslutas simuleringen. För varje DNA-sekvens som skickats till simuleringen skickar simuleringen tillbaka antalet poäng som dess agent fick.
  • Denna information använder ni för att generera nästa generation DNA-sekvenser (med hjälp av genetiska algoritmer) som sedan skickas simuleringen för ytterligare en omgång. Detta förlopp beskrivs i avsnittet om klassen BreedingFacility nedan.

Nedan beskrivs vad som händer varje runda i simuleringsmiljön.

Kartan och handlingar

Världen i simuleringsmiljön är en kvadratisk yta som är indelad i celler. Varje cell kan antingen vara tom eller ha mat på sig. I denna värld vandrar det runt agenter. Det finns ingen begränsning för hur många agenter som får befinna sig i samma cell.

Agenenterna har en begränsad mängd handlingar som de kan utföra. De kan förflytta sig ett steg rakt up/ned eller vänster/höger till en cell som ligger bredvid deras. De kan dock inte gå diagonalt. Förrutom att förflytta sig, kan agenterna också skörda mat om det finns i den cellen de befinner sig i, eller göra ingenting alls (att göra ingenting alls är alltså en handling).

Tiden i den simulerade miljön är diskret och varje agent utför exakt en handling varje runda. Alla handlingar genomförs dessutom samtidigt (dvs att om t.ex. tre agenter befinner sig på samma cell som innehåller mat, kan alla tre äta maten).

Beskrivning av klassen BreedingFacility

När ert program startas (som utgår från temauppg3_skelett.py) skapas en instans av klassen BreedingFacility som skickas som argument när simuleringsmiljön skapas. Simuleringsmiljön är en instans av klassen lifesimulator.Simulator.

Instansvariabler

Er BreedingFacility-klass ska ha följande instansvariabler:

  • en instansvariabel som innehåller den nuvarande generationen instanser av er DNA-klass

Metoder

Er BreedingFacility-klass ska minst följande metod:

  • get_next_generation_dna_sequences(latest_results)

Metoden get_next_generation_dna_sequences() används av simuleringsmiljön när den vill ha nästa generation av dna_sequence-listor. get_next_generation_dna_sequences() ska returnera en lista som i sin tur ska bestå av listor enligt specifikationen för dna_sequence (se avsnittet som beskriver DNA-sekvener nedan).

Argumentet latest_results kommer vara None om det är första generationen som ska skapas. Annars innehåller den ett dictionary där nycklarna är IDn till dna-sekvenser som körts och värdena är hur många poäng som den dna-sekvensen fick (t.ex. {"dna-1": 206, ... "dna-n": -14}. Använd denna information för att välja ut de dna-sekvsenser (instanser av er DNA-klass) som ska bli föräldrar till nästa generation instanser av er DNA-klass.

DNA-sekvens och DNA-klassen

Instansvariabler

Den DNA-klass som ni ska implementera ska ha minst nedanstående instansvariabler:

  • ID
  • action_catalog
  • strategy

Metoder

DNA-klassen ska även ha metoder för att jobba med dessa instansvariabler (ändra, plocka fram information etc). Att bestämma vilka dess ska vara ingår i er uppgift.

DNA-klassen ska även implementera metoden get_dna_sequence() som returnerar en lista som följer specifikationen för dna_sequence nedan.

dna_sequence

En dna_sequence är en lista som innehåller exakt tre element:

  1. ID : str
  2. action_catalog : list
  3. strategy : list

ID

Varje dna_sequence ska ha ett unikt ID (en sträng).

action_catalog och action_sequence

Listan action_catalog innehåller strängar (varje sträng är alltså en action_sequence. Varje sträng representerar en sekvens av handlingar eftersom varje tecken i sin tur representerar en specifik handling. Vilka tecken som man får använda finns i variabeln lifesimulator.Simulator.VALID_ACTIONS (som innehåller strängen "NSEWGI". Dessa tecken är:

  • N som står för North
  • S som står för South
  • E som står för East
  • W som står för West
  • G som står för Gather
  • I som står för Idle

Dessa är alltså de handlingar som en agent kan utföra i världen. En godkänd action_sequence är t.ex. strängen "NNNNNSSSEEEWW" eftersom varje tecken i den strängen är en av de godkända tecknena.

strategy

Listan strategy är en lista med heltal. Varje heltal refererar till ett index i listan action_catalog, dvs en specifik action_sequence. Om action_catalog innehåller fem element, kan listan strategy innehålla heltal mellan 0-4. Inga begränsningar finns på längden av listan strategy.

Fullständigt exempel på en dna_sequence

["dsf848076", ["NNN", "GWE", "SSSSEEEEE", "GNGWGE"], [1, 2, 3, 0, 1, 3]]

Genetiska algoritmer att implementera

  • De dna_sequence listor som skickas till simuleringen används för att skapa agenterna i simuleringen.
  • Istället för att jobba direkt med listan dna_sequence implementerar ni metoder som jobbar med instanser av er DNA-klass.
  • När en omgång är färdig och de bästa agenterna plockats fram, används olika algoritmer för att skapa nya instanser av er DNA-klass.

Vi ska använda oss av två olika algoritmer i denna uppgift. Ni kommer själva att utforma detaljerna i dessa, men nedan beskrivs vad de ska göra.

Crossover

En crossover-algoritm tar delar från olika “föräldrar-DNA” och kombinerar dem för att producera ett “barn-DNA”. Exakt hur detta ser ut beror på den DNA-struktur som används.

Om vi har en dna-sekvens som består av siffrorna 0 och 1 och är 8 siffror lång, skulle ett exempel på en crossoveralgoritm kunna skapa en ny dna-sekvens genom att ta de första 4 siffrorna från den ena föräldern och lägga ihop det med de sista 4 siffrorna från den andra föräldern:

Förälder A: 00000000
Förälder B: 11111111
Barn: 00001111

Självklart finns variationer här, t.ex. varannan siffra eller varva två siffror från den ena föräldern med två siffror från den andra föräldern. Det som är avgörande här är den struktur och betydelse som man valt att använda för dna-sekvensen.

För uppgiften är det den struktur som beskrivs i ovanstående avsnitt om DNA-sekvens som ska användas.

Mutation

Vid mutation behövs endast en dna-sekvens eftersom mutationsprocessen förändrar en dna-sekvens istället för att kombinera olika dna-sekvenser. Man kan tillämpa mutationen på en existerande dna-sekvens, eller t.ex. på en dna-sekvens som är ett resultat av en crossover. Hur en dna-sekvens muteras beror, precis som för crossover, på den struktur och betydelse som man användt när man specificerat utseendet på dna-sekvensen.

Exempel: Om en dna-sekvens är en sträng som består av 10 bokstäver från mängden {a,b,c,e,f} och vi har den ursprungliga dna-sekvensen aabbaacdef, skulle en mutationsalgoritm t.ex. kunna vara att det för varje bokstav finns en sannolikhet på 0.001 att bokstaven ökar i värde (dvs från a till b, … från f till a). En mutationsprocess skulle då t.ex. kunna ändra strängen aabbaacdef till aabbabcdef.

För uppgiften är det den struktur som beskrivs i ovanstående avsnitt om DNA-sekvens som ska användas.

Rekommenderad implementationsordning

Ni bör tänka igenom vilka delproblem som denna uppgift består av. Det går att dela upp implementationen i minst de delar som beskrivs nedan. Se till att namn på de metoder ni skapar är verb, samt vara beskrivande för det problem som det löser.

  1. Implementera ett första utkast till er DNA-klass. Implementera er första version av er DNA-klass. Koncentrera er på att få till instansvariablerna, samt metoden get_dna_sequence() som returnerar en lista enligt specifikationen för dna_sequence.
  2. Implementera funktionalitet som skapar den första, slumpade generationen.

    • När simuleringen körs för första gången kommer ett anrop till metoden get_next_generation_dna_sequences() med värdet None i argumentet latest_results. Metoden ska då alltså returnera en lista av dna_sequence-listor enligt specifikationen ovan.
    • Till första generationen ska ni alltså skapa slumpmässigt genererade instanser av er DNA-klass. Spara denna generation i instansvariabeln till BreedingFacility och returnera listan med dna_sequence listor.
  3. Implementera funktionalitet som plockar ut föräldrarna till nästa generation instanser av er DNA-klass.

    • När metoden get_next_generation_dna_sequences() körs för andra och efterföljande gånger, kommer argumentet latest_results att innehålla ett dictionary med resulataten från föregående omgång (se avsnittet ovan). Implementera funktionalitet som plockar fram de instanser av er DNA-klass som ska bli föräldrar
  4. Implementera algoritmerna crossover och mutation enligt instruktioner för er grupps variant.

    • Fortsatta anrop till get_next_generation_dna_sequences() kommer också också att skicka med ett värde i argumentet latest_results.
    • Implementera algoritmen för mutation och algoritmen för crossover. Ni kan implementera en i taget.

Tips

  • Spårutskrifter från systemet kommer till filen lifesimulator.log
  • Spårutskrifter från kod i klassen BreedingFacility kan skrivas ut med hjälp av self.logger.debug(meddelande) till filen breeding_facility.log. Se kommentarer i kodskelettet.
  • För att se spårutskrifter när de kommer in till filerna, öppna nytt/nya terminal-fönster och skriv tail -f filnamn. tail skriver ut slutet av en fil (argumentet filnamn). Flaggan -f gör att tail fortsätter köra och väntar på att nytt innehåll ska komma till filen.
  • Implementationstips: Gör så små steg i taget som möjligt. T.ex. för skapandet av den första generationen, börja med
    1. att skriva en metod som returnerar hårdkodade dna-sekvenser/instanser av er DNA-klass. Fortsätt sedan gradvis att utöka lösningen med
    2. att generera ID
    3. generera en strategy och till sist
    4. generera action_sequence-strängar

Uppdatering 2018-04-27

  • Om det går för fort och ni vill se varje runda utspela sig i terminalen, lägg till interactive=2 längst ner i kodskelettet i anropet till start_simulator(). Värdet 1 är default-värdet och värdet 0 gör att alla simuleringsomgångar körs utan paus.

Instruktioner för Brons, Silver och Guld

Ovanstående avsnitt gäller för alla nivåer. Nedan följer specifika instruktioner för de olika nivåerna.

OBS! Se information om “Variationer för olika grupper” nedan.

Brons-del

Krav på kommentarer i koden för Brons

  1. Namn på metoder ska vara verb
  2. Namn på instansvariabler ska vara substantiv
  3. Inga variabelnamn får bestå av endast en enskild bokstav (för exempel, se temauppgift 2).
  4. Alla satser som består av fler än en rad ska ha en tillhörande kommentar. Dvs if-satser, loopar, funktioner och metoder. Kommentaren ska inte vara en “innantilläsning” av koden den hör till. Använd rätt kommentarsmarkering (t.ex. """ för funktions- metodkommentarer, # för kommentarer i löpande kod, se PEP8 och PEP257). För exempel, se temauppgift 2.

Silver-del

  • Minimera användningen av hårdkodade siffror, använd istället variabler med förklarande namn.

Guld-del

  • Dela upp er kod vid behov:
    • När ni stöter på kod som ni upprepar, bryt ut koden (lägg koden i en metod)
    • Dela även upp er kod i fler metoder när den blir för lång.
    • Dra fördel av att ni implementerar en klass, spara undan information i instansvariabler. Se dock till att ni dokumenterar vilka instansvariabler som påverkas av metoden i metodkommentaren.
    • Se till att ni använder beskrivande metodnamn.

Koncentrera er framför allt på återkommande delar av er kod. Genom att bryta ut dessa till metoder kan ni använda er av dem istället för att skriva samma kod på flera ställen!

Variaioner för olika grupper

Variation 1

Använd en action_sequence-längd på 4 och en strategy-längd på 6. Se till att varje DNA-sekvens har exakt 6 element action_catalog (dvs 6 st action_sequence-strängar).

De bästa 50% av den tidigare generationen behålls. Dessa används för att skapa nya DNA-sekvenser så att den andra generationen innehåller lika många DNA-sekvenser som den första.

Crossover implementeras så att följande gäller:

  • Hälften av den nya dna-sekvensens action_catalog kommer från den ena föräldern, andra hälften kommer från den andra. Hur dessa hälfter plockas fram spelar mindre roll, det kan vara varannan eller t.ex. de två första och de två sista.
  • Hela strategy listan plockas från en av föräldrarna.

Mutation implementeras så att barnets strategy förändras: ändra på ett av heltalen.

Variation 2

Använd en action_sequence-längd på 4 och en strategy-längd på 6. Se till att varje DNA-sekvens har exakt 6 element action_catalog (dvs 6 st action_sequence-strängar).

De bästa 25% av den tidigare generationen behålls. Dessa används för att skapa nya DNA-sekvenser så att den andra generationen innehåller lika många DNA-sekvenser som den första.

Crossover implementeras så att följande gäller:

  • Alla den nya dna-sekvens action_seqence-element kommer från en av föräldrarna
  • Hälften av den nya dna-sekvensens strategy kommer från den ena föräldern, och att hälften kommer från den andra. Hur dessa hälfter plockas fram spelar mindre roll, det kan t.ex. vara varannan siffra eller t.ex. den första hälften kombinerat med den sista hälften.

Mutation implementeras så att det finns en viss sannolikhet att ett barns action_catalog förändras. T.ex. om ett slumptal är mindre än 0.01 ändras en siffra i en action_sequence.

Variation 3

Använd en action_sequence-längd på 4 och en strategy-längd på 6. Se till att varje DNA-sekvens har exakt 6 element action_catalog (dvs 6 st action_sequence-strängar).

De bästa 50% av den tidigare generationen behålls. Dessa används för att skapa nya DNA-sekvenser så att den andra generationen innehåller lika många DNA-sekvenser som den första.

Crossover implementeras så att följande gäller:

  • 1 av den nya dna-sekvensens action_sequence-strängar i action_catalog kommer från den ena föräldern, och 5 action_sequence-strängar ska komma från den andra
  • hela den nya sekvens strategy kommer från den förälern som bidrog med de flesta action_sequence-strängar.

Mutation implementeras så att det finns en viss sannolikhet att ett barns action_catalog förändras. T.ex. om ett slumptal är mindre än 0.01 ändras ett tecken i en action_sequence.

Övriga resurser


Sidansvarig: Jody Foo
Senast uppdaterad: 2018-04-27