Metaheuristik

Eine Metaheuristik ist in der Mathematik ein Algorithmus zur näherungsweisen Lösung eines kombinatorischen Optimierungsproblems. Im Gegensatz zu problemspezifischen Heuristiken, die nur auf ein bestimmtes Optimierungsproblem angewendet werden können, definieren Metaheuristiken eine abstrakte Folge von Schritten, die (theoretisch) auf beliebige Problemstellungen angewandt werden können. Die einzelnen Schritte müssen allerdings wieder problemspezifisch implementiert werden (oft wiederum als Heuristiken). Der Name Metaheuristik entstand durch die Verbindung zweier griechischer Wörter. Heuristik stammt vom Verb heuriskein ($\epsilon\upsilon\rho\iota\sigma\kappa\epsilon\iota\nu$) (zu Deutsch finden) und der Präposition meta.

Metaheuristiken können bei solchen Problemen eingesetzt werden, für die kein anderer effizienter Lösungsalgorithmus bekannt ist, etwa bei schweren kombinatorischen Optimierungsproblemen. In der Regel ist nicht garantiert, dass eine Metaheuristik eine optimale Lösung findet. Prinzipiell können all diese Verfahren gute Lösungen berechnen, aber auch beliebig schlecht im Vergleich zu einer Optimallösung sein. Generell hängen der Erfolg und die Laufzeit metaheuristischer Verfahren entscheidend von der Definition und Implementierung der einzelnen Schritte ab. Es gibt keine Metaheuristik, die für beliebige Probleme besser ist als alle anderen.

Beispiele für Metaheuristiken

Viele Metaheuristiken basieren auf dem Prinzip der lokalen Suche:

1. Bestimme eine Startlösung L.
2. Definiere eine Nachbarschaft von zu L „ähnlichen“ Lösungen.
3. Suche diese Nachbarschaft vollständig ab und bestimme die beste Lösung.

Die genaue Definition der einzelnen Schritte hängt vom untersuchten Problem ab (für Beispiele siehe lokale Suche), und die so gefundene Lösung ist in der Regel nicht global optimal. Durch Tabu-Listen wird vermieden, dass bereits gefundene Lösungen nochmal betrachtet werden. Um das Steckenbleiben in lokalen Optima soweit wie möglich zu verhindern, kann man beispielsweise

• mehrere Versuche starten (Bergsteigeralgorithmus),
• zwischendurch erst größere, später nur noch kleinere Verschlechterungen akzeptieren (Simulierte Abkühlung (engl. simulated Annealing) und Sintflutalgorithmus),
• mehrere bereits gefundene Lösungen zu einer neuen Lösungen kombinieren oder Lösungen zufällig verändern (evolutionäre und genetische Algorithmen).

Eine ganze Klasse weiterer naturinspirierter Verfahren verwendet Schwarmintelligenzen. Bei so genannten Ameisenalgorithmen (engl. Ant Colony Optimization), wird hierzu das natürliche Verhalten von Ameisen auf der Wegsuche modelliert, während bei der Partikelschwarmoptimierung das Verhalten von Vogel- oder Fischschwärmen als Vorbild genommen wird. Inwieweit diese Anlehnung an die Natur für das schnelle Finden guter Lösungen von Vorteil ist, ist umstritten. Auch mit künstlichen neuronalen Netzen und ähnlichen statistischen Verfahren, wie Self-Organizing Maps, gab es Versuche.