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".
Motivation
Anwendungsgebiete
Wirtschaftswissenschaften
Philosophie
Psychologie
Mathematik
Informatik
Heuristiken werden in der Informatik hauptsächlihc genutzt um mit möglichst geringem Rechenaufwand ein meist recht komplexes Problem zu lösen und eine zwar nicht optimale, aber dennoch zulässige Lösung zu erhalten. Es wird also im gegensatz zu anderen Algorithmen nicht garantiert, dass eine optimale Lösung errechnet wird, wodurch sich der Rechenaufwand und die somit benötigte Zeit meistens stark reduzieren und manchmal sogar fast minimieren. Bekannte Heuristiken sind zum Beispiel Simulated annealing und Greedy-Heuristiken, wie zum Beispiel die Nearest neighbour heuristic oder die Farthest insertion heuristic.
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 des Springers vielleicht besser nachvollziehen zu können.
Modifikationen der Warnsdorff Heuristik
Es ist möglich eine Heuristic zu modifizieren um eventuell eine Verbessserung zu erreichen, jedoch kann man bei Heuristiken nur sehr schwer nachweisen in wieweit die Heuristik sich verbessert hat, da sehr umständliche und komplizierte Tests durchgeführt werden müssen.
Nun einige Modifikationen der Warnsdorff Heuristik:
1. Wähle nicht das zuletzt/zuerst betrachtete Feld mit dem geringsten Feldwert, sondern das zuerst/zuletzt betrachtete Feld.
2. Wähle bei gleichwertigen Feldwerten die Felder mit den geringsten Feldwerten und bei einer Dopplung wähle eines zufällig aus.
3. Wähle das Feld, das die größte Summe aller Feldwerte der möcglichen Foldefelder hat.
4. Wähle das Feld, das am weitesten vom Brettrand entfernt ist, also in Zentrumsnähe liegt.
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
Das Ergebnis ist ein Näherungsalgorithmus, dessen Ergebnis zwar vom Optimum abweichen wird, jedoch kann man in den meisten Fällen sagen, dass die Ergebnisse zufriedenstellend bis gut sind, also in der Regel eine kaum nennenswerte Abweichung vom Optimums aufzeigen.
Greedy-Heuristiken
Der Unterschied zu einem zwischen einer Greedy-Heuristik und einem Greedy-Verfahren ist hauptsächlich besteht zum einem in der Qualität der Lösungen, da ein Greedy-Verfahren eine exakte Lösung und eine Greedy-Heuristik nur eine Näherungslösung, welche jedoch in den meisten Fällen recht nah an der exakten Lösung liegt. Ein Greedy-Verfahren benötigt, anders als eine Greedy-Heuristik, zur Angabe einer exakten Lösung ein Matroid als zugrunde liegende algebraische Strucktur. Es ist beispielsweise beim Bruchteil-Rucksackproblem der Fall, dass die zugrunde liegende algebraische Strucktur ein Matroid ist, jedoch nicht beim 0/1-Rucksackproblem. Wendet man trotz des nicht vorhandenem Matroids beim 0/1-Rucksackproblem dennoch ein Greedy-Verfahren an, so erhält man eine Näherungslösung und man spricht dann von einer Greedy-Heuristik.
Greedy-Heuristiken zeichnen sich dadruch aus, dass sie immer nach einem lokalem Optimum suchen und weder bereit sind eine Entscheidung zu revidieren noch eine lokale Verschlechterung zu ermöglichen.
Wenn man zum Beispiel eine Greedy-Heuristik zur Lösung des TSP verwenden möchte so wird man versuchen gerade den Knoten einzubinden, der den größten Gewinn, also hier die kürzeste Rundreise beschert. Beispielsweise könnte man auf die Idee kommen immer den Knoten einzubinden, welcher dem gerade betrachteten am nächsten liegt. Diese Strategier nennt man nearest neighbor heuristic. Sie ist jedoch in den meisten Fällen nicht wirklich hilfreich, da die Ergebnisse meist unbrauchbar sind oder zumindest ziemlich weit vom Optimum abweichen. Bessere Resultate erhält man zum Beispiel mit der farthest insertion. Bei der farthest insertion beginnt man die Knoten mit dem geringstem Abstand zu verbinden und erweitert die Tour dann um den Knoten, dessen Minimalabstand zu einem bereits auf der Rundreise liegendem Knoten maximal ist. Diese Technik führt zu ebenso guten Ergebnissen wie die random insertion, bei der ein unbenutzter Knoten zufällig ausgewählt wird und so integriert wird, dass die daraus resultierende Länge der Rundreise minimal wird. Ein weiteres Greedy-Verfahren ist die nearest insertion. Bei diesem Verfahren wird der Knoten eingebunden, der die geringste Verlängerung der daraus resultierenden Teilroute zur Folge hat. Es wurde mitlerweile bewiesen, dass größere Schritte besser sind als kleine. Es wird also anstelle kleine Veränderungen beim TSP zu betrachten, eine möglichst große gewählt. Dies führt zu einem weiteren Greedy-Verfahren, der best insertion. Bei diesem Verfahren geht man vor wie bei einem Bombenabwurf, es werden in einem kreisförmigen Gebiet alle Städte zertsört und dann nacheinander wieder aufgebaut, wobei man sie mittels der Farthest-Insertion-Methode in den Rundweg integriert, was best insertion genannt wird. Nach diesem Verfahren aus dem Ruin-and-recreate-Bereich ist die entstandene Länge des Rundweges im allgemeinen kürzer als vorher.
Zwei schöne Applets für Greedy Heuristiken finden sie auf dieser Seite von Stephan Mertens.
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 Bergsteiger aus dem zuvor beschriebenem Problem beim hill-climbing einen Nebengipfel erreicht hat und T bereits gesenkt wurde, so gibt es keine Möglichkeit für den Bergsteiger den höchsten Gipfel zu erreichen.
Simulated annealing
Die Herren Scott Kirkpatrick, Charles D. Gelatt und Mario P. Vecchi vom IBM-Forschungszentrum Yorktown Heights entwickelten 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.
Der Algorithmus baut auf dem sogenannten Metropolisalgorithmus auf, der 1953 von Nicholas Metropolis et al. publiziert wurde. Der Metropolisalgotithmus ist eine Monte-Carlo-Methode(siehe Probabilistische Algorithmen) zur Erzeugung von Zuständen eines Systems basierend auf der Boltzmann-Verteilung. Im Gegensatz zum treshold accepting wird trotz Überschreiten der festen Toleranzschwelle T mit einer bestimmten Wahrscheinlichkeit zufällig entschieden, den Lösungsvorschlag doch zuzulassen. Diese Wahrscheinlichkeit richtet sich nach der Größe der Überschreitung von T. Sehr große Überschreitungen werden dabei deutlich seltener zugelassen als kleinere.
Beim simulated annealing wird nun zusätzlich noch T immer weiter abgesenkt. Dieses Verfahren wir hauptsächlich dazu benutzt ein globales Minimum zu finden. Bezogen auf das beispiel des Bergsteigers bedeutet dies, das er nun versucht in das tiefste Tal hinabzusteigen. Dabei kann es passieren das der Bergsteiger sich in einem lokalen Minimum (Tal) verfängt und erst wieder durch eine große Überschreitung von T frei kommt.
Das untere Video verdeutlicht nochmal die Arbeitsweise des Algorithmus.
Video bei YouTube öffnenTabu-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.
http://www.omnisophie.com/downloads/spektrum mathematische optimierung.wmv .
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 vergleichsweise 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
Man kann sagen, dass Heuristiken in den meisten Fällen zwar keine Optimalen Lösungen zurückgeben, aber da meistens die Lösungen nur sehr geringfügig von einem Optimum abweichen und desshalb sehr nützliche Hilfsmittel sind um bei extrem komplexen Problemen mit möglichst kleinem Aufwand eine gute bis fast Optimale Lösung zu erhalten.
Übungsaufgaben
Überlegen Sie wie man es erreichen kann, dass beim verwenden der Warnsdorff-Heuristik bei der gleichen Startposition unterschiedliche oder gleiche Wege für den Springer entstehen.
Entwerfen Sie für den treshold-accepting-algorithmus einen Programmablaufplan mithilfe des kostenlosen Programmes PapDesigner.
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] Wikipedia hill climbing
[4] Construction Heuristics
[5] fh-friedberg Sintflut
[6] www.omnisophie.com
[7] www.siebn.de