cursus Inleiding Adaptieve Systemen Opleiding Kunstmatige Intelligentie 2020-21

Hoorcollege

Genetische Algoritmen

Kennen

  • De taxonomie (onderverdeling) evolutionaire algoritmen, genetische algoritmen, en genetisch programmeren.
  • Het verschil tussen genetische algoritmen en genetisch programmeren: GA's werken op strings met een vaste lengte, en GP's werken op (syntaxbomen van) computerprogramma's.
  • 's Werelds meest geciteerde bron uit dit veld, D.E. Goldberg's “Genetic Algorithms: in Search, Optimization and Machine Learning” (1989). Zie verder onder “Kunnen”.
  • Het idee achter GA's: algoritmen ontwerpen die zijn geïnspireerd op ideeën uit de evolutieleer.
  • Een GA is een probabilistisch, ook wel: stochastisch, proces, dat geen enkele zekerheid geeft over uitkomsten. Uitkomsten worden ook beïnvloedt door exogene factoren (factoren van buiten: een fenotype kan pech hebben omdat het slecht weer is).
  • Elementaire kennis van de werking van celdeling bij zoogdieren; genotype en fenotype; mitose en meiose; de chromosomen van de mens; X- en Y-chromosoom.
  • Het computationele analogon: alfabet, chromosoomlengte, zoekruimte (= alle genotypen aanwezig in een populatie).
  • Het voorbeeld van de restaurant-formule.
  • Fitness-proportionele selectie, plus het beeld daarvan als segmenten op een roulettewiel; toernooi-selectie.
  • Koza's stroomschema van een GA-cyclus; het bestaan van kansen pr, pm, pc, op selectie t.b.v. reproductie, mutatie, en recombinatie (crossover).
  • De notie “mating pool”, en de functie daarvan. Afhankelijk van de implementatie is de mating pool een al dan niet expliciet aan te leggen constructie. Het kan ook een theoretisch begrip blijven.
  • Voorbeelden van GA's: antenneontwerp, draagarmontwerp, het balanceerprobleem.
  • Het probleem van de fouragerende mier plus alles wat daar bij hoort, met name de vertaling van executieschema's naar strings voor de bijbehorende eindige automaat.
  • Het begrip “schema” in de context van GA's. Een schema representeert een hypothese. De fitness van een schema.
  • John Holland's schemastelling, en weten dat deze stelling controversieel is.
  • Kunnen

  • Een omschrijving van een GA geven, gebruikmakend van termen als waarschijnlijkheid, zoeken, iteratie, populatie, genotypen, fenotypen, fitness, natuurlijke selectie, en genetische operatie.
  • Goldberg's monograaf noemen als gevraagd wordt naar de meest invloedrijke publicatie uit dit veld.
  • Een algoritme voor fitness-proportionele selectie geven. Er zijn er tenminste twee: 1) selecteren uit een per iteratie expliciet aangelegde mating pool, waarbij het aantal voorkomens van elk genotype evenredig is aan haar fitness; 2) door het trekken van een willekeurig getal uit [0, F) waarbij F de totale fitness representeert.
  • De fitness van een schema berekenen.
  • Bekendheid met f(x), f(H), f(X), |H| en |X|, en er mee rekenen.
  • Elementaire kansrekening op selectie- en reproductieprocessen; elementaire kansrekening op schema's.
  • Het bepalen van populatielimieten bij selectie- en reproductieprocessen.
  • Twee of drie redenen voor de controverse achter John Holland's schemastelling geven.
  • Materiaal

  • Slides Genetische Algoritmen.
  • TCBoN H3.3 (LISP) & 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