Opdracht 3: Maanlander

Inleiding

Probeer een maanlander zo goed mogelijk te laten landen op het maanoppervlak met behulp van genetisch programmeren. Het optimalisatiedoel is hierbij de maanlander in een zo kort mogelijke tijd met een zo laag mogelijke snelheid en zo veel mogelijk resterende benzine te laten landen.

Benodigdheden

1. NetLogo 4.1
2. Het NetLogo moonlander programma.
3. jGE extension for NetLogo 4.1 (inclusief documentatie)

Randvoorwaarden

Hier staat wat moet. Bij afwijking van randvoorwaarden worden punten in mindering gebracht.

1. Zorg dat je programma beschikt over een geschikte BNF. Maak de taal zo dat het programma slechts keuze heeft uit de volgende vier commands: if, if-else, thrust-on, thrust-off. Voor booleans kun je gebruik maken van de greater-than en smaller-than functies, samen met de height, velocity, fuel en time variabelen. Zorg dat je BNF ook geschikte willekeurige getallen kan genereren voor de boolean vergelijkingen.
2. Zorg dat je programma beschikt over een geschikte fitness functie. De fitness van een gegenereerd programma hangt af van de volgende variabelen:
   1. crashed: Als het programma de shuttle laat landen, moet de fitness substantieel hoger zijn dan in geval van een crash.
   2. velocity: Hoe lager de landingssnelheid, hoe hoger de fitness.
   3. fuel: Hoe hoger het brandstofpeil bij landing, hoe hoger de fitness.
   4. time: Hoe sneller de shuttle landt, hoe hoger de fitness (vooral bij een geslaagde landing)
   De precieze weging van de variabelen mag je zelf weten, zolang ze maar terug komen in de uiteindelijke fitness functie.
3. Zorg dat je programma beschikt over een geschikt genetisch algoritme, die met behulp van je geschreven BNF taal een populatie aanmaakt en kan kruisen. Materiaal aangeboden op het college bevat flowcharts waarop de globale werking van een genetisch algoritme wordt gespecificeerd.
4. Zorg dat parameters voor het genetisch algoritme instelbaar zijn voor de gebruiker. Denk aan de populatie-grootte, het aantal generaties, en de kruisingskansen. Zorg ook dat het beste programma wordt onthouden en dat deze kan uitgevoerd worden als de gebruiker daar om vraagt.
5. De documentatie is erg belangrijk. Leg goed uit wat het programma doet, hoe het werkt, wat geschikte parameters zijn en hoe het verbeterd kan worden.
6. De simulatie van de raket mag niet aangepast worden, zie voor de precieze werking van de simulatie het kopje 'Simulatie'.
7. Er mag niet afgeweken worden van de 'jge' library.

Waardering

(Extra) punten kunnen worden verdient door het aanbrengen van de volgende features.

1. Werking. Je model moet in de allereerste plaats goed werken. Hoe laat je dat zien? Dat kan door eerst een goed gedocumenteerde en duidelijk geoperationaliseerde definitie (maat) voor de effectiviteit van adaptatie op te stellen. Maak grafieken (zoals een plot van de fitness van het beste individu tot dan toe).
2. Overzichtelijkheid. Zorg dat je programma overzichtelijk is. Probeer je programma niet te complex te maken.
3. Optimaliteit. Een programma wat goede oplossingen vindt in weinig tijd wordt beter gewaardeerd.

Aanpak

Een mogelijke globale aanpak voor het probleem is als volgt:

1. Begin met het maken van een BNF. Het moonlander programma bevat 2 demo's, de BNF moet in ieder geval die twee programma's kunnen genereren.
2. Probeer in NetLogo met 'jge' een populatie van willekeurige genotypen te laten maken, en probeer deze ook om te zetten naar fenotypen met behulp van de gemaakte BNF.
3. Maak een fitness functie, en probeer een functie te maken die een willekeurig genotype omzet naar een fitness waarde. Om de fitness van een genotype te bepalen werk je als volgt:
   1. Zet het genotype om naar een fenotype door middel van de BNF.
   2. Plug het gegenereerde programma in simulate, bijvoorbeeld: 'simulate "thrust-on" true' plugt het programma "thrust-on" en voert deze onzichtbaar uit. Nog een voorbeeld is 'simulate "" false' wat het lege programma laat zien (wat resulteert in een crash op het maanoppervlak).
   3. Bepaal vervolgens met variablen als 'velocity' en 'fuel' de uiteindelijke fitness waarde.
   Maak nu functies om de fitness van alle individuen in een populatie te bepalen. Vanaf dit punt is het mogelijk om daadwerkelijk een flowchart te implementeren.

Verdere tips

1. De documentatie van 'jge' bevat een voorbeeldprogramma waarin enkele functies van de library worden gedemonstreerd.
2. Zet de snelheid van het programma lager om de simulatie daadwerkelijk goed te kunnen zien.
3. Het aanroepen van 'to simulate [prog hidden]' is het hoofdingrediënt voor het bepalen van de fitness van een individu.
4. De 'jge' extensie is spatiegevoelig als het gaat om genereren van een programma uit een genotype met behulp van het BNF. NetLogo heeft hier over het algemeen geen problemen mee, tenzij het gaat om getallen (want in NetLogo is '2 3' niet gelijk aan '23').
5. Fig. 2.2 uit Hoofdstuk 2 van I. Dempsey et al. (2009) Grammatical Evolution is zeer erhelderend. (Chapter 2 in: Foundations in Grammatical Evolution for Dynamic Environments, SCI 194, pp. 9-24. Springer-Verlag.)

Simulatie

Details over de simulatie (niet nodig voor het begrijpen van de opdracht):

1. De maanlander begint op 28km hoogte, met een verticale snelheid van 0m/s en een constante horizontale snelheid van 100m/s (voor de curve).
2. De gravitatie van de maan is 1.63 m/s^2. De maanlander kan thrusten wat resulteert in een acceleratie van 5m/s^2 in tegenovergestelde richting. Thrusten kost 1L/1s met een tank van 80L.
3. Bij een verticale landingssnelheid groter dan 50m/s crasht de shuttle. Bij een landingssnelheid tussen de 10m/s en de 50m/s stuitert hij met een absorptie van 80%. Bij een snelheid van 10m/s of kleiner landt hij.