Optimierung

Bei der Optimierung geht es darum aus mehreren Lösungen die (in einem gewissen Sinn) "optimale" zu finden, z.B. minimale Spannbäume, das Handlungsreisendenproblem, das Rucksackproblem, etc.

Exakte Algorithmen für schwierige Optimierunsprobleme

Enumerationsverfahren

Bei den Enumerationsverfahren werden alle Lösungen aufgezählt und aus diesen dann die optimale ausgewählt. Allerdings kann das Bestimmen aller Lösungen sehr lange dauern.

Man kann dieses Verfahren zum Beispiel auf das Rucksackproblem anwenden: Man hat eine Menge von Gegenständen mit Gewicht und Wert sowie einen Rucksack mit Fassungsvermögen gegeben. Nun geht es darum, die Gegenstände mit möglichst hohem Gesamtwert einzupacken, ohne die Kapazität des Rucksacks zu überschreiten.

Auch das Acht-Damen-Problem kann mittels Enumeration gelöst werden. Es geht dabei darum, acht Damen - oder allgemeiner: Damen - so auf einem -Schachbrett zu platzieren, dass sie einander nicht bedrohen. Bei der Enumeration sollte man allerdings beachten, dass in jeder Zeile und jeder Spalte genau eine Dame stehen muss, damit die Aufgabe überhaupt erfüllt werden kann. Beachtet man das nicht, so erreicht der Aufwand .

Dynamische Programmierung

Bei der dynamischen Programmierung zerlegt man das Problem in Teilprobleme, die jedoch voneinander abhängig sind.

Mit ihrer Hilfe kann die Lösung des Rucksackproblems deutlich vereinfacht werden: Man betrachtet zuerst nur die ersten Gegenstände und merkt sich für alle möglichen Werte diejenigen Lösungen, die das kleinste Gewicht ergeben. In der Praxis macht man das durch einen Entscheidungsbaum: Die Verzweigungen vor der -ten Ebene entscheiden darüber, ob das -te Element aufgenommen wird oder nicht. In den Knoten wird das jeweilige -Paar gespeichert. Treten in einer Ebene Paare mit gleichem -Wert auf, so wird nur jene Lösung mit kleinerem Gewicht weiterverfolgt, die andere wird verworfen. Gleiches geschieht mit Paaren mit . In der letzten Ebene sucht man dann unter jenen Paaren mit dasjenige heraus, das den größten Wert besitzt, und hat somit die Lösung gefunden.

Branch-and-Bound

Bei Branch-and-Bound geht man von einem Problem aus, von dem eine minimale Lösung gesucht werden soll (Maximierungsaufgaben können durch Vorzeichenumkehr auch so behandelt werden).

Zunächst sucht man (z.B. mit Hilfe einer Heuristik - siehe Abschnitt 2.2) eine zulässige, nicht notwendigerweise optimale Lösung mit Wert und berechnet eine untere Schranke für alle möglichen Lösungswerte. Ist , so ist man fertig.

Andernfalls wird die Lösungsmenge partitioniert (Branching) und die Heuristiken werden auf die Teilmengen angewandt (Bounding). Man berechnet sich wieder eine untere Schranke für alle möglichen Lösungswerte (der jeweiligen Teilmenge). Ist , so muss man keine weiteren Lösungen aus dieser Teilmenge suchen und erspart sich somit weitere Enumeration.

Die Schwierigkeit bei dieser Art der Optimierung liegt meist in einer "guten" Aufteilung der Lösungsmenge. Darüber hinaus sollten die berechneten unteren Schranken möglichst gut sein, um möglichst viele Teilprobleme ausschließen zu können.

Approximative Algorithmen und Gütegarantie

Eine Heuristik ist ein Verfahren zur Bestimmung einer (nicht notwendigerweise optimalen) Lösung eines Minimierungs- bzw. Maximierungsproblems.

Ziel dabei ist es natürlich, möglichst nahe ans Optimum heranzukommen. Ist eine Instanz des zu lösenden Problems, der Optimalwert für und der Wert der Lösung, die mit Hilfe der Heuristik gefunden wurde, so nennt man einen -approximativen Algorithmus, wenn für alle Probleminstanzen gilt:

	bzw.
(für Minimierungsaufgaben)		(für Maximierungsaufgaben)

heißt dann Gütegarantie des Algorithmus .

Ein Beispiele für einen -approximativen Algorithmus ist die First-Fit-Heuristik für das Bin-Packing-Problem ().

Die Spanning-Tree-Heuristik () wird zur Lösung des euklidische Travelling Salesman Problem (TSP) benutzt: Zuerst bestimme man einen minimalen Spannbaum und verdopple anschließend dessen Kanten. Im entstanden Graphen suche man nun eine Eulertour (d.h. eine Tour, die jede Kante des Graphen genau einmal enthält) und gebe dieser eine Orientierung. Dann starte man bei einem beliebigem Knoten , markiere diesen und setze . Dann folge man der Eulertour, bis man auf einen nichtmarkierten Knoten trifft, markiere diesen, setze sowie und fahre solange fort, bis alle Knoten markiert sind. Fügt man nun zu noch jene Kante hinzu, die den letzten mit dem ersten besuchten Knoten verbindet, hat man eine Lösung des TSP gefunden.

Die Christophides-Heuristik, die ebenfalls für das euklidische TSP verwendet wird, erreicht durch ein geschickteres Vorgehen sogar .

Verbesserungsheuristiken

Verbesserungsheuristiken werden, wie der Name schon vermuten lässt, zur Verbesserung einer gegeben Lösung eines Optimierungsproblems verwendet.

Bei Austauschverfahren werden aus einer gegeben Lösung einige Elemente entfernt, um eine Teillösung zu erhalten. Anschließend versucht man, alle Lösungen zu bestimmen, die enthalten, und wählt aus all diesen die beste. Dabei kann es allerdings vorkommen, das es nicht mehr möglich ist, sogenannten "lokalen Optima" zu entkommen.

Dieses Manko beseitigt Simulated Annealing zumindest zum Teil: Hierbei wird (ausgehend von einer gegebenen Lösung ) in jedem Schritt eine "Nachbarlösung" bestimmt, die immer dann übernommen wird, wenn ihre Bewertung besser ist als jene der ursprünglichen Lösung. Schlechtere Lösungen werden allerdings auch mit einer gewissen Wahrscheinlichkeit akzeptiert (eben um lokalen Optima zu entkommen), wobei üblicherweise nur geringfügig schlechtere Lösungen eher übernommen werden als deutlich schlechtere. Außerdem nimmt diese Wahrscheinlichkeit mit fortschreitender Zeit noch zusätzlich ab.

Evolutionäre Algorithmen wiederum versuchen die Prinzipien der Evolution - Selektion, Rekombination und Mutation - zu simulieren. Ausgehend von einer Vielzahl von Lösungen (und nicht einer einzigen!) werden in jedem Schritt die besseren Lösungen zwar mit einer höheren Wahrscheinlichkeit selektiert als die schlechteren, aber auch letztere haben sozusagen "eine Chance". Dann wird aus zwei "Elternlösungen" (unter Umständen) eine neue Lösung kombiniert, bevor es schließlich (eventuell) durch zufällige kleine Änderungen zu einer Mutation einer oder mehrerer Lösungen kommt.