Glossar · method
Genetischer Algorithmus
Populationsbasierte Metaheuristik, die natürliche Selektion und genetische Vererbung nachbildet und eine Population von Lösungskandidaten iterativ über Selektion, Crossover und Mutation weiterentwickelt.
Genetic AlgorithmGAEvolutionärer AlgorithmusPopulationsbasierte MetaheuristikNSGA-II
Der genetische Algorithmus wurde von Holland (1975) eingeführt und durch Goldberg (1989) popularisiert. Der Algorithmus hält viele Lösungskandidaten (Individuen) gleichzeitig; jedes Individuum ist als Chromosom kodiert (binär, ganzzahlig, Permutation oder reellwertig). Jede Iteration wendet drei Kernoperatoren an: Selektion (Roulette, Turnier, rangbasiert), Crossover (Ein-Punkt, Mehr-Punkt, Uniform oder PMX/OX für Permutationen) und Mutation (Bit-Flip, Tausch, Inversion). Die Fitnessfunktion leitet sich aus der Zielfunktion ab und steuert den Selektionsdruck. Elitismus bewahrt die besten Individuen; Diversitätserhaltung (Niching, Crowding) verhindert vorzeitige Konvergenz. Die Konvergenztheorie beruht auf dem Schema-Theorem (Holland 1975); das No-Free-Lunch-Theorem (Wolpert und Macready 1997) zeigt, dass keine Metaheuristik universell dominiert. Die mehrkriterielle Erweiterung NSGA-II (Deb Pratap Agarwal Meyarivan 2002) ist Industriestandard für Pareto-Front-Approximation. Permutationsprobleme (TSP, Scheduling) erfordern spezialisierte Operatoren. Genetische Algorithmen liefern keine Optimalitätsgarantie, aber gute Lösungen in vertretbarer Zeit; sie werden für gemischt-ganzzahlige, kombinatorische und Black-Box-Probleme bevorzugt. Literatur: Goldberg (1989), Eiben und Smith (2015).
Örnek
Eine Möbelwerkstatt mit 30 Aufträgen auf 6 Maschinen sucht eine Reihenfolge mit minimalem Makespan. Exakte ganzzahlige Programmierung dauert bei grossen Instanzen Stunden; ein genetischer Algorithmus mit Population 80, Permutationskodierung, OX-Crossover und Swap-Mutation erreicht in 200 Generationen und 14 Minuten einen Makespan, der 22 Prozent unter der Anfangsheuristik liegt. Die Lösung ist nicht beweisbar optimal, aber für die tägliche Planung ausreichend und durch den Werkstattplaner umsetzbar.