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.

2017-05-04

  • lifesimulator.py uppdaterad med buggfixar
  • ändring av namn från action_sequences till action_catalog hade inte kommit till hemsidan, men det ska nu vara ordnat.

2017-05-05

  • fetmarkerat det som ska implementeras i “Att göra-avsnittet”
  • tips från första datorsalstillfället tillagt

Allmänt

Betyg

För att få betyget VG på momentet för Tema 3 (PRA3) behöver man göra VG-delen av temauppgiften. Kursbetyget baseras på betyget i tema 1-3.

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 PEP 8 och PEP 257 samt att ni förstår den kod ni skrivit.

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

Komplettering upp till VG: Ett specifikt tillfälle för VG-kompletteringsredovisningar kommer att hållas i slutet av kursen. Datumet är preliminärt 10-12, 245 i SU14. Anmäl dig senast fre 19 maj till jody.foo@liu.se om du önskar utnyttja detta tillfälle.

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.

Översikt

I Temauppgift 3 kommer ni få jobba med en simulerad värld som bebos av ett antal virtuella agenter. Agenternas uppgift är att överleva. En agent överlever genom att se till att den inte går runt hungrig. När den är hungrig förlorar den hälsopoäng. För varje runda som agenten körs i världen får den poäng. Om den mår bra får den fler poäng. Om den mår dåligt dras det bort poäng.

Flera agenter befinner sig i världen på samma gång. Agenterna är kvar i världen ett antal rundor. Efter simuleringen väljs ett antal de agenter som deltog i simuleringen ut (de bästa). Dessa används för att skapa en ny generation agenter som sedan placeras placeras i världen. Simuleringen fortsätter med denna cykel av liv, fortplantning och död ett specificerat antal gånger.

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

  1. skapar dna-sekvenser till de agenter som ska skapas i världen
  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.

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.

Genetiska algoritmer

Beteendet hos de agenter som vistas i världen bestäms av en “dna-sekvens”. När en omgång är färdig och de bästa agenterna plockats fram, används olika processer för att skapa nya dna-sekvenser till agenterna som ska in nästa omgång. Detta upplägg med utvärdering av prestationen hos olika dna-sekvenser och att sedan använda dem för att skapa nya dna-sekvenser brukar gå under samligsnamnet genetiska algoritmer.

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.

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.

Simuleringen

En simuleringskörning är uppbyggd av ett antal simuleringsomgångar. Varje omgång motsvarar en generation av agenter. Varje omgång i sin tur består av ett antal rundor.

Simuleringsvärlden och agenterna

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 tidsenhet. 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 skörda maten).

Uppgiften

Det finns en uppsättning uppgifter som gäller för G-nivå och tillägg till dessa för att komma upp i VG-nivå. Precis som under tidigare teman är det varierar uppgifterna beroende på vilen romersk siffra man fått på sin grupp.

Den kod som finns tillgänglig i uppgiften tar hand om själva simuleringen. Det som inte är implementerat är just framtagandet av de ursprungliga dna-sekvenserna, samt korsbefruktning/mutation (crossover/mutation) av dna-sekvenser för att producera en ny generation dna-sekvenser.

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.

Redovisning

Vid redovisning demonstreras ert program tillsammans med en översiktlig beskrivning i text av hur era algoritmer för crossover och mutation fungerar.

Uppdatering 2017-05-09 Beskrivningen i text kan antingen vara i detaljerade kommenterar i koden, eller en separat beskrivning av de olika stegen i era algoritmer. Beskrivningen bör beskriva de delar som inte är helt specificerade i uppgiftstexten (t.ex. hur ni parar ihop vilka två DNA-sekvenser som ska ingå i crossover, vad det är som muteras hos er etc).

Datastrukturer för DNA-sekvenser

dna_sequence

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

  1. ID (str)
  2. action_catalog (list) Hette förut action_sequences, men det spelar ingen roll vilket namn ni använder i er kod så länge som ni är konsekventa!
  3. strategy (list)

ID

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

action_catalog

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å DNA-sekvens

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

G-Nivå

Er uppgift är att implementera klassen BreedingFacility så att dess metod get_next_generation_dna_sequences() fungerar (ni kan skapa fler klasser om ni vill och behöver).

Metoden get_next_generation_dna_sequences(self, latest_results=None) ska returnera en lista som innehåller de dna-sekvenser som ska köras i simuleringen. Metoden kommer att anropas av simuleringen.

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 som ska gå vidare.

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

2017-05-03: Ändrade namn på argument till get_next_generation_dna_sequences() i instruktionerna från last_results till latest_results.

Att göra

Ni bör tänka igenom vilka delproblem som denna uppgift består av. Det bör går att dela upp i minst tre separata problem. Se till att ha minst en metod för varje delproblem. Namnet på metoden bör vara ett verb, samt vara beskrivande för det problem som det löser.

  • Implementera funktionalitet som skapar den första, slumpade generationen med dna-sekvenser. Simuleringen kommer att göra ett anrop till get_next_generation_dna_sequences() och funktionen ska då alltså returnera en lista av dna-sekvenser enligt specifikationen ovan.
  • Fortsatta anrop till get_next_generation_dna_sequences kommer också också att skicka med ett värde i argumentet result. Det kommer att vara ett dictionary där nycklarna är dna-sekvens-IDn och värdena är poängen som dna-sekvensens agent fick. Implementera crossover och mutation enligt spec för er grupps variant.
  • För att underlätta arbetet med att skapa en DNA-sekvens, skapa en klass som ni använder för att representera en DNA-sekvens och manipulera dess olika delar. Se också till att klassen har en metod som exporterar innehållet till list-formatet ska returneras av get_next_generation_dna_sequences.

VG-nivå

För att få VG på temauppgiften krävs att alla metoder, funktioner och variabler har namn som beskriver sitt innehåll/funktion på rätt nivå. Metoder och funktioner ska inte göra mer än vad som kan förväntas givet deras namn. Funktioner/metoder ska också vara nedbrutna i delproblem så att varje enskild funktion/metod inte blir för lång.

Någonstans kring 15 rader exklusive kommentarer är en riktlinje för maxlängden. Där det är ganska sannolikt att problemet går att bryta ner. Vissa programmerare försöker hålla sig under 5 rader…

Variaioner för olika grupper (I, II, III)

Avsnittet Datastrukturer för DNA-sekvenser innehåller information om hur DNA-sekvenslistor ska se ut. Avsnittet Genetiska algoritmer innehåller information om crossover och mutation.

Variation I

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 II

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 III

Uppdaterat
2017-05-04: Rättat till punkt 1 i crossover till att det ska vara 1 + 5.

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.

Tips

  • Spårutskrifter från systemet kommer till filen lifesimulator.log
  • Spårutskrifter från kod i BreedingFacility (via self.logger.debug(meddelande)) kommer till filen breeding_facility.log.
  • 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 -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) generera ID, 3) generera en strategy och till sist 4) generera action_sequence-strängar.

Övriga resurser


Sidansvarig: Jody Foo
Senast uppdaterad: 2017-05-10