Inhaltsverzeichnis

1.  Evolutionäre Algorithmen  4

1.1.  Vorbemerkung.  4

1.2.  Evolutionäre Standardalgorithmen.  4

1.2.1.  Terminologie  5

1.2.2.  Evolutionsstrategien  6

1.2.3.  Genetische Algorithmen.  6

1.2.4.  Genetische Programmierung  7

2.  Testumgebung Evolutionärer Algorithmen.  8

2.1.  Testfunktionen.  9

2.1.1.  Das Sphären-Modell.  10

2.1.2.  Die Rosenbrock-Funktion  11

2.1.3.  Die Treppenfunktion  12

2.1.4.  Funktion mit normalverteilter Störung.  13

2.1.5.  Shekels Fuchsbauten  14

2.1.6.  Die Rastrigin-Funktion.  15

2.1.7.  Schwefels Rochen  16

2.1.8.  Boshafte Schwefel-Funktion  17

2.1.9.  Die Griewangk-Funktion.  18

2.2.  Kombinatorische Optimierungsprobleme als Testumgebung für EA  19

3.  Problematik praktischer Leistungsvergleiche  20

4.  Stärken und Schwächen von EA.  21

5.  Rückschlüsse für praktische Anwendungen  22

6.  Fazit  24

Literaturverzeichnis.   25

2

Abbildungsverzeichnis   

Abb.  1: Das Sphärenmodell R 3  

Abb.  2: Die Rosenbrock-Funktion im R 3  

Abb.  3: Die Treppenfunktion R 3  

Abb.  4: Funktion mit normalverteilter Störung im R 3  

Abb.  5: Shekels Fuchsbauten im R 3  

Abb.  6: Die Rastrigin-Funktion im R 3  

Abb.  7: Schwefels Rochen im R 3  

Abb.  8: Boshafte Schwefel-Funktion im R 3  

Abb.  9: Die Griewangk-Funktion im R 3  

3

1. Evolutionäre Algorithmen

1.1. Vorbemerkung

Seit Beginn der 1990´er Jahre haben Evolutionäre Algorithmen (EA) als universell anwendbare Verbesserungs- und Optimierungsstrategien eine weite Verbreitung in allen Bereichen von Wirtschaft und Forschung gefunden. Ihr großer Erfolg liegt u.a. in der Tatsache begründet, dass ihre Anwendung auf einem scheinbar einfachen und leicht nachvollziehbarem Prinzip, dem Darwinschen ¹ Evolutionsparadigma, oder etwas zugespitzt ausgedrückt, dem „survival of the fittest“ basiert: Durch die Anwendung von Variation und Selektion auf eine Population von Lösungsalternativen werden nach dem Muster der Natur schrittweise bessere Lösungen gefunden und auf diese Weise Optima bestimmt - oder zumindest approximiert.

1.2. Evolutionäre Standardalgorithmen

Mit der zunehmenden Leistungsfähigkeit von Rechnern hat in den letzten Dekaden eine Entwicklung begonnen, die zu den drei heutigen Hauptströmungen Evolutionärer Algorithmen führte.

Ingo Rechenberg und Hans-Paul Schwefel arbeiteten etwa an der Optimierung des Windwiderstandes eines Stromlinienkörpers. „Als das Problem mathematisch nicht gelöst werden konnte, kam man auf den Gedanken, durch die Nachahmung evolutionärer Prinzipien in vereinfachter Form, den Körper sukzessiv zu optimieren. Aus diesen Überlegungen der praktischen Optimierung entstand die Evolutionsstrategie (ES).“ ² Sie verwendet kontinuierliche Parameter und Mechanismen zur Selbstadaption ihrer Steuerungsparameter und ist vor allem auf Optimierungsprobleme mit kontinuierlichen Parametern zugeschnitten.

„John H. Holland schließlich ging es bei seinen Untersuchungen um eine Theorie adaptiver Systeme, welche über die Biologie hinausging und auch Phänomene ganz anderer Bereiche, wie z.B. der Ökonomie, einschloß. Seine zur Modellierung adaptiver Prozesse vorgeschlagenen (...) Genetische Algorithmen (GA) beruhten auf einer Abstraktion und Generalisierung des Populationskonzepts, der genetischen Codierung und Genetischer

¹ Charles Darwin (1809-1882), heute oft als Vater der Evolutionstheorie bezeichnet

² [NISS97], S.9

4

Operatoren.“ ³ GA verwenden in ihrer ursprünglichen Form eine binäre Codierung, so dass sie sich vor allem für die kombinatorische Optimierung eignen. Besondere Bedeutung unter den vielen Verfahrensvarianten hat auch die Genetische Programmierung (GP) erlangt, deren Grundgedanke darin besteht, „(...) Lösungen in Form von Computerprogrammen zu repräsentieren, die dann mit den Mechanismen der Evolution verändert werden.“ 4

Die Suche nach einer Möglichkeit, künstlich intelligente Automaten zu entwerfen, die „(...) einerseits innovative Problemlösungen generieren, andererseits aber auch Schlussfolgerungen auf das Funktionieren des menschlichen Intellekts zulassen“ ⁵ , bestimmte die Evolutionäre Programmierung (EP), mit den Hauptoperatoren Mutation und Selektion. EP spielt aufgrund einiger einschränkender Annahmen heute aber eine eher geringere Rolle als die anderen Richtungen. 6

1.2.1. Terminologie

Die Terminologie der EA orientiert sich stark an der Terminologie der Evolutionstheorie und der Genetik. Eine einzelne Lösung eines Ausgangsproblems wird als Individuum bezeichnet. Jedes Individuum hat eine bestimmte Güte, welche äquivalent in der Natur zu finden ist, wo sie die Überlebensfähigkeit eines Individuums beschreibt. Diese Güte bezeichnet man als Fitness. Aufgabe der EA ist es, das Individuum mit der höchstmöglichen Fitness zu finden, da es die optimale Lösung für das Ausgangsproblem darstellt. Mehrere Individuen werden zu einer Population zusammengefasst, die über den gesamten Lösungsraum „verstreut“ sein kann. Wird eine Population im Laufe des Algorithmus durch eine neue ersetzt, so spricht man - wie in der Natur - von Generationen. Ein Individuum besitzt eine Reihe von Eigenschaften bzw. Parametern, die letztendlich die Fitness bestimmen. Die Einheiten, die diese Parameter repräsentieren, werden Gene genannt. Ein Gen kann verschiedene Werte annehmen, welche man als Allele bezeichnet. Als Chromosomen bezeichnet man im Allgemeinen die Gesamtheit aller Gene eines Individuums.

³ Ebenda, S. 9

⁴ Ebenda, S. 11

⁵ Ebenda, S. 9

⁶ vgl. [GERKLAKRU], S. 2

5

1.2.2. Evolutionsstrategien

In den sechziger Jahren des zwanzigsten Jahrhunderts wurde von deutschen Wissenschaftlern versucht, die Evolutionstheorie auch für Suchalgorithmen auszunutzen. I. Rechenberg und H.-P. Schwefel erarbeiteten dabei eine Variante Evolutionärer Algorithmen, die sie Evolutionsstrategien nannten.

Ausgangspunkt bei den ES ist eine Population mit µ Individuen, wobei die Gene ausschließlich reelle Werte annehmen. Aus dieser Startpopulation werden λ Kinder durch Rekombination und anschließender Mutation (unter Beachtung der Mutationsschrittweiten) erzeugt, aus welchen im Anschluß µ neue Eltern selektiert werden, die dann die Startpopulation ersetzen. Dieser Prozess wird solange fortgeführt, bis ein Abbruchkriterium erfüllt ist. Man wird feststellen, dass bei ES die Mutation der wichtigste genetische Operator ist, da jedes neue Individuum mit dessen Hilfe erzeugt wird. Mit ES wurden in ihren Einsatzgebieten sehr gute Ergebnisse erzielt, doch sie sind leider nicht so universell einsetzbar wie Genetische Algorithmen. Auch neigen sie eher als GA dazu vorzeitig in lokalen Optima „steckenzubleiben“, weshalb heutzutage häufiger mit Genetischen Algorithmen als mit Evolutionsstrategien gearbeitet wird. 7

1.2.3. Genetische Algorithmen

Um die Entwicklung einer Population von Lösungen eines Ausgangsproblems überhaupt simulieren zu können, müssen die Lösungen zunächst in geeigneter Form dargestellt werden. Man spricht hier von der Form der Kodierung, die zu wählen ist. Letztlich muss es möglich sein, mit der gewählten Repräsentation jede denkbare Lösung des Problems darstellen zu können. Ursprünglich wurde bei Genetischen Algorithmen ausschließlich die binäre Kodierung verwendet, d.h. Gruppen von Bits repräsentieren dabei jeweils ein bestimmtes Merkmal der Lösung. Heute werden jedoch zunehmend auch andere Kodierungsformen, wie reelle Zahlen oder Permutationsfolgen verwendet, da diese oftmals besser auf das Optimierungsproblem zugeschnitten und leichter verständlich sind. Nach der Wahl einer geeigneten Kodierung muss noch definiert werden, was als Fitness der Individuen betrachtet wird. Üblicherweise ist dies eine Funktion, die von allen kodierten Parametern abhängig ist. Das Ziel des GA ist es nun, für diese Funktion ein

⁷ vgl. [NISS94], S.140ff.

6

möglichst globales Maximum der Fitness-Funktion zu bestimmen und somit das Individuum zu finden, das die beste Lösung für das Ausgangsproblem darstellt.

1.2.4. Genetische Programmierung

Die Genetische Programmierung (GP), eine Variante der Genetischen Algorithmen mit einer besonderen Form der Lösungsrepräsentation, ist ein evolutionärer Ansatz, um automatisch ein Computerprogramm zu generieren, welches eine vorgegebene Aufgabenstellung erfolgreich bearbeitet. Als Lösung erhält man dabei ein allgemeines Programm, das auf eine betrachtete Klasse von Problemstellungen anwendbar ist. „Anders ausgedrückt untersuchte man, ob Computerprogramme, die eine gegebene Aufgabenstellung lösen können, sich nicht auch rein automatisch generieren lassen. Diese frühen Versuche hatten nur bescheidenen Erfolg, nicht zuletzt, weil noch keine hinreichend leistungsfähigen Computer verfügbar waren.“ 8

Mögliche Anwendungen der GP sind das Lernen von Bool´schen Ausdrücken, das Lösen von Gleichungssystemen oder die Bestimmung von Zufallszahlen. Die Startpopulation besteht dabei aus einer Menge von Computerprogrammen, die zufällig aus vorab festgelegten Mengen problemangepasster elementarer Funktionen sowie passender Variablen und Konstanten generiert werden. Die Fitness eines Individuums sagt aus, wie gut das jeweilige Programm die gestellte Aufgabe löst. J.R. Koza erzielte unter Verwendung der Programmiersprache LISP sehr gute Erfolge mit Genetischer Programmierung. 9

⁸ [NISS97], S.111

⁹ vgl. [NISS94], S.89ff.

7