Hoorcollege
Genetisch Programmeren
Kennen
De taxonomie (onderverdeling) evolutionaire algoritmen, genetische algoritmen, en genetisch programmeren; het verschil tussen genetische algoritmen en genetisch programmeren.
's Werelds meest geciteerde bron uit dit veld, John Koza's “Genetic Programming: on the Programming of Computers by means of Natural Selection” (1992). Zie verder onder “Kunnen”.
De programmeertaal LISP, de expansie van het acroniem (LISt Processing), geschiedenis (LISP's inventor, moeder van KI-talen, ..), opvolgers (Scheme, Clojure, Haskell, ..), invloed op op moderne imperatieve talen (Python, Ruby, ..), sterke en zwakke kanten, Edsger Dijkstra, Dijkstra's typering van LISP, elementaire werking; de geschiktheid van LISP voor GP.LISP's nauwe relatie met Church's (Turing-volledige) λ-calculus: (λx.x2)3 → 9; (λx.xxx)"a" → "aaa"; (λx.xxx)(λx.xxx) → (λx.xxx)(λx.xxx)(λx.xxx). [Zie ook TCBoN, p. 29.]
Flake's verhandeling over λ-calculus, LISP en Stutter in TCBoN H3, Sec. 2-3 ev.
LISP's syntax (vier soorten atomen, lijsten, de lege lijst (= het atoom NIL), symbolische expressies, ..); prefixnotatie van functies, bijvoorbeeld (* 2 3 4); LISP's semantiek (evaluaties van s-expressies); interne representatie (datastructuur) van LISP.
De functies QUOTE, SET, SETQ (set quote), SETF (set field), LIST, EVAL.
Terminal- en functieset.
Mutatie en kruising in GP, term-homogeniteit.
Initialisatie van een populatie middels ramped half-and-half.
Koza's stroomschema van een GP-cyclus; het bestaan van kansen pr, pm, pc, op selectie t.b.v. reproductie, mutatie, en recombinatie (crossover).
Survival of the fattest a.k.a. “bloat”; manieren om bloat tegen te gaan.
Voorbeelden van GP's: symbolische regressie, RoboCup Soccer.
Het probleem van fitness-evaluatie goed te definiëren. De kosten van fitness-evaluatie in termen van reken-, simulatie- of executietijd. Realisatie vs. simulatie. Valkuilen m.b.t. fitness-evaluatie, het credit assignment probleem.
Kennis m.b.t. evolutionaire grammatica's wordt niet gevraagd.
Kunnen
Het begrip GP omschrijven als een serie van genetische operaties op een pool van syntaxbomen; de meest belangrijke verschillen tussen GA's en GP's benoemen.
Koza's eerste deel uit de serie “Genetic Programming” (1992) noemen als gevraagd wordt naar de meest invloedrijke publicatie uit dit veld.
Een s-expressies duiden als identifier, getal, string, speciaal atoom, of lijst; Elementaire berekeningen uitvoeren, met name manipulaties van s-expressies.
Het aantal mogelijke mutaties danwel recombinaties (kruisingen) bepalen in een term-homogene verzameling; in een term-inhomogene verzameling.
De waarde van ramped half-and-half relativeren; het zien als een heuristiek (vuistregel), i.p.v. wetenschap.
Een bruikbare fitness- danwel performancemaat voor een GP-probleem definiëren. (Daarbij zijn vaak meerdere antwoorden mogelijk.)
Vaardigheden m.b.t. evolutionaire grammatica's worden niet gevraagd.
Materiaal
Slides Genetisch Programmeren.
TCBoN H20.
Dictaat Marco Wiering H3.
Handouts Marco Wiering 2007 “Evolutionary Computation”.
Werkcollegedictaat.