Opdracht 3: het evolueren van jagers

Inleiding

Een pursuit-evasion game is een spel waarbij één of meerdere jagers een prooi proberen te vangen. Vooral in de jaren '40-'60 van de vorige eeuw werd in het kader van de koude oorlog veel geld besteed aan onderzoek naar PE games (DARPA). Tegenwoordig zijn PE games voornamelijk een curiositeit. Een PE game kan op meerdere manieren worden gemodelleerd, van concreet tot abstract. Eén modelleermethode is door simulatie met boids.

De bedoeling van deze opdracht is een genetisch algoritme te programmeren waar boids jachtgedrag wordt aangeleerd door ze te belonen bij prooivangst.

Uitleg

1. Situatie. Er zijn meerdere jagers en er is één prooi. Jagers starten allemaal op dezelfde plek en wijzen allemaal in dezelfde richting. De prooi start op een vaste plek ergens verderop, en wijst in een willekeurige richting.
2. Run. Evaluatie vindt plaats in zg. runs. Elke run bestaat uit een reeks animaties van objecten (jagers en prooi). Elk animatie-frame nemen alle objecten een klein stapje. De beweging van de prooi is voor je uitgeprogrammeerd. De beweging van elke jager wordt gestuurd door zijn [of haar] genotype. Hierover later meer, bij “chromosomen”. Als een jager zich in de buurt van een prooi beweegt, dan ontvangt deze jager per stap een relatief kleine beloning, afhankelijk van de afstand tussen hem en de prooi. Als een jager daadwerkelijk een prooi vangt, dan ontvangt de jager een (veel) grotere beloning. Daarna nemen alle objecten hun oorspronkelijke startpositie en heading weer in, en begint de jacht opnieuw. In één run kunnen dus meerdere herstarts plaatsvinden als gevolg van het vangen van een prooi.
3. Jager perceptie. Elke jager kijkt in welk hoeksegment en op welke afstand de prooi zich beweegt. Traditioneel worden 12 hoeksegmenten gebruikt (“prooi tussen 7 en 8 uur”), elk segment is dan 360/12 = 30⁰ groot; 30 heet dan de hoekresolutie. Resoluties van 60, 90 of zelfs 180⁰ komen ook voor.
   Behalve een hoeksegment neemt elke jager ook grove afstanden tot de prooi waar. Met “grove” bedoelen we machten van 2. Want voor het bepalen van een volgende actie zijn grote afstanden minder belangrijk dan kleine afstanden. Dus ..., 1/32, 1/16, ..., 1, 2, 4, ... Om er voor te zorgen dat perceptie op een vaste chromosoomlengte wordt afgebeeld worden te grote en te kleine afstanden afgeknot (tot bv. 16 en 1/16). In het laatste geval zijn er negen verschillende grove afstanden en lopen de twee-machten van -4 tot 4 (inclusief -4 en 4).
4. Chromosomen. Combinaties van hoeksegmenten en afstanden worden op een chromosoom afgebeeld. Stel dat er bijvoorbeeld vier hoeksegmenten 45 (wat de sector 0-90 afdekt), 135 (wat de sector 90-180 afdekt), 225, 315 en drie grove afstanden 1/2, 1, 2 zijn. Dan is de chromosoomlengte 4×3 = 12. Een chromosoom kan nu als volgt worden ge-adresseerd:

   [[45 1/2] [45 1] [45 2] [135 1/2] [135 1] [135 2] [225 1/2] [225 1] ...]
   

   en kan er als volgt uitzien:

   [[0.07 -9] [0.12 -3] [0.21 -7] [0.28 -2] [0.29 -3] [0.29 -4] ...]
   

5. Jager actie. Bij hoek-segment 0 en afstand 1/2 zal volgens dit chromosoom de jager -9 graden naar links draaien en daarna 0.07 eenheden vooruit bewegen. Voorwaartse snelheid wordt hier dus als eerste element genoteerd, maar als laatste beweging toegepast.
   Om het chromosoom daadwerkelijk te addresseren, moeten hoeksegmenten en afstanden zich naar opeenvolgende integers vertalen. In dit geval vertalen hoeksegmenten zich naar indices 0, 1, 2, 3 en grove afstanden zich naar indices 0, 1, 2. Het instructie-paar voor de situatie 90, 2 bevindt zich dus op index 3×1 + 2 = 5 van het chromosoom (index 5 is positie 6, we tellen vanaf 0). Code hiervoor schrijven vereist goed tellen.
6. Random allel. Een voorbeeld van een allel is [0.07 -9]. Bij aanmaak van chromosomen en bij mutaties worden random allelen ingebracht. Een random allel wordt gezien als een lijst [s a] waarbij s een willekeurige snelheid is gekozen uit een vooraf vastgesteld arsenaal van mogelijke snelheden, en a een willekeurige draai-hoek is, gekozen uit een vooraf vastgesteld arsenaal van mogelijke draai-hoeken.

Parameters

Een evolutionair algoritme staat of valt met een geschikte keuze van parameter-waarden. Het zoeken daarnaar kan (te) veel tijd kosten. Hier zijn waarden de in ons geval werkten. Het staat je vrij om andere waarden te gebruiken als je dat beter lijkt.

1. Veld. (-20 + 1 + 20)×(-16 + 1 + 16), randen geidentificeerd als torus.
2. Genetica. Populatiegrootte: 30; toernooi-gebaseerde selectie; toernooigrootte: 15; selectiegroep per toernooi: 2. Kruising van genotypen vindt plaats door middel van een card deck shuffle: één kind chromosoom onstaat door per plaats telkens een willekeurig allel van één van de ouders te nemen. Mutatie vindt plaats door elk allel van het geproduceerde kind met een bepaalde kans (genaamd de mutatiegraad) te muteren. Hier is de mutatiegraad gelijk aan 0.05.
3. Run. Een run bestaat uit het 30,000 keer animeren van de jagers en de prooi. (Dus na een run hebben alle objecten 30,000 keer bewogen.)
4. Startposities. (En herpositie na vangen prooi.) Jagers: (min-pxcor, max-pycor); allemaal dezelfde heading, te weten 135⁰. Target: (1, -1); random heading.
5. Invoer. Hoek-resolutie: 60⁰; afstand-resolutie: 2, met afstanden 2^-4, 2^-3, ..., 2⁴.
6. Uitvoer. Voorwaartse snelheid van jagers per frame: varieert van -0.10 tot 0.40, oplopend met 0.01; draaihoek van jagers per frame: geheeltalig en varieert van -9 tot 9.
7. Vangst. Als een prooi op enig moment merkt dat er jagers op minder dan 0.05 eenheden afstand zijn, dan wordt door alle jagers de prooi als gevangen beschouwd.
8. Punten. Aan het begin van elke run wordt van elke jager het puntenaantal op nul gezet. Elke animatie-stap (elk frame) krijgt elke jager, X, een aantal van 10^-6d_X^-2 punten bij zijn [of haar] huidige puntenaantal opgeteld, waarbij d_X de afstand is van X tot de prooi. Als een jager daadwerkelijk een prooi vangt dan wordt zijn [of haar, etc.] puntenaantal met 1 opgehoogd.
9. Widgets. Buttons SETUP, STEP (S), en GO (forever). Sliders voor populatiegrootte, toernooi-grootte, mutatiegraad, hoek-resolutie, en aantal frames per run. Monitor widgets voor huidige generatie nummer en winnend genotype.
10. Plots. Na iedere run wordt het gemiddelde en het maximale aantal gescoorde punten getoond in resp. grijs en roze. Omdat deze waarden nogal schokkerig verlopen worden ook zg. voortschrijdende gemiddelden en maxima bijgehouden en geplot in resp. zwart en rood. Des formule voor het voortschrijdende gemiddelde v, bijvoorbeeld, is v = 0.9 * v + 0.1 * m, waarbij m het eigenlijke gemiddelde is. Aan de plot is een slider toegevoegd om de traagheid van het voortschrijdend gemiddelde en het voortschrijdend maximum in te stellen.
11. Uiterlijk. De prooi is wit, cirkelvormig, en bezit een omvang van 0.7 (merk op dat dit veel groter dan de vangst-radius, die gelijk is aan 0.05); de jagers bezitten een kleur uit [15 25 45 16 26 46 17 27 47] (dat zijn graden van geel, oranje en rood), bezitten een default vorm en omvang van 1.2.

Randvoorwaarden

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

1. Het algoritme voor de prooi respecteren. Er wordt je een Netlogo raamwerk aangeboden waar je gebruik van kunt maken, en dat een algoritme bevat voor de beweging van de prooi. Het raamwerk is bedoeld als opstarthulp en is facultatief, dat wil zeggen dat het niet verplichtis dit raamwerk te verder in te vullen. Het algoritme voor de prooi moet echter wél worden gerespecteerd; althans het gedrag moet worden gerespecteerd.. De prooi mag bijvoorbeeld niet stilstaan of zich alleen maar in een rechte lijn voortbewegen. Anderzijds wordt afgeraden de prooi steeds te laten vluchten voor de dichtstbijzijnde jager: jagers zouden het dan erg moeilijk krijgen. (Ga zelf na waarom.)
2. Doel. Laat door middel van plots zien dat jagers door evolutie steeds beter worden. Dit zou zeker al na ongeveer 30-50 generaties het geval moeten zijn. Het geeft niet dat de plot af en toe daalt, dit hoort er bij (evolutie gaat in horten en stoten: fenotype/genotype verhaal). Maar grosso modo zou de maximale en gemiddelde fitness moeten stijgen, en zouden jagers steeds effectiever moeten worden. Dat is wat je moet laten zien. In late generaties zul je zelfs zien dat jagers evolueren op elkaars gedrag, bijvoorbeeld dat jagers evolueren op het gegeven dat er insluiting plaatsvindt.
3. Gedrag. Neem in je documentatie-tab een kopje GEDRAG op. Onder dit kopje beschrijf je hoe jouw programma zich onder default parameter-instellen gedraagt. De nakijkers weten dan wat zij kunnen verwachten en hoe lang zij moeten wachten tot je populatie acceptabel jacht-gedrag vertoont.

Aanwijzingen

Hier volgen hints en tips.

1. Bepalen van het hoek-segment. Oftewel de grove richting (in veelvouden van de (bv.) slider angle-resolution) waar in de prooi zich bevindt.

   to-report coarse-target-heading [ target ]
     ; positie van target (in graden) vanuit jager bezien; 0 is recht voor de jager, 90 is links van de jager
     let relative-target-heading subtract-headings (towards target) heading
     let coarse angle-resolution * round(relative-target-heading / angle-resolution) ; reduceer tot een grove hoek
     report coarse mod 360 ; geef grove hoek terug tussen 0 en 360 graden
   end
   

   Je kunt ook meteen de hoek (bv. 0, 30, 60) gereduceerd tot een chromosoom-index (0, 1, 2) teruggeven:

   to-report target-heading-index [ target ]
     let relative-target-heading ( towards target - heading ) mod 360
     report round(relative-target-heading / angle-resolution)
   end
   

2. Bepalen van de grove afstand.

   to-report coarse-distance-to [ target ]
     report round log (distance target) 2 ; neem de 2-log van de werkelijke afstand, en rond dat af
   end
   

3. Card deck shuffle.

   to-report cross [ genotypes ] ; één of meer genotypen; typisch twee
     let n length one-of genotypes
     let sequence n-values n [ ? ] ; sequence is nu [0, 1, 2, .., n-1]
     report map [ item ? one-of genotypes ] sequence ; map is erg handig
   end
   

4. Toernooi-gebaseerde selectie. Dit wordt uitgelegd in Wiering's dictaat, Sec. 3.2.7, blz. 54. (Zie materiaal-pagina.)
5. Snelheid. Om je app sneller te laten lopen, en om überhaupt voortgang te boeken, is het noodzakelijk tijdelijk “view updates” uit te vinken.

Wijzigingen

01 april 2019

Ge-addresseerd → ge-adresseerd.

31 maart 2019

Uitleg 4 en gedrag functie coarse-target-heading met elkaar in overeenstemming gebracht. (Beiden representeerden sectoren op een iets andere manier. Uitleg 4 via de ondergrens van een sector; de functie coarse-target-heading via het midden van een sector. Nu wordt in het hele document een sector als de middenhoek van die sector gerepresenteerd.)

Nakijkmodel

Het volgende nakijkmodel zal worden gebruikt.

   ------------------------------------------------------

    1. GUI
    2. data-structuren
    3. werking basale evolutionaire mechanismen
    4. algemene werking
    5. kwaliteit evolutie (vindt het plaats? zo ja, hoe snel?)
    6. code-organisatie (zinvolle naamgeving, kleine procedures, globale modularisering, ...)
    7. efficiëntie
    8. voortgangsregistratie (generatienummer, max/avg fitness, beste genotype)
       randvoorwaarden respect prooi en documentatie GEDRAG
    9. algemene documentatie (in code, in tab, *.png)
   10. algehele uitvoering (= extra waarderingsruimte, ter discretie beoordelaar)

       Geen punten voor extra features.
       Bij 8) staan meerdere punten om het gewicht van de afzonderlijke criteria klein
       te houden.

   ------------------------------------------------------