cursus Inleiding Adaptieve Systemen Opleiding Kunstmatige Intelligentie 2020-21

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, expansie van het acroniem, 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, LISP's typering van Edsger Dijkstra, 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. De waarde van deze initialisatiemethode kunnen relativeren als een heuristiek (vuistregel).
  • 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 kunnen 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 berkeningen 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.
  • Een bruikbare fitnessmaat 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.
  • Deze pagina werd automatisch gegenereerd en moet nog worden bewerkt.


    Laatst gewijzigd op dinsdag 26 januari 2021, om 17:48 uur ——— translate to ru, ro, or en ——— commentaar welkom