Metaheuristik

Eine Metaheuristik ist ein Sammelbegriff für strategische höhere algorithmische Rahmenwerke, die den Suchraum jenseits lokaler Optima erkunden. Den Begriff prägte Glover (1986) im Kontext von Tabu Search; er etablierte sich in den 1990er Jahren in der OR-Literatur. Wichtige Metaheuristik-Familien: (1) Tabu Search (Glover 1989) — verbietet jüngste lokale Suchschritte via Tabuliste, um Zyklen zu verhindern; (2) Simulated Annealing (Kirkpatrick, Gelatt und Vecchi 1983) — physikinspirierter Temperaturparameter, der Verschlechterungsschritte probabilistisch akzeptiert; (3) genetischer Algorithmus (Holland 1975) — evolutionäre Suche mit Population, Selektion, Crossover und Mutation; (4) Variable Neighborhood Search (Mladenović und Hansen 1997) — systematische Übergänge zwischen mehreren Nachbarschaftsstrukturen; (5) GRASP (Feo und Resende 1995) — randomisiert-gierige Konstruktion plus lokale Suche; (6) Ameisenkolonie-Optimierung (Dorigo 1992) und Partikelschwarm-Optimierung (Kennedy und Eberhart 1995). Hybride Metaheuristiken (Matheuristiken) haben in den letzten zwanzig Jahren an Bedeutung gewonnen und nutzen einen MIP-Solver als Teilproblemlöser innerhalb einer Metaheuristik-Schleife. Parameter-Tuning (Tabulisten-Länge, Abkühlplan, Populationsgröße, Mutationsrate) bestimmt maßgeblich das Qualitäts-Zeit-Verhältnis. Standardreferenzen sind Glover und Kochenberger (2003), Talbi (2009) sowie Gendreau und Potvin (2010) Handbook of Metaheuristics.