uni/algodat/report4567/p7-fragestellungen.md

P5 Fragestellungen

lokales vs. globales Minimum

Wie aus Abb.10 hervorgeht, wird für alle Problemgrößen das globale Minimum zumindest ein Mal erreicht. Für $n = 1$ nämlich 1 Mal, für $n = 2$ gleich 4 Mal, usw.. Nicht wenige Male aber wurde das globale Minimum nicht erreicht. Gründe dafür könnten sein, dass die global kleinste Lösung nicht in der Nachbarschaft der Ausgangslösung enthalten ist oder durch die Auswahlstrategie eine Nachbarslösung betrachtet wird, von welcher wir nie auf die global kleinste Lösung kommen. Wird wie hier eine Best-Improvement Strategie verwendet, so kann die Greedy Heuristik verhindern, dass wir auf eine global kleinste Lösung kommen, selbst wenn diese in der Nachbarschaft enthalten ist.

mögliche Verbesserungen

Wir haben mehrere Möglichkeiten wenn wir versuchen wollen, die Nachbarschaftsstruktur zu verbessern. Zum einen könnten wir die Definition einer benachbarten Lösung ändern, meistens aber zu dem Preis, dass viel mehr Möglichkeiten entstehen. So könnte eine abgeänderte Nachbarschaftsstruktur zum Beispiel in jeder Spalte die Dame nicht nur 1 Feld gehen lassen, sondern potenziell alle. Dafür würden aber viel mehr Möglichkeiten entstehen, Nachbarslösungen zu erzeugen.

Eine zweite Idee wäre es, die Improvement Strategie von Best-Improvement auf Random-Neighbour oder First-Improvement umzusteigen. Dabei könnten wir zum Beispiel bei einer Random-Improvement gleich mehrere zufällige Nachbarn betrachten (z.B. best) und anhand einer Heuristik zwischen ihnen entscheiden.

% globales Minimum erreicht

n	% globales Minimum erreicht
1	100
2	100
3	77.78
4	13.28
5	16.99

Table: % globales Minimum erreicht

In Tab.1 kann ausgelesen werden, wie oft die lokale Suche ein globales Minimum erreicht hat.

Find Minimum 7953 - Size 5 - Local Minimum 0

In Abb.11 sind die iterativen Verbesserungen ersichtlich. Es sind nur 3 Schritte notwendig gewesen, um auf das lokale Minimum zu kommen.

Weil per Definition ein lokales Minimum sich dort befindet, wo kein Nachbar eine bessere Lösung darstellt, kann sobald ein lokales Minimum erreicht worden ist, kein Schritt mehr durchgeführt werden. Im Umkehrschluss bedeutet das, wenn ein Schritt durchgeführt wird, dann nur weil er eine Verbesserung darstellt. In diesem Fall lässt sich auch erkennen, dass wir bereits ein lokales MInimum erreicht haben, da unser lokales Minimum dem kleinstmöglichen globalen Minimum entspricht, nämlich 0.