game maker
Gebruikersnaam:
Wachtwoord:
Home Info Forums Help
Welkom, Gast. Alsjeblieft inloggen of registreren.
De activerings e-mail gemist?
+  Forums
|-+  Werken met Game Maker
| |-+  Tutorials en Uitbreidingen (Moderator: Maarten Baert)
| | |-+  [Tut+Exa+Lib] Genetische algoritmen
Pagina's: [1] 2
« vorige volgende »
Print
Advertenties

kaasje
Globale moderator


Offline Offline

Berichten: 2301


« Gepost op: 26 Mei 2013, 00:08:27 »

Genetische algoritmen
Theorie, BNFs, example en extensie

GM versie: Theorie en gex: elke versie, example: GameMaker 8.1 en lager (GEEN GMStudio)
Pro vereist: Nee
Niveau: Gevorderd/expert

In deze tutorial bespreek ik het fenomeen ‘genetische algoritmen’ (GA’s). Om genetische algoritmen te gebruiken in Game Maker heb ik speciaal voor deze tutorial een extensie om GA’s in te schrijven gemaakt. Naast de example en de extensie, behandel ik ook de algemene theorie van GA’s.

Inhoudsopgave:

1. Inleiding
  • 1.1 Waarom schrijf ik dit/voorwoord
  • 1.2 Wat is een GA?
2. Biologische theorie
  • 2.1 Genetica en evolutie
  • 2.2 Genetica: mutatie
  • 2.3 Genetica: cross-over
3. Uitwerking in de informatica
  • 3.1 Algemeen idee
  • 3.2 Representatie van het genotype
  • 3.3 Representatie van het fenotype
  • 3.4 Van genotype naar fenotype
  • 3.5 Evolueren
4. Toepassing
  • 4.1 Toepassingen in Game Maker
  • 4.2.Nadelen
5. GMGenetics
  • 5.1 Download en example
  • 5.2 Documentatie
  • 5.3 Geplande verbeteringen en changelog


1. Inleiding

1.1 Waarom schrijf ik dit?
Sinds een jaar studeer ik Kunstmatige Intelligentie aan de Universiteit Utrecht. Natuurlijk bestaat het eerste jaar voornamelijk uit voorkennis verzamelen. Pas in het dit blok (het laatste blok) krijg ik een vak wat zich enigszins met intelligentie bezighoudt: Inleiding Adaptieve Systemen. Zoals de naam doet vermoeden, gaat dit over geprogrammeerde systemen die zichzelf aanpassen (‘machine learning’). Eén van de onderwerpen die tijdens dit vak voorbij is gekomen, is genetische algoritmen. Ik was best wel enthousiast en de theorie is in principe niet heel moeilijk, maar wel erg geniaal. In Game Maker ben ik begonnen met het schrijven van een eigen GA, waarna ik besloot er een tutorial over te schrijven. Ten eerste omdat het een interessant onderwerp is. Ten tweede omdat ik heel erg benieuwd ben hoe jullie dergelijke algoritmen zouden implementeren in games. Ik denk namelijk dat daar heel veel vets uit kan komen en tja, als Best of redacteur moet ik toch af en toe iets vernieuwends zien.

1.2 Wat is een GA?
Ik kan me voorstellen dat jullie nog nooit van een genetisch (of: evolutionair) algoritme gehoord hebben. Een genetisch algoritme (GA) is een programma dat, met het idee van de evolutietheorie in het achterhoofd, als het ware ‘eigen code schrijft’ om zo complex (‘intelligent’) gedrag toe te kennen aan een agent.

Jullie volgende vraag zou prima kunnen zijn: “Wat heeft dat in godsnaam met de evolutietheorie te maken?”
In GA’s vervullen genetica en evolutie een belangrijke rol. Het punt is namelijk dat de programma’s die een GA ‘schrijft’ zolang evolueren tot ze gewenst gedrag vertonen of goed genoeg zijn.  Hierop wordt dieper ingegaan in de volgende hoofdstukken.

Een leuke laatste vraag die jullie me kunnen stellen, zou zijn: “Wat kan je hier mee?”
Hoewel ik de toepassing in Game Maker later in de tutorial bespreek, is het inderdaad nuttig om de toepassing van GA’s te kennen. Je zou GA’s in Game Maker kunnen gebruiken om zelflerende AI’s te schrijven (AI’s die zich bijvoorbeeld aanpassen op het gedrag van de speler, of die tactieken vinden om de speler uit te schakelen). In de praktijk worden GA’s gebruikt om machines, bijvoorbeeld robots, bepaald gedrag aan te leren. Een robot zou met een GA kunnen leren lopen.
Als laatste zijn GA’s gewoon ontzettend leuk om mee te experimenteren. Zeker programmeurs kunnen er denk ik wel leuke dingen mee doen.



2. Biologische theorie

Nu jullie een abstract beeld hebben van wat een GA is, is het tijd om de theorie achter GA’s te bespreken. Deze theorie zal niet zozeer op informatica gericht zijn. De uitwerking van de theorie in computers, lees je in het volgende hoofdstuk. Dit hoofdstuk zou zelfs meer ‘biologisch’ dan ‘technisch’ genoemd kunnen worden. Degenen die erfelijkheid, evolutie en genetica behandeld hebben op school, kunnen ervoor kiezen dit hoofdstuk over te slaan.

2.1 Genetica en evolutie
Elk organisme dat op deze aarde rondloopt is opgebouwd uit genen. Genen zijn een soort blauwdruk van je lichaam; ze bepalen bijvoorbeeld je oogkleur, maar ook je karakter kan beïnvloed zijn door je genen. Je hebt je genen gekregen van je ouders. Jouw genen zijn een mix van de genen van je moeder en de genen van je vader. In de realiteit zijn genen in paren verdeeld, maar omdat dat verder niet heel belangrijk is voor GA’s, zullen we dat niet bespreken. Welke genen je in je lichaam hebt, noemen we genotype. Een ‘rij’ genen heet een chromosoom. Aan de buitenkant van een organisme is niet af te leiden welk genotype dat organisme heeft, of hoe de chromosomen van dat individu eruit zien.

Je zou genen kunnen zien als een soort ‘codering voor eigenschappen’. Eigenschappen die tot uiting komen (oogkleur, karakter, etc.) noemen we fenotype. Het fenotype is afhankelijk van het genotype en invloeden van buitenaf.

In de negentiende eeuw bracht de welbekende bioloog Charles Darwin zijn boek The Origin of Species uit. In dit boek ging Darwin diep in op het begrip natuurlijke selectie. Waar natuurlijke selectie op neer komt, is dat alleen de sterkste individuen met de beste eigenschappen (= met de beste genen/de beste genotypen) overleven. Dit wordt survival of the fittest genoemd. Doordat alleen de fitste individuen overleven, is de kans ook groter dat de fitste individuen voortplanten. Ofwel, na elke generatie wordt een soort of populatie ietsje beter, omdat alleen de beste genen worden doorgegeven. Op deze manier evolueert een soort (of populatie) heel langzaamaan tot een betere soort. Dit is natuurlijk een proces dat niet bij je kleinkinderen al te merken is; evolutie neemt in de praktijk miljoenen jaren in beslag.



2.2 Genetica: mutatie
Een vraag die je je nu zou kunnen stellen, is: hoe komen er opeens nieuwe eigenschappen tevoorschijn? Dat er ooit, miljoenen jaren geleden, alleen maar vissen waren, en dat die vissen ontwikkeld zijn tot de huidige mens, is moeilijk voor te stellen. Nieuwe soorten ontstaan niet zomaar. Volgens de evolutietheorie zouden deze vissen ooit geëvolueerd moeten zijn in mensen, vogels, slangen en tijgers. Dat wil zeggen, door voortplanting van de sterkste individuen, zouden de vissen waar wij nu fossielen van vinden, ooit benen, vleugels en longen moeten hebben gekregen.

Dit is natuurlijk raar. Was er een soort ‘verborgen eigenschap’ voor vleugels of benen die niet tot uiting kwam in de vissen? Dat klinkt niet logisch, want als die eigenschap niet tot uiting kwam in eerste instantie bij geen enkele vis, is het onmogelijk (voor zover we nu weten) dat de eigenschap wel tot uiting komt bij het nageslacht van die vis. Immers, als twee vissen zonder benen nageslacht produceren, kan het niet zo zijn dat de kinderen van de twee opeens wel benen hebben.

Hoe zit dit dan? Heel simpel gezegd: door een foutje in de natuur. Het kan zo zijn dat genen tijdens ontwikkeling van een ongeboren individu per ongeluk ietsje veranderen. Als we een genotype G bekijken als rijtje cijfers, waarbij elk cijfer voor een bepaalde eigenschap staat, zou dat er zo uit zien:

G:  1 2 3 4 5 6
G’: 1 2 3 9 5 6


Hierin is G het genotype van het kind zonder verandering, en G’ het genotype met verandering. Zo’n verandering noemen we een mutatie. In de praktijk is het zo dat een mutatie in een groot aantal van de gevallen geen probleem is en niet tot uiting komt in het fenotype. In een klein aantal gevallen, echter, zorgen mutaties wel voor verandering in het fenotype. In een groot deel van die gevallen, leiden mutaties tot een biologisch nadeel (onvruchtbaarheid, gebrek aan eiwitten, etc.). In slechts een heel klein deel van de gevallen, leiden mutaties tot een biologisch voordeel. Een mutatie zou er bijvoorbeeld voor kunnen zorgen dat je beter kunt zien in het donker, of dat je – als vis – longen, benen of vleugels krijgt.

Doordat het gemuteerde individu in dat geval blijkbaar sterker is, worden de gemuteerde genen overgebracht in het nageslacht. De positieve eigenschap blijft op die manier dus behouden.



2.3 Genetica: cross-over
Zoals ik al eerder zei, heb jij de genen van je ouders geërfd. Jouw vader en moeder hebben allebei verschillende genotypen en jij hebt een ‘mix’ van die twee genotypen in je lichaam zitten.
Stel, dit zijn de genotypen van je ouders:

M: 0 1 2 3 4 5
V: 5 6 7 8 9 0

(waarin M = genotype moeder, en V = genotype vader)

Toen jij gemaakt werd, zijn deze twee genotypen gemengd. Het ‘mengen’ van twee genotypen noemen we cross-over. Hier zitten natuurlijk wat regeltjes aan vast. Het is niet zo dat de genen van je ouders willekeurig door elkaar gehusseld zijn om zo een nieuw genotype teweeg te brengen.

Bij cross-over worden twee genotypen op dezelfde plek doormidden geknipt. De twee ‘afgeknipte stukjes’ worden vervolgens ‘omgewisseld’. Een voorbeeld:

M: 0 1 2 3 | 4 5
V: 5 6 7 8 | 9 0

K: 0 1 2 3 9 0


Het kind K bevat nu van zowel M als V genen. Het is belangrijk dat de knip op dezelfde plek gebeurt, omdat een chromosoom anders langer wordt (dat kan gebeuren bij mutatie en kan dan ook de gevolgen hebben van een mutatie). Op deze manier krijg jij als het ware een mix van de genotypen van je ouders.

Tot zover is kennis van genetica en evolutie vereist. Natuurlijk zit alles in de realiteit wat ingewikkelder en minder zwart-wit in elkaar. Voor het begrijpen van GA’s is deze basiskennis echter voldoende.



3. Uitwerking in de informatica

Dit hoofdstuk bevat de uitwerking van evolutie en genetica vanuit de informatica. Dit hoofdstuk is nog steeds theoretisch, maar op de werking GA’s gericht. Dit hoofdstuk bevat geen codes of voorbeelden, maar beschrijft de werking van een GA. In het laatste hoofdstuk laat ik een praktisch voorbeeld van een GA in Game Maker zien. Merk overigens op dat de manier die ik beschrijf om een GA te maken, niet de enige manier is om een GA te maken.

3.1 Algemeen idee
Hoewel er nog mensen zijn die Darwins evolutietheorie in twijfel trekken, is het, ongeacht of de theorie juist is of niet, een interessant idee om evolutie te implementeren in een zelflerende machine. Het mooie is dat, met de hedendaagse techniek, we evolutie van een intelligentie, in vergelijking met de evolutie van bijvoorbeeld de mens, ontzettend kunnen versnellen. Dat is precies wat een GA doet: we laten een algoritme evolueren, totdat we een programma hebben met ‘sterke genen’ – ofwel, een programma dat doet wat we willen.

Hoe gaat dit te werk? Verbluffend genoeg net zoals de evolutie die Darwin beschreef. We laten de computer een willekeurige set genen maken en kijken welke daarvan het sterkste is. Het sterkste genotype gaan we dan door middel van mutatie en cross-over evolueren. Het idee hiervan is dat we op een gegeven moment een genotype hebben dat exact doet wat we willen.

Natuurlijk is dit nog een beetje abstract. Immers, hoe kunnen we ervoor zorgen dat een set genotypen ook iets voor elkaar krijgt? Hoe representeren we de genen van een individu? Hoe zetten we deze genen om in uitvoerbare code (hoe zetten we een genotype om in een fenotype)? En hoe bepalen we welk individu (of, welk genotype) het sterkste is?

Er zijn meerdere manieren om een GA te maken. Daarom zijn er ook meerdere antwoorden op de bovenstaande vragen. De manier die ik beschrijf zal gebruik maken van begrippen uit de taalkunde. Waarom dat een goede benadering is, zal blijken uit de rest van dit hoofdstuk.
 
Voordat we dieper de theorie van de GA’s in duiken, zou ik graag een globaal stappenplan geven van hoe een GA in elkaar zit. Hiervoor werken we met populaties (= groepen individuen met eventueel een ander genotype) en agenten (= een individu). Eerst zal ik het stappenplan geven, en daarna zal ik er dieper op in gaan.

1. Maak een populatie aan met willekeurig gegenereerde individuen;
2. Laat elk individu een test afleggen en hou bij hoe goed dit individu de test aflegt;
3. Als elk individu uit de populatie geweest is, evolueer de populatie op basis van de fitness;
4. Ga met de nieuwe populatie terug naar stap 2, totdat er een individu is dat aan de eisen voldoet.

Stap één lijkt me vanzelfsprekend. We hebben een populatie nodig met een grootte meer dan 1. Dat wil zeggen, genereer een aantal willekeurige genotypen. Deze genotypen zullen getest worden en met deze genotypen worden vervolgens cross-overs en mutaties gedaan.

Stap twee is de testfase van een genotype. Laat een agent een bepaalde test afleggen (elke agent dezelfde test!) en bekijk hoe goed een bepaalde agent met een bepaald genotype presteert. De mate waarin een agent goed presteert noemen we de fitness van een agent. In het algemeen kan je zeggen: hoe hoger de fitness, hoe beter de agent gepresteerd heeft. En hoe beter een agent gepresteerd heeft, hoe beter het genotype van die agent is.

Stap drie is veruit de moeilijkste stap. Alle genotypen in de populatie hebben de test afgelegd. Nu is het tijd om de genotypen te evolueren. Dit evolueren gaat aan de hand van de fitness van een bepaald genotype. Hoe beter het genotype, hoe groter de kans is dat het genotype in de volgende generatie te vinden is. Het genotype dat het best presteerde noemen we de winnaar. De winnaar is sowieso in de volgende generatie te vinden. Met behulp van kansen vullen we een nieuwe populatie met gemuteerde en gecross-overde genotypen. We gaan hier dieper op in in de komende paragrafen.

Stap vier is een check of de winnaar voldoet aan de vooraf gestelde eisen (bijvoorbeeld: leg een bepaald pad in minder dan tien seconden af). Ofwel, is het doel bereikt? Zo ja, dan zijn we klaar en is dit genotype het eindresultaat. Zo nee, dan moet er nog meer geëvolueerd worden, totdat het doel wel bereikt is.

Dit is een heel globaal stappenplan van hoe een GA in elkaar zit. Naarmate dit hoofdstuk vordert, zullen we het stappenplan uitbreiden en verder bespreken.



3.2 Representatie van het genotype
Omdat we agenten gaan evolueren, hebben we voor elke agent een genotype nodig. Met dit genotype gaan we cross-overs doen met andere agenten. Elk genotype moet dus op een bepaalde manier gelijkvormig zijn, zodat ze te combineren zijn met de genotypen van andere agenten.

In dit GA kiezen we voor de representatie van genotypes door middel van bitstrings. Dit zijn strings die bestaan uit enkel nullen en enen. Merk op dat zowel mutaties als cross-overs makkelijk te realiseren zijn met bitstrings:

G:  0 0 0 0 0 0
G’: 0 0 0 1 0 0

Mutatie

P1: 0 0 | 0 0 0 0
P2: 1 1 | 1 1 1 1
K1: 0 0 1 1 1 1
K2: 1 1 0 0 0 0

Cross-over. Merk op dat een cross-over leidt tot twee kinderen.

Bij GA’s hebben genotypen over het algemeen dezelfde lengte. Oftewel, bij cross-over moet er nog steeds vast ‘knippunt’ zijn. Hoewel dit een keuze kan zijn, zal blijken dat cross-overs zonder vast lengte kunnen leiden tot zeer beperkt gedrag. Meer daarover in de paragraaf ‘Evolueren’. Tevens zal ik daar ook beschrijven waarom we bitstrings gebruiken en geen strings met willekeurige getallen erin.



3.3 Representatie van het fenotype
Bij organismen vallen alle waarneembare eigenschappen van een individu onder het fenotype. Bij agenten, echter, definiëren we het fenotype als ‘de code die een agent uitvoert om bepaald gedrag te vertonen.’

Als we agenten hebben die enkel naar voren, naar achteren, naar links en naar rechts kunnen bewegen, zou een fenotype kunnen zijn:
Code:
move_forward();
move_left();
move_forward();
Waarin move_forward() en move_left() functies of scripts zijn.

We moeten natuurlijk op een bepaalde manier kunnen definiëren wat wel en niet onder een fenotype valt. Hiervoor maken we gebruik van een BNF. BNF staat voor Backus-Naur Form. Een BNF is een zogeheten Context Free Grammar (CFG – contextvrije grammatica). Met een CFG kun je definiëren wat wel en niet onder een bepaalde grammatica valt. Een CFG bestaat uit een aantal regels met terminale en non-terminale symbolen (‘terminals’ en ‘non-terminals’). Voor non-terminale symbolen is altijd een bepaalde regel waarmee je het non-terminale symbool omzet in een terminaal symbool. Een terminaal symbool is een deel van het eindresultaat; er is geen regel waarmee je het terminale symbool kan omzetten naar een ander (non-)terminaal symbool. Je bereikt een eindresultaat (of: eindstaat) als er geen non-terminale symbolen meer aanwezig zijn. Je start altijd met een bepaalde non-terminal en gaat vanuit daar afleiden wat de CFG bevat.
Een voorbeeld-CFG:
Code:
S --> aSa|b
Een sluisteken ( | ) staat voor ‘of’. Het startsymbool is S.

We beginnen dus met een S, een non-terminaal symbool, en volgen dan de regel. We zien dat een S ofwel aSa, ofwel b kan afleiden. Stel, we kiezen voor aSa, dan vervangen we het startsymbool voor aSa. Volgens vragen we ons af of er nog een non-terminaal symbool aanwezig is in ons resultaat. Die is er, namelijk: weer een S. We zoeken voor deze S een nieuwe regel en vinden weer de regel S --> aSa|b. We kiezen nu b voor S en vervangen de S in de aSa die we verkregen hadden in een b. Dat resulteert in de string aba. Hier staan geen non-terminale symbolen meer in, dus we zijn klaar. Immers, voor a en b zijn geen regels. Intuïtief kan je zien dat deze grammatica alle strings die beginnen met n keer een a, dan één b, en dan weer n keer een a kan genereren.

Dit kan je natuurlijk zo ingewikkeld maken als je zelf wilt. Een BNF is bijna hetzelfde als een CFG. Een voorbeeld van BNF zou kunnen zijn (met startsymbool <ACTION> – bij een BNF is de bovenste regel altijd het startsymbool):
Code:
<ACTION> ::= move_forward()|move_left()|move_right()|move_backward()
In dit geval genereert deze BNF alleen maar de vier terminals move_forward(), move left(), move_right() en move_backward(). Merk op dat deze terminals meer zijn dan alleen symbolen: het zouden functies kunnen zijn! Je vult je BNF dus met opdrachten voor je agent. Je kan hier bijvoorbeeld prima iets neerzetten in de trant van motion_set(90,4).

We kunnen het echter wat interessanter maken door meer non-terminale symbolen toe te voegen (met startsymbool <ACTION>):
Code:
<ACTION> ::= move_forward()|move_right()|if (<CONDITION>) { <ACTION> } else { <ACTION> }
<CONDITION> ::= <DIGIT> != <DIGIT>|true|false
<DIGIT> ::= 1|2|3|4|5|6|7|8|9|0
Dit is al een veel interessantere BNF. Deze BNF genereert bijvoorbeeld:
Code:
if (2 != 3) { move_forward() } else {move_right() }
Een schematisch overzicht van hoe deze eindstaat gegenereerd is:
1. Begin met startsymbool <ACTION> en kies if (<CONDITION>) { <ACTION> } else { <ACTION> }
2. De eerste non-terminal die we tegenkomen, is <CONDITION>, kies iets uit het rijtje <CONDITION>, bijvoorbeeld <DIGIT> != <DIGIT>. Ons resultaat wordt nu: if (<DIGIT> != <DIGIT>) { <ACTION> } else { <ACTION> }
3. De eerste non-terminal die we tegenkomen is <DIGIT>, kies iets uit het rijtje <DIGIT>, bijvoorbeeld 2. Ons resultaat wordt nu: if (2 != <DIGIT>) { <ACTION> } else { <ACTION> }
4. De eerste non-terminal die we tegenkomen is weer <DIGIT>, kies iets uit het rijtje <DIGIT>, bijvoorbeeld 3. Ons resultaat wordt nu: if (2 != 3) { <ACTION> } else { <ACTION> }
5. De eerste non-terminal die we tegenkomen is <ACTION>, kies iets uit het rijtje <ACTION>, bijvoorbeeld move_forward(). Ons resultaat wordt nu: if (2 != 3) { move_forward() } else { <ACTION> }
6. De eerste non-terminal die we tegenkomen is <ACTION>, kies iets uit het rijtje <ACTION>, bijvoorbeeld move_right(). Ons resultaat wordt nu: if (2 != 3) { move_forward() } else { move_right() }
7. We komen geen non-terminals meer tegen, dus we hebben onze eindstaat bereikt. De gegenereerde string is: if (2 != 3) { move_forward() } else { move_right() }

Merk op dat ook de volgende strings gegenereerd kunnen worden:
Code:
move_forward()

if (8 != 8) { move_right() } else { move_right() }

if (0 != 5) { if (4 != 4) { move_right() } else { move_right() } } else { move_right() }

if (2 != 7) { if (2 != 7) { if (2 != 7) { move_right() } else { move_right() } } else { move_forward() } } else { move_right() }
Het bereik van deze BNF is in theorie oneindig, omdat elke <ACTION> met een if (…) kan worden ingevuld.

Voor het GA wat wij gaan bespreken is het belangrijk om BNFs te snappen. De BNF zal ons fenotype gaan representeren. Een kleine fout in je BNF kan resulteren in vreemde of langdradige resultaten. In het de volgende paragraaf gaan we bitstrings aan BNFs koppelen om zo door middel van een genotype een fenotype te creëren.  



3.4 Van genotype naar fenotype
Nu we de twee gereedschappen hebben om genotypen en fenotypen mee te representeren, wordt het tijd om duidelijk te maken hoe we een genotype in een fenotype omzetten. Dit zal ik doen aan de hand van een aantal voorbeelden.
We hebben een agent met genotype 0001 en we gebruiken de BNF:
Code:
<ACTION> ::= move_forward()|turn_left()|turn_right()|move_backward()
Je zou de BNF kunnen zien als een lijst met elementen. De lijst met naam <ACTION> heeft de elementen move_forward(), turn_left(), turn_right() en move_backward(). Elk element heeft een bepaalde index in de lijst, beginnend bij 0. Het element met index 2 is bijvoorbeeld move_backward().

Als we BNFs op deze manier bekijken, gaat er wellicht direct een belletje rinkelen. We zouden de bitstring die we als genotype gebruiken kunnen opdelen om zo lijstindexen te krijgen. Door (een deel van) de bitstring om te zetten in een decimaal getal, krijgen we een prima index. Als we dus het fenotype voor onze agent met genotype 0001 bepalen, zetten we 0001 om in een decimaal getal: 1. Vervolgens starten we met ons startsymbool <ACTION> . We kijken op index 1 van de lijst voor <ACTION> en vinden daar turn_left(). Daar staan geen non-terminals meer in, dus we zijn klaar. Het fenotype van deze agent is enkel turn_left().

Tot zover geen probleem. Echter, wat gebeurt er als onze agent genotype 1010 zou hebben? Dit is 10 in decimaal stelsel. Het tiende element van de lijst <ACTION> bestaat niet en nu hebben we een probleem. We lossen dit op door het verkregen decimale getal modulo de lengte van de lijst te doen. Onze lijst heeft in totaal 4 elementen, dus krijgen we nu 10 mod 4 = 2. We krijgen nu fenotype turn_right().

In ons bovenstaande voorbeeld, echter, zit iets wat niet zo elegant is. We hebben een bitstring van lengte 4 en een BNF met enkel een startsymbool met vier regels. Onze bitstring staat echter toe om 24 = 16 lijstindices te hebben. Hiervan worden er slechts 4 gebruikt. De overige 12 indices die wel bereikt kunnen worden, maar niet bestaan, zijn dus eigenlijk overbodig. Om deze reden zouden we onze bitstring op willen delen in stukjes van 2 (immers, 22 = 4, en dat is precies het aantal regels dat we hebben). Deze stukjes noemen we codons. Elk codon heeft een vaste lengte – in dit geval dus 2. Het genotype van onze eerste voorbeeldagent heeft dus twee codons: 00 en 01. In dit geval is ons fenotype dus ook enkel move_forward() (00 is index 0 = move_forward() – hierin zitten geen non-terminals in, dus we zijn klaar).

Als we nog een regel aan <ACTION> toe zouden voegen in onze BNF, bijvoorbeeld look_ahead(), dan zou onze BNF vijf regels hebben. Met een codongrootte van 2 zal deze vijfde regel nooit bereikt worden (het maximum is 11 = 3, en de index van de vijfde regel is 4). We zullen de codongrootte dus groter moeten maken om alle regels te kunnen omvatten. Stel, we maken onze codongrootte nu 3, dan is het maximum aantal regels 23 = 8; meer dan het aantal regels dat we hebben. Maar dat is geen probleem, want we kunnen gewoon weer de modulo nemen om binnen de elementen van de lijst te blijven. Nu omvatten we dus alle regels, én hebben we een zo klein mogelijke codonsize.

Nu we dit simpele voorbeeld bekeken hebben en de basis van het converteren van bitstring naar fenotype begrijpen, beschouwen we een moeilijker voorbeeld.
We nemen een agent met genotype 0010 en codongrootte 2.
Daarnaast hebben we een BNF als volgt:
Code:
<ACTION> ::= move_forward(); <ACTION>|turn_left(); <ACTION>|turn_right()|move_backward()
We gaan nu het fenotype van deze agent bepalen. We beginnen met de eerste codon: 00. Ons fenotype wordt nu move_forward(); <ACTION> (de regels lopen tot de sluistekens – je kan dus twee commando’s geven met één lijstindex). Zoals je ziet, zijn we nu nog niet klaar. Immers, er staat nog een non-terminal in ons fenotype. We gaan dus verder kijken. Het eerste codon hebben we gehad, dus nu gaan we naar het tweede codon: 10. 10bin verwijst naar het tweede element, dus turn_right(). We vullen nu turn_right() in voor <ACTION> in ons eerder verkregen resultaat en krijgen fenotype move_forward(); turn_right(). Er staan nu  geen non-terminals meer in ons fenotype, dus we zijn klaar.

Dit gaat hetzelfde voor non-terminals anders dan het startsymbool. Bezie nogmaals dezelfde agent, maar nu met BNF:
Code:
<ACTION> ::= move_forward(); <TURN>|move_backward(); <TURN>|move_forward()|move_backward()
<TURN> ::= turn_left()|turn_right()
We starten weer met het eerste codon, 00. Dit levert move_forward(); <TURN> op. We gaan naar het tweede codon, 10, maar nu kijken we niet in de <ACTION> lijst, maar de <TURN> lijst (immers, ons resultaat vraagt om iets voor de non-terminal <TURN>).
10bin = 2dec, dus kijken we op index 2 van de lijst <TURN>. De lijst heeft echter maar twee regels en element 2 bestaat niet in de lijst. Nu wordt de modulo van de lijstlengte van <TURN> genomen om te berekenen welk element aangesproken wordt. 2 mod 2 = 0, dus we nemen element 0 uit <TURN>: turn_left(). Ons eindresultaat wordt: move_forward(); turn_left().

Er gelden dus twee regels:
1. Voor het bepalen van de codongrootte zorg je ervoor dat dat alle regels bereikt kunnen worden. Als je twee tot de macht van de grootte van je codon neemt, moet die uitkomst groter dan of gelijk zijn aan de non-terminal met de meeste regels.
2. Indien een codon codeert naar een decimaal getal groter dan of gelijk aan het aantal elementen in een lijst van non-terminal regels, dan doe je de index modulo de lengte van de lijst om binnen de lijst te blijven.

Er is nog één geval waar we het niet over gehad hebben: wat als je bitstring ‘op’ is?
Bezie een agent met genotype 0001 en codonsize = 2 en de BNF:
Code:
<ACTION> ::= move_forward(); <ACTION>|turn_left(); <ACTION>|turn_right()|move_backward()
Als we beginnen met het eerste codon krijgen we move_forward(); <ACTION>. We kijken naar het tweede codon en vinden 01. We vervangen <ACTION> en krijgen nu: move_forward(); turn_left(); <ACTION>.
Er staat nog een non-terminal in het resultaat, dus willen we verder kijken. We kijken naar het volgende codon en zien… dat dat codon niet bestaat; het einde van de bitstring is bereikt.
In dit geval kan je twee dingen doen. Als eerste kan je zeggen: dit fenotype is incompleet, ik gooi hem weg en geef deze agent een hele lage fitness. Een tweede optie is om het genotype te ‘wrappen’. Ofwel, als het einde van de bitstring bereikt is, begin dan gewoon weer van voor af aan (in dit geval dus weer het codon 00). Merk op dat dat in dit voorbeeld niets uit zal halen, maar in complexere BNFs kan dit zeker het verschil maken.

We zijn nu in staat om genotypen om te zetten in fenotypen. Deze fenotypen zijn dus codes die een agent (bijvoorbeeld een object in Game Maker) kan uitvoeren.



3.5 Evolueren
Een zeer belangrijke stap in ons GA-stappenplan is natuurlijk evolutie. Hierin moeten we echter niet te gehaast zijn. We moeten een reden hebben om een bepaalde agent met een bepaald genotype te kiezen om verder te laten evolueren.

Voordat je kan gaan evolueren, moet je elke agent een fitness toekennen. De fitness van je agenten wordt berekend aan de hand van een fitnessformule. Aangezien de fitnessformule voor elke toepassing anders is, is het moeilijk om die te generaliseren. Ik zal een simpele fitnessformule geven aan de hand van een voorbeeld.

Stel, je hebt een genetisch algoritme gemaakt dat de weg moet vinden door een doolhof. Agenten zoeken hun weg door een doolhof, totdat ze bij de finish terecht komen. Dit moet binnen een bepaalde tijd gebeuren (zeg, één minuut). Als de agent niet binnen de tijd bij de finish komt, is de volgende agent aan de beurt. Verder houdt de agent bij welke vakjes hij al bezocht heeft (vakjes van 32*32).
Met een complex doolhof kan je nu niet verwachten dat de agent bij de eerste generatie direct bij de finish komt.  Sterker nog, met het simpelste doolhof kan je dat al niet verwachten.
Je zou de fitness kunnen berekenen aan de hand van het aantal vakjes dat de agent bezocht heeft. Immers, hoe meer vakjes de agent bezocht heeft, hoe meer hij gebieden hij onderzocht heeft. Dit is natuurlijk positief, want we willen dat de agent de finish vindt, en dat kan alleen door het doolhof te verkennen.
Een voorbeeld van een fitnessformule voor dit geval zou kunnen zijn: (aantal bezochte vakjes)/(aantal totale vakjes) + (tijd over). Dit is het percentage bezochte vakjes, plus de tijd die de agent eventueel over heeft. Merk op dat de agent alleen tijd over heeft als hij de finish bereikt.

Je kan je voorstellen dat de fitnessformule erg belangrijk is voor het GA. Een ongebalanceerde formule zou ervoor kunnen zorgen dat een agent die beter is, door de fitnessfunctie slechter wordt bestempeld. Dat wil je niet! Denk dus goed na over je fitnessformule.

Nadat alle agenten aan de beurt zijn geweest en een fitness hebben gekregen, gaan we de populatie evolueren. Dit gebeurt op basis van de fitness van een agent. Een agent met een hogere fitness, heeft meer kans om gekozen te worden om te evolueren. Daarnaast is een voorwaarde wel dat alle agenten een kans moeten hebben om te evolueren, ook als de agent compleet waardeloos gepresteerd heeft.

Voor de zekerheid doen we alvast één ding: de agent met de hoogste fitness aan de nieuwe, geëvolueerde populatie toevoegen. Mocht de rest van de geëvolueerde populatie tegenvallen, dan hebben we in ieder geval de genen van de oude winnaar nog. Zo zorgen we er steeds voor dat we niet terugzakken naar een slechtere populatie.

Als we de winnaar aan de nieuwe populatie hebben toegevoegd, moeten we de nieuwe populatie bijvullen met gemuteerde, gecross-overde en gekopieerde genotypen. Voor elk ‘plekje’ in de nieuwe populatie kiezen we of we dat plekje willen opvullen met een gemuteerd, gecross-overd of gekopieerd genotype. Na paragraaf 3.4 is het duidelijk wat voor een (soms ingrijpende) veranderingen een mutatie of crossover teweeg kan brengen. Immers, een verandering in de bitstring zorgt voor een verandering in de gekozen lijstindex (= ander fenotype). We nemen voor nu even de volgende kansen:

Kans op mutatie: 30%
Kans op crossover: 60%
Kans op reduplicatie (kopie): 10%

Er is één ding wat deze drie dingen gemeen hebben: alle drie vereisen ze een bepaalde agent waarmee gewerkt gaat worden. Het selecteren van agenten gaat bij alle manieren op dezelfde manier.

Hoe hoger de fitness van een agent, hoe groter de kans is dat deze agent gekozen wordt voor een handeling. Stel, we hebben een populatie van 5 agenten met de volgende genotypen en fitnesses:

Agent 1: G: 001011 F: 0,5
Agent 2: G: 110100 F: 2
Agent 3: G: 101010 F: 0,8
Agent 4: G: 010101 F: 1,3
Agent 5: G: 111000 F: 0,1

Het idee is dat je nu van deze vijf agenten een cirkeldiagram maakt en daar (random) een dartpijltje op gooit. De agenten met een hogere fitness, hebben een groter oppervlak op het cirkeldiagram en derhalve is de kans groter dat het dartpijltje in het oppervlak van die agent terecht komt.

Helaas kunnen computers geen dartpijltjes gooien. Er zijn een aantal manieren om dit in te programmeren. Een aantal methoden vind je in dit topic. Ik zal niet dieper ingaan op het uitkiezen van agenten. Het is overigens niet zo dat elke agent slechts één keer gebruikt kan worden om te evolueren. Telkens als je een agent moet kiezen, gooi je een nieuw pijltje op het cirkeldiagram. De kansen blijven dus telkens even groot, ongeacht hoe vaak je nu een agent kiest.

Laten we meteen de bovenstaande populatie van agenten gebruik voor ons voorbeeld. In de nieuwe populatie zit nu in ieder geval agent 2: hij is met een fitness van 2 de winnaar en hij gaat dus automatisch ‘door’ naar de volgende ronde.

We bepalen nu op basis van de kansen welke methode we gaan toepassen. Toevallig kiezen we nu voor een mutatie. Vervolgens kiezen we een agent voor de mutatie (op basis van de fitnesses van de agenten). Stel, dit is agent 4.
We muteren het genotype van agent 4. Dit gaat als volgt: je kiest een random bit uit in het genotype en vervangt deze vervolgens voor ofwel 0, ofwel 1 (wederom random, beide hebben een kans van 50%. Het kan dus voorkomen dat een mutatie hetzelfde genotype overlevert).

G:   0 1 0 1 0 1
Random wordt bepaald dat bit 2 gemuteerd wordt. Dit kan twee kinderen opleveren:
G’:  0 1 1 1 0 1
G’’: 0 1 0 1 0 1


Onze mutatie levert kind G’ op. We voegen nu G’ toe aan de nieuwe populatie. Merk op dat een mutatie één genotype als input heeft, en één genotype als output.

De nieuwe populatie bestaat nu uit twee agenten: de winnaar en G’. De populatie heeft nog niet de grootte van de oude populatie bereikt, dus gaan we door met evolueren. Dit keer gaan we een cross-over doen. Er zijn verschillende soorten cross-over. Ik zal elk soort cross-over bespreken. Een cross-over verwacht twee ‘ouders’ bij wie een cross-over plaatsvindt. We nemen telkens als ouders de genotypen 000000 en 111111. Merk ook op dat de meeste cross-overs twee kinderen teweeg brengen. Daarnaast verwachten bijna alle cross-overs een index. Deze index kan ook 0 of de lengte van de bitstring zijn. Een crossover op positie 0 zorgt voor substitutie van de eerste bit tot een bepaalde andere bit. Een crossover op positie lengte zorgt ervoor dat er niets gesubstitueerd wordt.

Normale cross-over: De normale cross-over is de cross-over beschreven in paragraaf 2.3. Er wordt een willekeurig punt gekozen en vanaf dat punt worden de twee genotypen uitgewisseld:
P1: 0 0 0 0 0 0
P2: 1 1 1 1 1 1
Cross-over op positie 4 levert op:
K1: 0 0 0 0 1 1
K2: 1 1 1 1 0 0


Tweepunts cross-over: Bij tweepunts cross-over knip je een bitstring op twee plekken door. Vervolgens wissel je de stukken tussen de twee knippen om. Tweepunts cross-over vereist een bepaalde lengte tussen de twee knippen. De maximum index van de knip is de lengte van de bitstring minus de lengte van de knip.

P1: 0 0 0 0 0 0
P2: 1 1 1 1 1 1
Tweepunts cross-over op positie 2 met lengte 3 levert op:
K1: 0 0 1 1 1 0
K2: 1 1 0 0 0 1


Uniforme cross-over met key: Bij uniforme cross-over met key kies je op basis van een bitkey van welke ouder je een bit neemt. Een bitkey 001100 betekent: de eerste en tweede bit neem je van de eerste ouder, de derde en vierde van de tweede ouder, en de vijfde en zesde weer van de eerste ouder. Het tweede kind doet het precies andersom: één en twee van ouder twee, drie en vier van ouder één, en vijf en zes weer van ouder twee. Een voorbeeld:

P1: 0 0 0 0 0 0
P2: 1 1 1 1 1 1
Uniforme cross-over met bitkey 011001 geeft:
K1: 0 1 1 0 0 1
K2: 1 0 0 1 1 0

Merk op dat K1 en K2 in dit geval precies gespiegeld zijn. Er zijn gevallen waarin dit niet precies zo mooi uitkomt. Bedenk bijvoorbeeld eens waarin P1 = 011100 en P2 = 101101 met deze bitkey resulteren.

Uniforme cross-over met kans: Bij uniforme cross-over met kans worden de bits van de ouders met een bepaalde kans gewisseld. De hele bitstring wordt langsgelopen en telkens wordt er willekeurig (met een opgegeven kans) gekozen of de betreffende bit wordt omgedraaid.

P1: 0 0 0 0 0 0
P2: 1 1 1 1 1 1
Uniforme cross-over met kans 0,5 geeft (bijvoorbeeld):
K1: 1 1 0 0 0 1
K2: 0 0 1 1 1 0
 

Merk op dat een kans van 0,5 niet per se betekent dat de helft van de bits gewisseld wordt. Omdat het een kans is, kunnen net zo goed meer dan de helft of minder dan de helft van de bits omgewisseld worden.

Drie-ouder cross-over: Bij drie-ouder cross-over worden er drie ouders opgegeven om één kind te genereren. Als eerste worden de bits van de eerste twee ouders vergeleken. Zijn die bits hetzelfde, dan wordt die bit aan het kind toegevoegd. Verschillen die twee bits, dan wordt de bit van ouder drie toegevoegd aan het kind.

P1: 0 0 0 0 0 0
P2: 0 0 1 0 1 1
P3: 1 1 1 1 1 1
Drie-ouder cross-over geeft:
K: 0 0 1 0 1 1

Merk op dat in plaats van de kleur rood in K ook de kleur groen gekozen had kunnen worden. De rode bit is afkomstig van zowel P1 als P2.

Cut & Splice cross-over: De laatste cross-over die we zullen bespreken, is een methode die in de praktijk zelden gebruikt wordt. Cut & Splice cross-over kiest willekeurig een knippunt voor ouder 1 en vervolgens willekeurig een ander knippunt voor ouder 2. Hierdoor is het dus mogelijk om kinderen te generen die korter of langer dan de ouders zijn.

P1: 0 0 0 0 0 0
P2: 1 1 1 1 1 1
Cut & Splice cross-over op posities 1 en 4 geeft:
K1: 0 1 1
K2: 1 1 1 1 0 0 0 0 0


In de praktijk wordt het sterk afgeraden om Cut & Splice cross-over te gebruiken. Het liefste houd je de lengte van je bitstrings gelijk om zogeheten junk-bits te voorkomen. Door junk-bits wordt kans op cross-over en mutatie in belangrijke bits ernstig verkleint.
Daarnaast zorgen hele korte bitstrings voor fenotypen die niet tot uiting komen omdat ze nog een non-terminal bevatten. In het algemeen wil je de lengte van je bitstrings dus constant houden.

Er zijn geen goede of foute cross-overs. Elke cross-over heeft zijn voordeel en nadeel. Welke cross-over(s) je gebruikt, is je eigen keuze.

Nu we de verschillende soorten cross-overs behandeld hebben, kunnen we verder met het vullen van onze populatie. We kiezen voor de tweepunts cross-over met lengte 2 en agenten 1 en 3 worden uitgekozen. De tweepunts cross-over pakt als volgt uit:

P1: 0 0 1 0 1 1
P2: 1 0 1 0 1 0
Tweepunts cross-over lengte 2 op random positie (0 in dit geval) geeft:
K1: 1 0 1 0 1 1
K2: 0 0 1 0 1 0


We voegen de twee kinderen toe aan de nieuwe populatie.

De nieuwe populatie bestaat nu uit 4 agenten: W (winnaar), G’, K1 en K2. We hebben nog één agent nodig om de oorspronkelijke populatiegrootte te bereiken.

Dit keer wordt er random gekozen voor een kopie. De kans op een normale kopie is altijd het kleinste. Bij een kopie (of reduplicatie) wordt er een willekeurige agent gekozen (wederom op basis van de fitness). Die agent wordt toegevoegd aan de populatie. Willekeurig wordt agent 2 gekozen voor reduplicatie. Agent 2 wordt toegevoegd aan de nieuwe populatie. De populatie bestaat nu uit: W, G’, K1, K2 en agent 2. Merk op dat agent 2 en W hetzelfde waren. Dit is geen probleem. Immers, als er twee dezelfde agenten in een populatie zitten, wil dat waarschijnlijk zeggen dat dit twee relatief goede agenten zijn.

Nu heeft onze nieuwe populatie de oorspronkelijke grootte bereikt. De agenten in deze populatie moeten nu de test afleggen en elk een fitness krijgen. Als dat gebeurt is, begint het verhaal weer van voor af aan en gaan we die populatie weer evolueren.

Op deze manier hopen we dat de agenten steeds beter worden. We herhalen het evolueren totdat we een agent hebben die aan onze eisen (bijvoorbeeld: vind de finish in het doolhof binnen één minuut) voldoet. Dan stoppen we en kunnen we zeggen dat de evolutie gewerkt heeft.



4.Toepassingen

Nu je in principe in staat bent zelf een GA te maken, is de vraag natuurlijk: wat kan je ermee? In dit hoofdstuk bespreken we de toepassingen van GA’s wat uitgebreider.

4.1 Toepassingen in games
Omdat wij games maken, is het voor ons natuurlijk interessant hoe we GA’s kunnen gebruiken in games. Het leuke van GA’s is dat je alle agenten tussen de agent die als allereerste een test doet en de agent die uiteindelijk aan de eisen voldoet, kan simuleren. Langzaamaan worden de agenten dus steeds beter. Je zou daarom GA’s kunnen gebruiken om een steeds slimmere AI te maken. Natuurlijk gaat de ontwikkeling heel erg langzaam. Daarom zou je telkens een paar generaties achter de schermen kunnen simuleren om vervolgens, zeg, de winnaar van tien generaties verder tegen de speler te laten strijden.

Een redelijk ultieme manier om GA’s te gebruiken, is in een tower defense-achtig spel. Hierin heb je verschillende waves. Deze waves zou je kunnen vergelijken met populaties. Omdat je bij tower defense games vaak verder dan tien waves komt, krijgen de agenten de kans om zich te ontwikkelen. Ik heb zoiets zelf nog niet geprobeerd, maar het moet denk ik zeker te doen zijn.

GA’s worden in games in de praktijk niet heel veel gebruikt. Zelf vind ik dat jammer, omdat ik denk dat er met wat creativiteit best wat toepassingen voor te bedenken zijn. Dat is dan ook de reden dat ik deze tutorial geschreven heb; om jullie aan te sporen om eens te kijken of je er iets mee kan. Zou toch wel geniaal zijn, een relatief simpel zelflerend systeem.



4.2 Nadelen
Helaas komen GA’s niet zonder nadelen. In deze paragraaf zal ik een aantal van deze nadelen bespreken.

Redundante code. Door de BNF die gebruikt wordt, is de mogelijkheid groot dat er nogal wat redundantie in het fenotype komt. Het voorbeeld dat in paragraaf 3.3 is aangehaald getuigd hiervan:
Code:
if (2 != 7) { if (2 != 7) { if (2 != 7) { move_right() } else { move_right() } } else { move_forward() } } else { move_right() }
De bovenstaande code zou in een bepaald geval prima kunnen werken. Helaas, echter, maakt de BNF het mogelijk om drie keer de check (2 != 7) te doen. Dit is natuurlijk compleet nutteloos en het vertraagt je programma enorm als het te vaak voorkomt. Natuurlijk kan je iets schrijven dat redundantie voorkomt, om dit probleem op te lossen (en dat is in de praktijk ook al gedaan).

Onbegrijpelijke code. GA’s kunnen codes genereren die eigenlijk nergens op slaan, maar wel werken. Waarom de codes werken is een compleet raadsel. De oorzaak van de onbegrijpelijke code zit hem in het feit dat een GA eigenlijk random code genereert en op basis van trial and error goede codes door laat gaan. Er zit geen logica of intelligentie achter, enkel een wiskundige fitnessfactor.

Toepasbaar op slechts één zoekruimte. Een ander probleem van GA’s is dat de gegenereerde code enkel succes oplevert in de zoekruimte waar de code op getest is. Dat wil zeggen: als bijvoorbeeld de code die je GA gegenereerd heeft werkt in het ene doolhof, wil dat niet zeggen dat die code net zo succesvol is in een ander doolhof. De code zal alleen werken op de zoekruimte waarop deze getest is. GA’s in dynamische omgevingen zijn dus lastig te realiseren.

execute_string. Door het gebruik van een BNF sla je functienamen op als string. Aangezien er geen mogelijkheid is om een string om te zetten naar een getal, zal je in Game Maker de execute_string functie moeten gebruiken. Ik vermoed echter dat hier wel workarounds voor te vinden zijn. Je zou in plaats van de namen van scripts of functies, getallen kunnen gebruiken die verwijzen naar een bepaald script of functie.




« Laatste verandering: 26 November 2013, 21:18:02 door kaasje »

ECCE QUAM SIT...
Naar boven Gelogd

kaasje
Globale moderator


Offline Offline

Berichten: 2301


« Antwoord #1 Gepost op: 26 Mei 2013, 00:08:59 »

5.GMGenetics

Als laatste wil ik jullie een opstapje geven naar het maken van jullie eigen GA’s. Ik heb in Game Maker een extensie gemaakt met basisfuncties voor GA’s. Deze extensie heb ik, heel origineel, GMGenetics genoemd. De extensie zit voor nu nog in een bètafase. Dat wil zeggen: niet alles werkt nog lekker. Voor basale toepassingen, echter, zou het voor nu voldoende moeten zijn.

5.1 Download en example
Via de onderstaande links kan je GMGenetics, samen met een example, downloaden. De example zal niet werken in Game Maker Studio, omdat execute_string gebruikt wordt. Ik ben hard aan het werk om deze nare functie te vervangen voor iets beters. De extensie zou het als het goed is wel moeten doen in Game Maker Studio.
De example bevat een pathfinding GA en een BNF. Laat deze eens een generatie of 50 draaien en zie hoe ver de agent komt.

Bekijk vooral ook even paragraaf 5.3 voor bekende fouten en vreemdheden en paragraaf 5.2 voor de documentatie.

Extensie (*.gml bestand): GMGenetics V0.21
Example (*.gmk, *.gml en *.txt): Genetics_example (V2.1)

Verouderde versies:
Extensie (*.gml bestand): GMGenetics V0.11
Example (*.gmk en *.txt): Genetics_example

Let op: geef de example wat tijd. In tien generaties heb je nog geen werkend algoritme. Run de example ook eens in debug mode en bekijk de variabelen obj_agent.phenotype en obj_controller.rolling (V0.11).



5.2 Documentatie
Hier zal ik alle scripts die bij de extensie zitten beschrijven. Sommige scripts geven een zogenaamde genetic list terug. Een genetic list is een string die een lijst representeert. De elementen zijn gescheiden door sluistekens.

GML:
genetics_init(grammar file);
Initialiseert een grammatica. Het argument grammar file moet path naar een tekstbestand (*.txt) zijn, waarin je BNF staat. Let op: je BNF mag in versie 0.1 van GMGenetics, op terminals na, niet de tekens < en > bevatten. De bovenste regel in je BNF wordt automatisch geïnterpreteerd als het startsymbool. Retourneert true als de file succesvol geladen is.

GML:
genetics_get_phenotype(genotype, codonsize, maximum wraps);
Zet de bitstring genotype om in een fenotype (string), gebruik makend van codongrootte codonsize. Deze functie geeft een lege string terug als het niet mogelijk is een fenotype te genereren zonder non-terminals. Het argument maximum wraps geeft aan hoe vaak de bitstring gewrapt mag worden voordat er een lege string teruggegeven wordt.

GML:
genetics_replace_variable(rule name, codon);
Geeft het element op index codon van lijst rule name. Het argument codon is een decimaal getal en hoeft nog niet modulo de lengte van de lijst gedaan te worden; dit zit in het script verwerkt. Het argument rule name staat voor een non-terminal in je BNF.

GML:
genetics_unbound_number(phenotype);
Geeft het aantal voorkomens van non-terminals in phenotype.

GML:
genetics_create_individual(codonsize, minimum codons, maximum codons);
Geeft een random gegenereerde bitstring terug met een aantal codons tussen de waarden minimum codons en maximum codons. In normale gevallen geldt: minimum codons == maximum codons.

GML:
genetics_create_population(population size, codonsize, minimum codons, maximum codons);
Geeft een genetic lijst met het aantal elementen gelijk aan population size, gevuld met random gegenereerde bitstrings met een aantal codons tussen de waarden minimum codons en maximum codons terug. In normale gevallen geldt: minimum codons == maximum codons.

GML:
genetics_mutation(genotype, probability);
Past, met kans probability, een mutatie toe op de bitstring genotype en geeft de gemuteerde bitstring terug. Geeft genotype terug indien de kans faalt.

GML:
genetics_crossover(P1 genotype, P2 genotype, probability);
Past, met kans probability, een normale cross-over toe op de bitstrings P1 genotype en P2 genotype. Geeft twee nakomelingen terug in de vorm van een genetic lijst. Geeft een lege string terug als de kans faalt.

GML:
genetics_crossover_splice(P1 genotype, P2 genotype, probability);
Past, met kans probability, een Cut & Splice cross-over toe op de bitstrings P1 genotype en P2 genotype. Geeft twee nakomelingen terug in de vorm van een genetic lijst. Geeft een lege string terug als de kans faalt.

GML:
genetics_crossover_twopoint(P1 genotype, P2 genotype, length, probability);
Past, met kans probability, een tweepunts cross-over van lengte length toe op de bitstrings P1 genotype en P2 genotype. Het argument length is groter dan of gelijk aan 0 en kleiner dan of gelijk aan de lengte van de ingevoerde bitstrings. Vul voor length -1 in om telkens een willekeurige lengte te laten kiezen. Geeft twee nakomelingen terug in de vorm van een genetic lijst. Geeft een lege string terug als de kans faalt.

GML:
genetics_crossover_uniform_key(P1 genotype, P2 genotype, bitkey, probability);
Past, met kans probability, een uniforme cross-over met key bitkey toe op de bitstring P1 genotype en P2 genotype. Geeft twee nakomelingen terug in de vorm van een genetic lijst. Geeft een lege string terug als de kans faalt.

GML:
genetics_crossover_uniform_chance(P1 genotype, P2 genotype, swap probability, probability);
Past, met kans probability, een uniforme cross-over met kans swap probability toe op de bitstring P1 genotype en P2 genotype. Geeft twee nakomelingen terug in de vorm van een genetic lijst. Geeft een lege string terug als de kans faalt.

GML:
genetics_crossover_threeparent(P1 genotype, P2 genotype, P3 genotype, probability);
Past, met kans probability, een drie-ouder cross-over toe op de bitstrings P1 genotype, P2 genotype en P3 genotype. Geeft één nakomeling terug. Geeft een lege string terug als de kans faalt.

GML:
genetics_to_decimal(genotype, codonsize);
Zet de codons van de bitstring genotype om in decimale getallen en maakt daar een decimal string van, die teruggegeven wordt.

GML:
genetics_list_element(list, index);
Geeft element nummer index terug uit genetic lijst list.

GML:
genetics_list_length(list);
Geeft het aantal elementen in genetic lijst list terug.

GML:
genetics_list_add(list, element);
Voegt het element element toe aan het einde van genetic lijst list en retourneert vervolgens de nieuw verkregen lijst.

GML:
genetics_list_max(list);
Retourneert de index van het element met de hoogste waarde in genetic lijst list. Deze lijst moet bestaan uit waarden die omgezet kunnen worden naar reals.

GML:
genetics_get_borderlist(fitnesslist);
Geeft een lijst met grenzen terug, gebaseerd op fitnesslist. Als voorbeeld: genetics_get_borderlist("1|3|1|6|") geeft de lijst "1|4|5|11|" terug. Dit kan handig zijn voor het kiezen van een willekeurige agent op basis van de fitness.

GML:
genetics_get_random_agent(genotypelist, fitnesslist);
Geeft een willekeurige agent uit genotypelist op basis van fitnesslist terug. Agenten met een hogere fitness hebben een hogere kans om gekozen te worden. De fitness op index n van fitnesslist moet overeenkomen met de fitness van de agent op index n van genotypelist.

GML:
genetics_evolve(genotypelist, fitnesslist, chance crossover, type crossover, chance mutation, chance duplication);
Geeft een geëvolueerde populatie in de vorm van een genetic lijst terug, gebaseerd op de genotypen in genotypelist, de fitnesses in fitnesslist, de kansen op crossover (chance crossover), mutatie (chance mutation) en duplicatie (chance_duplication), en het type crossover (type crossover). De waarde van het argument type crossover bepaalt de vorm van crossover die gebruikt wordt: 0 = splice, 1 = twopoint, 2 = uniform_key, 3 = uniform_chance, 4 = normal crossover, 5 = threeparent. Zie de desbetreffende crossover_* scripts voor meer informatie.



5.3 Geplande verbeteringen en changelog
- De functies omschrijven naar een DLL, om ze te versnellen
- Meerdere grammatica’s toestaan
- Tekens als > en < toestaan in BNFs
- Aanpassing aan genetics_unbound_number, zodat alleen daadwerkelijke non-terminals geteld worden

Changelog:
Versie 2.1:
- Toevoeging van nieuwe functies: genetics_list_add, genetics_list_max, genetics_get_borderlist, genetics_get_random_agent, genetics_evolve.

Op dit moment werkt de extensie volgens mij verder naar behoren. De example werkt af en toe wat minder, maar verder is daar ook weinig mis mee. Als je opmerkingen of suggesties hebt, hoor ik dat graag.



Tot zover deze monsterlijke tutorial. Ik hoop dat mijn uitleg duidelijk genoeg was. Ook hoop ik in de toekomst wat leuke dingen met GA’s te zien. Mochten er dingen nog niet duidelijk zijn, dan hoor ik het graag.

« Laatste verandering: 9 Maart 2014, 17:30:48 door kaasje »

ECCE QUAM SIT...
Naar boven Gelogd

Maarten Baert
Forumbeheerder


Offline Offline

Berichten: 4942

Gelieve quote te gebruiken als je PMs beantwoordt.


WWW
« Antwoord #2 Gepost op: 26 Mei 2013, 13:40:53 »

Heel interessant, ik mis alleen een beetje een praktisch voorbeeld in GM waarbij dit ook effectief werkt Tong. Heb je een simpele proof-of-concept o.i.d. waarin je de vooruitgang van het algoritme kan zien?


Naar boven Gelogd

lambiory
Gebruiker


Offline Offline

Berichten: 450

met wiskunde kan alles


« Antwoord #3 Gepost op: 26 Mei 2013, 14:21:59 »

Zeker interessant! Lijkt me leuk om hier eens een middagje mee te spelen Gemoedelijk

Ik vraag me echter af: In de biologie heb je een grote populatie nodig om goed te kunnen evolueren; je moet immers veel verschillende mutaties uitproberen om te zien wat het best werkt, en er moet rekening gehouden worden met incest. Is dat niet hier ook het geval, en moet je daarom een populatie van veel meer dan 5 nemen en daarnaast veel meer dan 2 individuen zich laten reproduceren?


Naar boven Gelogd

timo777
Gebruiker

Offline Offline

Berichten: 284

GML-HTML-CSS-AJAX-PHP-C++-C-Java-D-Git-Make


« Antwoord #4 Gepost op: 26 Mei 2013, 15:05:36 »

Erg interessant. Alleen is dit geschikt voor grotere spellen? Ik kan me voorstellen dat de vele mogelijkheden ervoor zullen zorgen dat het lang duurt voordat hij een "winnaar" heeft.


Wat zou hier moeten staan?
Naar boven Gelogd

Erik Leppen
Forumbeheerder


Offline Offline

Berichten: 9655


WWW
« Antwoord #5 Gepost op: 26 Mei 2013, 15:18:53 »

Interessante theorie, en er moet toch iets mee te doen zijn, ook in GM. Alhoewel je volgens mij niet heel strak per se aan de theorie hoeft vast te houden.

Zo heb ik wel eens gehoord van een applicatie die random inktvlekkenpatronen maakte, en mensen liet beoordelen in hoeverre die op gezichten lijken (dat bepaalde dan de fitness), en op die manier de best gewaardeerde inktvlekkenpatronen weer liet evolueren. En dat leek inderdaad ergens toe te leiden. (Helaas heb ik geen idee meer waar ik het gezien heb.)

Je zou zoiets zelf kunnen maken maar héél simpel, met kleurenpaletten. Genereer random kleurenpaletten en laat mensen die beoordelen. De mooist gevonden paletten laat je dan evolueren. Eens kijken wat daar uit komt. En dat kan ook met vormen, figuren, patronen, lettercombinaties, zinnen. Zou je zo een taal kunnen maken?

Misschien kun je het toepassen op een level-generator. Je genereert op de een of andere manier random levels en laat mensen die spelen en je meet op de een of andere manier hoe "goed" die levels zijn (hoe lang mensen erover doen, hoe vaak mensen doodgaan, of ze het level uitspelen, of ze de weg kunnen vinden, etc.) en bepaalt op basis daarvan de fitness van elk level.

Wat ik me nog een beetje afvraag is hoe die genotypen in mekaar zitten. Ik zie het eigenlijk als een ingewikkelde manier om te zeggen dat al je individuen parameters hebben die je kan bijstellen. Immers volgens mij is dit idee ook prima toepasbaar met niet-gegenereerde code, maar alleen voor het optimaliseren van de juiste parameters. Zo kan ik een levelgenerator maken die paramaters accepteert zoals afmetingen, hoeveelheid van allerlei soorten items, opeengepaktheid, complexiteit, mate van clustering van items, aantal kamers, etc. Dan is de code vast, maar zijn de parameters vrij en vervolgens kun je die laten evolueren: elk individu is dan simpelweg een waardenset voor die parameters. Alleen gaat je mutatiefunctie er dan ook anders uitzien. Je zou hier mee volgens mij een "lerende levelgenerator" kunnen bouwen - mits je spelerstatistieken bijhoudt om de levels op fitness te beoordelen.


Naar boven Gelogd

Yvanis
Gebruiker


Offline Offline

Berichten: 690

If you kill yourself, I’ll kill you. ~Roronoa Zoro


« Antwoord #6 Gepost op: 26 Mei 2013, 15:50:37 »

Het was leuk om te lezen, ik snap er nog niet heel veel van, maar ik zal het ooit opnieuw lezen, en er dan hopelijk meer van begrijpen. Ik heb wel een probleem in je .gmk file: hij zegt dat global._startsign niet bestaat. Ik kan wel iets doen van global._startsign = 0, maar ik weet niet of ik de code dan verpest.

~Ilja


We zijn bijna zo ver met het maken van een aangepast thema wat de index.php verwijdert bij de eerste pageload.
Current project(s): The Captain's Last Journey - Labyrinth of Chess -
Geld Moet Rollen
Naar boven Gelogd

ShroomProductions
Gebruiker


Offline Offline

Berichten: 1374


« Antwoord #7 Gepost op: 26 Mei 2013, 16:09:00 »

Citaat
Zo heb ik wel eens gehoord van een applicatie die random inktvlekkenpatronen maakte, en mensen liet beoordelen in hoeverre die op gezichten lijken (dat bepaalde dan de fitness), en op die manier de best gewaardeerde inktvlekkenpatronen weer liet evolueren. En dat leek inderdaad ergens toe te leiden. (Helaas heb ik geen idee meer waar ik het gezien heb.)

ik moest hier aan denken http://www.electricsheep.org/


back on topic: Zeer interessante tut om te lezen, maar helaas een beetje te hoog gegrepen voor mij om iets mee te gaan doen.

« Laatste verandering: 26 Mei 2013, 16:12:32 door ShroomProductions »

Naar boven Gelogd

Red Owl Games
Gebruiker


Offline Offline

Berichten: 359

In het land der blinden is éénoog koning.


WWW
« Antwoord #8 Gepost op: 26 Mei 2013, 16:25:30 »

Fascinerend!

Dit heeft zeker mogelijkheden voor spellen, bijvoorbeeld als aanvulling op procedurele generatie.

Overigens is het maken van A.I.'s voor dynamische omgevingen denk ik wel mogelijk als je als CONDITIONs meer waarnemingsscripts toevoegt, en ze vervolgens ook in dynamische omgevingen laat beoordelen op fitness.

Wel jammer dat execute_string niet meer werkt in GM:Studio. Maar het kan ook op andere manieren geïmplementeerd worden, natuurlijk.

Je zou ook een spel kunnen maken waarin je een zo goed mogelijk GA moet ontwikkelen. Tong


Neem een kijkje op mijn website: Red Owl Games
 
Naar boven Gelogd

Neojume
Gebruiker


Offline Offline

Berichten: 1258


« Antwoord #9 Gepost op: 26 Mei 2013, 16:37:24 »

Aangezien ik zelf redelijk wat ervaring heb met GA's wil ik hier nog even wat opmerkingen over plaatsen.

Je hoeft niet per se een grammatica te gebruiken, bijvoorbeeld. Een genetisch algoritme is in dit opzicht een optimalisatie techniek. Je hebt een aantal paramaters waarvan je het verband niet goed weet en je wilt de beste oplossing hebben.

Je kunt daarom ook een standaard AI schrijven met bepaalde thresholds (de neiging om te schieten/weg te rennen etc). Vervolgens kun je die thresholds met GA finetunen.

Er is een goede reden om bitstrings te kiezen als genen, maar er kunnen ook erg goede redenen zijn om dit juist niet te doen. Dit hangt volledig af van het domein waar je het op toepast.

Een ding wat vaak met de from scratch aanpak erg vervelend is: het duurt eeuwen. Nouja niet letterlijk (kan wel), maar het duurt meestal lang om te convergeren. Vandaar dat als je domeinkennis hebt over het domein wat je aan het optimaliseren bent, gebruik het vooral! Dit kan bijvoorbeeld terugkomen in de manier waarop je muteert, of hoe je je genen representeert.

Ik heb ooit ook een genetische AI geschreven in GM voor een race-spelletje. Misschien dat ik die nog eens aanpas om als example te tonen.

Voor de rest een goede tutorial. Hoewel ik een beetje twijfel of het deel over CFG's duidelijk is voor iemand die niet uit de AI-wereld komt. Als je GA gebruikt kun je bovendien ook kiezen om geen CFG te gebruiken.



MSc Artificial Intelligence
Naar boven Gelogd

Perry26
Gebruiker


Offline Offline

Berichten: 1054

Vragen over GM bij mij WEL via pm :p


« Antwoord #10 Gepost op: 26 Mei 2013, 16:47:27 »

Woh, lange text, duurt zeker net zo lang om te schrijven.

Heb niet veel ervaring hiermee: Dus als ik het aan het einde begrijp zal hij goed zijn. (waarom werkt hij niet op  Game Maker Studio GameMaker: Studio)
EDIT:
Jullie volgende vraag zou prima kunnen zijn: “Wat heeft dat in godsnaam met de evolutietheorie te maken?”
Niet als je biologie hebt gehad...
EDIT2:
Je zou GA’s in Game Maker kunnen gebruiken om zelflerende AI’s te schrijven (AI’s die zich bijvoorbeeld aanpassen op het gedrag van de speler, of die tactieken vinden om de speler uit te schakelen).
link: http://www.game-maker.nl/forums/topic,29369.0
Praktisch elk organisme dat op deze aarde rondloopt is opgebouwd uit genen. Genen zijn een soort bouwstenen van je lichaam; ze bepalen bijvoorbeeld je oogkleur, maar ook je karakter kan beïnvloed zijn door je genen.
Practisch? Dat kun je wel schrappen. (Dit lijkt misschien een onbelangrijk detail, maar dat dit practisch weghalen geeft aan de GA's de enige optie in de natuur is...)

Het kind K bevat nu van zowel M als V genen. Het is belangrijk dat de knip op dezelfde plek gebeurt, omdat een chromosoom anders langer wordt (dat kan gebeuren bij mutatie en kan dan ook de gevolgen hebben van een mutatie). Op deze manier krijg jij als het ware een mix van de genotypen van je ouders.
Je kunt het misschien beter zo uitleggen: Beide ouders hebben 2 genen voor bijv. oogkleur, en jij krijgt er 1 van je vader en 1 van je moeder. (Overigens mis ik dominant/receccief), dat vind ik iets duidelijker.


Bij GA’s hebben genotypen over het algemeen dezelfde lengte. Oftewel, bij cross-over moet er nog steeds vast ‘knippunt’ zijn. Hoewel dit een keuze kan zijn, zal blijken dat cross-overs zonder vast lengte kunnen leiden tot zeer beperkt gedrag.
Waarom doe je dat dan niet in het voorbeeld?:
P1: 0 0 | 0 0 0 0
P2: 1 1 | 1 1 1 1
K1: 0 0 1 1 1 1
K2: 1 1 0 0 0 0
Cross-over. Merk op dat een cross-over leidt tot twee kinderen.'

« Laatste verandering: 26 Mei 2013, 17:19:09 door Perry26 »
Naar boven Gelogd

Simon B.
Gebruiker


Offline Offline

Berichten: 2023

Ex-Gamemaker


« Antwoord #11 Gepost op: 27 Mei 2013, 11:37:26 »

Deze tutorial zet ik alvast in mijn bladwijders, dit is iets wat ik zeker nog eens grondig ga bekijken. Goed werk! Blij


Naar boven Gelogd

kaasje
Globale moderator


Offline Offline

Berichten: 2301


« Antwoord #12 Gepost op: 27 Mei 2013, 15:22:10 »

Heb je een simpele proof-of-concept o.i.d. waarin je de vooruitgang van het algoritme kan zien?
Hoewel ik niet echt weet hoe je een proof of concept formeel maakt, heb ik wel zoiets voor je Tong :
De example maakt een ini-file aan, waarin na elke generatie het genotype en de fitness van de winnaar worden opgeslagen. Naarmate het algoritme vordert is een stijging in fitness te zien. Hieruit valt op te maken dat het algoritme inderdaad steeds beter wordt.
Ik vraag me echter af: In de biologie heb je een grote populatie nodig om goed te kunnen evolueren; je moet immers veel verschillende mutaties uitproberen om te zien wat het best werkt, en er moet rekening gehouden worden met incest. Is dat niet hier ook het geval, en moet je daarom een populatie van veel meer dan 5 nemen en daarnaast veel meer dan 2 individuen zich laten reproduceren?
Een populatie van grootte 5 is wel erg klein. Ik zou voor populaties van ongeveer 20-50 individuen gaan.
In theorie zou een doel ook bereikt worden met een kleinere mutatie, maar dit zou (zowel in aantal generaties als in hoeveelheid tijd) langer duren. Doordat je slechts 5 individuen hebt in je populatie, is er minder variëteit in genotype. Cross-overs zijn dus minder effectief dan bij grote populaties, zou ik zeggen.
Erg interessant. Alleen is dit geschikt voor grotere spellen? Ik kan me voorstellen dat de vele mogelijkheden ervoor zullen zorgen dat het lang duurt voordat hij een "winnaar" heeft.
Hmm, interessante vraag. Je vraag is dus: is de tijd die een GA erover doet afhankelijk van de grootte van je BNF?
Ik zou zeggen: dat ligt er geheel aan hoe je je eisen stelt. Een uitgebreide BNF zorgt voor uitgebreider gedrag. Als je doel is 'bereik binnen een minuut het einde van een doolhof', dan ben je tevreden met een agent die er 55 seconden over doet, terwijl het met een uitgebreidere BNF mogelijk zou kunnen zijn om een agent te maken die er misschien maar 10 seconden over doet.
Los van je doelstelling: ik denk dat een GA met een uitgebreidere BNF met veel mogelijkheden er langer over doet om een geschikt algoritme te vinden, simpelweg omdat er meer opties zijn om uit te kiezen.
Overigens is te betwisten of 'grote' spellen ook een uitgebreidere BNF vereisen.

Je zou zoiets zelf kunnen maken maar héél simpel, met kleurenpaletten. Genereer random kleurenpaletten en laat mensen die beoordelen. De mooist gevonden paletten laat je dan evolueren. Eens kijken wat daar uit komt. En dat kan ook met vormen, figuren, patronen, lettercombinaties, zinnen. Zou je zo een taal kunnen maken?
Ik denk dat een dergelijke BNF zeker te realiseren is. Merk ten eerste op dat het fenotype uitgevoerd kan worden in elk willekeurig event. Je zou met een BNF de waarden van een aantal variabelen kunnen instantiëren, bijvoorbeeld: hoeveelheid vlekken, kleur van elke vlek, radius van elke vlek, x- en y-coördinaat van elke vlek, aantal uitstulpsels van elke vlek, et cetera. Definieer die variabelen in het create event en gebruik ze vervolgens in het draw event.
Zo'n taal moet best te schrijven zijn, al zal hij ingewikkelder in elkaar zitten dan de BNFs die als voorbeeld gegeven zijn, omdat je een variabel aantal vlekken hebt en je voor elke vlek een aparte variabele moet instantiëren, maar merk op dat je als deel van je BNF ook best een for-loop kan gebruiken, bijvoorbeeld.
Citaat
Wat ik me nog een beetje afvraag is hoe die genotypen in mekaar zitten. Ik zie het eigenlijk als een ingewikkelde manier om te zeggen dat al je individuen parameters hebben die je kan bijstellen. Immers volgens mij is dit idee ook prima toepasbaar met niet-gegenereerde code, maar alleen voor het optimaliseren van de juiste parameters. Zo kan ik een levelgenerator maken die paramaters accepteert zoals afmetingen, hoeveelheid van allerlei soorten items, opeengepaktheid, complexiteit, mate van clustering van items, aantal kamers, etc. Dan is de code vast, maar zijn de parameters vrij en vervolgens kun je die laten evolueren: elk individu is dan simpelweg een waardenset voor die parameters. Alleen gaat je mutatiefunctie er dan ook anders uitzien. Je zou hier mee volgens mij een "lerende levelgenerator" kunnen bouwen - mits je spelerstatistieken bijhoudt om de levels op fitness te beoordelen.
Iemand van mijn studie heeft eens zoiets gedaan met Mario Levels Tong
Je zou inderdaad een BNF kunnen schrijven die datasets genereert (een beetje zoals mijn voorstel voor de BNF voor het vlekkenprobleem); dat is geen probleem. Waar je echter mee op moet passen is het gebruiken van random-functies op die dataset. Elke dataset moet in principe precies één level kunnen voortbrengen en andersom: elk level is afkomstig van slechts één dataset (een soort bijectie dus). Door gebruik van random factoren kan het zijn dat een dataset in het ene geval een heel goed level in elkaar zet, en in het andere geval een heel slecht level.
Ik heb wel een probleem in je .gmk file: hij zegt dat global._startsign niet bestaat. Ik kan wel iets doen van global._startsign = 0, maar ik weet niet of ik de code dan verpest.
Heb je de *.zip uitgepakt en staat grammar.txt (de BNF) bij de *.gmk in de map?
Overigens is het maken van A.I.'s voor dynamische omgevingen denk ik wel mogelijk als je als CONDITIONs meer waarnemingsscripts toevoegt, en ze vervolgens ook in dynamische omgevingen laat beoordelen op fitness.
Inderdaad, hoe uitgebreider je BNF, hoe complex het gedrag is wat je kan vertonen. Je kan in principe alles gebruiken wat in Game Maker ondersteund wordt, inclusief eigen scripts en resources. Daaronder vallen dus ook while- en forloops die je met je BNF kan invullen. Ik heb het met loops niet geprobeerd, maar het zou best interessante dingen kunnen opleveren.
Je hoeft niet per se een grammatica te gebruiken, bijvoorbeeld. Een genetisch algoritme is in dit opzicht een optimalisatie techniek. Je hebt een aantal paramaters waarvan je het verband niet goed weet en je wilt de beste oplossing hebben.
Oh, nee, absoluut niet. Dit is inderdaad een manier om een GA te maken. Persoonlijk vind ik dit een vrij gemakkelijke en weinig abstracte manier, maar voor technische toepassingen zijn er vast betere manieren.
Bedankt voor je opmerkingen Gemoedelijk Ik heb in de tutorial nogmaals benadrukt dat dit niet de enige manier is om een GA te maken. Ben wel benieuwd naar jouw GA-example.
Ik denk niet dat het mogelijk is om met een GA alleen een dergelijke intelligentie te kunnen maken. Een AI redeneert op basis van logica, terwijl een GA eigenlijk random wat klooit en toevallig een juist resultaat krijgt. Ik denk echter wel dat een GA een (al dan niet grote) rol kan spelen in het maken van een creepy smart AI.
Je kunt het misschien beter zo uitleggen: Beide ouders hebben 2 genen voor bijv. oogkleur, en jij krijgt er 1 van je vader en 1 van je moeder. (Overigens mis ik dominant/receccief), dat vind ik iets duidelijker.
Ik heb er bewust voor gekozen om niet op genenparen, dominatie en recessiviteit in te gaan; dit is niet relevant voor GA's. Genenparen zouden juist verwarring brengen omdat, in tegenstelling tot in de natuur, in deze versie van GA's elke agent slechts één rij genen heeft en geen paar.
Waarom doe je dat dan niet in het voorbeeld?:
Voor zover ik zie hebben P1, P2, K1 en K2 dezelfde lengte bitstring? Met het sluisteken in de strings van de ouders geef ik aan waar er geknipt wordt, daarom lijkt het alsof P1 en P2 langer zijn, maar het aantal nullen en enen is gelijk Knipoog

Bedankt voor je kritiekpunten.


« Laatste verandering: 27 Mei 2013, 15:26:00 door kaasje »

ECCE QUAM SIT...
Naar boven Gelogd

Yvanis
Gebruiker


Offline Offline

Berichten: 690

If you kill yourself, I’ll kill you. ~Roronoa Zoro


« Antwoord #13 Gepost op: 27 Mei 2013, 15:37:01 »

Nu werkt hij wel  Blij, dankje! En ik wil nogmaals zeggen dat de tutorial erg gaaf is!

~Ilja


We zijn bijna zo ver met het maken van een aangepast thema wat de index.php verwijdert bij de eerste pageload.
Current project(s): The Captain's Last Journey - Labyrinth of Chess -
Geld Moet Rollen
Naar boven Gelogd

Perry26
Gebruiker


Offline Offline

Berichten: 1054

Vragen over GM bij mij WEL via pm :p


« Antwoord #14 Gepost op: 27 Mei 2013, 18:32:53 »

3.3 Representatie van het fenotype
Bij organismen vallen alle waarneembare eigenschappen van een individu onder het fenotype. Bij agenten, echter, definiëren we het fenotype als ‘de code die een agent uitvoert om bepaald gedrag te vertonen.’

Als we agenten hebben die enkel naar voren, naar achteren, naar links en naar rechts kunnen bewegen, zou een fenotype kunnen zijn:
Code:
move_forward();
move_left();
move_forward();
Waarin move_forward() en move_left() functies of scripts zijn.

We moeten natuurlijk op een bepaalde manier kunnen definiëren wat wel en niet onder een fenotype valt. Hiervoor maken we gebruik van een BNF. BNF staat voor Backus-Naur Form. Een BNF is een zogeheten Context Free Grammar (CFG – contextvrije grammatica). Met een CFG kun je definiëren wat wel en niet onder een bepaalde grammatica valt. Een CFG bestaat uit een aantal regels met terminale en non-terminale symbolen (‘terminals’ en ‘non-terminals’). Voor non-terminale symbolen is altijd een bepaalde regel waarmee je het non-terminale symbool omzet in een terminaal symbool. Een terminaal symbool is een deel van het eindresultaat; er is geen regel waarmee je het terminale symbool kan omzetten naar een ander (non-)terminaal symbool. Je bereikt een eindresultaat (of: eindstaat) als er geen non-terminale symbolen meer aanwezig zijn. Je start altijd met een bepaalde non-terminal en gaat vanuit daar afleiden wat de CFG bevat.
Een voorbeeld-CFG:
Code:
S --> aSa|b
Een sluisteken ( | ) staat voor ‘of’. Het startsymbool is S.
Snapte ik echt helemaal niks van ; totdat ik las:

We beginnen dus met een S, een non-terminaal symbool, en volgen dan de regel. We zien dat een S ofwel aSa, ofwel b kan afleiden. Stel, we kiezen voor aSa, dan vervangen we het startsymbool voor aSa. Volgens vragen we ons af of er nog een non-terminaal symbool aanwezig is in ons resultaat. Die is er, namelijk: weer een S. We zoeken voor deze S een nieuwe regel en vinden weer de regel S --> aSa|b. We kiezen nu b voor S en vervangen de S in de aSa die we verkregen hadden in een b. Dat resulteert in de string aba. Hier staan geen non-terminale symbolen meer in, dus we zijn klaar. Immers, voor a en b zijn geen regels. Intuïtief kan je zien dat deze grammatica alle strings die beginnen met n keer een a, dan één b, en dan weer n keer een a kan genereren.

Dit kan je natuurlijk zo ingewikkeld maken als je zelf wilt. Een BNF is bijna hetzelfde als een CFG. Een voorbeeld van BNF zou kunnen zijn (met startsymbool <ACTION> – bij een BNF is de bovenste regel altijd het startsymbool):
Code:
<ACTION> ::= move_forward()|move_left()|move_right()|move_backward()
In dit geval genereert deze BNF alleen maar de vier terminals move_forward(), move left(), move_right() en move_backward(). Merk op dat deze terminals meer zijn dan alleen symbolen: het zouden functies kunnen zijn! Je vult je BNF dus met opdrachten voor je agent. Je kan hier bijvoorbeeld prima iets neerzetten in de trant van motion_set(90,4).

We kunnen het echter wat interessanter maken door meer non-terminale symbolen toe te voegen (met startsymbool <ACTION>):
Code:
<ACTION> ::= move_forward()|move_right()|if (<CONDITION>) { <ACTION> } else { <ACTION> }
<CONDITION> ::= <DIGIT> != <DIGIT>|true|false
<DIGIT> ::= 1|2|3|4|5|6|7|8|9|0
Dit is al een veel interessantere BNF. Deze BNF genereert bijvoorbeeld:
Code:
if (2 != 3) { move_forward() } else {move_right() }
Een schematisch overzicht van hoe deze eindstaat gegenereerd is:
1. Begin met startsymbool <ACTION> en kies if (<CONDITION>) { <ACTION> } else { <ACTION> }
2. De eerste non-terminal die we tegenkomen, is <CONDITION>, kies iets uit het rijtje <CONDITION>, bijvoorbeeld <DIGIT> != <DIGIT>. Ons resultaat wordt nu: if (<DIGIT> != <DIGIT>) { <ACTION> } else { <ACTION> }
3. De eerste non-terminal die we tegenkomen is <DIGIT>, kies iets uit het rijtje <DIGIT>, bijvoorbeeld 2. Ons resultaat wordt nu: if (2 != <DIGIT>) { <ACTION> } else { <ACTION> }
4. De eerste non-terminal die we tegenkomen is weer <DIGIT>, kies iets uit het rijtje <DIGIT>, bijvoorbeeld 3. Ons resultaat wordt nu: if (2 != 3) { <ACTION> } else { <ACTION> }
5. De eerste non-terminal die we tegenkomen is <ACTION>, kies iets uit het rijtje <ACTION>, bijvoorbeeld move_forward(). Ons resultaat wordt nu: if (2 != 3) { move_forward() } else { <ACTION> }
6. De eerste non-terminal die we tegenkomen is <ACTION>, kies iets uit het rijtje <ACTION>, bijvoorbeeld move_right(). Ons resultaat wordt nu: if (2 != 3) { move_forward() } else { move_right() }
7. We komen geen non-terminals meer tegen, dus we hebben onze eindstaat bereikt. De gegenereerde string is: if (2 != 3) { move_forward() } else { move_right() }

Merk op dat ook de volgende strings gegenereerd kunnen worden:
Code:
move_forward()

if (8 != 8) { move_right() } else { move_right() }

if (0 != 5) { if (4 != 4) { move_right() } else { move_right() } } else { move_right() }

if (2 != 7) { if (2 != 7) { if (2 != 7) { move_right() } else { move_right() } } else { move_forward() } } else { move_right() }
Het bereik van deze BNF is in theorie oneindig, omdat elke <ACTION> met een if (…) kan worden ingevuld.

Voor het GA wat wij gaan bespreken is het belangrijk om BNFs te snappen. De BNF zal ons fenotype gaan representeren. Een kleine fout in je BNF kan resulteren in vreemde of langdradige resultaten. In het de volgende paragraaf gaan we bitstrings aan BNFs koppelen om zo door middel van een genotype een fenotype te creëren.  
Ja, misschien iets duidelijker. Laat anders eerst even zien waar je naartoe gaat...
Kans op mutatie: 30%
Kans op crossover: 60%
Kans op reduplicatie (kopie): 10%
Hoe bedoel je die mutatie? Muteert er een crossover, een bestaande, een geredupliceerde?


Oh ja, ik heb de examples in de gm-converter gegooid en nu lopen ze bij het opstarten vast...  Verdrietig

Maar ik snap nu wel het principe van GA's, en
Heb niet veel geen ervaring hiermee: Dus als ik het aan het einde begrijp zal hij goed zijn. (waarom werkt hij niet op  Game Maker Studio GameMaker: Studio)

« Laatste verandering: 27 Mei 2013, 19:05:56 door Perry26 »
Naar boven Gelogd

Advertenties
« vorige volgende »
Pagina's: [1] 2
Print


Topic Informatie
0 geregistreerde leden en 1 gast bekijken dit topic.

Ga naar:  

Powered by SMF 1.1.21 | SMF © 2006-2007, Simple Machines
www.game-maker.nl © 2003-2020 Nederlandse Game Maker Community