Metaheuristiken sind übergeordnete Suchstrategien, die einfachere Heuristiken steuern, um schwere Optimierungsprobleme näherungsweise zu lösen. Das griechische „Meta" („über, jenseits") drückt aus: Eine Metaheuristik arbeitet über der eigentlichen Problemsuche — sie ist weitgehend problemunabhängig und kann auf viele Aufgaben angewendet werden.
Idee und Grundprinzipien
Viele praktische Probleme wie das Handelsreisendenproblem, Job-Shop-Scheduling oder Vehicle Routing sind NP-vollständig — exakte Verfahren werden für große Instanzen zu langsam. Metaheuristiken finden in vertretbarer Zeit gute, aber nicht notwendigerweise optimale Lösungen.
Zentrale Prinzipien sind Exploration (breites Absuchen des Suchraums, um gute Regionen zu entdecken) und Exploitation (intensive Verbesserung innerhalb einer vielversprechenden Region). Je nach Strategie wechseln die Verfahren zwischen diesen beiden Polen — oft durch die zeitweise Akzeptanz von Verschlechterungen.
Die wichtigsten Klassen
- Einzelpunkt-basiert (lokale Suche): Ein Startpunkt wird verbessert. Vertreter: Hill-Climbing als Grundbaustein, Simulated Annealing (Abkühlung, akzeptiert Verschlechterungen probabilistisch) und Tabu-Suche (Gedächtnis verbietet Zyklen).
- Populations-basiert: Eine Menge von Lösungen evolviert gemeinsam. Vertreter: Genetischer Algorithmus (Evolution durch Selektion, Crossover, Mutation) und Ameisenalgorithmus (indirekte Kommunikation über Pheromonspuren).
Abgrenzung: Heuristik vs. Metaheuristik
Eine Heuristik ist eine einfache, problemabhängige Daumenregel (z. B. „nimm immer den nächsten Kunden"). Eine Metaheuristik ist die übergeordnete Strategie, die solche Regeln steuert und kombiniert — sie enthält Mechanismen wie Gedächtnis, Populationsdynamik oder probabilistische Entscheidungen, die über die einzelne Heuristik hinausgehen.
Kein Metaheuristik-Verfahren garantiert das globale Optimum. Der Vorteil liegt in der Laufzeit: Statt exponentieller Suche liefern die Verfahren in polynomieller Zeit pro Iteration gute Näherungen — oft näher am Optimum als deterministische Approximationsalgorithmen mit Gütegarantie, dafür ohne solche Garantie.
Anwendungsfelder reichen vom Tuning neuronaler Netze (Hyperparameter, Neuroevolution) über Logistik und Produktionsplanung bis zur Feature-Auswahl im maschinellen Lernen.