Metaheuristik
Eine Metaheuristik (zusammengesetzt aus der Präposition meta und Heuristik, vom Verb εὑρίσκειν (heuriskein)) nennt die Informatik einen Algorithmus zur näherungsweisen Lösung von Optimierungsproblemen. 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.
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 (No-free-Lunch-Theoreme).
Beispiele für Metaheuristiken
Viele Metaheuristiken basieren auf dem Prinzip der lokalen Suche:
- Bestimme eine Startlösung L.
- Definiere eine Nachbarschaft von zu L „ähnlichen“ Lösungen.
- 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 wiederholt betrachtet werden. Um das Steckenbleiben in lokalen Optima so weit 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ösung kombinieren oder Lösungen zufällig verändern (evolutionäre Algorithmen),
- mehrere (Meta-)Heuristiken miteinander kombinieren, wie z. B. lokale Suchverfahren mit den global suchenden evolutionären Algorithmen zu den sogenannten memetischen 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.