¶ Einführung
Genetische Algorithmen (GAs) sind evolutionäre Optimierungs- und Suchverfahren, die auf den Prinzipien der natürlichen Selektion und der Vererbung nach dem genetischen Prinzip basieren[1]. GAs sind Teil der Klasse der evolutionären Algorithmen, wobei die Idee der GA in die 1960er Jahre auf John H. Holland an der University of Michigan zurückgeführt werden kann[2]. Dort wurde von John Holland erstmals „reproductive plans“, also Modelle biologischer Anpassungsprozesse, formuliert. Worauf John H. Holland dann 1975 mit der Erstauflage von "Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence" das wissenschaftliche Feld diesbezüglich eröffnete und die theoretischen Grundlagen in diesem Bereich gelegt hat[3]. GAs haben schon Anwendung in modernen Forschungsbereichen gefunden, dabei werden sie gerne eingesetzt, um gute Lösungen für schwere Probleme zu finden. So ist ein klassisches und sehr bekanntes praxisnahes Beispiel für den Einsatz eines GAs die Antennen-Entwicklung für die ST5-Mission[4][5].
¶ Bestandteile
Tatsächlich gibt es keine strenge Definition des Begriffs "genetischer Algorithmus", die in der Forschungsgemeinschaft von allen akzeptiert wird und die GAs von anderen evolutionären Berechnungsmethoden unterscheidet.
¶ Grundbegriffe
Auch wenn in der Forschung nicht ausschließlich mit den Begrifflichkeiten der Genetik (Chromosom, Gen, Allel...) gearbeitet wird, werden im Folgenden diese eingeführt und angewandt, da sie in der Lehre verbreitet sind.
¶ Individuum / Chromosom
Ein Individuum (auch Chromosom genannt) bezeichnet biologisch einen lebenden Organismus, dessen Chromosomen als Träger der Erbinformation dienen. Im Kontext von genetischen Algorithmen (GA) wird der Begriff synonym für eine mögliche Lösung verwendet und die Begriffe Chromosom und Individuum gleichgesetzt. [6]
¶ Gen
Ein Gen ist eine bestimmte Stelle oder Sequenz innerhalb eines Chromosoms. In der Praxis kann es sowohl ein einzelnes Bit (bei binärer Kodierung) als auch einen längeren Abschnitt repräsentieren. Die genaue Interpretation des Gens – ob als einzelnes Merkmal oder als Segment – hängt vom jeweiligen Anwendungskontext ab.[6:1]
¶ Allel
Ein Allel beschreibt die konkrete Ausprägung eines Gens und entspricht somit dem Wert einer Variablen an einer bestimmten Stelle eines Gens. [6:2]
¶ Population
Unter einer Population versteht man die Menge strukturell gleichartiger Individuen. In genetischen Algorithmen ändert sich die Populationsgröße dynamisch: Neue Lösungen („Geburten“) werden erzeugt und alte Lösungen („Tode“) werden gelöscht, wodurch ein ständiger Evolutionsprozess entsteht.[6:3]
¶ Generation
Eine Generation bildet den Zustand einer Population zu einem bestimmten Zeitpunkt ab. Über mehrere Entwicklungsstufen hinweg entsteht so eine Sequenz von Populationen, in der jede Generation auf den Ergebnissen der vorherigen aufbaut und durch Auswahl, Crossover und Mutation weiterentwickelt wird. [6:4]
¶ Fitness-Funktion
Die Fitness-Funktion gibt einem Individuum anhand einer Policy einen Fitness-Wert. Denn damit die Evolution stattfinden kann, braucht man externen Druck, eine Methode, mit der angepasstes genetisches Material an die Nachkommen weitergegeben wird. Die Fitnessfunktion soll den äußeren Druck nachahmen.
¶ Rekombination
Die Rekombination ahmt die Fortpflanzung nach, wobei bestehende Individuen neue Individuen hervorbringen. Hierfür gibt es verschiedene Mechanismen. Ein Ausschnitt dieser Mechanismen wird im Abschnitt Ablauf aufgelistet.
¶ Mutation
Eine Mutation ist eine zufällige Änderung eines Allels.
¶ Selektion
Die Selektion ist ein Auswahlverfahren, welches die Individuen bestimmt, die in die nächste Generation kommen. Ein zu zufälliges Auswahlverfahren kann gute Individuen (d.h. Individuen mit hohem Fitness-Wert) zerstören und es schlechten Individuen ermöglichen, sich durchzusetzen. Allerdings kann ein Auswahlverfahren, das nicht zufällig genug ist, den GA ermutigen, eine allzu naive Lösung für das Optimierungsproblem zu entwickeln oder in lokalen Optima stecken zu bleiben.
¶ Ablauf
Man kann sagen, dass die meisten Methoden, die als "GA" bezeichnet werden, zumindest die folgenden Elemente gemeinsam haben:
Populationen von Chromosomen, Selektion nach Fitness, Kreuzung zur Erzeugung neuer Nachkommen und zufällige Mutation neuer Nachkommen[7].
Des Weiteren ist folgender Ablauf, der am häufigsten in der Lehre zu finden ist:
-
Kodierung
Das zu lösende Problem wird in eine chromosomale Repräsentation überführt (z.B. binär oder realwertig). Jedes Chromosom codiert eine mögliche Lösung [8]. -
Initialisierung
Die Ausgangspopulation von Chromosomen wird üblicherweise zufällig generiert. Domänenspezifisches Wissen kann integriert werden [8:1]. -
Bewertung
Nach Initialisierung oder Erzeugung einer Nachkommenpopulation werden die Fitnesswerte der Chromosomen ermittelt [8:2]. -
Selektion
Chromosomen mit höheren Fitnesswerten erhalten mehr Kopien („Survival-of-the-Fittest“). Verfahren umfassen:- Roulette-Rad-Selektion (Auswahlwahrscheinlichkeit proportional zur Fitness)
- Stochastisch universelle Selektion (gleichmäßige Verteilung der Selektionschancen)
- Rangbasierte Selektion (Selektion nach Rangplatz, nicht absoluter Fitness)
- Turnierselektion (Wettbewerb zwischen zufällig ausgewählten Individuen) [8:3]
-
Rekombination
Kombiniert elterliche Chromosomen zu neuen Nachkommen. Gängige Rekombinationsoperatoren umfassen[9]:- k-Punkt-Crossover (Teilaustausch an k Positionen)
- Uniformes Crossover (jedes Gen zufällig von einem Elternteil)
- Ordnungsbasiertes Crossover (Order-Based Crossover)
- Uniformes ordnungsbasiertes Crossover
- Partiell abgestimmtes Crossover (Partially Matched Crossover)
Die Leistungsfähigkeit hängt von einem geeigneten Rekombinationsmechanismus ab. Nachkommen kombinieren Merkmale neuartig:
"The offspring [...] will instead combine parental traits in a novel manner" - John Henry Holland
-
Mutation
Modifiziert Chromosomen lokal und zufällig (typischerweise durch Änderung von Genen). Mutation führt einen Zufallsschritt in der Nähe einer Lösung aus [8:4]. -
Ersetzung
Die Nachkommenpopulation ersetzt die ursprüngliche Elternpopulation. Methoden:- Elitismus-basierte Ersetzung (beste Individuen bleiben erhalten)
- Generationenweise Ersetzung (kompletter Populationsaustausch pro Generation)
- Steady-State-Ersetzung (schrittweise Ersetzung einzelner Individuen)[8:5]
-
Terminierung
Wiederholung der Schritte 3–7 bis zur definierten Abbruchbedingung [8:6].
¶ Theoretische Grundlagen
Es stellt sich die Frage, ob genetische Algorithmen wirklich immer eine optimale Lösung finden und ob sie dies auch tatsächlich effizient tun. Dies lässt sich mit der Konvergenzeigenschaft genetischer Algorithmen und dem Schematheorem zeigen. Dabei soll das Schematheorem, welches bereits in der Einleitung erwähntem Werk "Adaptation in Natural and Artificial Systems" vorgestellt wurde, erklären, warum zufallsbasierte Prozesse zu sinnvollen Lösungen führen können.
¶ Konvergenz
Die Konvergenz zum globalen Optimum ist keine inhärente Eigenschaft von GAs, sondern vielmehr eine Folge von algorithmischen Tricks. Unter den folgenden Bedingungen lässt sich formal anhand endlicher Markov-Ketten beweisen, dass ein elitäres GA asymptotisch mit Wahrscheinlichkeit 1 ein Optimum erreicht:
- Endlicher Suchraum
- Elitäre Selektion
- Strikt positive Mutationsrate
Durch Elitismus entsteht eine monoton nicht fallende Folge der besten Fitnesswerte, die aufgrund der Beschränktheit durch ein vorhandenes Optimum gegen dieses konvergiert. F ist Fitnesswert und x ist das beste Individuum der k-ten Generation.
Die strikte Positivität der Mutationsrate garantiert, dass jeder Punkt des Suchraums mit endlicher Wahrscheinlichkeit erreicht werden kann, wodurch das globale Optimum als einziger absorbierender Zustand in der Markov-Kette fungiert.
Der grundlegende formale Beweis von Günter Rudolph diesbezüglich erschien 1994[10].
¶ Schematheorem
Abstrakt besagt das Schematheorem, dass sich kompakte und durch die Fitness-Funktion überdurchschnittlich bewertete Schemata (ein Muster von Genen) in einer Population über mehrere Generationen hinweg im Erwartungswert verbreiten. Das bedeutet: Individuen mit höherer Fitness setzen sich statistisch gesehen durch. [3:1] [11]
Holland erkannte, dass ein genetischer Algorithmus, wenn er den Fitnesswert eines Chromosoms bewertet, implizit viele Schemata gleichzeitig evaluiert. Denn jedes Chromosom gehört zu einer Vielzahl von Schemata, die sich in ihren Platzhaltern unterscheiden. Die Fitnessbewertung eines Chromosoms liefert daher Informationen über alle Schemata, die es erfüllt. [3:2]
¶ Schemadefinition
Ein Schema ist eine Zeichenkette der Länge über dem Alphabet , wobei * für beliebige Werte ("don’t care") steht. Ein Schema beschreibt also eine Gruppe von Bitstrings, die an bestimmten Stellen festgelegt sind (0 oder 1), an anderen jedoch beliebige Werte annehmen können. [3:3]
¶ Eigenschaften eines Schemas
- Feste Positionen: Indizes mit einem festen Wert (0 oder 1) [3:4]
- Anzahl Instanzen: ist die Anzahl der Individuen in Generation , die Schema erfüllen [11:1]
¶ Wichtige Kennzahlen
- Ordnung : Anzahl fester Positionen im Schema [11:2]
- Definierende Länge : Abstand zwischen erster und letzter fester Position [3:5]
- Fragilität: Anteil der möglichen Crossover-Stellen, die das Schema zerstören können: [11:3]
- Fitness eines Schemas : Durchschnittliche Fitness aller Schema-Träger in Generation [11:4]
- Gesamtfitness : Durchschnittliche Fitness der gesamten Population in Generation [11:5]
¶ Variation durch genetische Operatoren
- Einpunkt-Crossover (mit Wahrscheinlichkeit ): Ein Schema kann zerstört werden, wenn der Crossover-Punkt innerhalb der definierenden Länge liegt [3:6]
- Bitweise Mutation (mit Wahrscheinlichkeit ): Jedes feste Bit im Schema kann mutieren. Die Wahrscheinlichkeit, dass alle festen Positionen unangetastet bleiben, beträgt: [3:7]
¶ Formale Aussage des Schematheorems
Die folgende Ungleichung gibt eine untere Schranke für die erwartete Anzahl der Individuen in der nächsten Generation an, die Schema erfüllen: [3:8] [11:6]
Diese Aussage zeigt, dass sich überdurchschnittlich fitte und kompakte Schemata im Erwartungswert durchsetzen – trotz der potenziellen Störungen durch Crossover und Mutation. Der Beweis basiert auf elementarer Wahrscheinlichkeitsrechnung. [3:9]
¶ Laufzeitverhalten und Komplexität
¶ Rechenaufwand
Genetische Algorithmen arbeiten, wie in Ablauf dargestellt, mit einer Population von Individuen über viele Generationen. Dabei hängt der Rechenaufwand direkt mit der Anzahl an Generationen und der Populationsgröße zusammen. Denn umso größer eine Population ist, desto mehr Fitness-Bewertungen müssen von Individuen einer Generation gemacht werden. Klar ist auch: Umso mehr Generationen berechnet werden, desto mehr wird die Gesamtzahl an Fitness-Bewertungen vervielfacht[12]. Die Fitness-Funktion stellt dabei generell den größten Anteil des Rechenaufwands eines genetischen Algorithmus dar, obwohl die Größe dieses Anteils von dem zu lösenden Problem abhängt. So kann der Anteil größer für Probleme sein, wo die Bewertung jedes Individuums von einer Differentialgleichung oder dem Training eines neuronalen Netzes abhängt [12:1]. Andererseits können die Operationen Selektion, Rekombination und Mutation je nach Implementierung und Verfahren auch anteilig viel Rechenaufwand erzeugen - vor allem die Rekombination[13].
Damit sind die rechenaufwändigsten Faktoren eines GAs:
- Populationsgröße und Rechenaufwand: Dabei hat man den Trade-off: größere Populationen und mehr Generationen können die Fähigkeit des GAs verbessern, den Suchraum zu erkunden und eine vorzeitige Konvergenz zu vermeiden. Allerdings erhöhen sie auch die benötigte Rechenzeit und die Ressourcen [14].
- Komplexität der Fitness-Funktion: Umso komplexer die Auswertung eines Individuums ist, desto zeitaufwändiger ist die Ausführung des GAs.
- Restliche Operatoren: Je nach Verhalten können diese auch einen größeren Faktor des Rechenaufwandes darstellen.
¶ Fitnesslandschaften und lokale Optima
¶ Definition Fitnesslandschaft
Der Begriff Fitnesslandschaft fasst die Beziehung zwischen allen möglichen Lösungen eines Problems und ihren jeweiligen Fitnesswerten zusammen. Formal: Sei der Suchraum aller möglichen Lösungen und die Funktion bildet jedes auf einen Fitnesswert ab. Dann ist die Fitnesslandschaft die Paarung .
Ob ein GA das globale Optimum garantiert findet, hängt von der Struktur des Lösungsraums ab. Aufgrund der stochastischen Charakteristik von genetischen Algorithmen kann eine Konvergenz zum globalen Optimum nur bei unimodalen Lösungsräumen garantiert sein[15]. Allerdings sind in der Praxis Lösungsräume komplexer mit vielen lokalen Optima und Plateaus.
Ein GA verhält sich anders als ein Gradientenverfahren, denn ein GA springt von Generation zu Generation zwischen Punkten/Lösungen in der Fitnesslandschaft. So wird durch Selektion, Rekombination und Mutation nur eine höhere Wahrscheinlichkeit einer Lösung in einem Optimum forciert. Bei Fitnesslandschaften mit vielen lokalen Optima kann es vorkommen, dass sich die Population des GA auf eines dieser lokalen Optima konzentriert und somit nicht die global optimale Lösung für das Problem findet. Somit ergibt sich der Trade-off zwischen suboptimaler Konvergenz und Techniken zur Erhaltung der Populationsdiversität, wie Fitness-Sharing oder Multiobjektiv-Optimierung [16], welche wiederum den Rechenaufwand erhöhen. Insgesamt lässt sich festhalten, dass die Leistungsfähigkeit eines GAs sehr von der jeweiligen Implementierung und der Fitnessfunktion abhängt.
¶ Geeignete Probleme für GA
Genetische Algorithmen eignen sich besonders gut für kombinatorische und NP-harte Optimierungsprobleme, denn diese haben meist einen sehr großen Suchraum. Ab einer gewissen Größe ist eine vollständige Durchsuchung eines Suchraums technisch unmöglich. In solchen Fällen können GAs unter den richtigen Populationsdiversitäts-Einschränkungen parallel die verschiedenen Regionen eines Lösungsraums erkunden und aufgrund des globalen Suchcharakters bei der Initialisierung in einer vertretbaren Zeit eine relativ gute und mit Glück die optimale Lösung finden [17].
Im Vergleich zu simplen Gradientenverfahren haben GAs über ihren initialen globalen und sprunghaften Charakter eine größere Wahrscheinlichkeit, aus lokalen Optima zu entkommen und so das globale Optimum wahrscheinlicher zu finden.
Ein weiterer Vorteil, der in der Natur von GAs steckt, ist, dass sie sowohl diskrete als auch kontinuierliche Parameter kodieren können.
¶ Bildquellen
Abb. 1: Hornby, G. (2006). Photographs of prototype evolved antennas [Foto]. In "Automated Antenna Design with Evolutionary Algorithms". ResearchGate. Abgerufen von https://www.researchgate.net/profile/Greg-Hornby/publication/254179034/figure/fig3/AS:667617048137736@1536183716377/Photographs-of-prototype-evolved-antennas-a-the-best-evolved-antenna-for-the-initial_Q320.jpg
Abb. 2: Pstrykotwórca, O. (2010). Estimation of Distribution Algorithm animation [GIF]. Wikimedia Commons. (Lizenz: CC BY-SA 3.0). Abgerufen von https://upload.wikimedia.org/wikipedia/commons/2/2b/Estimation_of_Distribution_Algorithm_animation.gif
¶ Literatur
Sastry, K., Goldberg, D., Kendall, G. (2005). Genetic Algorithms. In: Burke, E.K., Kendall, G. (eds) Search Methodologies. Springer, Boston, MA. https://doi.org/10.1007/0-387-28356-0_4 ↩︎
Nissen, V. (1997). Genetische Algorithmen. In: Einführung in Evolutionäre Algorithmen. Computational Intelligence. Vieweg+Teubner Verlag. https://doi.org/10.1007/978-3-322-93861-9_2 ↩︎
Holland, J. H. (1992). Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. MIT Press. Verfügbar über IEEE Xplore: https://ieeexplore.ieee.org/book/6267401 ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎
Lohn, J. D., Hornby, G. S., & Linden, D. S. (2004). An evolved antenna for deployment on NASA’s Space Technology 5 Mission. NASA Ames Research Center. Verfügbar über NASA Technical Reports Server: https://ntrs.nasa.gov/citations/20040152147 ↩︎
Hornby, G. S., Globus, A., Linden, D. S., & Lohn, J. D. (2006, September). Automated antenna design with evolutionary algorithms. In AIAA Space Forum (Paper No. 2006‑7242). American Institute of Aeronautics and Astronautics. https://www.researchgate.net/publication/228909002_Automated_Antenna_Design_with_Evolutionary_Algorithms ↩︎
Selzam, B. (2003). Genetische Algorithmen (S. 2-2). Technische Universität Dortmund. Verfügbar als PDF: https://ls11-www.cs.tu-dortmund.de/lehre/SoSe03/PG431/Ausarbeitungen/GA_Selzam.pdf ↩︎ ↩︎ ↩︎ ↩︎ ↩︎
Mitchell, M. (1996). An Introduction to Genetic Algorithms. The MIT Press. Reprint 1998 edition. Verfügbar über MIT Press Direct: https://direct.mit.edu/books/monograph/4675/An-Introduction-to-Genetic-Algorithms ↩︎
Selzam, B. (2003). Genetische Algorithmen (S. 7). Technische Universität Dortmund. Verfügbar als PDF: https://ls11-www.cs.tu-dortmund.de/lehre/SoSe03/PG431/Ausarbeitungen/GA_Selzam.pdf ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎
Sastry, K., Goldberg, D., & Kendall, G. (2005). Genetic Algorithms (S. 98-104). In E. K. Burke & G. Kendall (Hrsg.), Search Methodologies. Springer, Boston, MA. https://doi.org/10.1007/0-387-28356-0_4 ↩︎
Rudolph, Günter (1994). Convergence analysis of canonical genetic algorithms. IEEE TRANSACTIONS ON NEURAL NETWORKS, VOL. 5. https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=265964 ↩︎
White, David (2014). AN OVERVIEW OF SCHEMA THEORY (arXiv:1401.2651). arXiv. Verfügbar über: https://arxiv.org/pdf/1401.2651 ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎
Feri Sulianta (2023). Critical Evaluation of Genetic Algorithms: From Computational Costs to Theoretical Gaps (S. 4). ResearchGate. Verfügbar als PDF: https://www.researchgate.net/publication/383235567_Critical_Evaluation_of_Genetic_Algorithms_From_Computational_Costs_to_Theoretical_Gaps ↩︎ ↩︎
Sastry, K., Goldberg, D., & Kendall, G. (2005). Genetic Algorithms. In: Burke, E.K., Kendall, G. (Hrsg.), Search methodologies: Introductory tutorials in optimization and decision support techniques (S. 97-125). Springer. https://doi.org/10.1007/0-387-28356-0_4 ↩︎
Bäck, T. (1996). Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms. Oxford University Press. ↩︎
Mitchell, M. (1998). An Introduction to Genetic Algorithms. MIT Press. ↩︎
Whitley, D. (1991). Fundamental Principles of Deception in Genetic Search. In: Rawlins, G. J. E. (Hrsg.), Foundations of Genetic Algorithms (Bd. 1, S. 221–241). Morgan Kaufmann. ↩︎
de Jong, K. A., & Spears, W. M. (1989). Using genetic algorithms to solve NP‑complete problems. In Proceedings of the Third International Conference on Genetic Algorithms (S. 124–132). Morgan Kaufmann. Verfügbar über ACM DL: https://dl.acm.org/doi/10.5555/93126.93172 :contentReference[oaicite:1] ↩︎