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]

Eigenschaften von Metaheuristiken

Nachstehende Eigenschaften kennzeichnen die meisten Metaheuristiken:^[3]

• Metaheuristiken sind Strategien, die einen Suchprozess steuern.
• Das Ziel besteht darin, den Suchraum effizient zu erkunden, um optimale oder nahezu optimale Lösungen zu finden.
• Die Techniken, die metaheuristische Algorithmen kennzeichnen, reichen von einfachen lokalen Suchverfahren bis hin zu komplexen Lernprozessen.
• Metaheuristische Algorithmen sind approximativ und in der Regel nicht-deterministisch.
• Metaheuristiken sind nicht problemspezifisch. Sie wurden allerdings häufig bezogen auf eine Problemklasse wie die der kontinuierlichen^[14][15] oder der kombinatorischen Optimierung^[16] entwickelt und dann zum Teil erst später verallgemeinert.^[17][18]
• Sie können auf domänenspezifisches Wissen in Form von Heuristiken zurückgreifen, die von der übergeordneten Strategie gesteuert werden.
• Sie können Mechanismen enthalten, die vermeiden, dass sie in bestimmten Bereichen des Suchraums stecken bleiben.
• Moderne Metaheuristiken nutzen häufig den Suchverlauf, um die Suche zu steuern.

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 das globale Optimum. Durch Tabu-Listen kann vermieden werden, 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.

Klassifikation

Es gibt eine Vielzahl von Metaheuristiken^[2][6] und eine Reihe von Eigenschaften, anhand derer sie klassifiziert werden können.^{[1][3][19][20]} Die nachstehende Liste ist daher exemplarisch zu verstehen.

Populationsbasierte versus Einzelpunktsuche

Ein Unterscheidungsmerkmal besteht in Anzahl der parallel betrachteten Lösungen: Suche mit einem Punkt im Suchraum oder einer vorgegebenen Menge, meist Population genannt.^[3][11] Einzellösungsansätze basieren auf der Modifizierung und Verbesserung eines einzelnen Lösungskandidaten. Beispiele sind Simulated Annealing, Tabu Search, Iterated Local Search,^[21] Variable Neighborhood Search^[22], GRASP^[23] oder Guided Local Search^[24]. Ihnen gemeinsam ist die Eigenschaft, während des Suchvorgangs eine Bewegungsbahn im Suchraum zu beschreiben.^[3] Bei populationsbasierten Ansätzen werden mehrere Lösungskandidaten bearbeitet und verbessert, wobei häufig Populationsmerkmale zur Steuerung der Suche verwendet werden. Zu den typischen Vertretern zählen alle Arten evolutionärer Algorithmen, Scatter Search,^[25][26] die Partikelschwarmoptimierung und die Ameisenalgorithmen. Ebenfalls auf einer Population basiert das Konzept der Schwarmintelligenz als das kollektive Verhalten dezentralisierter, selbstorganisierter Systeme, unabhängig davon ob sie natürlich oder künstlich sind.^[27]

Lokale versus globale Suche

Ein weiteres wichtiges Unterscheidungsmerkmal betrifft die Art der Suchstrategie.^[3] Bei lokal suchenden Verfahren wird die Nachbarschaft eines Startpunktes untersucht. Ein typischer Vertreter ist der einfache Bergsteiger-Algorithmus, bei dem die Gefahr groß ist, an einem Suboptimum hängen zu bleiben. Um die Suche auszuweiten, wurden unterschiedliche Strategien entwickelt, Gebiete des Suchraums von minderer Qualität zu überspringen. Zu den sich daraus ergebenden Metaheuristiken zählen alle zuvor genannten Verfahren der Einzelpunktsuche. Im Gegensatz dazu suchen alle zuvor genannten populationsbasierten Metaheuristiken von vornherein global.

Hybridisierung und memetische Algorithmen

Eine hybride Metaheuristik ist eine Kombination aus einer Metaheuristik und anderen Optimierungsverfahren, wie z. B. Algorithmen der mathematischen Optimierung, der Constraintprogrammierung oder des maschinellen Lernens.^[1][28] Beide Komponenten einer hybriden Metaheuristik können gleichzeitig laufen und Informationen austauschen, um die Suche zu steuern.^[29]

Memetische Algorithmen nutzen die Synergie von populationsbasierten und darunter insbesondere von evolutionären Verfahren und separaten individuellen Lern- oder lokalen Verbesserungsalgorithmen.^[30] Ein Beispiel für einen memetischen Algorithmus ist die Verwendung eines oder mehrerer lokaler Suchverfahren zusätzlich zu oder anstelle von Mutationsoperatoren in evolutionären Algorithmen.^[31] Dabei kann die Metaheuristik um eine Lernkomponente erweitert werden, um den Einsatz der lokalen Suchverfahren oder Heuristiken basierend auf Erfolg und Aufwand zu steuern.^[32][33]

Parallele Metaheuristiken

Parallele Metaheuristik nutzt Techniken der parallelen Programmierung, um mehrere metaheuristische Suchläufe parallel laufen zu lassen; diese können von einfachen verteilten Läufen bis hin zu gleichzeitigen Suchläufen reichen, die zur Verbesserung der Gesamtlösung zusammenwirken.^[3][34] Bei populationsbasierten Metaheuristiken kann einerseits die Population selbst parallelisiert werden, indem entweder jedes Individuum oder eine Gruppe von einem eigenen Thread bearbeitet wird oder die Metaheuristik selbst läuft auf einem Rechner und die Nachkommen werden pro Iteration verteilt bewertet.^[35] Letzteres ist vor allem dann sinnvoll, wenn der Rechenaufwand für die Bewertung erheblich größer ist als der zur Erzeugung von Nachkommen. Dies ist bei vielen praktischen Anwendungen der Fall, insbesondere bei simulationsgestützten Berechnungen der Lösungsqualität.^[36][37]

Von der Natur inspirierte Metaheuristiken

Ein sehr aktives Forschungsgebiet stellt die Entwicklung und Erprobung naturinspirierter Metaheuristiken dar. So war die Physik von Abkühlungsvorgängen Vorbild beim Simulated Annealing und die Grundlagen der biologischen Fortpflanzung standen Pate bei allen Arten evolutionärer Algorithmen. Bei den Ameisenalgorithmen wird das natürliche Verhalten von Ameisen auf der Wegsuche modelliert und die Partikelschwarmoptimierung geht auf das Verhalten von Vogel- oder Fischschwärmen zurück.

Andererseits ist in letzter Zeit eine sehr große Zunahme an metapher- und naturinspirierten Metaheuristiken zu beobachten. Dies hat zu Kritik in der Forschungsgemeinschaft geführt, da es vielen diesbezüglichen Publikationen an wissenschaftlicher Tiefe, Neuheit oder dem Nachweis der Tauglichkeit oder Überlegenheit über ältere und erprobte Verfahren mangelt.^{[38][39][40][41]} Das hat auch dazu geführt, dass die Veröffentlichungsrichtlinien von etlichen Fachzeitschriften entsprechend angepasst wurden.^[42][43][44]

Anwendungen

Die meisten Metaheuristiken sind Suchverfahren und bei deren Anwendung ist zu beachten, dass an die Bewertungsfunktion größere Ansprüche als bei einer mathematischen Optimierung gestellt werden sollten. Denn es muss nicht nur der gewünschte Zielzustand formuliert werden, sondern die Bewertung sollte auch Verbesserungen einer Lösung auf dem Weg zum Ziel belohnen, soweit dies nicht bereits Bestandteil der Zielfunktion ist. Als Beispiel können die Fitnessfunktionen von evolutionären oder memetischen Algorithmen dienen.

Metaheuristiken werden für alle Arten von Optimierungsproblemen eingesetzt, von kontinuierlichen über gemischt-ganzzahlige Probleme bis hin zur kombinatorischen Optimierung oder Kombinationen davon.^[9][29][45] Bei der kombinatorischen Optimierung wird eine optimale Lösung in einem diskreten Suchraum gesucht. Ein Beispiel ist das Problem des Handlungsreisenden, bei dem der Suchraum der Lösungsvorschläge mit zunehmender Größe des Problems schneller als exponentiell wächst, was eine vollständige Suche nach der optimalen Lösung undurchführbar macht.^[46][47] Ein weiteres Beispiel sind alle Arten von Schedulingaufgaben, wie z. B. die Produktionsplanung, bei der die einzelne Arbeitsschritte zur Herstellung eines Produkt unterschiedlichen Bearbeitungsstationen zeitlich so zuzuordnen sind, dass alle rechtzeitig fertig werden und die Gesamtbearbeitungszeit möglichst kurz ist.^[7][4][48] Bei praktischen Anwendungen müssen häufig zusätzliche Restriktionen beachtet werden, z. B. eine Begrenzung der zulässigen Abfolge einiger Arbeitsschritte eines Jobs durch vordefinierte Workflows^[49] und/oder hinsichtlich der Ressourcennutzung, z. B. in Form einer Glättung des Energiebedarfs und der Vermeidung von Verbrauchsspitzen.^[50][51]

Ein weiteres großes Anwendungsgebiet sind Optimierungsaufgaben in kontinuierlichen oder gemischt-ganzzahligen Suchräumen, da viele technische Entwurfsprobleme, wie z. B. die Form- und Verhaltensfindung, ebenfalls dem Problem hoher Dimensionalität oder dem von Nichtlinearitäten unterliegen, was sie für exakte Analysemethoden oder eine umfassende Suche unzugänglich macht.^{[52][5][53][54]} Auch bei anderen ingenieurtechnischen Aufgabenstellungen kommen Metaheuristiken zum Einsatz.^[55][56][57] Ein Beispiel für eine Anwendung mit gleichzeitiger kombinatorischer und kontinuierlicher Optimierung ist die Planung günstiger Bewegungsbahnen für Industrieroboter.^[58][59]

Es gibt eine Reihe von Framework-Implementierungen für Metaheuristiken, die eine oder mehrere Metaheuristiken zusammen mit nützlichen Tools enthalten. Eine umfassende Übersicht und Bewertung kann in^[60] gefunden werden. Zu der darin vermisste Unterstützung paralleler Implementierungen gab es vor allem ab Ende der 2010er Jahre eine Reihe von Arbeiten.^{[61][37][62][63][36]}

Literatur

• Rafael Martí, Panos M. Pardalos, Mauricio G. C. Resende (Hrsg.): Handbook of Heuristics. Springer International Publishing, Cham 2018, ISBN 978-3-319-07123-7, doi:10.1007/978-3-319-07124-4.
• Bassem Jarboui, Patrick Siarry, Jacques Teghem (Hrsg.): Metaheuristics for Production Scheduling (= Automation - control and industrial engineering series). Wiley & Sons Ltd, 2013, ISBN 978-1-84821-497-2, doi:10.1002/9781118731598.
• Timothy Ganesan, Pandian Vasant, Irraivan Elamvazuthi: Advances in Metaheuristics: Applications in Engineering Systems. CRC Press, Taylor & Francis Group, Boca Raton, FL, USA 2016, ISBN 978-1-315-29765-1, doi:10.1201/9781315297651.
• Mohamed Abdel-Basset, Laila Abdel-Fatah, Arun Kumar Sangaiah: Metaheuristic Algorithms: A Comprehensive Review. In: Arun Kumar Sangaiah, Michael Sheng, Zhiyong Zhang (Hrsg.): Intelligent Data-Centric Systems, Computational Intelligence for Multimedia Big Data on the Cloud with Engineering Applications (= Intelligent data centric systems). Academic Press, an imprint of Elsevier, London Cambridge, MA 2018, ISBN 978-0-12-813314-9, S. 185–231, doi:10.1016/B978-0-12-813314-9.00010-4.
• Luis Velasco, Hector Guerrero, Antonio Hospitaler: A Literature Review and Critical Analysis of Metaheuristics Recently Developed. In: Archives of Computational Methods in Engineering. Band 31, Nr. 1, Januar 2024, S. 125–146, doi:10.1007/s11831-023-09975-0.