Näherungsverfahren 1 SS11

Aus ProgrammingWiki

< AuK
Wechseln zu: Navigation, Suche

Autoren:



Inhaltsverzeichnis

Approximation des Optimums

In der Praxis interessiert man sich für NP-vollständige Probleme, für denen es keine effizienten Algorithmen gibt. Für eine sinnvolle Lösung sind deshalb "Ersatzalgorithmen" sinnvoll, die sich durch eine Modifizierung des Problems gefunden werden können. Das geschieht z.B. durch das Verstärken oder Abschwächen von Nebenbedingungen oder durch das Einschränken auf Teilprobleme. Das Ergebnis solcher Näherungsalgorithmen sollte sich möglichst geringfügig von der exakten Lösung abweichen.

Heuristik

Der Begriff Heuristik kommt aus dem griechischen "heuriskein" und bedeutet "auffinden" oder "entdecken". Eine Heuristik ist eine Methode, mit der man ein Problem sinnvoll lösen kann, die aber nicht immer funktioniert. Es werden aus einer Vielzahl von Möglichkeiten eine gewisse Anzahl von Möglichkeiten herausgefiltert. Ein Bauer sagt zum Beispiel am Abend schlechtes Wetter für den nächsten Tag vorher und mach am nächsten Tag nur die Aufgaben, die bei schlechtem Wetter möglich sind. Dabei wendet er globale und individuelle Erfahrungsgrundsätze an.

Der Unterschied zwischen Heuristiken und probabilistische Algorithmen besteht darin, dass bei probabilistischen Algorithmen Entscheidungen durch Zufall getroffen werden.

Heuristiken eignen sich vermutlich für NP-vollständige Probleme.

Heuristiken für das Springerproblem

Das Springerproblem, auch das Problem des Rösselsprungs genannt, wurde vor über 200 Jahren von Euler folgendermaßen formuliert:

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

Ein Springer ist eine Schachfigur, die sich von ihrem aktuellen Feld zu einem Feld bewegen kann. Dabei gilt entweder

und oder
und ,

"Im Klartext" bedeutet dies, dass der Springer in einem Zug in jede Richtung zwei Felder vorwärts und ein Feld seitwärts bewegt werden kann. Die Koordinaten können dabei Werte natürlicher Zahlen aus [] annehmen.

Die Anzahl der erreichbaren Felder variiert dabei, so kann ein Springer in einer Ecke des Brettes lediglich zwei mögliche Züge ausführen, während ein Springer in der Mitte des Brettes ganze acht Zugmöglichkeiten besitzt. Ein Schaubild mit Springer S und Springer R plus deren mögliche Züge veranschaulicht den Sachverhalt.

Folgefelder vom Rand und von der Mitte des Brettes

Zu beachten ist, dass es sich bei dem Springerproblem um ein Entscheidungsproblem handelt. Das bedeutet, es wird nicht nach einem konkreten Weg gefragt, sondern lediglich nach der Existenz eines solchen. Auch das Startfeld des Springers ist nicht festgelegt, das heißt, dass auf jedem der Felder begonnen werden kann. Dies ist wichtig, da im Allgemeinen nicht für jedes Startfeld ein (vollständiger) Springerweg besteht.

Das Springerproblem kann als eine Art des -Weg-Problems (alle Knoten eines Graphen werden genau ein Mal besucht) aufgefasst werden. Im Gegensatz zu diesem allgemeineren Problem ist das Springerproblem jedoch nicht NP-vollständig, d.h. zur Lösung existieren effiziente Algorithmen.

Die wohl simpelste Herangehensweise wäre ein schlichter naiver Algorithmus mit Backtracking, dieser scheitert jedoch schon an relativ kleinen Schachbrettern (etwa ab Größe 10 10) aufgrund des exponentiellen Aufwandes. Jedoch gibt es ebenfalls einen Algorithmus, der das Problem für große Bretter in exakt löst(im Prinzip für eine gerade Feldzahl in . Mit diesem Algorithmus soll sich nun jedoch nicht näher befasst werden.

Eine sehr bekannte Heuristik zur Lösung des Springerproblems stellt die -Heuristik dar. ihr liegt die einfache (und richtige) Vermutung zugrunde, dass ein Feld eher Gefahr läuft, isoliert zu werden(und damit eine Lösung auf dem aktuellen Weg ausschließt), wenn es nur wenige mögliche Folgefelder gibt, da diese Anzahl gleich der Anzahl Felder ist, von denen aus man das entsprechende Feld betreten kann. Davon ausgehend lassen sich folgende Regeln formulieren:

  • Ziehe stets auf das Feld mit der niedrigsten Zahl (noch) möglicher Folgefelder.
  • Sollten mehrere Folgefelder die gleiche Zahl möglicher Folgefelder aufweisen, ziehe auf das zuletzt betrachtete Feld. (Es kann auch genauso gut das zuerst betrachtete Feld sein, entscheidend ist lediglich, dass ein geeignetes Feld gewählt wird)

Ein diese Heuristik nutzender Algorithmus leistet folgendes:

  • Das zuletzt besuchte Feld ist nicht mehr begehbar und wird somit als Folgefeld für alle Felder gestrichen (dh. implizit, die Feldwerte der Folgefelder werden dekrementiert.)
  • Das zuletzt besuchte Feld wird als ebensolches markiert und landet in einer Wegliste.
  • Das als nächstes zu besuchende Feld wird nach o.g. Kriterien ermittelt.
  • Sollte es kein Folgefeld geben, wird abgebrochen (und z.B. eine Fehlermeldung ausgegeben.)
  • Nach Zügen wird eine Springertour ausgegeben.

Diese Heuristik liefert eine näherungsweise Lösung des Springerproblems, jedoch meidet diese Heuristik für hinreichend große Felder nicht alle Sackgassen. Für hinreichende kleine Bretter (2 4, von der Triviallösung für = 1 kann getrost abgesehen werden) gibt es hingegen keinerlei Lösungen.


Diese Heuristik arbeitet ebenfalls in Polynomzeit, genauer in , jedoch nur, falls sie alle Sackgassen meidet. Da dies, wie bereits angebracht, nicht für beliebig große Bretter zutrifft, arbeitet der Algorithmus tatsächlich mit einem höheren Aufwand als dem angegebenen.

Aufgrund dieser Tatsache liegt es nahe, die Heuristik zu modifizieren, um so einen effizienteren Algorithmus erzeugen zu können. So könnte zum Beispiel einfach das nächste zu besuchende Feld zufällig ausgewählt werden, anstatt das letzte geeignete Feld zu betreten. Auch andere Modifikationen sind sinnvoll, wie zum Beispiel:

  • Wähle als nächstes Feld das am nächsten zur Brettmitte gelegene.
  • Wähle als nächstes Feld jenes, welches die größte Summe aller Feldwerte dessen möglicher Folgefelder besitzt.

Neben dem klassischen Springerproblem gibt es auch Varianten mit verschärften Bedingungen:

  1. Gibt es eine geschlossene Springertour? (D.h., der Springer kann vom Zielfeld in einem Zug das Startfeld erreichen.)
  2. Gibt es einen Springerweg auf einem Schachbrett von einem vorgegebenen Startfeld S zu einem vorgegebenen Zielfeld Z?
  3. Gibt es einen Springerweg auf einem Schachbrett von einem vorgegebenen Startfeld S zu einem vorgegebenen Zielfeld Z?

Problem 1 lässt sich auch mit der Frage nach der Existenz eines -Kreises beschreiben.

Lokale Suche

Verzweigen und Begrenzen, Greedy und Hill Climbing

Verzweigen und Begrenzen können unter bestimmten Vorraussetzungen für Approximationen verwendet werden. Die erforderliche Schrankenfunktion muss durch eine grobe Schätzfunktion ersetzt werden. Bei Greedy-Verfahren muss die zugrunde liegende Struktur ein Matroid sein, wie zum Beispiel beim Bruchteil-Rucksackproblem. Durch Anwendung des Gerrdy-Verfahren auf das 0/1-Rucksackproblem bekommt man Näherungslösungen. Hier handelt es sich um eine Greedy-Heuristik. Greedy-Heuristiken streben nach einer Verbesserung und sind dafür weder bereit, eine Entscheidung zu revidieren noch eine vorübergehende Verschlechterung hinzunehmen.

Beispiel TSP (Nearest-Neighbour-Heuristik)

Greedy-Heuristiken können zum Beispiel auf das TSP angewendet werden. Da wird der Knoten als nächstes in die Rundreise eingebindet, der den größten Gewinn realisiert. Dadurch entsteht eine kürzere Rundreise. Man wählt den Knoten als nächstes aus, der dem jeweils aktuellem Standort am nächsten liegt. Diese Heuristik wird Nearest-Neighbour-Heuristik genannt. Sie hat einen Aufwand von . Die Nearest-Neighbour-Heuristik liefert im Allgemeinen keine guten Ergebnisse.

Farthest Insertion, Random Insertion, Best Insertion

Farthest Inerstion bietet bessere Ergebnisse. Die Tour wird erweitert, indem man am engsten zusammenliegenden Knoten den Knoten anfügt, dessen Minimalabstand zu einem bereits auf der Rundreise liegende Knoten maximal wird. Bei der "Random insertion"-Methode integriert man einen zufällig noch nicht benutzten Knoten so, dass die Rundreiselänge minimal wird.

Größere Schritte sind besser, als kleinere. Man zerstört Städte, die im Kreis stehen. Dann baut man sie wieder auf, wobei man sie mittelst "Farthest-Insertion" in die Rundreise integriert. Das nennt man "best insertion".

Hill Climbing

Es gibt noch weitere Verbesserungsstrategien, wie zum Beispiel Hill Climbing (Bergsteigen). Hier verfährt man, wie ein Autofahrer, der in der Nacht versucht, ein Hotel auf einem Berg zu finden. Er entscheidet sich an jeder Weggabelung für den Weg mit dem größten Anstieg. Da Nebel ist, kann er keine gute Sicht auf dem Weg. Der Fahrer ist sehr enttäuscht, wenn er auf einem Nebengipfel landet, wo er sein Hotel nicht sehen kann in allzu großer Ferne. Hill-Climbing ermittelt ein lokals statt ein globales Optimum und ist eine sehr einfache lokale Verbesserungsstrategie. Diese Methode wird auch zum Nachbessern von Näherungslösungen genutzt. Beim TSP kann man eine vorgeschlagene Rundreise durch Modifikation der Streckenführung an zwei zufällig (nicht benachbart) ausgewählten Knoten zu einem neuen Minimum führen. Die Entfernungsmatrix muss dafür symmetrisch sein und die Rundreise darf nicht in zwei Komponenten fallen. Hill Climbing erwartet einen Lösungsvorschlag, der durch Modifikation verbessert wird.

Solche Heuristiken werden in unseren täglichen Leben genutzt zum Beispiel bei Planungen. Beim Kofferpacken beispielsweise beginnt man mit den wichtigeren bzw. größten Teilen. Danach kommen die weniger wichtigen Teile, bis es Schwierigkeiten beim Verpacken gibt, die unüberwindbar sind.

Threshold accepting, simulated annealing , Tabu-Suche

Man kann noch bessere Näherungslösungen erreichen, wenn man zwischenzeitliche Verschlechterungen in Kauf nimmt. Man arbeitet dabei mit einer Toleranzschwelle (threshold) . Die Lösung wird verworfen, wenn eine lokale Veränderung zu einer Bewertung führen würde, die mehr als unter der der Vorgängerlösung liegt. Der in der Veranschaulichung genannte Autofahrer würde auch Straßen mit einem sehr geringen Gefälle nutzen. wird langsam auf Null sinken, wenn über längere Zeit keine Verbesserungen stattfinden. Das entspricht dem Hill Climbing. kann auch so groß gewählt werden, dass daduch kaum Beschränkungen entstehen. Es kann nicht garantiert werden, dass wirklich das globale Optimum gefunden wird. Wenn der in der Veranschaulichung genannte Autofahrer nach einiger Fahrzeit und schon reduzierten auf einem Nebengipfel ist, dann kann er von dort nicht mehr zurück. Um das zu vermeiden wurde 1983 eine Idee des simulierten Ausglühens (simulated annealing) von Scott Kirkpatrick, C.D.Gellat und M.P.Vecchi in IBM-Forschungszentrum Yorktown Heights entwickelt. Es wird zufällig entschieden, ob man den Kandidaten nicht doch zulässt. Die Wahrscheinlichkeit für diese Genehmigung ist von der Größe der -Überschreitung abhängig. Kleine Verschlechterungen werden eher toleriert, als größere. Es werden gelegentlich sogar sehr große Abweichungen zu zugelassen. Das ermöglicht den Rückzug zum Nebengipfel. Simulated-annealing-Verfahren verfangen sich sehr leicht in lokalen Optima und brauchen lange Zeit, um da wieder wegzukommen. Bei Threshold acceptiong und simulated annealing können auch ein oder mehrere Schritte rückgängig gemacht werden. Die vorangegangengen Lösungen müssen gespeichert werden, damit sichergestellt wird, dass im jeden Schritt wirklich nur neue Lösungen erzeugt werden. Diese Lösungen werden in sogenannten Tabu-Listen gepspeichert. Wenn eine neue Lösung mit einer Lösung in der Tabu-Liste übereinstimmt, wird sie nicht genommen. Diese Heuristik heißt Tabu-Suche.

Sintflut Algorithmus

Bei Sintflut Algorithmen gibt es eine globale untere Schranke für den Zielfunktionswert. Im jeden Schritt kann zwischen eine besseren oder schlechteren Lösung entschieden werden. Das gilt nur, wenn dadurch nicht unterschritten wird. Im Verlauf des Prozesses wird langsam erhöht, bis die Freiheitsgrade für weitere Schritte versiegen. Das veranschaulicht eine Sintflut, die den Wasserstand (S) auf der Erde langsam weiter ansteigen lässt. Der Wasserstand steigt solange an, bis ein Bergsteiger ertrinkt, der vor den Wassermassen auf einem höheren Punkt zu flüchten versucht. Der Sintflut-Algorithmus ist fast genauso gut, wie threshold accepting, aber nicht ganz so stabil in der Lösungsqualität. Wenn man diesen Algorithmus geschickt implementiert, wird er etwas schneller. Threshold accepting und Sintflut arbeiten deterministisch im Gegensatz zu Simulated annealing.

Video

DNA Computing

In der Genetik wurden neue Arbeitsbereiche für die Informatik geschaffen. In der Informatik nutzt man für den Entwurf neuer Methoden und Inhalte Vorbilder aus der Biologie. Hieraus entwickelten sich DNA Computing und Evolutionäre Algorithmen.

1994 wurde eine neue Instanz des gerichteten HAMILTON-Kreis-Problems mit 7 Knoten durch die Interaktion zwischen DNA-Molekülen von Leonard Adleman gelöst. Das Ergebnis war eine Berechnungstechnik. Damit entstand ein neues Forschungsgebiet der Informatik. Die Effizienz des Verfahrens war schlechter, als die Effizienz von klassischen Verfahren. Der Rechenprozess wurde im Reagenzglas durchgeführt. Es werden DNA-Computer entwickelt, die die zugrunde liegenden biologischen Operationen als Grundoperationen sehr schnell ausführen. Damit wird die massive Parallelisierbarkeit ausgenutzt und eine erhebliche Effizienzverbesserung erzielt. Dieses Forschungsgebiet ist brandaktuell.

Evolutionäre Algorithmen

Der Prozess der Evolution ist ein Prozess, der in der Natur dafür sorgt, dass sich Arten bzw. Populationen bestimmten Bedingungen anpassen. Dies geschieht durch verschiedene Faktoren (Mutation, Selektion, Rekombination als Hauptfaktoren) und dient dazu, Populationen gegenüber oben genannten Bedingungen zu optimieren, damit sie höhere Chancen haben, ihre Existenz beizubehalten.

Mutation als zufälliger Faktor ist dazu gedacht, mögliche neue Varianten zu finden, um festzustellen, ob sie für ihren Lebensraum eine verbesserte Anpassung darstellen oder ungeeignet sind. Mutation sorgen für gewöhnlich nur für geringfügige Veränderungen am Genpool einer Population, sind aber die Grundlage für Veränderungen in der Evolution, da sich viele kleine Änderungen zu einer großen Gesamtänderung aufsummieren.

Rekombination beschreibt den Prozess, aus dem Erbgut zweier Individuen Erbgut für ein Nachkommenindividuum zu erzeugen, das sich aus dem alten Erbgut zusammensetzt. Durch diesen Faktor können Kombinationen von Eigenschaften gefunden werden, die dem Optimum näher kommen als die vorhandenen.

Selektion als einziger gerichteter Vorgang sorgt dafür, dass sich eher bzw. nur die vorteilhaftesten Eigenschaften einer Population durchsetzen. Dabei wird in der Natur allerdings kein höheres Ziel angesteuert, sondern lediglich die Optimale momentane Anpassung erstrebt. Ein Fitnesswert, der aussagt, wie viel ein Individuum im Moment "taugt". So kann zum Beispiel über die Anzahl der Nachkommen ein Fitnesswert mit folgender Formel gebildet werden:

G' stellt dabei das Individuum mit der höchsten Anzahl an Nachkommen in der Population dar.

Wie sich bis hier leicht erkennen lässt, ist Evolution ein Optimierungsprozess mit den Faktoren als Funktionen. Durch diesen Umstand wäre es mehr als eine Überlegung wert, zu versuchen, einen Evolutionsprozess zu simulieren, um Optimierungsprobleme algorithmisch zu lösen. Wenn davon ausgegangen wird, dass die Menge aller Lösungskandidaten (im weiteren als Individuen bezeichnet) den Suchraum definiert und jedem Kandidaten ein Gütewert durch eine Funktion zugewiesen werden kann, die durch eine Vergleichsrelation mit anderen Gütewerten verglichen werden kann, dann kann man die Menge der globalen Optima, also der Optimallösungen, wie folgt definieren:

Der evolutionäre Algorithmus, um sich dieser Lösung zu nähern, lässt sich mit einem Zyklus darstellen.

Ein evolutionärer Algorithmus

Hierbei bedeutet Initialisierung die Auswahl einiger Lösungskandidaten aus dem Suchraum, um eine "Startpopulation" herzustellen, also eine für den Algorithmus geeignete Menge von Lösungskandidaten. Diese wird nun nach der oben genannten Funktion bewertet. Anschließend wird der Evolutionsprozess so lang wiederholt, bis die End- bzw. Terminierungsbedingung erfüllt ist (wenn zum Beispiel der Grad der Verbesserung des bis jetzt gefundenen Optimums unter einen festgelegten Wert fällt oder aber eine bestimmte Anzahl an Durchläufen erreicht wurde.) Die Darstellbarkeit des Suchraumes sowie eine geeignete Bewertungsfunktion sind dabei die einzigen Vorraussetzungen, die erfüllt sein müssen, dait der Algorithmus für ein Problem angewendet werden kann.

Am Beispiel des TSP kann nun gezeigt werden, wie der simulierte Evolutionsprozess abläuft. Es kann gesagt werden, dass für eine Anzahl von Städten eine Permutation gesucht ist, für die gilt:

Dabei bezeichnet die Fahrzeit bzw die Kosten der Kante. Nun werden Unteralgorithmen entwickelt, mit denen die einzelnen Faktoren simuliert werden können. So kann für den Mutationsprozess zum Beispiel eine vertauschende Mutation entwickelt werden. Dabei werden einfach ein und ein vertauscht. Dies würde bei einem Individuum (1, 2, 3, 4, 5, 6, 7, 8) mit = 2 und = 6 zu einer Mutation (1, 6, 3, 4, 5, 2, 7, 8) führen. Würden diese Individuen grafisch dargestellt, so wäre zu sehen, dass 4 Kanten entfernt und 4 neue Kanten eingefügt werden.

Eine weitere Variante der Mutation besteht zum Beispiel darin, ein Teilstück des Individuums zu invertieren, indem wieder ein und ein zufällig ausgesucht werden, wobei es sich hier um Anfang und Ende des zu invertierenden Teils handelt. Darum sollte hier auch gelten (dies kann auch durch ein Vertauschen der beiden Werte, falls nötig, erreicht werden). Da sich bei grafischer Darstellung zeigt, dass bei dieser Mutation nur 2 Kanten gelöscht und 2 ergänzt werden, ist diese Mutation vorzuziehen, da Mutationen kleine Veränderungen darstellen sollten.

Sollte gelten, so ist diese Mutation neutral, dies ist durchaus zulässig.

Der nächste Faktor, Rekombination, stellt einen anderen Ansatz dar. Anstatt kleine zufällige Veränderungen durchzuführen, wird aus jeweils 2 Individuen ein neues erzeugt, das möglichst viele Eigenschaften der Eltern erbt und dabei noch Teil des Suchraumes bleibt. Die Herangehensweise soll dabei die folgende sein: Zuerst werden mögliche Adjazenzinformationen für jeden Knoten des neuen Individuums erzeugt, dies geschieht durch Vereinigung der Adjazenzinformationen beider Eltern für den jeweiligen Knoten. Anschließend wird der Anfangswert eines der "Elternteile" als Anfangswert des neuen Individuums gesetzt. Nun wird aus der Vereinigungsmenge ein geeigneter Nachfolgerknoten ausgewählt. Wie schon beim Springerproblem ist es ratsam, einem Knoten mit weniger Folgeknoten den Vorzug zu geben, um Isolationen zu vermeiden. Sollte es dennoch zur Isolation eines Knotens kommen, so muss stattdessen ein zufälliger Nachfolgerknoten aus den verbleibenden ausgewählt werden.

Da nun diese Funktionen zur Verfügung stehen, kann der komplette Algorithmus zur evolutionären Lösung des TSP entwickelt werden. Dazu ist als erstes eine Liste mit einer kleinen Anzahl an Individuen, zum Beispiel 10. Nun werden alle dieser Individuen mit der Zielfunktion bewertet. Danach beginnt der eigentliche simulierte Evolutionprozess. Aus den vorhandenen Individuen werden durch Rekombination (nur in einigen Fällen, da ihr Berechnungsaufwand wesentlich höher ist als der einer Mutation) und Mutation völlig neue Individuen erzeugt(zum Beispiel 40 Individuen.) Nun werden diese neuen Individuen ebenfalls bewertet. Anschließend werden aus allen vorhandenen Individuen (10 Startindividuen und 40 neue Individuen = 50 Individuen gesamt) die besten 10 ausgewählt, mit denen der Zyklus fortgesetzt wird. Nach einer festgelegten Anzahl Durchläufen endet der Algorithmus und gibt das bis dahin beste, d.h. dem Optimum am nächsten gekommene Individuum aus und gibt es zurück.

Neuronale Netze

Ein neuronales netz, ein Produkt der gehirnforschung, besteht aus vielen (künstlichen) Neuronen, die untereinander mit gewichteten Verbindungen gekoppelt sind. Die Gewichte sorgen dabei für Hemmung bzw Erregung der Reizweiterleitung, die in der Natur über Dendriten(Input) bzw. Axone(Output) über Synapsen (der Kontakt zwischen benachbarten Neuronen) stattfinden.

Sobald die eingehenden Signale einen bestimmten Schwellwert überschreiten, gibt ein Neuron ein elektrisches Signal an andere Neuronen ab. Ein Neuron, das einen solchen Impuls empfängt, kann ebenfalls ein Signal aussenden.

Aus der Zusammenschaltung und "Reizverbindung" von Neuronen ergeben sich zu bestimmen Eingaben bestimmte Ausgaben. Allerdings müssen die Gewichte so korrigiert werden, dass zu einer bestimmten Eingabe auch eine gewünschte Ausgabe stattfindet. Danach kann es auf echte Eingaben reagieren und zur Lösung von Problemen dienen.

Mit genetischen Algorithmen können Lerndaten neuronaler Netze generiert und Gewichte optimiert werden.

Übungen

Quellliteratur

[1] Wagenknecht, Chr.: Algorithmen und Komplexität, Leipzig: Fachbuchverlag, 2003.

[2] Weicker, Karsten: Evolutionäre Algorithmen, Wiesbaden: Teubner Verlag, 2002.

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