Dieser Audiobeitrag wird von der Universität Erlangen-Nürnberg präsentiert.

Es geht heute noch mal um Heuristiken. Also wir waren im Kapitel 10 stehen geblieben.

Und das wollen wir heute abschließen, das Kapitel. Also was war noch mal Heuristiken?

Heuristiken sind Algorithmen, die zulässige Lösungen berechnen,

aber nicht garantieren, dass wir wirklich eine Optimallösung finden.

either-

Ihr hattet letzte Woche schon mal die ersten Heuristiken kennengelernt.

Also angefangen hatten wir mit Greedy und als zweites die lokale Suche.

Und dann noch Tabu Search. Wobei halt dieses Tabu Search ist ein lokales Suche-Algorithmus.

So und diese, also heute wollen wir jetzt noch zwei weitere Heuristiken kennenlernen,

nämlich einmal Simulated Annealing und genetische Algorithmen.

Also fangen wir an mit 10.2. 2. Simulated Annealing.

Simulated Annealing ist auch ein Algorithmus, der zu diesen lokale Suche-Algorithmen gehört

und bedeutet so viel wie simulierte Abkühlung.

Die Idee für diesen Algorithmus kommt aus der theoretischen Physik.

Also es soll eine Art Abkühlungsprozess simuliert werden, also nach Erhitzen von Metall.

Sorgt halt so ein langsamer Abkühlungsprozess und hier ist wirklich langsam gemeint,

dass die Atome ausreichend Zeit haben sich zu ordnen und stabile Kristalle zu bilden

und dann so einen energiearmen Zustand erreichen.

Und das wollen wir hier halt auch machen.

Also deswegen kommen in diesem Algorithmus halt auch Begriffe vor wie Temperatur oder Gefrierpunkt.

Das kommt halt wie gesagt aus der theoretischen Physik.

Written 2 Peoplestage отк creepen.

Und die Idee ist hier halt auch, wie bei dem Tabu Search, im Laufe des Verfahrens nicht

nur immer bessere Zwischenlösungen zu erlauben, sondern mit einer bestimmten Wahrscheinlichkeit

auch schlechtere Lösungen. Aber diese Wahrscheinlichkeit wird halt umso geringer, je schlechter die

Lösung ist und auch je länger das Verfahren dauert. Also am Anfang des Verfahrens erlauben

wir noch häufig auch mal eine schlechtere Lösung anzunehmen, aber am Ende des Verfahrens

wird die Wahrscheinlichkeit immer kleiner. Und die Wahrscheinlichkeit, schlechtere Lösungen

zu erlauben, wird halt in dem Algorithmus über diese Temperatur simuliert. Das werden

wir gleich noch mal genauer sehen.

Also schauen wir uns mal an, wie der Algorithmus funktioniert.

So, in vase.

Also der Input des Algorithmus ist wie vorher auch bei den lokale Suchenalgorithmus.

Wir haben eine Menge von zulässigen Lösungen.

Die nennen wir f.

Die ist auch wie vorher nur implizit gegeben, also die haben wir nicht wirklich da.

Dann haben wir eine Nachbarschaftsfunktion, die jeder zulässigen Lösung eine Menge von

Nachbarn zuordnet.

Die haben wir n von s genannt.

Und wir haben eine Gewichtsfunktion, die jeder zulässigen

Lösung irgendwie ein Wert zuordnet.

Also sprich sagt, ob die Lösung jetzt gut oder schlecht ist.

Und eventuell haben wir auch noch eine Startlösung gegeben.

Und berechnen wollen wir halt eine andere zulässige Lösung.

Also unser Output ist auch jetzt irgendwie eine zulässige Lösung.

Wobei halt die im besten Fall natürlich besser sein soll, als die, die wir am Anfang reingesteckt

haben.

Und vielleicht auch die, die das Leben finden koennen.

Gut, also wie funktioniert der Algorithmus jetzt? Also als allererstes, wenn wir keine