Näherungsverfahren 1 SS09

Aus ProgrammingWiki

< AuK
Wechseln zu: Navigation, Suche
Autoren
Daniel Flex sidaflex@stud.hs-zigr.de
Steffen Lehmann sistlehm@stud.hs-zigr.de

Inhaltsverzeichnis

Approximation des Optimums

Motivation

In der Praxis besteht oft großes Interesse an der Lösung von NP-vollständigen Problemen. Wie jedoch das P-NP-Problem zeigt muss davon ausgegangen werden, dass für NP-vollständige Probleme keine effizienten Algorithmen für deren Lösung existieren. Dieser Art von Problemen ist man jedoch nicht völlig hilflos ausgeliefert.

Lösungsverfahren

Heurisitken

Begriff

Der Begriff Heuristik stammt aus dem Griechischen und kann mit "Erfindungskunst" übersetzt werden. Eine Heuristik besteht aus Regeln und Prinzipien, die aufgrund von Erfahrungen oder Intuitionen methodisch zusammengetragen wurden. Das Ziel der Heuristik besteht im möglichst effizienten Lösen eines schweren Problems, dessen exakte Lösung durch mathematische Berechnungen praktisch nicht zu finden ist. Bei Optimierungsaufgaben werden Heuristiken verwendet, um eine Lösung zu finden, die möglichst nahe am Optimum liegt.

Ein Beispiel für Heuristiken sind Bauernregeln, wie

Ist der Mai kühl und nass, füllt's dem Bauern Scheun' und Fass.

Es gab lange Zeit keine Möglichkeit das Wetter zuverlässig vorherzusagen. Auch derzeit ist es nicht möglich für einen längeren Zeitraum eine exakte Vorhersage zu treffen. Die Bauern beobachteten das Wetter und stellten fest, dass auf ein bestimmtes Ereignis in der Regel ein bestimmtes anderes Ereignis folgt. Sie formulierten diese Beobachtung in einer Bauernregel und hatten von da an eine Empfehlung, um ihre Arbeit effizienter gestalten zu können. Die Erfolgsquote einer solchen Regel ist jedoch nicht vorhersehbar.

Hier liegt auch der entscheidende Unterschied zu den probabilistischen Algorithmen, die eine Fehlerwahrscheinlichkeitsbestimmung zulassen.

Weitere Beispiele für Heuristiken findet man im Bereich der Medizin. Schon immer wurden Pflanzen und Kräuter benutzt, um bestimmte Wirkungen, wie das Heilen von Krankheiten oder das Lindern von Schmerzen, bei Menschen oder Tieren zu erzielen. Auch hier war meist nicht bekannt weshalb im Einzelnen diese speziellen Ergebnisse erzielt wurden. Man wusste nur aus Erfahrung, dass sie vielfach eintraten. Heutzutage sind oft zumindest die entscheidenden Wirkstoffe der Pflanzen bekannt und es ist möglich, diese in Medikamentenform herstellen und anbieten zu können.

Das Springerproblem

Das Springerproblem wurde Mitte des 18.Jh von Leonhard Euler formuliert. Es ist ein spezielles Hamilton-Weg-Problem, welches nicht NP-vollständig ist.

Gibt es für einen Springer einen Weg, der jedes Feld eines n x n Schachbrettes genau einmal besucht?

Viele der nachfolgenden Betrachtungen können mit Hilfe der hierzu entwickelten Software nachempfunden bzw. visualisiert werden.[2]

Spielregeln

Zugmöglichkeiten eines Springers

Es wird lediglich nach der Existenz eines Weges gefragt und nicht nach der zurückgelegten Route. Das Startfeld kann frei gewählt werden. Die Zugregeln des Springers sind die aus dem Schach bekannten. Der Springer darf:

  • 2 Felder in vertikaler Richtung ziehen und 1 Feld in horizontaler Richtung oder
  • 2 Felder in horizontaler Richtung und 1 Feld in vertikaler Richtung und
  • natürlich darf er das Spielfeld nicht verlassen

Bei einem Schachbrett mit einer ungeraden Anzahl an Feldern (5x5, 7x7, ...) ist es nicht möglich eine Lösung zu finden, wenn man ein Startfeld der Farbe mit weniger vorhandenen Feldern wählt. Vereinbart man, dass alle Bretter als linke untere Ecke (a1) ein schwarzes Feld besitzen, so betrifft dies immer die weißen Felder von denen man eine Springertour nicht erfolgreich starten kann.

Nichtheuristische Algorithmen

Beispiel für die Zerlegung eines Schachbrettes

Der naheliegendste Versuch das Problem zu lösen, ist der Einsatz von Backtracking. Der Algorithmus durchläuft jede mögliche Kombination und findet daher auch immer eine Lösung, sofern es diese überhaupt gibt. Backtracking scheitert jedoch in diesem Fall schon bei recht kleinen Schachbrettern (etwa ab Größe 10 x 10) am exponentiell wachsenden Zeitaufwand, da dann ein Rechner für das Finden einer Lösung mehrere Monate oder sogar Jahre benötigt. Mit diesem Algorithmus kann leicht gezeigt werden, dass für Bretter der Größe 2x2, 3x3 und 4x4 keine Lösung existiert.

Eine Schülergruppe gelang es 1992 im Rahmen des Bundeswettstreits für Informatik einen vollständige Lösung des Springerproblems anzugeben. Der Conrad Algorithmus wurde nach Axel Conrad einem Mitglied der Gruppe benannt. Die Lösung folgt dem Prinzip Teile und Herrsche. Das Schachbrett wird in 5x5 große Teile zerlegt. Ist die Seitenlänge des Brettes kein Vielfaches von 5, so entstehen bei der Zerlegung L-förmige Teile und ein Mittelteil der Größe 6x6 bis 9x9. Man kann zeigen, dass es möglich ist von einem dieser Teile ins nächste zu Springen und so alle Teile zu durchqueren. Auf der Webseite von Axel Conrad findet man unter anderem auch eine Lösung für rechteckige Bretter.[1]

Warnsdorff Heuristik

H.C. Warnsdorff beschrieb um 1823 eine Heuristik, die sich aus der Beobachtung ableitet, dass häufig die Felder mit der geringsten Anzahl an Folgefelder isoliert wurden. Gibt es von allen möglichen Folgefeldern eines mit nur einem Folgefeld muss es im nächsten Zug besucht werden, ansonsten entsteht eine Sackgasse. Man kann das Feld auch später noch besuchen, jedoch ist dann der Rückweg abgeschnitten. Er stellte folgende Regeln auf und hatte damit eine Näherungslösung gefunden die in liegt:

  • Ziehe auf das Feld mit der geringsten Anzahl möglicher Folgefelder.
  • Haben mehrere Felder die gleiche minimale Anzahl, so ziehe auf das zuerst bzw. zuletzt betrachtete Feld.

Vor einer Springertour muss festgelegt werden in welcher Reihenfolge die zu betrachtenden Felder ausgewählt werden.

Da Warnsdorff alle Springertouren per Hand durchrechnen musste, entging ihm vermutlich, dass sein Verfahren nicht alle Sackgassen meidet. Durch Computeranalysen konnte dies nachgewiesen werden und somit wurde das Verfahren als Heuristik eingestuft. Im aufwandsmäßigen Vergleich mit dem Conrad Algorithmus schneidet es schlechter ab. Es liegen zwar beide in , jedoch gerät der Conrad Algorithmus in keine Sackgassen.

Modifikation der Warnsdorff Heuristik

Modifikationen können zur Verbesserung einer Heuristik führen. Meist müssen jedoch umfangreiche Test durchgeführt werden, um eine Verbesserung zu bestätigen, da eine Verbesserung in einem Instanzbereich eine Verschlechterung in einem anderen zur Folge haben kann.

Das Springerproblem könnte unter anderem wie folgt modifiziert werden:

  • Gibt es aktuell gleichwertige Folgefelder in der Betrachtung so wähle das Feld für den nächsten Zug zufällig aus
  • Ändere die Richtung der Betrachtung von Folgefeldern in Abhängigkeit vom Springerabstand zum Rand.
  • Wähle im nächsten Zug das Feld mit der größten Summe der Feldwerte aller möglichen Folgefelder.

Modifikation des Springerproblems

Wird die Problemstellung verändert wird in den meisten Fällen auch eine Anpassung der Heuristik bzw. des angewandten Algorithmus notwendig. Bei einer Verschärfung des Springerproblems um ein bestimmtes Start- und Zielfeldes scheitert die Warnsdorff-Heuristik.

Folgende neue Problemstellungen lassen sich nun beispielsweise beschreiben:

  • Gibt es eine Springertour von Startfeld S zum Zielfeld Z?
  • Gibt es eine Springertour in der Start und Zielfeld identisch sind?

Lokale Suche

  • Die bereits behandelten Verfahren "branch and bound" und "Greedy" können unter bestimmten Voraussetzungen auch für Näherungen (Approximationen) verwendet werden. Die Vorgehensweise für diese Verfahren wird in den nächsten Abschnitten erklärt.


Verzweigen und Begrenzen

  • Beim Verzweigen und Begrenzen (branch and bound) wird die eigentlich erforderliche Schrankenfunktion durch eine grobe Schätzfunktion ersetzt. Dadurch entfällt die Berechnung für die Schranke (bound). Man akzeptiert keine Schranke ermittelt zu haben, aber die entstandenen Näherungswerte für das Optimum sind trotzdem zufriedenstellend.


Greedy Heuristiken

  • Greedy-Heuristiken streben stets nach einer lokalen Verbesserung und sind dafür weder bereit eine vorübergehende Verschlechterung hinzunehmen, noch eine Entscheidung zu revidieren.
  • Wenn man die Greedy-Heuristiken zur näherungsweisen Lösung des Rundreiseproblems anwendet, dann wird jeweils der Knoten als nächstes integriert der den größten Gewinn realisiert also in diesem Fall eine kürzere Rundreise beschert.

Nearest neighbour heuristic

  • Bei dieser Methode wählt man einen beliebigen Startpunkt auf der Rundreise und bindet dann jeweils den Knoten mit dem minimalsten Abstand zum aktuellen Knoten ein. Diese Variante ist natürlich sehr einfach, aber die entstandenen Ergebnisse sind nicht wirklich gut. Hier ein Link zum Applet was die Methode grafisch darstellt:
    Applet - nearest neighbour heuristic (Mertens)

Farthest insertion

  • Hier wird die Tour um jeweils den Knoten, dessen Minimalabstand zu einem bereits auf der Route vorhandenen Knoten maximal ist, erweitert. Hat den jeweiligen Knoten ermittelt wird er so in die Rundreise integriert das Streckenzuwachs minimal ist.
  • Dafür gibt es verschiedene Ansatzmöglichkeiten:
  1. Wie im Buch "Algorithmen und Komplexität" von Prof. Wagenknecht beschrieben, beginnt man mit den jeweils am engsten zusammenliegenden Knoten und erweitert die Tour dann wie oben beschrieben.
  2. Herr Mertens von der Universität Magdeburg beschreibt auf seiner Website eine andere Vorgehensweise.
    • Man beginnt mit den Knoten die das größte Dreieck aufspannen und integriert dann die restlichen Knoten oder
    • Man benutzt eine "Konvexe Hülle". Es wird eine Verbindung durch alle am äußersten Rand liegenden Knoten hergestellt, so dass man eine Art Hülle um alle noch nicht integrierten Knoten erhält. Anschließend bindet man diese Knoten wie gehabt ein.
    • Eine Beschreibung und ein schönes Applet was diese Vorgehensweise verdeutlicht findet man unter folgendem Link:
      Applet - farthest insertion (Mertens)
  • Diese Anwendung führt zu guten Werten.

Random insertion

  • Die random insertion führt zu ebenfalls guten Werten.
  • Die Vorgehensweise ist ähnlich der farthest insertion mit dem Unterschied das die Knoten zufällig ausgewählt werden. Dadurch wird die Zeit für die Ermittlung des Knoten, dessen Minimalabstand am maximalsten ist, eingespart.

Best insertion

  • Man hat herausgefunden das größere Schritte besser sind als kleine.
  • Anstelle beim TSP die Auswirkungen kleinerer Veränderungen zu betrachten, wählt man große.
  • Ähnlich wie bei einem Bombenabwurf zerstört man in einem kreisförmigen Gebiet alle Städte, baut sie nacheinander wieder auf und integriert sie mittels Farthest-insertion-Methode.
  • Die Rundweglänge in diesem Ruin-and-create-Bereich ist danach meist kürzer als vorher.

Hill climbing

  • auch local search genannt
  • Es stellt eine einfache lokale Verbesserungsstrategie dar, die gelegentlich ein lokales anstelle des globalen Optimums ermittelt
  • Zum Beispiel ein Bergsteiger der einen Gipfel erklimmmen will nimmt an jeder Gabelung den Weg mit dem höchsten Anstieg. Wenn er am Ende angekommen ist kann es durchaus passiert sein das er auf einem Nebengipfel gelandet ist.
  • Auf das Rundreiseproblem angewandt werden in der fertigen Rundreise zufällig 2 nicht benachbarte Knoten ausgewählt und zu einem neuen Minimum geführt. Das gelingt wenn die Entfernungsmatrix symmetrisch ist und die die Rundreise dadurch nicht in 2 Komponenten zerfällt.
  • Im Unterschied zu Greedy-Verfahren erwartet hill climbing einen Lösungsvorschlag der durch Modifikation (hoffentlich) verbessert wird.
  • Um einen ersten Lösungsvorschlag bereitzustellen ist es sinnvoll zuerst Greedy anzuwenden.
  • Applet - hill climbing


Diese einfachen Heuristiken werden im täglichen Leben verwendet und entsprechen unserer Intuition.
Bei vielen Planungen, z.B. Kofferpacken beginnnen wir immer mit den wichtigsten, den größten Teilen. Danach folgen weniger wichtige bis man auf unüberwindliche Verpackungsschwierigkeiten stößt.
Dennoch sind diese Heuristiken in vielen Fällen erfolgreich. Aber es gibt noch bessere Verfahren wie z.B.:


Threshold accepting

  • es hat sich gezeigt, das zwischenzeitliche Verschlechterungen in Kauf zu nehmen noch bessere Näherungslösungen bringt
  • diese Verschlechterungen werden angenommen solange diese nicht mehr als T (Toleranzschwelle-treshold) unter der Vorgängerlösung liegen, ansonsten wird eine andere Lösung versucht
  • am Anfang kann T so groß gewählt werden dass es kaum Beschränkungen gibt
  • der Bergsteiger aus dem vorhergehenden Beispiel darf dann auch Wege benutzen die nicht den höchsten Anstieg haben
  • gibt es längere Zeit keine Verbesserung senkt man T langsam auf 0
  • die Findung des globalen Optimum ist nicht garantiert

Simulated annealing

  • simuliertes Ausglühen
  • 1983 entwickelt von Scott Kirkpatrick, C.D. Gellat und M.P. Vecchi vom IBM-Forschungszentrum Yorktown Heights (USA)
  • wie beim treshold accepting gibt es auch hier eine Toleranzschwelle T
  • beim unterschreiten dieser Schwelle wird zufällig entschieden ob der Kandidat zugelassen wird
  • die Akzeptanz hängt dabei von der Abweichung zu T ab
  • kleine Abweichungen werden eher toleriert als große Abweichungen
  • leider verfangen sich Simulated-annealing-Verfahren sehr leicht in lokalem Optima und benötigen relativ lange Zeit um von dort wieder wegzukommen
  • je größer die Werte für die Problemgröße n sind, desto geringer die Chance das die Treshold-accepting-Verfahren zu einem lokalen Optima führen

Tabu-Suche

  • bei den vorherigen Verfahren kann es vorkommen das ein oder mehrere Schritte rückgängig gemacht werden
  • damit wirklich nur neue Lösungen erzeugt werden, muss man die vorangegangenen k Lösungen speichern
  • dies wird in Tabu-Listen realisiert, welche eine oder mehrere Warteschlangen implementieren
  • ist ein Ergebnis in einer Tabuliste bereits vorhanden wird es verworfen


Sintflut-Algorithmus

  • während beim Treshold-accepting-Verfahren für jeden Schritt ein Schwellwert vorgegeben wird, gibt es bei den Sintflut-Algorithmen eine Art globale untere Schranke S für den Zielfunktionswert
  • es kann in jedem Schritt zwischen besserer und schlechterer Lösung entschieden werden, wenn S dadurch nicht unterschritten wird
  • im weiteren Verlauf wird S langsam erhöht bis es keine Freiheitsgrade für weitere Schritte gibt
  • zur Veranschaulichung: Eine Sintflut lässt einen Wasserstand (S) immer weiter ansteigen während ein Bergsteiger versucht auf einen möglichst hohen Punkt zu flüchten und dabei ertrinkt. Es war ihm aber jeder Aufstieg genauso möglich wie ein Abstieg ins Tal.
  • der Sintflutalgorithmus ist beinahe so gut wie treshold accepting, allerdings nicht so stabil in der Qualität der Lösungen
  • treshold accepting und Sintflut arbeiten im Gegensatz zu simulated annealing deterministisch
  • diese Verfahren die Veränderungsschritte berechnen schneiden besser ab als Verfahren die diese zufällig ermitteln
  • Hier gibt es ein interessantes Video von Gunter Dueck zum Thema Sintflutalgorithmus.

Übungsaufgaben

  1. Gehen Sie anhand der Software[2] den Vorlesungsstoff zum Thema Springerproblem noch einmal durch.
  2. Versuchen Sie auf der Rückseite des in der Vorlesung ausgegebenen Blattes eine Rundreise in den Graphen zu finden. Informieren Sie sich hier über die Lösung des Problems.
  3. Überlegen Sie wie die Warnsdorff Heuristik verändert werden muss, damit eine geschlossene Springertour entsteht.
  4. Gehen Sie noch einmal die verschiedenen Heuristiken durch und machen Sie sich mit ihnen vertraut.
  5. Probieren Sie an dem in der Vorlesung gezeigtem Beispiel eigene Lösungen für die verschiedenen Heuristiken zu finden und vergleichen Sie die Lösungen anschließend.
  6. Wenden Sie den Sintflutalgorithmus auf dieses Beispiel an.


Literatur

  • Christian Wagenknecht Algorithmen und Komplexität. Fachbuchverlag Leipzig, 2003, ISBN 3-446-22314-2, Seite 153-163


Siehe auch

Hamilton Wege
TSP/Mertens
Startseite

Einzelnachweise

[1] Axel Conrad Das Springerproblem
[2] Software zur Veranschaulichung des Springerproblems

Von „https://programmingwiki.de/AuK/N%C3%A4herungsverfahren_1_SS09“
Persönliche Werkzeuge