Evolutionäre Algorithmen (EAs) sind eine Klasse populationsbasierter metaheuristischer Optimierungstechniken, die von den Mechanismen der biologischen Evolution wie Reproduktion, Mutation, Rekombination und Selektion inspiriert sind. Sie werden verwendet, um Näherungslösungen für schwierige Optimierungsprobleme zu finden, für die keine exakten oder zufriedenstellenden Methoden bekannt sind. Als Teil der evolutionären Berechnung und der Computational Intelligence arbeiten EAs mit einer Population von Kandidatenlösungen, bewerten deren Qualität über eine Fitnessfunktion und wenden iterativ evolutionäre Operatoren an, um die Population über Generationen hinweg zu verbessern. Ihr Hauptvorteil besteht darin, dass sie nur wenige Annahmen über die zugrunde liegende Fitnesslandschaft treffen, wodurch sie eine Vielzahl von Problemen bewältigen können, obwohl ihre rechnerische Komplexität oft aus den Kosten der Fitnessbewertung resultiert.
Generischer Algorithmus
Der typische evolutionäre Algorithmus folgt einem iterativen Prozess:
- Zufälliges Erzeugen einer Anfangspopulation von Individuen (der ersten Generation).
- Bewerten der Fitness jedes Individuums in der Population.
- Prüfen, ob das Ziel erreicht ist; wenn ja, Beenden.
- Auswählen von Individuen als Eltern, vorzugsweise solchen mit höherer Fitness.
- Erzeugen von Nachkommen durch Crossover (das die Reproduktion nachahmt) und optional Mutation.
- Anwenden von Mutationsoperationen auf die Nachkommen.
- Auswählen von Individuen zur Ersetzung, vorzugsweise solchen mit niedrigerer Fitness, um die nächste Generation zu bilden.
- Zurückkehren zu Schritt 2 und Wiederholen bis zur Beendigung.
Dieses generische Rahmenwerk wird in verschiedenen EA-Typen angepasst, jeweils mit spezifischen Repräsentationen und Operatoren.
Typen evolutionärer Algorithmen
Es existieren mehrere EA-Varianten, die sich in genetischer Repräsentation und Implementierungsdetails unterscheiden:
- Genetischer Algorithmus (GA): Der beliebteste Typ, bei dem Lösungen als Zahlenfolgen (oft binär) dargestellt werden. Operatoren wie Rekombination und Mutation werden angewendet. GAs werden häufig bei Optimierungsproblemen eingesetzt.
- Genetische Programmierung (GP): Lösungen sind Computerprogramme, und die Fitness wird durch ihre Fähigkeit bestimmt, Rechenprobleme zu lösen. Varianten umfassen kartesische genetische Programmierung, Genexpressionsprogrammierung, grammatische Evolution, lineare genetische Programmierung und Multi-Expressions-Programmierung.
- Evolutionsstrategie (ES): In den 1960er und 1970er Jahren von Ingo Rechenberg, Hans-Paul Schwefel und Kollegen entwickelt, konzentriert sich ES auf numerische und technische Optimierung. Sie arbeitet mit reellwertigen Vektoren und verwendet Mutation, Rekombination und deterministische Selektion. Ein charakteristisches Merkmal ist die Selbstadaption der Mutationsverteilung, mit Formen wie (1+1)-ES, (μ, λ)-ES und (μ+λ)-ES. Spätere Entwicklungen umfassen Kovarianzmatrix-Adaption (CMA-ES) und natürliche Evolutionsstrategien.
- Differential Evolution (DE): Basiert auf Vektordifferenzen und ist hauptsächlich für numerische Optimierung geeignet.
- Evolutionäre Multiobjektiv-Optimierung: Erweitert EAs auf Probleme mit mehreren widersprüchlichen Zielen und erhält eine Population, die Kompromisslösungen auf der Pareto-Front annähert.
- Koevolutionärer Algorithmus: Lösungen werden anhand von Interaktionen mit anderen Lösungen bewertet, die konkurrieren oder kooperieren können. Nützlich für dynamische oder wettbewerbsorientierte Fitnesslandschaften.
- Neuroevolution: Genome repräsentieren künstliche neuronale Netze und kodieren Struktur und Verbindungsgewichte, entweder direkt oder indirekt.
- Lernendes Klassifikatorsystem (LCS): Lösungen sind Mengen von Klassifikatoren (Regeln). Michigan-LCS evolviert einzelne Klassifikatoren, während Pittsburgh-LCS Populationen von Klassifikatormengen evolviert. Die Fitness wird über bestärkendes Lernen oder überwachtes Lernen bestimmt.
- Qualitäts-Diversitäts-Algorithmen (QD): Zielen gleichzeitig auf qualitativ hochwertige und vielfältige Lösungen ab und erkunden eine breite Vielfalt von Lösungen über den Problemraum.
Theoretischer Hintergrund
No-Free-Lunch-Theorem
Das No-Free-Lunch-Theorem der Optimierung besagt, dass bei Betrachtung aller möglichen Optimierungsprobleme alle Optimierungsstrategien gleichermaßen effektiv sind. Dies impliziert, dass kein evolutionärer Algorithmus einem anderen über alle Probleme hinweg grundsätzlich überlegen ist. In der Praxis ist die Menge der Probleme jedoch eingeschränkt, und EAs können durch die Nutzung problemspezifischen Wissens verbessert werden, beispielsweise durch die Wahl geeigneter Repräsentationen und Operatoren.
Rechenkomplexität
In den meisten realen Anwendungen ist die Rechenkomplexität von EAs ein bedeutender Faktor, hauptsächlich aufgrund der Kosten der Fitnessfunktionsbewertung. Techniken zur Fitnessapproximation können dieses Problem abmildern. Interessanterweise können einfache EAs oft komplexe Probleme lösen, was darauf hindeutet, dass es keine direkte Verbindung zwischen Algorithmuskomplexität und Problemkomplexität gibt.
Anwendungen und Einschränkungen
Evolutionäre Algorithmen werden in verschiedenen Bereichen angewendet, darunter technisches Design, Planung, maschinelles Lernen (z. B. Neuroevolution) und Multiobjektiv-Optimierung. Sie sind besonders wertvoll, wenn der Suchraum groß, nichtlinear oder schlecht verstanden ist. Ihre Leistung hängt jedoch von der Parameterabstimmung und der Problemrepräsentation ab. Techniken aus EAs werden auch zur Modellierung biologischer Mikroevolution und zellulärer Prozesse verwendet, allerdings mit Einschränkungen.