Ein genetischer Algorithmus ist eine Such- und Optimierungstechnik, die von den Prinzipien der natürlichen Selektion inspiriert ist. Dabei wird eine Population von Lösungskandidaten iterativ durch Operationen weiterentwickelt, die Mutation, Crossover (Rekombination) und Selektion analog nachbilden, um über aufeinanderfolgende Generationen die Fitness im Hinblick auf ein definiertes Ziel zu verbessern. Genetische Algorithmen gehören zur breiteren Familie der evolutionären Berechnungsmethoden innerhalb von künstlicher Intelligenz und maschinellem Lernen.
Mechanismus
Ein genetischer Algorithmus beginnt mit einer zufällig erzeugten Population von Lösungskandidaten, die jeweils typischerweise als Zeichenkette oder Vektor kodiert sind, analog zu einem Chromosom. Jeder Kandidat wird mit einer Fitnessfunktion bewertet, die misst, wie gut er das Zielproblem löst. Kandidaten mit höherer Punktzahl werden mit größerer Wahrscheinlichkeit als "Eltern" ausgewählt, deren Kodierungen durch Crossover kombiniert werden, um Nachkommen zu erzeugen, wobei gelegentlich zufällige Mutationen eingeführt werden, um die Vielfalt zu erhalten und eine vorzeitige Konvergenz auf eine suboptimale Lösung zu vermeiden. Dieser Zyklus aus Bewertung, Selektion und Rekombination wiederholt sich über viele Generationen, wobei die Population als Ganzes tendenziell im Laufe der Zeit in der durchschnittlichen Fitness verbessert wird, obwohl nicht garantiert ist, ein globales Optimum zu finden.
Geschichte
Die mathematischen Grundlagen dieses Bereichs wurden von John Holland formalisiert, dessen 1975 erschienenes Buch „Adaptation in Natural and Artificial Systems" genetische Algorithmen als einen allgemeinen Rahmen für adaptive Suche einführte, aufbauend auf früheren evolutionären Computer-Experimenten aus den 1950er- und 1960er-Jahren. Hollands Studenten und Mitarbeiter, darunter David Goldberg, erweiterten die theoretische Fundierung des Rahmens und popularisierten praktische Anwendungen in den 1980er- und 1990er-Jahren.
Anwendungen
Genetische Algorithmen wurden auf Planungs- und Routenprobleme sowie auf die Optimierung im Ingenieurdesign angewendet, einschließlich von Antennen- und aerodynamischen Formen, die von der NASA und anderen bewertet wurden. Zudem werden sie für automatische Programmsynthese im verwandten Bereich der genetischen Programmierung sowie für die Hyperparametersuche bei maschinellen Lernsystemen eingesetzt. Sie werden besonders bevorzugt bei Problemen mit großen, komplexen, nicht differenzierbaren Suchräumen, in denen gradientenbasierte Methoden nicht verfügbar oder ineffektiv sind, da genetische Algorithmen nur die Fähigkeit benötigen, die Fitness eines Kandidaten zu bewerten, nicht jedoch eine Ableitung der Zielfunktion zu berechnen.
Neuroevolution
Ein bemerkenswertes Anwendungsgebiet ist die Neuroevolution, die evolutionäre Methoden verwendet, um neuronale Netze Architekturen und Gewichte zu entwerfen oder zu trainieren, manchmal kombiniert mit Verstärkungslernen für Steuerungs- und Spieleaufgaben. Neuroevolution wurde als Alternative oder Ergänzung zu durch Backpropagation trainierten Robotern Systemen und der KI-Forschung erforscht, wo das Belohnungssignal spärlich ist oder die Netzwerktopologie selbst, nicht nur die Gewichte, eine Designvariable darstellt.
Einschränkungen und moderne Relevanz
Genetische Algorithmen skalieren im Vergleich zu gradientenabstiegsbasierten Optimierungen wie Backpropagation schlecht auf den sehr hohen, dimensionalen Parameterraum moderner Deep-Neuronaler Netze, und traten ab den frühen 2010er Jahren weitgehend in den Hintergrund des Mainstreams, als auf Backpropagation trainierte Deep learning-Architekturen die Domäne dominieren. Sie bleiben jedoch aktiv in Optimierungsbereichen außerhalb des standardmäßig überwachten Trainings, in Nischen der Neuroevolution und als konzeptioneller Referenzpunkt für die Forschung zu offenen und evolutionären Ansätzen, die vielfältige, neuartige Lösungen erzeugen, statt eine einzelne feste Zielfunktion zu optimieren.