Näherungsverfahren 1 SS10
Inhaltsverzeichnis |
Autoren:
- Patrick Breite (sipabrei@stud.hs-zigr.de)
- Marcel Mücke (simamuec@stud.hs-zigr.de)
Einführung
Das Thema der Effizienten Näherungsalgorithmen baut zum teil auf andere Themenkomplexe auf,die sehr zu empfehlen sind:
Greedy-Algorithmen
Probabilistische Algorithmen
P-NP-Problem
Heuristiken
Begriff
Der Begriff Heuristik ist aus dem altgriechischen Wort "heuriskien" abgeleitet und bedeutet so viel wie "(auf)-finden" bzw. "entdecken".
Anwendungsgebiete
Wirtschaftswissenschaften
Philosophie
Psychologie
Mathematik
Informatik
Springerproblem
Erläuterung des Springerproblems
Vor mehr als 200 Jahren formulierte der Schweizer Mathematiker Leonhard Euler erstmals das Problem des Rösselsprungs, auch Springerproblem genannt:
"Gibts es für einen Springer einen Weg, der jedes Feld eines n x n-Schachbrettes genau einmal besucht?"
|x_1 - x_2| = 1 und |y_1 - y_2| = 2
oder
|x_1 - x_2| = 2 und |y_1 - y_2| = 1
für die Bewegungen des Springers gelten muss.
Auf dem folgenden Bild sind die möglichen Züge eines Springers zu erkennen.
Lösung mit Backtracking
Lange Zeit war für die Lösung des sogenannten Rösselsprungs nur der Naive Algorithmus mit Backtracking bekannt, wodurch ein Exponentieller Aufwand Zeitaufwand entsteht. Der Versuch mit diesem Algorithmus eine Lösung für ein n x n-Schachbrett mit n>7 zu finden ist nur mit enormem Zeitaufwand zu lösen, da bei einem 8 x 8-Schachbrett bereits über 3 Milliarden Züge überprüft werden müssten um mit einem reinen Backtracking Algorithmus zum Ziel zu gelangen.
Ein Applet welches mit einem eingeschränkten Backtracking algorithmus arbeitet finden sie hier. Es ist zu beachten dass in diesem Algorithmus bestimmte Sackgassen schon vor dem Programmstart ausgeschlossen werden, um die Lösung diese 8 x 8-Schachbretts in einer möglichst kurzen Zeit zu gewährleisten.
Warnsdorff Heuristik
Die Warnsdorff Heuristik wurde 1823 von H.C. Wanrsdorff entwickelt und der Grundgedanke ist, dass Felder mit wenigen Folgefeldern schnell isoliert werden und so nicht mehr besucht werden können.
Warnsdorff entwickelte desshalb folgende Regeln:
1. Ziehe auf das Feld mit der geringsten Zahl an noch zu erreichenden unbesuchten Folgefelder.
2. Wenn 2 oder mehr Felder die selbe Anzahl an noch zu erreichenden unbesuchten Folgefelder aufweisen ziehe auf das Feld, welches zuletzt (oder zuerst) betrachtet wurde.
Wenn man Beispielsweise die 1. Regel auf ein anwendet auf ein noch leeres Schachbrett sieht dies folgendermaßen aus:
<eval id="4c0e16e3c7564"> </eval> Die Heuristik von Warnsdorff garantiert jedoch nur eine näherungsweise Lösung des Springerproblems, da bei größeren Schachbrettern nicht alle Sackgassen gemieden werden, was für Warnsdorff unmöglich zu untersuchen war, da er noch keine Computer zur Verfügung gehabt hat, welche diese Springertour auf beispielsweise einem 100x100 großem Schachbrett errechnen.
Weiterhin kann man zeigen, dass es für Schachbretter der Größe n \le 4 keine Lösungen existieren, da der Springer immer in einer Sackgasse landet, egal von wo er startet. Sie können dies auch in dem unten verlinktem Java Programm austesten.
Einen kurzen Algorithmus, zur Lösung des Springerpoblems mit der Warnsdorff Heuristik, finden Sie in diesem Java Programm und ebenfalls ist dieses Applet zu empfehlen, wenn man selbst einen Weg für das Springerproblem finden möchte und um den Weg vielleicht besser nachvollziehen zu können.
Lokale Suche
Verzweigen und Begrenzen
Der ihnen schon bekannte branch and bound Algorithmus (siehe Verzweigen und beschränken SS10) wird folgendermaßen abgewandelt:
1. Anstatt die eigentliche Schrankenfunktion zu berechnen wird diese durch eine mehr oder weniger grobe Schätzfunktion ersetzt
2. Die Bound-Berechnung entfällt -> man akzeptiert also, dass nicht wirklich eine Schranke berechnet wurde
3. Das Ergebnis dieses Näherungsalgorithmus kann zwar von dem Optimum abweichen, jedoch kann man in den meisten Fällen sagen, dass die Ergebnisse zufriedenstellend bis gut sind, also in der nähe des Optimums liegen und nur geringe Abweichungen aufzeigen
Greedy-Heuristiken
Hill climbing
Beim Hill-Climbing, auch Bergsteigeralgorithmus genannt, wird von einer beliebigen Startlösung aus versucht aus den in der nähe befindlichen Lösungen die bessere auszuwählen, bis keine Verbesserung mehr möglich ist.
Am Beispiel eines Bergsteigers bedeutet dies, das ein Bergsteiger auf einer beliebigen Postion in der Landschaft immer Versucht eine höhere Position zu erreichen. Dabei wird auch schnell der Schwachpunkt des Hill-Climbing-Algorithmus ersichtlich, denn er endet oft in einem lokalen Maximum. Bezogen auf den Bergsteiger bedeutet dies, wenn zwischen seiner aktuell höchsten (lokalen) Position und einer höheren (globalen) Position ein Tal liegt, hat er somit keine Möglichkeit diese zu erreichen.
Das Problem kann aber mit verschiedenen Ansätzen minimiert werden:
- mehrmaliges Ausführen der Methode
- mehrere Bergsteiger mit verschiedenen Startpunkten
- zufällige große Sprünge und danach erneutes Anwenden der Methode
Programmablaufplan Hill-Climbing
Threshold accepting
1990 veröffentlichten Dueck und Scheuer ihr Buch über die Schwellenakzeptanz (Threshold accepting: a general purpose optimization algorithm appearing superior to simulated annealing). Der Threshold accepting Algorithmus befasst sich hauptsächlich damit einen gewisse Tolleranzgrenze T einzurichten um mögliche zwischenzeitliche Verschlechterungen zu ermöglichen, was zu besseren Näherungslösungen führen kann. Man würde also überprüfen, ob eine lokale Veränderung nach einer Bewertung um mehr als T von der vorhergehenden Lösung abweicht und sie verwerfen insofern dies der Fall ist. Es wird somit zu anfang ein T gewählt welches möglichst groß ist, wobei auch ein T gewält werden kann durch welches anfangs kaum Beschränkungen entstehen, da wenn über längere Zeit keine Verbesserungen eintretetn T langsam auf null gesenkt wird. Der Nachteil ist, dass wenn zum Beispiel der Autofahrer aus dem zuvor beschriebenem Problem eine Nebengipfel erreicht hat und T bereits erhöt wurde, so gibt es kenie Möglichkeit für den Autofahrer den höchsten Gipfel zu erreichen.
Simulated annealing
Um die Schwachstelle des treshold accepting zu vermeiden entwickelten die Herren Scott Kirkpatrick, C. D. Gelatt und M. P. Vecchi vom IBM-Forschungszentrum Yorktown Heights 1983 das sogenannte simulated annealing, was übersetzt "simuliertes langsames Abkühlen bedeutet".
Dieses Verfahren wird hauptsächlich in der Werkstofftechnik eingesetzt. Bei diesem Verfahren werden Metalle erhitzt und dabei werden die atomaren Teilchen aus ihrer festen Gitterstruktur gelöst. Beim langsamen abkühlen verbinden sich die Teilchen wieder zu einer festeren und geordneteren Gitterstruktur. Dadurch erhält man Metalle mit verbesserten Eigenschaften(weniger Unregelmäßigkeiten in der Struktur). Zur Herstellung von Mikroprozessoren und Speicherbausteinen werden z.B. Materiallien wie Silizium benötigt welche keine Unregelmäßigkeiten besitzten.
Tabu-Suche
Der Algorithmus der Tabu-Suche wurde von Fred Glover entwickelt und erfährt seitdem immer wieder Verbesserungen. Die zugrunde liegende Idee basiert darauf, dass es bei den oben genannten Algorithmen (treshold accepting und simulated annealing) vorkommen kann das ein oder mehrere Schritte rückgängig gemacht werden. Um dies zu vermeiden werden die vorangegangen x Lösungen bzw. Schritte in einer sogenannten Tabu-Liste gespeichert, die mehrere Warteschlangen implementieren kann. Stimmt ein neuer Schritt mit einer Lösung in der Tabu-Liste überein, wird er verworfen und es muss eine neue Lösung gefunden werden, die noch nicht in der Tabu-Liste vorhanden ist.
Ein passendes Java-Applet zum besseren Verständnis befindet sich hier.
Sintflut-Algorithmus
Der Sintflutalgorithmus wurde 1993 von Gunter Dueck und Tobias Scheuer bei der Firma IBM in Heidelberg entwickelt. Er ist eine Weiterentwicklung bzw. Vereinfachung des weiter oben beschriebenen "Simulated Annealing"-Algorithmus und hat im Gegensatz zu den Treshold-accepting-Verfahren keinen Schwellwert der für jeden Schritt vorgegeben ist sondern eine globale untere Schranke die sich langsam aber stetig erhöht. Dabei spielt es keine Rolle, ob der nächste Schritt näher oder weiter entfernt von der Lösung gegenüber dem vorigen Schritt liegt, solange die globale Schranke nicht unterschritten wird. Im laufe des Prozesses wird dadurch die Anzahl der möglichen Schritte immer weiter eingeschränkt, bis keine Schritte mehr möglich sind und das gesuchte Optimum der Lösung gefunden ist.
Am besten lässt sich dies am Beispiel des Bergsteigers erklären, der sich versucht während einer steigenden Flut auf den in seiner Umgebung befindlichen höchsten Punkt zu retten. Der höchste Punkt bzw. Gipfel ist dabei das gesuchte Optimum. Während der Wasserstand immer weiter steigt ist der Wanderer ständig in Bewegung. Er merkt er sich dabei den höchsten Punkt den er bisher erreicht hat. Es ist ihm möglich jeden Gipfel und jedes Tal zu beschreiten, solange er sich über der Wasserlinie bewegt. Ist er komplett von den Wassermassen umgeben und kein Schritt mehr möglich, hat er den höchsten lokalen Punkt erreicht.
Die untere Abbildung zeigt die Anwendung im 2-dimensionalen Raum, wobei der rote Punkt den Wanderer, der gelbe Punkt den bisher höchsten lokalen Punkt und die blaue Linie den aktuellen Wasserstand darstellen.
Programmablaufplan Sintflut-Algorithmus
Ein passende Java-Applet befindet sich hier.
Der Sintflut-Algorithmus arbeitet, wie auch treshold accepting, im Gegensatz zum simulated annealing deterministisch. Bei geschickter Implementierung arbeiet er etwas schneller als die beiden anderen Verfahren, wobei er in der Qualität seiner Lösungen nicht ganz so stabil ist. Dieser vermeintliche Nachteil ist einfach zu erklären.
Wird die Schrittgröße des Wanderers zu groß gewählt, kann es passieren das er mit einem einzigen Schritt den Gipfel überspringt. Ist die Schrittgröße stattdessen zu klein steigt das Wasser zu schnell um möglichst viele verschiedene Punkte zu beschreiten. Das bedeutet das der Algorithmus stark von der Schrittgröße abhängig ist. Des Weiteren kann es passieren das der Wanderer auf einem niedrigeren Gipfel(lokales Maximum) von den Wassermassen eingeschlossen wird und damit keine Möglichkeit mehr hat auf den höheren Gipfel(globales Maximum) zu gelangen.
Dieser Nachteil wird mit steigender Anzahl der Dimensionen verkleinert. Schon bei der Anwendung im 3-dimensionalen Raum ergeben sich für den Wanderer mehr Möglichkeiten sich zu bewegen. Anstatt nur nach rechts oder links zu gehen kann er sich nun ebenfalls nach vorn und nach hinten bewegen, wobei auch hier die Wahrscheinlichkleit nur ein lokales Maximum zu erreichen vegleichsweise hoch ist. Die eigentliche Anwendung des Sintflut-Algorithmus liegt aber sowieso hauptsächlich im hochdimensionalen Raum mit 100 Dimensionen und mehr z.b. beim TSP.
Anwendung des Sintflut-Algorithmus im 3-dimensionalen Raum
Zum Abschluss findet man hier noch ein sehenswertes Video von Tobias Scheuer, das den Sintflut-Algorithmus einfach und verständlich erklärt.
Fazit
Übungsaufgaben
Quellen
Literatur
- [1] Christian Wagenknecht
- Algorithmen und Komplexität,- Fachbuchverlag Leipzig, 2003.- ISBN 3-446-22314-2
- [2] Doina Logofatu
- Grundlegende Algorithmen mit Java - Vom Algorithmus zum fertigen Programm: Lern- und Arbeitsbuch für Informatiker und Mathematiker ,- Verlag Vieweg+Teubner, 2007.- ISBN 3834803693
Weblinks
[1] Wikipedia Heuristik
[2] Wikipedia Tabu-Suche
[3] Construction Heuristics
[4] fh-friedberg Sintflut
[5] www.omnisophie.com
[6] www.siebn.de