Evolutionäre Algorithmen sind eine Gruppe stochastischer, direkter Suchalgorithmen, welche von der Darwin'schen Evolutionstheorie inspiriert sind.[1]
Hierbei repräsentieren die Individuen mögliche Lösungen, welche in der Gesamtheit eine Population bilden. Durch Anwendung verschiedener Operatoren werden neue Individuen erzeugt, wobei Individuen mit einer besseren Bewertung, oder Fitness bevorzugt selektiert werden.[2]
Besonders für Optimierungsprobleme werden evolutionäre Algorithmen aufgrund ihrer Flexibilität und Robustheit oft verwendet.[3]
¶ Biologische Grundlagen
Um im Folgenden die einzelnen Umsetzungen der Arten evolutionärer Algorithmen besser nachzuvollziehen, gehen wir hier auf die grundlegenden biologischen Begrifflichkeiten kurz ein.
¶ Evolution
Biologische Evolution ist die von Generation zu Generation stattfindende Veränderung der genetischen Merkmale einer Population.[4] Gene repräsentieren dabei die Merkmale von Lebensformen.[4:1]
¶ Selektion
Selektion, hier besonders die natürliche Selektion, bezeichnet die Reduzierung/Erhöhung der Fortpflanzungsrate eines Individuums, je nachdem wie gut angepasst das Individuum an die Umwelt ist. Dabei vermehren sich besser angepasste, also fittere, Individuen mit einer höheren Rate und kann so eher seine Gene vererben.[5]
Die Selektion entsteht durch verschiedene Methoden: durch sexuelle Selektion durch einen Sexualpartner, sowie durch die Umwelt, ausgedrückt durch bestimmte umwelttechnische Faktoren wie begrenzte Ressourcen oder Konkurrenz.[1:1]
¶ Mutation
Mutationen sind spontan oder durch äußere Einflüsse beeinflusste Veränderungen des Erbgutes. Diese können sich sowohl negativ als auch positiv auf das Individuum auswirken.[6]
¶ Rekombination
Unter Rekombination versteht man die Neuanordnung des genetischen Materials, wodurch neue Gen- und Merkmalskombinationen auftreten. Diese beeinflussen die genetische Vielfalt der Generation.[7]
¶ Bestandteile
In diesem Abschnitt werden die einzelnen Bestandteile von evolutionären Algorithmen erklärt. Die genaue Implementation unterscheidet sich bei den verschiedenen Arten von Algorithmen, sowie zwischen unterschiedlichen Algorithmen einer Art. Beispielsweise unterscheiden sich die Arten der Selektion zwischen genetischen Algorithmen und Evolutionären Strategien.[1:2]
¶ Individuen
Evolutionäre Algorithmen arbeiten auf Lösungskandidaten, den sogenannten Individuen.[8] Diese sind aufgebaut aus Chromosomen, welche aus Genen bestehen.[8:1] Die Chromosomen kodieren potenzielle Lösungen, meist in Binärstrings festgesetzter Länge[8:2]. Dabei ist es auch möglich, für die Darstellung der Chromosomen andere Datentypen verwendet werden.[1:3] Einzelne Gene stellen dabei meist einen bestimmten Parameter dar.[8:3]
Der Genotyp ist die Gesamtzahl der Chromosomen des Individuums, auf welche die Suchoperatoren angewandt werden.[8:4]
Der Phänotyp entsteht aus dem Mapping von dem Genotyp auf die Parameter[1:4], und stellt implementierbare Lösungskandidaten dar.[1:5]
¶ Initialisierung, Terminierung
Der Algorithmus wird meist mit einer Anzahl von zufällig generierten Individuen initialisiert.[3:1] Die Terminierung ist problemabhängig.
Beliebte Terminierungskriterien sind dabei: Anzahl der Fitness-Funktionsevaluationen, maximale Laufzeit, Konvergenz gegen einen bestimmten Fitnesswert.[8:5]
¶ Suchoperatoren
Die Suchoperatoren arbeiten auf den Genotypen der Individuen.[1:6] Dabei müssen Mutation und Rekombination nicht während jeder Generation von Individuen angewendet werden[9]. In einigen Fällen reichen bestimmte Wahrscheinlichkeiten, mit denen die Operatoren angewendet werden. Laut Spears und De Jong reichen in den meisten Fällen für NP-vollständige Probleme eine Rekombinationsrate von 60 % und eine Mutationsrate von 0.1 %.[9:1]
¶ Rekombination/Crossover
.jpg)
Die Rekombination kommt in Verwendung im Zusammenhang der Paarung. Dieser Operator ist ein binärer Operator, welcher mit zwei Individuen arbeitet.[3:2] In der Literatur wird dafür oft der Begriff Crossover verwendet.
Nachdem die Elternindividuen selektiert wurden, wird durch Rekombination ein neues Kind erschaffen, welches einen neuen Genotyp enthält. Der Rekombinationsoperator organisiert dabei bestehende Informationen nur neu[1:7]. Der Vorteil dabei ist, dass der Suchraum auf vielversprechende Lösungskandidaten reduziert wird, da im Voraus Individuen mit einer höheren Fitness gewählt wurden.
Es gibt verschiedene Arten des Crossover-Operators.
Die einfachste ist one-point oder single-point crossover. Dabei werden die Elternchromosomen an einem Punkt geteilt, und das Kind aus jeweils einem Teil des Elternteils und aus dem anderen Teil des anderen Elternteils zusammengesetzt. Dabei müssen die Anteile nicht gleich sein. Die Auswahl, welcher Teilstring von welchem Elternteil genommen wird, ist meist zufällig.[1:8]
Auch two-point crossover, wobei die Chromosomen an zwei Stellen geteilt werden, oder uniform crossover, wo für jedes Gen zufällig entschieden wird, von welchem Elternteil es kommt[10], sind beliebte Arten der Rekombination.
¶ Mutation
.jpg)
Mutation arbeitet als unärer Operator ausschließlich auf einem Individuum[3:3].
Der einfachste Mutationsoperator ist das Bit-Flip-Verfahren, bei dem an einer oder mehreren Stellen des Chromosoms ein Bit in das Gegenteil geändert wird. In dem Prozess werden neue Informationen erschaffen, im Gegensatz zur Rekombination[1:9]. Mutation stellt sicher, dass die Suche nicht frühzeitig stoppt[1:10], da durch Mutation unabhängig von Rekombination neue Individuen entstehen. Die Vielfalt wird durch die zufällige Änderung erhöht.
Wie auch bei biologischen Organismen kann die Mutation gutartige oder bösartige Folgen haben. Gutartige Mutation erhöht die Fitness des Individuums, wobei bösartige Mutation sie verringert.
¶ Selektion
Bei evolutionären Algorithmen werden zwei verschiedene Arten von Selektion angewandt: Paarungs-/ Elternselektion[11] und Umweltselektion.[1:11]
Bei der Paarungsselektion werden zwei Individuen in Hinsicht ihrer Fitness gewählt, wonach aus ihnen neue Kindindividuen entstehen.
Bei der Umweltselektion geht es um den Konkurrenzkampf der Individuen, wo die fittesten, also die Individuen mit einer hohen Fitness, "überleben". Dabei geht es im konkreten darum, welche Individuen im Suchraum übernommen werden bzw. verbleiben, und welche aus dem Suchraum genommen werden.[11:1]
¶ Selektionsoperator
Der Selektionsoperator gibt die Richtung der Suche an, indem er die Individuen mit einer hohen Fitness priorisiert[8:6]. Es gibt einige populäre Arten von Selektionsoperatoren, wobei die ausgewählten Elternindividuen meist erneut in die Population übernommen werden. So können sie im Verlauf erneut gewählt werden.[8:7]
¶ Plus-Selektion, ""-Selektion[8:8]
Plus-Selektion ist elitär, was bedeutet, dass die besten Individuen ausgewählt werden, sowie deterministisch. Hierbei werden die beiden Individuen mit der höchsten Fitness gepaart.
Wähle die besten Individuen aus einer Population von Kindern und Eltern , also einer Menge von Individuen, aus.[11:2]
¶ Komma-Selektion, ","-Selektion[8:9]
Diese Selektionsart ist elitär. Dabei werden die besten Individuen aus der Kindgeneration zur Paarung ausgewählt. Die Elterngeneration wird dabei nicht betrachtet.
Wähle die besten Individuen aus der Kindgeneration , wobei gilt, dass bzw. .
¶ Zufällige Selektion[8:10]
.jpg)
Bei zufälliger Selektion wird ebenfalls die Fitness im Betracht genommen.
Eine Art davon ist die Roulette-Selektion. Dabei werden die verfügbaren Individuen wie auf einer Roulette-Scheibe angeordnet, wobei die Größe der einzelnen Areale proportional zu der Fitness der jeweiligen Individuen ist. Fittere Individuen haben also eine höhere Wahrscheinlichkeit, gewählt zu werden. Durch die zufällige Art dieser Selektion können hierbei, im Vergleich zu anderen Selektionsarten, auch Individuen mit einer schlechteren Fitness gewählt werden.
¶ Fitness[8:11]
Die Implementierung der Fitness, sowie der Fitness-Funktion ist stark abhängig von dem (Optimierungs-)Problem. Jedoch ist sie besonders wichtig für Selektionsvorgänge.
Die Fitness, oder auch fitness value, eines Individuums ist immer in Abhängigkeit zu der Problemstellung zu betrachten. Sie ist das Qualitätsmerkmal des Individuums und besagt, wie geeignet es als Lösungskandidat ist. Eine höhere Fitness entspricht dabei einer höheren Qualität.
Die Fitness-Funktion ist dabei die Funktion, welche im Laufe des Algorithmus optimiert werden soll. Sie hängt stark von den Parametern des Algorithmus ab, wobei die Eingabeparameter der Funktion die Objektparameter des Algorithmus sind. Die Ausgabe ist dabei ein (oder bei Multiparameter-Optimierungsproblemen mehrere) Wert, welcher die Qualität des Individuums repräsentiert.
So kann eine Fitness-Funktion beispielsweise alle Gene des Individuums addieren, um die Fitness zu berechenen. In der Praxis kommen meist komplexere Formel zum Einsatz.
¶ Typen der Evolutionären Algorithmen
Es gibt verschiedene Typen von evolutionären Algorithmen. Diese Methoden simulieren Evolution von Individuen durch die oben genannten verschiedenen Operatoren, Selektion, Mutation und Rekombination. Sie unterscheiden sich jedoch in der Implementierung und der Methodik, wie sie auf spezifische Probleme angewendet werden.[3:4]
¶ Genetische Algorithmen (GA)
Genetische Algorithmen (GA) sind die bekannteste Form der evolutionären Algorithmen, da sie den natürlichen Evolutionsprozess am klarsten auf den Computer abbilden.[3:5] Sie basieren ursprünglich auf binären (Bit-)String-Repräsentationen, ähnlich dem DNA-Alphabet in der Biologie.[1:12] Ursprünglich in den 1970er Jahren von Holland und seinem Studenten entwickelt.[3:6] Der GA verwendet Rekombinations- und Mutationsoperatoren, um Lösungen in Form von Zahlenfolgen (traditionell binär) zu finden, die die Gene repräsentieren.[1:13][3:7]
¶ Pseudocode[1:14]
population = InitializePopulation(populationSize, problemDimension);
evaluatePopulation(population);
bestSolution = getBestSolution(population);
while testForTermination == false do
offspring = ∅
parents = matingSelection(population);
for parent₁, parent₂ ∈ population do
(offspring₁, offspring₂) = crossover(parent₁, parent₂);
offspring₁ = mutate(parent₁);
offspring₂ = mutate(parent₂);
offspring = {offspring} ∪ offspring₁ ∪ offspring₂;
end for
evaluatePopulation(offspring);
bestSolution = getBestSolution(offspring);
population = replace(population, offspring);
end while
Return(bestSolution);
¶ Evolutionäre Programmierung (EP)
Das Konzept der Evolutionären Programmierung (EP) wurde erstmals 1966 von Fogel als Methode zur Erreichung von Künstlicher Intelligenz eingeführt.[3:8] Die Selektion in der Evolutionären Programmierung (EP) ist häufig probabilistisch. EP arbeitet auf der natürlichen Problemrepräsentation, weshalb keine Genotyp-Phänotyp-Abbildung verwendet wird. Im Gegensatz zu den anderen Typen wird in EP keine Rekombination (Crossover) verwendet. Als Variationsoperator wird nur Mutation eingesetzt.[1:15]
¶ Pseudocode [1:16]
population = InitializePopulation(populationSize, problemDimension);
evaluatePopulation(population);
bestSolution = getBestSolution(population);
while testForTermination == false do
offspring = ∅
for parentᵢ ∈ population do
offspringᵢ = mutate(parentᵢ);
offspring = {offspring} ∪ offspringᵢ;
end for
evaluatePopulation(offspring);
bestSolution = getBestSolution(offspring, bestSolution);
population = {population} ∪ {offspring};
population = environmentalSelection(population);
end while
Return(bestSolution);
¶ Evolutionäre Strategien (ES)
Es wurde erstmals 1973 von Rechenberg als Optimierungsmethode für komplexe, multimodale und nicht differenzierbare Funktionen vorgeschlagen. Es wird verwendet, um den tatsächlichen Ausdruck eines Attributs zu lösen, indem redundante Codierung weggelassen wird. Daher werden in der Evolutionären Strategie die Lösungen mit Vektoren von reellen Zahlen dargestellt, und es werden selbstadaptive Mutationsraten verwendet.[3:9]
Die erste Evolutionäre Strategie (ES), das sogenannte (1 + 1)-ES verwendet nur einen Elternteil und einen Nachkommen. Wenn die Nachkommenlösung besser ist als die Elternlösung, wird sie als neuer Elternteil übernommen, andernfalls bleibt der Elternteil erhalten.[1:17]
population = InitializePopulation(populationSize, problemDimension);
evaluatePopulation(population);
bestSolution = getBestSolution(population);
while testForTermination == false do
offspring = ∅
for i = 0 to offspingSize do
matingPop = matingSelection(population);
offspringᵢ = recombination(matingPop);
offspringᵢ = mutate(offspringᵢ);
offspring = {offspring} ∪ offspringᵢ;
end for
evaluatePopulation(offspring);
population = environmentalSelection(population);
bestSolution = getBestSolution(population);
end while
Return(bestSolution);
¶ Genetische Programmierung (GP)
Genetische Programmierung (GP) wurde 1992 von Koza entwickelt. Im Gegensatz zu GA, bei denen Attribute durch allgemeine binäre Kodierung dargestellt werden, stellt Genetische Programmierung Programme als Attribute dar. GP erzeugt Lösungen in Form von Computerprogrammen, deren Fähigkeit zur Lösung eines rechnerischen Problems durch die Fitnessfunktion bestimmt wird.[2:1]
¶ Pseudocode[1:18]
population = InitializePopulation(populationSize);
evaluatePopulation(population);
bestSolution = getBestSolution(population);
while testForTermination == false do
offspring = ∅;
while ‖offspring‖ < ‖population‖ do
genOp = selectGeneticOperation;
if genOp == crossover then
(parent₁, parent₂) = matingSelection(population);
(offspring₁, offspring₂) = crossover(parent₁, parent₂);
offspring = {offspring} ∪ offspring₁ ∪ offspring₂;
if genOp == mutation then
parent = matingSelection(population);
offspring₁ = mutate(parent);
offspring = {offspring} ∪ offspring₁;
if genOp == reproduction then
parent = matingSelection(population);
offspring = {offspring} ∪ parent;
evaluatePopulation(offspring);
bestSolution = getBestSolution(offspring, bestSolution);
population = replace(population, offspring);
Return(bestSolution);
¶ Anwendungen
Evolutionsalgorithmen (EAs), insbesondere genetische Algorithmen (GAs), wurden erfolgreich bei einer Vielzahl von NP-schweren Problemen angewendet und haben signifikante Erfolge geschafft. Einige Beispiele für die Anwendungen von GAs: [12]
-
Operationsmanagement
Genetische Algorithmen (GA) zeigten hohe Effizienz bei der Lösung von Problemen wie Facility Layout, Scheduling, Lagersteuerung, Prognose und Netzwerkdesign. -
Multimedia
Genetische Algorithmen (GA) sind in verschiedenen Bereichen der Multimedia eingesetzt, wie z. B. in der Informationssicherheit (Verschlüsselung), Bildverarbeitung (Segmentierung, Rauschunterdrückung, Objekterkennung), Videoverarbeitung (Gesten- und Gesichtserkennung), medizinischer Bildgebung (Tumorerkennung) und Präzisionslandwirtschaft (Ernteertrag, Unkrauterkennung). -
Wireless Networking
Genetische Algorithmen (GA) werden zur Lösung von Problemen in drahtlosen Netzwerken eingesetzt, wie Routing, Lastenausgleich, Lokalisierung, Bandbreiten- und Kanalzuweisung. GA hilft bei der Optimierung von Routen und Lasten in Netzwerken und wird in Kombination mit anderen Algorithmen wie ACO verwendet. In der Lokalisierung von drahtlosen Knoten wird GA mit Fuzzy Logik und simuliertem Annealing kombiniert. GA optimiert auch die Bandbreitenzuweisung und Kanalzuweisung, etwa in kognitiven Funknetzwerken und bei dynamischen Zuweisungsproblemen. -
Spiele
Genetische Algorithmen (GA) wird auch in Gaming-Anwendungen genutzt, etwa für die Routenplanung und Bewegungssteuerung in Echtzeit-Strategiespielen.
Beispiele für Spiele, in denen GA genutzt werden:
¶ Referenzen
Bartz‐Beielstein, Thomas, Jürgen Branke, Jörn Mehnen, and Olaf Mersmann. 2014. “Evolutionary Algorithms.” WIREs Data Mining and Knowledge Discovery 4 (3): 178–95. pdf. ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎
Wiggers, Wouter, and Willem van Bergen. "A comparison of a genetic algorithm and a depth first search algorithm applied to Japanese nonograms." Twente student conference on IT. 2004. pdf ↩︎ ↩︎
Vikhar, Pradnya A. 2016. “Evolutionary Algorithms: A Critical Review and Its Future Prospects.” In 2016 International Conference on Global Trends in Signal Processing, Information Computing and Communication (ICGTSPICC), 261–65. Jalgaon, India: IEEE. pdf. ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎
https://de.wikipedia.org/wiki/Evolution (accessed: 30.12.2024, 17:20) ↩︎ ↩︎
https://de.wikipedia.org/w/index.php?title=Selektion_(Evolution)&stableid=242010103 (accessed: 30.12.2024, 17:47) ↩︎
https://de.wikipedia.org/w/index.php?title=Mutation&oldid=251294985 (accessed: 30.12.2024, 17:49) ↩︎
https://de.wikipedia.org/w/index.php?title=Rekombination_(Genetik)&oldid=250627783 (accessed: 30.12.2024, 17:52) ↩︎
http://ls11-www.cs.tu-dortmund.de/people/beyer/EA-glossary/def-engl-html.html (accessed: 31.12.2024, 13:38) ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎
Kenneth A. De Jong and William M. Spears. Using genetic algorithm to solve np-complete problems. In Proc. of the Third Int. Conf. on Genetic Algorithms, pages 24–132, 1989. pdf ↩︎ ↩︎
https://en.wikipedia.org/wiki/Crossover_(evolutionary_algorithm) (accessed: 30.12.2024 18:45) ↩︎
https://agra.informatik.uni-bremen.de/doc/lehrmat/wise0405/ea/kap3.pdf (accessed: 31.12.2024, 15:44) ↩︎ ↩︎ ↩︎
Katoch, Sourabh, Sumit Singh Chauhan, and Vijay Kumar. “A Review on Genetic Algorithm: Past, Present, and Future.” Multimedia Tools and Applications 80, no. 5 (February 1, 2021): 8091–8126. https://doi.org/10.1007/s11042-020-10139-6. pdf ↩︎