Emergenta system, HT-05

Introduktion

På 60-talet utvecklade John Holland genetiska algoritmer för att formellt studera fenomenet adaptation i naturen och för att utveckla metoder för hur mekanismerna i naturlig adaptation skulle kunna användas i datorsystem. Sedan dess har flera olika utökningar och variationer av Holland's grundmodell utvecklats och utvärderats. Nedan ges en enkel genetisk algoritm:

1. Starta med en slumpmässigt genererad population med n stycken l-bit kromosomer (strängar)
2. Beräkna fitness, f(x), för varje kromosom, x, i populationen
3. Upprepa följande steg tills n stycken avkommor skapats:
• Välj ett par föräldrakromosomer från nuvarande population där sannolikheten för val är en ökande funktion av fitness och valet görs med återläggning
• Med viss sannolikhet utför cross-over i en slumpmässigt vald punkt i kromosomen (cross-over i mer än en punkt är också möjligt)
• Med viss sannolikhet mutera de två avkommorna i varje punkt
4. Ersätt nuvarande population med den nya
5. Gå till steg 2

Observera att ovanstående algoritm inte terminerar. För att få den att terminera kan man antingen bestämma hur många generationer som ska köras, alternativt avbryta algoritmen när en tillräckligt bra lösning hittats.

För att förstå hur emergenta egenskaper uppstår och påverkas i emergenta system är visualisering viktigt. En implementerad modell av ett system som på ett så tydligt och enkelt sätt som möjligt visualiserar det som sker i modellen är ett viktigt verktyg för att öka förståelsen för det systemet.

Laborationen ska lösas självständigt i grupper om två personer.

Syfte

Det övergripande syftet är att öka förståelsen för emergenta system. Laborationen har följande delsyften:

• Öka förståelsen för genetiska algoritmer
• Träna förmågan att visualisera emergenta egenskaper
• Stimulera till tankar kring emergenta egenskaper i system

Uppgift

Uppgiften är att på ett så tydligt och enkelt sätt som möjligt visa hur genetiska algoritmer fungerar. Det ska vara möjligt att enkelt förändra parametrar i systemet och att på något sätt se effekten av olika parameterinställningar. Mindre modifieringar av den genetiska algoritmen som gavs ovan är tillåtna.

Vilket problem ni väljer för att visualisera ovanstående är upp till er. Tänk på att er modells möjlighet till att underlätta förståelsen av genetiska algoritmer är det viktigaste.

Er modell ska vara implementerad i NetLogo. Under informationsfliken i er NetLogo-modell ska information om er modell finnas.

Tips

• Börja med att fundera ut ett problem som både går att lösa med hjälp av genetiska algoritmer och går att visualisera i NetLogo
• Låt inte NetLogo-formatet begränsa er för mycket. Ett tips kan vara att kolla runt bland de färdiga modellerna som följer med NetLogo för att få en uppfattning om vad som kan göras
• När ni väl har ett problem kan ni börja fundera på hur fitnessfunktionen, cross-over och mutation ska realiseras i ert problem
• Tänk på för att visualisera data kan även grafer, räknare och dylikt användas

Redovisning

Denna laboration ska inte redovisas med någon större rapport.

Innehåll i rapport

I er rapport ska följande punkter tas med (ta gärna hjälp av skärmdumpar):

• Ett fullständigt försättsblad
• Sökvägen till er NetLogo-kod (kan skrivas på försättsbladet)
• Reflektioner och motiveringer till de val ni gjort i samband med lösandet av uppgiften, exempelvis val av problem, val av operatorer, val av funktionalitet i gränsytan
• En kortfattad reflektion kring saker ni upptäckt själva som ni vill reflektera kring
• Utskriven dokumenterad källkod

Datum

Rapporten ska vara inlämnad senast 29 november 10.00.

Lycka till!