Forschungsschwerpunkt

---

Abstract

Evolutionäre Algorithmen und Evolutionsstrategien

Evolutionäre Algorithmen (EA) gehören zur Klasse der randomisierten Suchverfahren. EAs sind an der biologischen Evolution orientiert, indem sie deren wesentlichen Elemente wie Variation von Lösungen durch Rekombination und Mutation sowie Selektion der besten Individuen übernehmen. Der Vorteil evolutionärer Algorithmen gegenüber anderen problemspezifischen Verfahren liegt in ihrer universellen Einsatzfähigkeit.

Man kann zwischen verschiedenen Grundformen evolutionärer Algorithmen unterscheiden, die sich in Aspekten wie Lösungsrepräsentation und in Struktur und Bedeutung von Suchoperatoren wie Rekombination und Mutation unterscheiden. Zu diesen Grundformen gehöre die Evolutionsstrategien (ES), die genetischen Algorithmen (GA), die evolutionäre Programmierung (EP) und die genetische Programmierung (GP). Aktuelle Entwicklungen führen zu einer gegenseitigen Annäherung der ersten drei Formen. Evolutionäre Verfahren können u.a. dann zum Einsatz kommen, wenn klassische Optimierverfahren versagen oder nicht anwendbar sind. Dieser Fall tritt z.B. bei vielen technischen Optimieraufgaben auf, bei denen ein Simulationsmodell die Grundlage für den Optimierprozess darstellt. Für klassische Verfahren treten Probleme bei nicht metrischen, stochastisch gestörten, nicht stetigen oder nicht differenzierbaren Zielfunktionen auf.

Die Form eines allgemeinen evolutionären Algorithmus ist folgender Abbildung  zu entnehmen.

 

1    Start
2      t:=0;
3      Initialisiere P(t);
4      Bewerte P(t);
5      Repeat
6        Ändere P(t) in P'(t) durch Mutation und Rekombination
7        Bewerte P'(t)
8        Selektiere P(t+1) aus P'(t);
9        t:=t+1;
10     Until Abbruchbedingung
11   End

Der Ablauf eines allgemeinen evolutionären Algorithmus.

 

Jeder EA arbeitet mit einer Population P von Individuen P(t)= {x₁^t,...,x_n^t} zur Generation t. Jedes Individuum repräsentiert eine potentielle Lösung für das betrachtete Problem und wird mit Hilfe einer Datenstruktur S implementiert. Die Güte der Lösung wird häufig durch eine Bewertungsfunktion bestimmt. In jedem Generationsschritt werden die Individuen der aktuellen Population mittels so genannter genetischer Operatoren einer Transformation unterworfen und bilden die Population P'(t). Dabei kann ein neues Individuum aus einem Eltern-Individuum entstehen (Operation m: S -> S) oder aus mehreren Eltern (Operation c: S x ... x S -> S). Die beiden Hauptformen genetischer Operatoren sind Mutation und Rekombination. Nach der Anwendung genetischer Operatoren erfolgt die Bewertung der Güte der einzelnen Individuen, sprich der Lösungen für das betrachtete Problem. Auf Basis dieser Bewertung erfolgt im letzten Schritt die Selektion der Individuen, die als Grundlage für die Generierung neuer Individuen im nächsten Generationsschritt in Frage kommen. Die Größe der Population P(t) kann von der Größe der Population P'(t) abweichen. Es existiert mittlerweile eine Fülle von hybriden Systemen, die sich ausgewählte Eigenschaften der einzelnen Hauptformen zu Nutze machen, deren weitere Klassifizierung jedoch nur von geringer Relevanz ist.

Restriktionsbehandlung bei Evolutionäre Algorithmen

Für evolutionäre Algorithmen existieren mittlerweile eine Vielzahl von Restriktionsbehandlungsmethoden. Allen voran kam in der Vergangenheit vor allem bei Evolutionsstrategien die Methode Death Penalty zum Einsatz. Hierbei werden ungültige Individuen einfach verworfen und solange neue erzeugt bis die Population der Nachkommen nur gültige Individuen enthält. Die meisten anderen Methoden zur Behandlung von Restriktionen sind die sogenannten Penalty-Funktionen, die ungültige Individuen in den Suchprozess mit einbeziehen, jedoch mit einem ungünstigen Fitness-Wert bestrafen. Restringierte Problemräume können in manchen Fällen durch spezielle Repräsentationen und angepasste Operatoren vermieden werden. Eine weitere Klasse von Restriktionsbehandlungsmethoden stellen die Decoder dar. Sie bilden den restringierten Problemraum in einen anderen Problemraum ab und lassen die evolutionäre Suche dort stattfinden. Reparatur-Algorithmen transformieren ungültige Individuen mit Hilfe heuristischer Verfahren in gültige Individuen und benutzen die reparierten Individuen zur Bewertung bzw. zur Integration in die Population. Im Rahmen der als Coevolution bezeichneten Verfahren wird ein Räuber-Beute-Ansatz mit einer Population aus Lösungen und einer aus Restriktionen verwendet. Die Restriktionsbehandlung basierend auf multikriteriellen Verfahren fasst jede Restriktionsfunktion als Zielfunktion auf und ermöglicht auf diese Weise die Anwendung vieler Verfahren der Mehrzieloptimierung.

---

Selected Publications

• Oliver Kramer, Chuan-Kang Ting, Hans Kleine Büning: A New Mutation Operator for Evolution Strategies for Constrained Problems.
  Proc. Congress on Evolutionary Computation (CEC 2005), Edinburgh, 2005.
• Oliver Kramer, Chuan-Kang Ting, Hans Kleine Büning: A Mutation Operator for Evolution Strategies to Handle Constrained Problems
  Proc. Genetic and Evolutionary Computation Conference (Gecco 2005), Washington, 2005.
• Oliver Kramer, Hans-Paul Schwefel: On Three New Approaches to Handle Constraints within Evolution Strategies.
  To appear in Journal 'Natural Computing'.
• Steffen Priesterjahn, Oliver Kramer, Alexander Weimer, Andreas Goebels: Evolution of Reactive Rules in Multi Player Computer Games Based on Imitation.
  Proc. First International Conference on Natural Computation.