Opdracht 2: leren balanceren

Inleiding

De bedoeling van deze opdracht is om met behulp van een genetisch algoritme te leren een stok met daar op een dienblad in evenwicht te houden.

Uitleg

Een stok met daarop een dienblad beweegt als gevolg van fietsbewegingen. Dit is een natuurkundig proces: de artiest oefent een kracht uit op z'n fiets, de fiets versnelt, de onderkant stok versnelt mee, etc., met als effect dat een (labiel) evenwicht ontstaat. Dit labiele evenwicht volgt de wetten van de mechanica en kan (dus) worden gevangen in formules. De formules die beschrijven hoe het systeem beweegt hebben we voor je gemodelleerd. Daar hoef je je dus niet druk over te maken.

De formules die beschrijven wanneer de fietser welke kant uit moeten bewegen zijn gedeeltelijk voor je gemodelleerd. De fietser beweegt volgens een vereenvoudigd model. Hij/zij beweegt op een toneel en kan slechts twee kanten op: naar links of naar rechts. We nemen aan dat de fietser op regelmatige momenten beslist welke richting dat is. Vervolgens oefent hij/zij een bepaalde (korte) tijd een constante kracht uit in die richting. Die constante kracht zorgt er voor dat de fiets versneld. Na die korte tijd van kracht uitoefenen is er een korte tijd waarin de fietser heel eventjes geen kracht uitoefent. Daarna begint het proces opnieuw. De fietser beslist opnieuw welke kant hij/zij uit wil fietsen, vervolgens oefent de fietser korte tijd kracht uit in die richting, etc. Ook dit hoef je niet te modelleren! Maar het is wel nodig dit te weten.

De fietser neemt zijn/haar beslissingen op basis van vier gegevens: plaats, snelheid, hoek van de stok, en hoeksnelheid van de stok. Alles wordt gemeten in standaard eenheden, dus: meter, meter per seconde, radialen, en radialen per seconden. De plaats in het midden heeft x-coördinaat nul. De stok recht omhoog is 0⁰, en de hoek is positief tegen de klok in. Netlogo meet hoeken op dezelfde manier. Het enige verschil is dat wij hoeken in radialen meten (Netlogo in graden).

We nemen aan dat de artiest op elk moment dat deze een richting kiest, zijn/haar keuze laat afhangen van het teken (+ of -) van de volgende uitdrukking:

w_plaats×plaats + w_snelheid×snelheid + w_hoek×hoek + w_hoeksnelheid×hoeksnelheid,

w_plaats, w_snelheid, w_hoek, en w_hoeksnelheid.

Termen:

• Systeem Fiets + berijder + stok + dienblad.
• (Systeem-) toestand Een combinatie van: de verlopen tijd sinds start balanceer-act, de plaats, de snelheid, de stokhoek, en de hoek-snelheid van de stok. (Merk op dat versnelling en hoek-versnelling geen onderdeel uitmaken van de toestand.)
• Policy Een combinatie van vier gewichten.

Wat al voor je is geïmplementeerd

1. Fenotypen. Een fenotype representeert de systeem-toestand (en niet meer dan dat). Een fenotype is geïmplementeerd als een turtle breed waarvan de turtles bij creatie onzichtbaar worden gemaakt. Een fenotype kan niet handelen zonder genotype. De fenotype-variabele chromosoom wordt gebruikt om er een genotype in op te slaan. Als dat is gebeurd dan spreken we van een geïnstantieerd fenotype.
2. Fysica Er zijn al methoden geïmplementeerd die berekenen hoe het systeem door de tijd heen beweegt, mogelijk als gevolg van de extra kracht die de fietser op enig moment kan uitoefenen op het systeem.
3. Kracht De methode bepaal-kracht-op-basis-van-toestand bepaalt, op basis van de huidige tijd en het genotype, in welke richting de fietser kracht uitoefent.
4. Animatie De plaatjes (“sprites”) die worden gebruikt om de fietser, de stok, en het dienblad te animeren zijn al voor je aangemaakt middels turtle breeds genaamd Fiets en Dienblad. Dit zijn de enige zichtbare turtles. Ook zijn is er een methode geïmplementeerd, genaamd animeer, om het systeem te simuleren en animeren op basis van een geïnstantieerd fenotype, of op basis van de muis-cursor (hangt af van switch animeer-beste?).

Wat je nog moet implementeren

1. Genotypen. Een genotype kan worden geïdentificeerd met een policy (de vier gewichten). In Netlogo is het handig genotypen te representeren als onzichtbare turtles. Maak van genotypen een apart breed met variabelen gewicht-plaats, gewicht-snelheid, enz. Geef genotypen ook een variabele genotype-fitness.
2. Populatie. Een populatie zal (in ons geval) bestaan uit genotypen. Je mag zelf de populatiegrootte bepalen. Als genotypen worden geïntroduceerd als breed, dan is de populatie van genotypen al binnen Netlogo bekend en hoef je geen aparte lijst of container voor de populatie aan te maken.
3. Evolutie-lus Eén evolutieslag vindt plaats in een observer-methode, genaamd go:

   to go
     ; ...
   end

   go is de standaard naam voor de lus (loop) in Netlogo waarin alle actie plaatsvindt. Binnen deze evolutieslag kun je sterke genotypen met elkaar kruisen, je kunt genotypen muteren, en je kunt zwakke genotypen verwijderen. Wat je binnen deze evolutieslag doet is aan jou, en is deel van de programmeeropdracht. De go methode is gekoppeld aan een button, ook genaamd go, die op “forever” is gezet. Dus als de button is ingedrukt, wordt de evolutieslag herhaaldelijk uitgevoerd.

Aanwijzingen

Voorbeeld-implementatie. Links zie je widgets die het systeem karakteriseren. Ze staan op zinnige default-waarden en gedurende de opdracht is het niet nodig deze waarden te wijzigen. Rechts zie je widgets die te maken hebben met evolutie. De waarde van groepsgrootte wordt gebruikt voor toernooi-selectie. De betekenis van mutatiegraad wordt hieronder besproken. Per zoveel slagen wordt een histogram van de fitness getekend, met kolommen van 500 breed. Omdat een run (een simulatie) na 10,000 tijdseenheden automatisch wordt afgebroken, loopt de laatste kolom van 9,500 tot 10,000. De afgebeelde 10,500 is te danken aan Netlogo's automatische labeling van de x-as.

Hier volgen hints en tips.

1. Zelf equilibreren Het is mogelijk handmatig te equilibreren. Zet de schakelaar “animeer-beste?” uit, klik met de muis op het wit buiten de widgets, dit is om de A-shortcut van de animeer-knop te activeren. Plaats de muis-cursor op de artiest, raak de A-toets, en balanceer. Lukt het niet? Schuif Netlogo's speed slider (geplaatst boven het canvas) naar links om de animatie te vertragen.
2. Selectie Toernooi-gebaseerde selectie is eenvoudig te implementeren. Rang-gebaseerde selectie is iets moeilijker te implementeren. Fitness-gebaseerde selectie is weer wat moeilijker te implementeren. Aan jou de keuze.
3. Generatie-vrij Het is toegestaan om generatie-vrij te werken en een populatie ter plekke te veranderen door het toevoegen van kinderen, mutanten, of anderszins. Tegelijkertijd worden evenveel zwakke genotypen weggehaald om de populatiegrootte constant te houden. Een typische operatie is bijvoorbeeld het creëren van een nieuw genotype door kruising van twee maximaal fitte genotypen uit een willekeurige groep en het tegelijkertijd weghalen van het minst fitte genotype uit diezelfde groep. Het effect is dat de populatiegrootte constant blijft. Een andere typische operatie is het op enig moment muteren van een willekeurig genotype. Ook bij deze operatie blijft de populatiegrootte constant.
4. Fitness Bij het ter plekke evolueren van een populatie is het handig van elk genotype na creatie meteen de fitness te berekenen. Dus als de populatie wordt aangemaakt, bereken dan in één keer de fitness van alle elementen. Bereken daarna alleen nog de fitness van nieuw gecreëerde elementen.
5. Kruising Als je een populatie ter plekke laat evolueren, dan kan kruising op een slimme manier geïmplementeerd worden met toernooi-selectie: kies eerst een willekeurige groep (van een vaste grootte); kies dan een zwak genotype uit die groep. Kies dan twee sterke genotypen uit die groep, kruis deze, en overschrijf de attribuut-waarden van het zwakke genotype met de attribuut-waarden van de kruising. Op deze manier hoeven er geen turtles van het breed Genotype gecreëerd of verwijderd te worden.
6. Mutatie Mutatie kan op veel manieren worden geïmplementeerd. Per evolutie-slag kun je bijvoorbeeld met een bepaalde kleine kans (de mutatiegraad) een willekeurig genotype muteren, waarbij muteren dan betekent dat precies één gewicht een willekeurige nieuwe waarde krijgt. Maar een mutatie kan ook gedefinieerd worden als het aanbrengen van een kleine afwijking in een bestaand gewicht. Of het aanbrengen van een kleine afwijking in minstens één bestaand gewicht. Je ziet, er zijn veel (subtiele) variaties mogelijk. De meeste blijken te werken.

Randvoorwaarden

Hier staat wat moet. Bij afwijkingen worden punten in mindering gebracht.

Extra

• Extra punten kunnen worden verdient door het aanbrengen van zinvolle features.

Zie ook

• Netlogo raamwerk Alhier.