Week 7 Flashcards
Wat is een atoom in Stutter?
Een rijtje van karakters
Wat voor punctuatie gebruikt Stutter?
( = open lijst
) = sluit lijst
‘ = quote atomen of lijst
; = negeer, begin van een opmerking
Value functions
Functies in Stutter die je niet kunt herdefiniëren, primitieven
Special functions
Functies in Stutter waarvan de argumenten niet meteen worden geëvalueerd, maar alleen wanneer het nodig is.
Wat doet de car-functie in Stutter?
De car-functie geeft het eerste element van een lijst en kan alleen voor een lijst gebruikt worden. Uitzondering: car van nil = nil.
Wat doet de cdr-functie in Stutter?
Geeft alle elementen uit de lijst, behalve het eerste element. Kan alleen op lijsten gebruikt worden. Uitzondering: de cdr van nil is nil.
Wat doet een lambda-expressie in Stutter?
Met de lambda-expressie kun je nieuwe functies definiëren. Lambda is een speciale atoom.
Hoe wordt adaptatie omschreven in neo-Darwinisme?
adaptatie = variatie + erfenis + selectie
Wat betekent coevolutie?
Hoe twee soorten zich aanpassen aan elkaar zodat er een circulaire relatie ontstaat.
Wat is het idee achter genetische algoritmes?
Algoritmen ontwerpen die zijn geïnspireerd op ideeën uit de evolutieleer.
Wat is een genetisch algoritme?
Een probabilistisch zoekalgoritme dat door middel van iteratie een verzameling genotype met elk een fitness-waarde omzet in een nieuwe verzameling genotypen dmv natuurlijke selectie, kruising en mutatie.
Geeft een genetisch algoritme zekerheid over uitkomsten?
Nee, want het is een stochastisch proces.
Wat zijn de 4 componenten van DNA-structuren?
A, C, G en T
A met T
C met G
Wat is een voorwaarde om een Genetisch Algoritme te kunnen gebruiken op een probleem?
Er moet een omkeerbare methode zijn om de strings te vertalen naar de informatie die we echt nodig hebben.
Wat is de ‘raw fitness’?
Het percentage van letters dat correct is
fraw = Number of correct letters / Length of target string
Wat is ‘scaled fitness’?
A measure for fitness that takes into account the length of the string
fscale = 2 ^(fraw)
Waar bestaat de zoekruimte uit?
Alle genotypen die aanwezig zijn in een populatie.
Wat is normalized fitness?
the fitness of the whole population
finorm = (fi scale) / (the sum of j=i, n of fj scale)
Hoe werkt selectie in een Genetisch Algoritme?
Elk individueel heeft een kans op winnen. De kans op winnen is gelijk aan de genormaliseerde fitness.
Wat is crossover?
Een speciaal geval van recombinatie: wanneer delen van 2 of meer chromosomen met elkaar verwisseld worden.
Hoe werkt kruising?
Er wordt een random crossover point gekozen in het DNA van de ouders. Het genetisch materiaal links van dit punt van ouder 1 wordt geplakt aan het materiaal rechts van dit punt van ouder 2. De nieuwe string heeft van beide ouders dan een deel.
Hoe wordt de keuze van muteren of niet gemaakt?
Maak de keuze met een coin toss per letter. Zo kunnen sommige individuen meerdere stukken gemuteerd krijgen.
Hoe ziet een function optimization problem eruit?
Bestaat vaak uit een real-world probleem dat zich gedraagt als een functie van een paar parameters.
Het doel is om de instellingen van de paramaters zo te vinden dat een bepaalde waarde gemax - of geminimaliseerd wordt.
Hoe ziet een string voor een Genetisch Algoritme op het Iterated Prisoner’s Dilemma eruit?
Bestaat uit 5 karakters:
(1) de actie voor de eerste beurt
(2) actie als beide spelers meewerken
(3) actie als wij meewerkten en tegenstander niet
(4) actie als wij niet meewerkten en tegenstander wel
(5) actie als beide spelers niet meewerkten
Wat is impliciet parallellisme?
Een eigenschap van GA’s waardoor ze erg accuraat oplossingen kunnen zoeken.
Wat is een schema?
Een mogelijke verklaring.
Bij een alfabet van K letters en chromosoomlengte L zijn er (K+1)^L schema’s.
Elk chromosoom is lid van 2^L schema’s.
Wat is een schemata?
Een type template. Bestaan uit twee binaire symbolen en een ‘wild card symbol’.
Wat is Evolutionair Programmeren?
Techniek voor evolutie simulatie:
Gebruikt geen tussenrepresentatie of recombinatie. Maakt gebruik van toernooiselectie.Werkt langzamer als dichterbij de oplossing
Wat betekent het als een probleem NP-compleet is?
Het probleem is niet in polynomiale tijd op te lossen, behalve als P=NP
Uit welke twee componenten bestaan optimalisatie problemen?
representatie/oplossings ruimte S, evaluatie/fitness functie
Geef de pseudo-code van een Genetisch Algoritme
1) Maak een populatie van N individuen
2) Herhaal:
a) Evalueer alle individuen met fitness voorwaarde
b) Herhaal N keer:
Selecteer 2 individuen adhv fitness waarden
Combineer deze om 1 nieuwe te krijgen
Muteer de nakomeling
Voeg de nakomeling toe aan een nieuwe populatie
3) Vervang de populatie door de nieuwe populatie
Wat is een genotype?
De encodering op het chromosoom waarop de genetische operaties werken, de set van chromosomen die een individu met zich meedraagt.
Wat is een fenotype?
De uiterlijke verschijningsvorm van het organisme, dat bepaald wordt door het genotype. Wordt getest met de fitness functie.
Welke representatie gebruik je als je een phenotype van real numbers wil construeren?
Encodeer de real numbers direct in het genotype en zoek in de ruimte van real numbers.
Wat zijn mogelijke initialisaties?
Binaire strings
Reële getallen
Geordende lijsten
Mutatie in Genetische Algoritmes
Verandert een individu lichtelijk zodat een nieuwe wordt gecreeërt, die nog wel op de oude lijkt
Hoe werkt fitness proportionele/roulettewiel selectie?
Hogere fitness geeft een hogere probabiliteit op selectie voor reproductie.
Hoe werkt Tournament Selection?
k individuen worden random geselecteerd van de populatie zonder te vervangen. Van die k wordt de beste gekozen.
Hoe werkt Rank-based selection?
Elk individu krijgt een rank. Hoe beter het individu, hoe hoger de rank.
Hoe werkt Truncated Selection?
De beste zoveel worden geselecteerd, onder deze individuen wordt geen onderscheid gemaakt.
Wat is het verschil tussen generationeel genetisch algoritme en steady-state genetisch algoritme?
In een generationeel genetisch algoritme wordt de populatie in zijn geheel vervangen, terwijl in een steady-state genetisch algoritme 1 individu per keer een ander individu vervangt.
Wat zijn Evolutionaire Algoritmen?
Technieken voor het simuleren van evolutie.
Wat zijn drie theoriën binnen Evolutionaire Algoritmen?
1) Evolutionair Programmeren
2) Evolutionaire Strategieën
3) Genetische Algoritmen. (John Holland)
Waar hangt de keuze om wel of geen crossover te gebruiken van af?
Is de fitness functie splitbaar?
Er moeten building blocks zijn
Is er een semantisch betekenisvollen recombination opeterator? Dan niet crossover ook.
Hoe werkt point-mutatie in Genetisch Programmeren?
Een terminal mag alleen naar een andere terminal gemuteert worden en een functie alleen naar een andere functie met dezelfde ariteit.
Hoe werkt Population Based Incremental Learning?
Een chromosoom bestaat uit waarschijnlijkheden voor het genereren van 1 op een bepaalde plek
Hoe werkt de Probabilistic Program Tree?
Begin bij de root node en kies een functie adhv waarschijnlijkheden. Ga dan naar de subtrees van de PPT om de nodige argumenten te genereren. Herhaal tot het programma klaar is.
Wat is evolutionaire computatie?
Gebruiken genetische strings als representatie, zijn goed in verdeeld zoeken in grote ruimte.
Waar kunnen evolutionaire algorithmen voor gebruikt worden?
Controle taken
Combinatorische optimalisatie
Functie optimalisatie
Wat is het doel bij een optimalisatie probleem?
Het vinden van de oplossing smax in S met maximale fitness
Hoe werkt local-hillclimbing?
- Genereer een oplossing s0, t=0
- Herhaal tot de stopconditie geldt:
s.new = verander(s.t)
Als f(s.new)>f(s.t) dan s.t+1=s.new
Anders s.t+1=s.t
t= t+1
Wat is een nadeel van local-hillclimbing? Hoe ga je daarmee om?
Komt vaak in een lokaal minimum terecht.
Algoritme vanaf verschillende punten starten.
Hoe maak je een evolutionair algoritme? (Abstract)
Ontwerp een representatie
Initialiseer de populatie
Ontwerp een manier om een genotype om te zetten naar een phenotype
Ontwerp een evaluatie functie om een individu te evalueren
Hoe maak je een evolutionair algoritme? (Specifiek)
Ontwerp bepaalde mutatie operatoren
Ontwerp bepaalde recombinatie operatoren
Beslis hoe ouders worden geselecteerd
Beslis hoe individuen worden gestopt in de nieuwe populatie
Beslis wanneer het algoritme kan stoppen
Wat zijn de twee methoden voor initialisatie?
- Uniform willekeurig over de gehele zoekruimte. Binaire strings: 0/1 met kans 0.5. Reeële getallen: uniform op gegeven interval
- Gebruik vorige resultaten. Nadeel=mogelijk verlies genetische diversiteit, soms niet ontsnappen aan initiële bias.
Wat is een mating pool?
Een verzameling waaruit de ‘partner’ gekozen wordt.
Hoe ga je om met eisen voor phenotypes in evolutionaire algoritmes?
Gebruik een penalty term in de fitness functie.
Gebruik specifieke evolutionaire algoritmen die omgaan met eisen.
Wat zijn 3 voorwaarden bij het maken van mutatie operatoren in evolutionaire algoritmes?
- Tenminste 1 mutatie operator moet het mogelijk maken om de hele zoekruimte te kunnen doorzoeken.
- De grootte van de mutatie stap moet controleerbaar zijn.
- Mutatie moet geldige chromosomen opleveren.
Wat doet een recombinatie operator?
Mapt 2 ouders op 1 of 2 kinderen.
Wat zijn 3 belangrijke punten bij het maken van recombinatie operatoren in evolutionaire algoritmes?
- Het kind moet iets van elke ouder erven.
- Moet samen met de representatie ontworpen worden.
- Moet geldige chromosomen opleveren.
Wat zijn 3 nadelen van fitness proportionele selectie in evolutionaire algoritmes?
- Gevaar van voorbarige convergentie
- Lage selectie druk als fitness waarden dichtbij elkaar liggen
- Gedraagt zich verschillend voor translatieve veranderingen van fitness functie.
Wat is recombinatie?
Wanneer bij het reproduceren bepaalde DNA-delen van plaats veranderen.
Noem 3 eigenschappen van recombinatie:
1) Veranderingen hangen van de hele populatie af
2) Afnemend effect met convergentie van populatie
3) Exploitatie operator
Noem 2 eigenschappen van mutatie
Verplicht om uit lokale minima te ontsnappen
Exploratie operator
Wat is het verschil tussen Genetische Algoritmen en Evolutionair Programmeren?
GA gebruikt crossover en mutatie, ES alleen mutatie.
GA werkt op genotypes, EP meer op fenotypes.
Hoe werkt genetisch programmeren?
Gebruikt functionele bomen als representatie ipv binaire strings
(Onderste 2 takken * node ) *node tak erboven
Hoe werkt PIPE?
Gebruikt kansen om functies op een knoop in programma boom te genereren. Slaat 1 PPT op ipv alle individuen. Maakt individuen adhv PPT.
Waar staat PIPE voor?
Probabilistic Incremental Program Evolution
Hoe maakt PIPE individuen met behulp van PPT?
Begin bij wortel en kies hiervoor functie volgens kansverdeling
Ga naar subbomen van PPT om argumenten te genereren
Herhaal tot programma af is
Wat zijn voordelen van een EC?
Kunnen vaak direct ingezet worden
Goed in doorzoeken van grote zoekruimtes
Kunnen gebruikt worden voor veel soorten problemen
Makkelijk te parallelliseren
Wat zijn nadelen van een EC?
Soms last van voorbarige convergentie/verlies genetische diversiteit
Veel individuen niet meer gebruikt na evaluatie
Kan traah leerproces opleveren
Weinig selectie druk als meeste individuen gelijke+slechte fitness hebben.
Hoe verhouden Evolutionaire Algoritmen, Genetische Algoritmen en Genetisch Programmeren zich tot elkaar?
Evolutionaire algoritme is de grootste verzameling.
Genetisch Algoritme is een subset, net als genetisch programmeren. Deze twee hebben overlap.
Mitose
Chromosoomopsplitsing bij normale celdeling. Duurt 12-24 uur.
Meiose
Chromosoomopsplitsing bij geslachtelijke celdeling. Produceert zaad-/eicellen. Vindt plaats in ouder
Hoe verhouden genotypen en fenotypen zich tot elkaar?
Populatie van genotypen
Genotypen uiten zich in een organisme: het fenotype.
Fenotype presteert en bezit een fitness. Genotype kannzichzelf voortplanten.
Wat is het verschil tussen Genetische Algoritmen en Genetisch Programmeren?
GA werken op strings met een vaste lengte, GP werkt op syntaxbomen van computerprogramma’s.
Wat zijn Evolutionaire Strategiën?
Werkt op chromosomen, de genen zijn representatie van parameters. Deterministisch
Wat is de meest invloedrijke publicatie op het gebied van Genetische Algoritmes?
Goldberg’s monograaf.
Beschrijf het restaurant-probleem:
Drank: 0=cola/1=wijn
Prijs: 0=laag/1=hoog
Service: 0=snel/1=traag
Fitness = de opbrengst
Hoe bereken je de zoekruimte bij een probleem?
K = omvang van het alfabet
L = chromosoom lengte
Dan is de omvang van de zoekruimte:
K^L
Wat zijn 4 probabilistische elementen in Genetische Algoritmen?
De nul-generatie is random,
probabilistische selectie,
weinig + willekeurige mutatie,
invloed exogene factoren
Noem 4 toepassingen van Genetische Algoritmen:
1) antenne-ontwerp
2) giek van een hijskraan
3) balanceer-probleem
4) fouragerende mier
Wat is het antenne ontwerp?
De x,y,z coördinaten van 6 kogelscharnieren moeten bepaald worden, met het eindpunt van een 7-delige antenne.
Antenne start in (0,0,0) en moet passen in de (0.5l)^3 kubus. Fitness = ontvangstkwaliteit.
Hoe wordt de antenne gerepresenteerd in het antenne ontwerp?
Elk 3D-punt heeft 5 bits: 1 voor het teken en 4 voor de getallen.
Dimensie = 3
Er zijn 7 scharnierpunten met ieder 5 bits.
chromosoomlente = 3x7x5=105 bits
Wat is het giek van de hijskraan probleem?
Het gewicht van de stangenconstructie moet geminimaliseerd worden. Een giek met 10 stangen: 6 van 30cm en 4 van 41cm. Diameter stang is variabel.
Hoe is de representatie van het giek van de hijskraan probleem?
Diameters zijn bit strings van 4 bits. Lengte van chromosoom is 10x4 = 40 bits.
Fitness = totale gewicht en penalty als constructie breekt. (hoe lager, hoe beter dus)
Wat is het balanceer-probleem?
Een fietser met een stok die verticaal gebalanceerd wordt. Fietser kiest een richting gebaseerd op: plaats, snelheid, hoek van de stok en hoeksnelheid van de stok.
Hoe is de representatie van het balanceer-probleem?
Gebruikt toernooiselectie.
Richting bepaald door:
w.plaatsxplaats +w.snelheidxsnelheid + w.hoekxhoek + w.hoeksnelheidxhoeksnelheid.
Beschrijf het probleem van de fouragerende mier:
Rooster van 32x32 met zwart=voedsel en grijs=pad.
Mier wordt verdwijderd als voedsel op is of hij er te lang over doet. Mier ziet alleen het vakje voor zich. Chromosoomlengte = 34 bits.
Wat zijn de vier acties van de fouragerende mier?
00 = doe niets
01 = draai 90 graden naar links
10 = draai 90 graden naar rechts
11 = doe een stap naar voren.
Geef een voorbeeld van een algoritme van de fouragerende mier:
- Kijk of er eten voor je ligt. Nee? Draai rechts.
- Kijk of er eten voor je ligt. Nee? Draai links.
- Kijk of er eten voor je ligt. Nee? Draai links.
- Kijk of er eten voor je ligt. Nee? Draai rechts.
In andere gevallen: loop naar eten, eet het op en ga naar toestand 1.
Geef een voorbeeld van algoritme en toestanden van de fouragerende mier uitgedrukt in bitstrings.
00) Als voer: move, eet en goto 00. Anders turn right en goto 01.
01) Als voer: move, eet en goto 00 Anders: turn left en goto 10.
10) Als voer: move, eet en goto 00. Anders: turn left en goto 11
11) Als voer: move, eet en goto 00. Anders: turn right en goto 00.
Hoe is een transitietabel voor Evolutionaire Algoritmen opgebouwd?
Toestand - Input - Nieuwe Toestand - Actie
Wat is de formule voor fitness proportionele selectie in een individu?
p.selecteer(x) = Def. (1 / |X| ) * ( f(x) / f(X) )
met p.selecteer = waarschijnlijkheid van selectie,
x= individu
X = verzameling van individuen.
Wat is de formule voor fitness proportionele selectie in schema’s?
p.selecteer(H) = ( |H| / |X| ) * ( f(H) / f(X) )
met p.selecteer = waarschijnlijkheid selectie,
H = verzameling van elementen.
Geef de formule van John Holland’s schemastelling:
p (H.t+1) >= ( |H.t| / |X.t| ) * ( f(H.t) / f(X.t) ) * (1 - eta.c) * (1-eta.m)
H = schema
t= tijdsstap
X = generatie verzameling
eta= kans
c= crossover
m= mutatie
Wat is de schemastelling van John Holland in woorden?
De kans dat schema H in de volgende generatie zit, is groter of gelijk aan
de frequentie van H in de huidige generatie
* de fitness van schema H
* de kans op verlies van schema H als gevolg van crossover
* de kans op verlies van schema H als gevolg van mutatie.
Wat zijn 4 opmerkingen op John Holland’s schemastelling?
Populatie is geen representatieve sample van een schema.
De formulie klopt ook al zonder crossover en mutatie.
Een ruime ondergrens is weinig informatief (=>).
Fitness is exogeen en varieert per genotype.
Noem 3 eigenschappen van Genetisch Programmeren:
Traag,
Werkt alleen met grote populaties,
concurreert met andere connectionistische technieken
Wat is er speciaal aan Genetisch Programmeren?
Gebruikt niet-lineaire chromosomen (bomen, grafen) en
genotype bezit variabele omvang.
Hoe wordt Genetisch Programmeren in Koza’s versie gemaakt?
Genotypen zijn programma’s in LISP.
Waar staat LISP voor?
LISt Processing Language
(f a b c) in Stutter
Functie f wordt aangeroepen met argumenten a, b en c.
Wat is een atoom wanneer ie niet geevalueerd wordt?
Zichzelf. Bijv a = a.
Wat is een atoom als deze geevalueerd wordt?
Zn waarde.
Wat gebeurt er als je een atoom zonder quote input?
Als deze gebonden is aan een waarde, geeft Stutter de waarde. Anders komt er een error.
set in Stutter
Functie met 2 argumenten: eentje evalueert naar het atoom waar je een waarde aan wil geven, en eentje is het atoom waarvan het resultaat na evaluatie gebonden wordt aan het atoom uit arg1.
Wat doet de cons functie in Lisp?
Maakt een nieuwe lijst van twee argumenten. Eerste argument is de car van resultaat lijst (1e element) en tweede argument is de cdr van resultaat lijst (dus alle elementen behalve eerste).
if-functie in Stutter
Neemt drie argumenten:
1) voorwaarde
2) argument als 1) waar is, stopt functie
3) argument als 1) niet waar is, dan evalueert ie 2) niet.
Wat is ‘true’ en ‘false’ in Stutter?
true= alles dat niet nil is
false= nil
Wat zijn de 4 soorten atomen in LISP?
Identifiers, getallen, strings en speciale atomen.
Noem een identifier in LISP:
x12, t4
begint met een letter
Noem getallen in LISP:
-3, 9, 0+45
Noem string in LISP:
“hallo”, “hallo\n”
Noem speciale atomen in LISP:
NIL, T
Wat is een S-EXP?
Een symbolische expressie:
een atoom of een lijst
Wat is de recursieve definitie van een s-expressie?
Een s-expressie is een atoom of een lisjt.
Wat is de recursieve deinitie van een lijst?
Een lijst is een linkerhaakje, gevolgd door een eindig (mogelijk leeg) rijtje s-expressies, gevolgd door een rechterhaakje.
Welke dingen in LISP evalueren naar zichelf?
Getallen, strings, T en NIL.
Hoe construeer je eerst expressies en evalueer je ze later pas?
Zet eerst de waarde van je expressies op wat je wilt,
(SETQ expressie-x ‘waarde-lijst).
Zet daarna de waarde van een expressie waarin je ze samenvoegt:
(SETQ expressie-samen (LIST ‘* expressie-x expressie-y)).
Als je nu expressie-samen evalueert, dan krijg je de uitkomst van de * operatie omdat ie alles dan evalueert.
Welke code gebruik je als je een bepaald argument van een eerder gedefinieerde functie wil instantieren in LISP?
Bijv. functie (SETQ ‘(if (food-ahead) then-part **else-part), dan:
(SETF (NTH 2 code) argument-watjewil)
als je arg2 wilt aanpassen.
Wat is een homogene term-verzameling?
Alle functies zijn toe te passen op alle termen.
Noem drie opvolgers van LISP:
Python, JavaScript en C#
Wat bevat een terminal-set?
Alle terminals die gebruikt worden in het programma.
Wat bevat een fuctional set?
Alle functies die gebruikt worden in het programma, zoals kwadrateren en /.
Wat is een voorwaarde voor kruising in LISP-bomen?
De te kruisen structuren moeten van hetzelfde type zijn.
Hoe werkt de groemethode als initialisatie?
Expressies worden willekeurig gekozen uit de unie van functieverzameling en terminalverzameling. De expressie op de maximale diepte van de syntaxboom kan alleen een terminal zijn.
Hoe werkt de verzadigde methode als initialisatie?
Expressies worden willekerig gekozen uit de functieverzameling. Op diepte gelijk aan maximale diepte van syntaxbom worden ze willekeurig gekozen uit de terminal verzameling.
Hoe werkt de ramped half-and-half initialisatiemethode?
De verzadigde methode en de groeimethode generaliseren ieder de helft van de populatie.
Beschrijf het BLOAT-probleem:
Bij kruising en mutaties groeit de gemiddelde omvang van expressies. Ook wel survival of the fattest genoemd.
Wat zijn manieren om bloat tegen te gaan?
Verbied het krijgen van dikke kinderen,
of geef dikke kinderen een lagere fitness. (pressure of parsimony/occam’s razor)
Wat is symbolische regressie?
Een voorbeeld van genetisch programmeren
Wat is het probleem in symbolische regressie?
Een verzameling punten in R^2 zijn gegeven en er moet een functievoorschrift gevonden worden dat de punten zo goed mogelijk omschrijft.
Wat is de restrictie op het functievoorschrift in symbolische regressie?
MOet zijn opgebouwd uit variabele x, getallen, +, - , * /, sin, cos, exp of log.
Geen een voorbeeld van de fitness in symbolische regressie:
de som van de fouten op alle punten +
0.05* de lengte van het functievoorschrift
Beschrijf Genetisch Programmeren
Een serie van genetische operaties op een pool van syntaxbomen.
