Metaheuristik

In der Informatik und der mathematischen Optimierung ist eine Metaheuristik (von altgriechisch μετα (über, darüber) und εὑρίσκειν heurískein (auffinden, entdecken)) ein Verfahren oder eine Heuristik auf höherer Ebene. Es dient dazu, eine oder mehrere Heuristiken (auf Erfahrung und begrenztem Wissen beruhender Suchalgorithmus) zu finden, zu generieren, zu tunen oder auszuwählen, die eine hinreichend gute Lösung für ein Optimierungsproblem oder ein Problem des maschinellen Lernens bieten kann, insbesondere bei unvollständigen oder unvollkommenen Informationen oder begrenzter Rechenleistung.^[1][2][3] Metaheuristiken können mit relativ wenigen Annahmen über das zu lösende Optimierungsproblem auskommen und sind daher für eine Vielzahl von Problemen verwendbar.^[2][4][5] Ihr Einsatz ist immer dann von Interesse, wenn exakte oder andere (Näherungs-)Verfahren nicht zur Verfügung stehen oder nicht zielführend sind, sei es wegen zu langer Rechenzeiten oder weil z. B. die gelieferte Lösung zu ungenau ist.

Im Vergleich zu exakten Optimierungsalgorithmen und iterativen Methoden der numerischen Mathematik garantieren Metaheuristiken nicht, dass für eine bestimmte Klasse von Problemen das globale Optimum gefunden werden kann.^[3] Viele Metaheuristiken implementieren eine Form der stochastischen Optimierung, so dass die gefundene Lösung von den erzeugten Zufallsvariablen abhängt und jeder Optimierungslauf ein anderes Ergebnis bringen kann und seien die Unterschiede auch nur gering.^[6] In der kombinatorischen Optimierung gibt es viele Aufgabenstellungen, die zur Klasse der NP-vollständigen Probleme gehören. Sie sind damit ab einem relativ geringen Komplexitätsgrad nicht mehr in akzeptabler Zeit exakt lösbar.^[7][8] Metaheuristiken liefern dann oft gute Lösungen mit weniger Rechenaufwand als iterative Methoden, Näherungsverfahren oder einfache Heuristiken.^[2][3][6] Dies gilt ebenfalls im Bereich der kontinuierlichen oder mixed-integer Optimierung.^[2][9][10] Mehrere Bücher und Übersichtsarbeiten sind zu diesem Thema veröffentlicht worden.^{[2][3][6][11]} Der Begriff Metaheuristik geht auf Fred Glover zurück,^[12] der sie als Lösungsmethoden beschrieb, die eine Interaktion zwischen lokalen Verbesserungsverfahren und Strategien auf höherer Ebene organisieren, um einen Prozess zu schaffen, der in der Lage ist, aus lokalen Optima zu entkommen und eine robuste Suche in einem Lösungsraum durchzuführen.^[2]

Generell hängen Erfolg und 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). Die meiste Literatur über Metaheuristiken ist experimenteller Natur und beschreibt empirische Ergebnisse auf der Grundlage von Computerexperimenten mit den Algorithmen. Es liegen aber auch einige formale theoretische Ergebnisse vor, häufig zur Konvergenz und zur Möglichkeit, das globale Optimum zu finden.^[3][13]

1. ↑ Günther R. Raidl: A Unified View on Hybrid Metaheuristics. In: Francisco Almeida et al. (Hrsg.): Hybrid Metaheuristics, Conf. Proc of Third Int. Workshop (HM 2006). LNCS 4030. Springer, Berlin, Heidelberg 2006, ISBN 3-540-46384-4, S. 1–12, doi:10.1007/11890584_1. 
2. ↑ ^{a b c d e f} Fred Glover, Gary A. Kochenberger (Hrsg.): Handbook of Metaheuristics (= International Series in Operations Research & Management Science. Band 57). Springer US, Boston, MA 2003, ISBN 1-4020-7263-5, doi:10.1007/b101874. 
3. ↑ ^{a b c d e} Christian Blum, Andrea Roli: Metaheuristics in combinatorial optimization: Overview and conceptual comparison. In: ACM Computing Surveys. Band 35, Nr. 3, September 2003, S. 268–308, doi:10.1145/937503.937505. 
4. ↑ Referenzfehler: Ungültiges <ref>-Tag; kein Text angegeben für Einzelnachweis mit dem Namen :10.
5. ↑ Referenzfehler: Ungültiges <ref>-Tag; kein Text angegeben für Einzelnachweis mit dem Namen :11.
6. ↑ ^{a b c} Leonora Bianchi, Marco Dorigo, Luca Maria Gambardella, Walter J. Gutjahr: A survey on metaheuristics for stochastic combinatorial optimization. In: Natural Computing. Band 8, Nr. 2, Juni 2009, S. 239–287, doi:10.1007/s11047-008-9098-4. 
7. ↑ Peter Brucker, Sigrid Knust: Complex Scheduling. Springer, Berlin, Heidelberg 2012, ISBN 978-3-642-23928-1, doi:10.1007/978-3-642-23929-8. 
8. ↑ Christos H. Papadimitriou, Kenneth Steiglitz: Combinatorial optimization: algorithms and complexity. Dover Publ., korrigierte, ungekürzte Neuauflage des 1982 bei Prentice-Hall erschienenen Werks., Mineola, NY, USA 2000, ISBN 0-486-40258-4. 
9. ↑ Ahmed G. Gad: Particle Swarm Optimization Algorithm and Its Applications: A Systematic Review. In: Archives of Computational Methods in Engineering. Band 29, Nr. 5, August 2022, S. 2531–2561, doi:10.1007/s11831-021-09694-4. 
10. ↑ Zhenhua Li, Xi Lin, Qingfu Zhang, Hailin Liu: Evolution strategies for continuous optimization: A survey of the state-of-the-art. In: Swarm and Evolutionary Computation. Band 56, August 2020, S. 100694, doi:10.1016/j.swevo.2020.100694. 
11. ↑ El-Ghazali Talbi: Metaheuristics: from design to implementation. Wiley, Hoboken, NJ, USA 2009, ISBN 978-0-470-27858-1. 
12. ↑ Fred Glover: Future paths for integer programming and links to artificial intelligence. In: Computers & Operations Research. Band 13, Nr. 5, Januar 1986, S. 533–549, doi:10.1016/0305-0548(86)90048-1. 
13. ↑ Günter Rudolph: Self-adaptive mutations may lead to premature convergence. In: IEEE Transactions on Evolutionary Computation. Band 5, Nr. 4, August 2001, S. 410–414, doi:10.1109/4235.942534.