Hoorcollege
Simulated annealing
Kennen
Het “Energie = #conflicterende buren”-model (met de rode/blauwe/groene/gele pijltjes), en de werking daarvan.
De naïeve warmtewet van Newton: dT/dt = K(T − Tomgeving). Het tegen-exponentieel verloop daarvan.
De simulated annealing-formule die aangeeft wat de kans is om bij een bepaalde temperatuur T tóch een minder goede oplossing te accepteren: P{ Accepteer } = e−(E/kT).
De grafiek van de simulated annealing-formule, op het domein (T, Δuitkomst) ∈ [0,10]×[0,1].
Simulated annealing toegepast op functie-minimalisatie (-maximalisatie).
Het 0-1 rugzakprobleem; naïeve algoritmes om dit probleem aan te pakken.
Het 0-1 rugzakprobleem is NP-volledig.
Simulated annealing toegepast op het 0-1 rugzakprobleem.
Kunnen
In het “Energie = #conflicterende buren”-model de kans bepalen dat een deeltje flipt.
Verklaren waarom bij een te snelle afkoeling niet alle pijlen dezelfde kant op staan.
De simulated annealing-formule toepassen op een concreet voorbeeld.
Uitleggen hoe simulated annealing kan worden ingezet bij functie-minimalisatie (-maximalisatie). Van een functie op één variabele; van een functie op twee variabelen.
Materiaal
Slides Overzicht.
Werkcollegedictaat.