2.1 Erste Arbeiten zu Evolutionären Algorithmen

Viele der frühen Arbeiten zur Verwendung von Prinzipien der Evolution in Suchalgorithmen waren biologisch motiviert. Das Ziel dieser Untersuchungen war das Verständnis natürlicher Phänomene. Beispiele dafür sind in [Fra62], [Ros67] und [Wei70] zu finden. Eine weitere Gruppe von Arbeiten untersuchte verschiedene Evolutionäre Algorithmen und wendete diese auf Testbeispiele an, wie z.B. [Bre62], [Bag67] und [Hol71]. Ein Teil der frühen Arbeiten beschäftigte sich bereits mit der Lösung praktischer Probleme ([Box57] und [Cav70]; [FOW66]: siehe Abschnitt 2.2; [Sch68] und [Rec73]: siehe Abschnitt 2.3). Einen frühen Versuch der Generierung von Computerprogrammen stellten die Arbeiten in [Fri58] und [FDN59] dar. In diesem Abschnitt werden die frühen Arbeiten kurz vorgestellt und auf ihre wesentlichen Bestandteile eingegangen.

Fraser ([Fra62]) untersuchte die Abhängigkeiten zwischen einzelnen Genen und die Auswirkungen auf den Phänotyp. Dabei wurde eine Population von Individuen verwendet, die als Bitstring kodiert waren. Die Individuen zur Produktion der folgenden Generation (Eltern) wurden in Abhängigkeit vom Phänotyps (Zielfunktionswert) aus dieser Population ausgewählt. Dieser Phänotyp mußte in einem bestimmten Intervall liegen. Mittels dieser Simulationen ermittelte Fraser den Anteil akzeptabler Individuen in folgenden Generationen. Bei Fraser findet sich allerdings kein Hinweis, daß sein natürliches Suchverfahren auch auf technische Probleme anwendbar sei.

Rosenberg ([Ros67]) veröffentlichte seine Dissertation 1967. Er betonte mehr den biologischen Aspekt und die Simulationen, so daß die Dinge, die heute als Evolutionärer Algorithmus gesehen werden, weniger Beachtung fanden. Rosenberg verwendete eine Population einzelliger Organismen, die eine einfache Biochemie und die klassische genetische Struktur (1 Gen, 1 Enzym) besaßen. Außerdem war jedes Individuum als Chromosomenpaar (diploide Variablenstruktur) kodiert. Paarung und Selektion wurden entsprechend einer Fitneßfunktion durchgeführt. Obwohl Rosenberg mehrere Fitneßwerte berechnete, wurde immer nur einer dieser Werte für die Selektion verwendet. Weiterhin benutzte Rosenberg einen adaptiven Rekombinationsoperator. Eine Betrachtung der Effekte der diploiden Kodierung (Dominanz, Rezessivität) als separate Effekte fand aber nicht statt. Dominanz war nur ein Merkmal in Abhängigkeit von internen Variablen, das nachfolgend die Ausbildung eines anderen Merkmals kontrollierte.

Weinberg ([Wei70]) benutzte genetische Algorithmen, um die Parameter eines biologischen Simulationsmodells (Simulation von E. coli - Zellen) zu optimieren. Sein Modell hatte 15 Parameter, die in einem großen Bereich veränderbar waren. Der genetische Algorithmus arbeitete direkt mit den reellen Variablen. Rekombination und Inversion kamen zur Anwendung. Zur Mutation wurde ein Operator verwendet, den er als directed mutation bezeichnete. Außerdem beschreibt Weinberg die Verwendung eines zweistufigen genetischen Algorithmus. Die untere Stufe (adaptive genetic program) dient der Optimierung der Parameter des Problems, die obere Stufe (non-adaptive genetic program) optimiert die Parameter des genetischen Algorithmus auf der unteren Stufe. Die Verbesserung in der Güte des besten Individuums auf der unteren Stufe diente jeweils als Güte eines Parametersatzes (Rekombinations-, Inversions- und Mutationswahrscheinlichkeit) auf der oberen Stufe. Dadurch sollte eine schrittweise Adaption der Parameter des genetischen Algorithmus der unteren Stufe erreicht werden. Weinberg präsentierte in seiner Arbeit allerdings keine Ergebnisse mit diesem mehrstufigen genetischen Algorithmus.

Bremermann ([Bre62]) berichtete in seiner Arbeit von der Generierung von Populationen. Die Populationen bestanden aus binär bzw. reell kodierten Individuen. Durch Selektion wurden Eltern ausgewählt. Aus diesen wurden durch Mutation neue Individuen gebildet, wobei immer eine diskrete Mutation verwendet wurde (starke Orientierung an der diskreten Darstellung der genetischen Information in der Natur). Von Bremermann wurde auch die Verwendung eines Rekombinationsoperators vorgeschlagen. Unter anderem schlug er vor, mehrere Nachkommen pro Elter zu generieren und die besten dieser Nachkommen durch eine Rekombination auf ein einzelnes Individuum zu reduzieren. Bremermann verwendete für seine Experimente einfache lineare und konvexe Funktionen. Die experimentellen Ergebnisse waren nicht sehr erfolgreich und konnten nur durch die Einbeziehung speziellen Wissens verbessert werden.

In seiner Dissertation erwähnte Bagley ([Bag67]) als Erster den Begriff ,,Genetischer Algorithmus" und veröffentlichte auch dessen erste Anwendung. Bagley konstruierte einen genetischen Algorithmus, der alle Bestandteile heute verwendeter Algorithmen beinhaltete: Selektion, Reproduktion, Rekombination und Mutation. Dabei verwendete er eine diploide und nicht-binäre Repräsentation für seine Individuen. Die diploiden Chromosomen wurden durch variable Dominanzparameter, die Teil der Repräsentation waren, in einen Phänotyp umgewandelt. Dies erlaubte die Anpassung des Dominanzschemas über die Generationen. Da keine Mutation in den Dominanzparametern zugelassen wurde, kam es aber zu einer schnellen Fixierung dieser Werte. Es fand kein Vergleich mit einer haploiden Repräsentation statt. In der Selektion benutzte Bagley eine variable Fitneßzuweisung. Zu Beginn der Berechnungen wurde der Selektionsdruck verringert, wodurch verhindert werden sollte, daß wenige gute Individuen sehr schnell die Population dominieren. Im Verlauf der Berechnungen wurde der Selektionsdruck erhöht, um den Wettbewerb zwischen den immer ähnlicher werdenden Individuen zu erhalten. Bagley wendete den GA in der Spieltheorie auf ein 3x3 Damespiel an und verglich die Ergebnisse mit anderen, damals gebräuchlichen Ansätzen. Der GA funktionierte dabei gut über eine große Breite von Problemen.

Hollstien ([Hol71]) untersuchte in seiner Dissertation die Anwendung genetischer Algorithmen zur Optimierung einer Anzahl von Funktionen, die je von zwei Variablen abhängig waren. Das spezielle Augenmerk galt der Untersuchung verschiedener Selektionsverfahren sowie dem Test verschiedener Schemata, welche Individuen miteinander Nachkommen erzeugen können (mating schemes). Am Ende waren fünf Selektionsverfahren und acht mating schemes an 14 Testfunktionen zu untersuchen. Hollstien verwendete Populationen mit 16 Individuen, deren Variablen binär- oder gray-kodiert waren. Am Ende wurden einige Kombinationen der Verfahren als am robustesten ermittelt. Außerdem wurde festgestellt, daß die gray-kodierten Individuen bessere Ergebnisse lieferten als die binär-kodierten. Die verwendeten Populationen stellten sich als zu klein heraus, es wurde die Verwendung größerer Populationen empfohlen. Hollstien untersuchte außerdem Diploidie mit einem sich entwickelnden Dominanzmechanismus. Dafür führte er neben den binären Variablen 0 und 1 eine dritte Variable 2 ein. Dadurch änderte sich die Bedeutung der Werte der Variablen. Die 1 wurde zu einer rezessiven 1 und die 2 zu einer dominanten 1. Nur die 0 blieb 0. Damit werden zwei der drei Variablen, 1 und 2, zu einer 1, aber die 2 ist dominant über eine 0, während die 0 dominant über eine 1 ist. Dies wird auch als dreialleliges Schema {0, 1, 2} bezeichnet. Nach der Anwendung eines Dominanzschemas bleiben nur noch die binären Variablen 0 und 1. Eines der diploiden Schemata von Hollstien hatte bei Simulationen eine höhere Diversität in der Population als das haploide Schema. Ansonsten wurden jedoch keine signifikanten Verbesserungen berichtet.

Die Arbeit von Box ([Box57]) stellt einen der frühen Fälle dar, bei dem der Begriff evolutionary zur Charakterisierung des benutzten Verfahrens verwendet wurde. Box beschrieb ein Verfahren zur Durchführung von Experimenten, die von einem aktuellen Arbeitspunkt ausgehen. Um den Arbeitspunkt wurde ein Hyperwürfel gelegt, entsprechend der Anzahl der Parameter. Die Ecken dieses Hyperwürfels wurden systematisch bewertet. Wenn eine deutliche Verbesserung gefunden wurde, so konnte ein neuer Arbeitspunkt festgelegt und ein neuer Hyperwürfel erstellt werden. Mit einem Evolutionären Algorithmus hat dieses Verfahren aber nur wenig gemeinsam, auch wenn Box schreibt, daß die Veränderungen als Mutationen angesehen werden können und die Auswahl eines besseren Punktes als Selektion. Das Verfahren von Box erinnert eher an einen Simplex-Algorithmus und sollte auch in dieser Richtung eingeordnet werden.

Cavicchio ([Cav70]) wendete einen genetischen Algorithmus auf die Entwicklung eines Sets von Detektoren zur Mustererkennung (hier zur Erkennung von Buchstaben) an. Dadurch wurde, im Gegensatz zur direkten Mustererkennung, das Problem der Buchstabenerkennung auf den Entwurf eines Sets von Detektoren reduziert. Cavicchio verwendete in seinem genetischen Algorithmus Selektion, Crossover und Mutation. Verschiedene Selektionsverfahren wurden getestet und am Ende eines verwendet, so daß gute Individuen bevorzugt wurden. Gleichzeitig verhinderte das Verfahren, daß die guten Individuen zu viele Nachkommen erzeugen. Der Crossoveroperator ist ein single-point crossover, wobei sichergestellt wurde, daß nur zwischen Blöcken gekreuzt werden konnte (und nicht an jeder Stelle). Drei verschiedene Mutationsoperatoren wurden verwendet, die auf Grund der komplexen Repräsentation der Individuen notwendig waren. Außerdem wurden inversion (Umkehrung), two-point crossover und duplication (Vervielfachung) verwendet. Cavicchio unternahm den Versuch der automatischen Anpassung der Parameter seines Algorithmus. Die Parameter waren aber nicht Teil des Algorithmus selbst, sondern wurden von außen in Abhängigkeit der globalen Verbesserung verändert. Es konnten deutliche Vorteile des adaptiven genetischen Algorithmus gegenüber einem einfachen genetischen Algorithmus sowie einem anderen adaptiven Algorithmus und einer Zufallssuche, die zum Vergleich herangezogen wurden, gezeigt werden.

Ein sehr früher Versuch zur Generierung von Computerprogrammen wurde von Friedberg ([Fri58], [FDN59]) unternommen. Friedberg verwendete eine binäre Kodierung. Neue Programme wurden durch Austausch von Instruktionen sowie die zufällige Veränderung von Instruktionen erzeugt. Die erzeugten Computerprogramme sollten einfache Aufgaben lösen. Von Friedberg wurde eine Erfolgszahl (success number) eingeführt, die angab, wie gut eine Instruktion in vorherigen Tests war. Die Mutationswahrscheinlichkeit einer Instruktion hing von dieser Erfolgszahl ab; je kleiner der Erfolg, um so größer war die Mutationswahrscheinlichkeit. Erfolgreiche Instruktionen wurden dadurch seltener mutiert. Der Ansatz von Friedberg hatte zwei Hauptprobleme: Es fehlte ein ausreichender Selektionsdruck, und die verwendete Methode der Bewertung der Computerprogramme führte zu einer stark nichtkontinuierlichen Zielfunktion. Um das erste Problem des fehlenden Selektionsdruckes zu lösen, wurde vorgeschlagen, mehrere Programme auf der Grundlage eines Programmes durch Austausch von Instruktionen und zufällige Veränderung von Instruktionen zu generieren und das beste dieser Programme als Startpunkt für den nächsten Schritt zu verwenden. Diese Variante konnte wegen Beschränkungen der vorhandenen Rechentechnik aber nicht getestet werden.

Eine der ersten Veröffentlichungen der erfolgreichen Anwendung Evolutionärer Algorithmen zur Generierung und Optimierung strukturierter Lösungen und damit ein Vorläufer der Genetischen Programmierung stammt von Forsyth [For81]. Er beschrieb das Computerprogramm BEAGLE zur Erstellung von Entscheidungsregeln. Die Regeln wurden als binäre Bäume kodiert, auf die Mutation und Rekombination angewendet wurden. Zwischen den Individuen (den Regeln) fand eine natürliche Auslese statt. Die Regeln wurden entsprechend ihrer Kategorisierungsgüte sortiert (ranking) und nachfolgend die Nachkommen produziert. Die besten 25% der Individuen überlebten unverändert, die nächsten 25% wurden durch Mutation vergrößert, die nächsten 25% durch Mutation verkleinert und die letzten 25% wurden aus den besten 25% durch Rekombination neu gebildet. Mit diesem System konnte Forsyth sehr gute Ergebnisse für einige Klassifikationsprobleme erzielen, die sich nachfolgend durch ihre Verständlichkeit einfach anwenden ließen.

Neben den hier aufgeführten Arbeiten gab es einzelne weitere Veröffentlichungen. Tiefergehende Besprechungen weiterer früher Arbeiten finden sich u.a. in [Gol89], S.89-104, [Sch81], S.100-103, [Bäc96], S.57-60 und [Fdb95], S.67-75.

Diese Dokument ist Teil der Dissertation von Hartmut Pohlheim "Entwicklung und systemtechnische Anwendung Evolutionärer Algorithmen". This document is part of the .
The is not free.
© Hartmut Pohlheim, All Rights Reserved, (hartmut@pohlheim.com).