8.2 Ausblick
8.2 Ausblick |
|
Die heute verwendeten Evolutionären Algorithmen, eingeschlossen die in dieser Arbeit vorgestellten, die Verwendung von Populationsmodellen und deren Erweiterungen, sind im Vergleich zu den Vorgängen in der Natur immer noch stark vereinfacht. Dies betrifft verschiedene Aspekte:
Als Ausblick sollen einige dieser Aspekte untersucht und auf ihre Relevanz für die weitere Entwicklung Evolutionärer Algorithmen hin bewertet werden. Dabei muß beachtet werden, daß Merkmale, Eigenschaften und Abläufe, die sich an einer Stelle entwickelt haben, meist mit denen auf einer oder mehreren anderen Ebenen in Zusammenhang stehen, auch wenn dies nicht für jedes der Beispiele extra betont wird.
Die Art der Kodierung der genetischen Information ist eine Frage, die im Bereich der Evolutionären Algorithmen mit jedem neuen Problem aufs neue zur Diskussion steht. In der Natur hat sich eine Variante etabliert. Die genetische Erbinformation liegt in Chromosomensätzen vor. Jeder Chromosomensatz besteht aus einer (für die jeweilige Art charakteristischen) Anzahl von Chromosomen. Die Chromosomen sind Träger der Gene. Die Gene wiederum lassen sich Teilen bzw. Abschnitten der DNS zuordnen. Die DNS besteht von den bestimmenden Komponenten her aus einer Sequenz von 4 verschiedenen Basen, wobei immer drei aufeinanderfolgende Basen eine Aminosäure kodieren. Von den theoretisch möglichen 64 Aminosäuren werden allerdings nur 20 verschiedene Aminosäuren benutzt. Mit diesen in der Grundlage einfachen Mitteln lassen sich die verschiedensten Informationen kodieren und speichern. Stark vereinfacht könnte man sagen, daß die Information durch Sequenzen der Zahlen 1, 2, 3 und 4 gespeichert wird. Oder, wenn man die Aminosäuren als Grundlage verwendet, aus einer Sequenz der ganzzahligen Ziffern 1 bis 20. Komplexere Strukturen, wie z.B. ein größerer Bereich der zur Kodierung verwendeten Symbole oder eine komplexere Struktur als die Sequenz haben sich im Prinzip nicht herausgebildet bzw. durchgesetzt. Die Grundlage der Kodierung und Speicherung der Erbinformation bleiben einfachste Varianten; komplexere Strukturen entstehen erst durch die Interpretation bzw. Umsetzung des einfachen genetischen Kodes.
Damit in direktem Zusammenhang stehen die Fragen, wie der genetische Kode interpretiert wird bzw. wie die genetische Information in phänotypische Merkmale umgesetzt wird. Wie oben schon angedeutet, hat sich dafür in der Natur ein teilweise mehrstufiges System herausgebildet. An der Ausbildung eines phänotypischen Merkmals sind meist mehrere Gene beteiligt und die Wechselwirkungen dabei variieren auf den verschiedensten Ebenen. Deshalb ist es nicht so einfach, einem Merkmal eine bestimmte Gensequenz bzw. einen Abschnitt des genetischen Kodes zuzuordnen. Rückschlüsse von einer Veränderung der genetischen Information auf die folgende Veränderung von phänotypischen Merkmalen sind bisher nur in wenigen Fällen möglich (z.B., wenn nur ein Gen die Ausprägung eines Merkmals bestimmt und/bzw. nur wenige Zustände dieses Merkmals möglich sind).
Welche Überlegungen ergeben sich für die Anwendung bei Evolutionären Algorithmen? Mit einer einfachen Kodierung lassen sich die verschiedensten Informationen darstellen. Die Komplexität liegt dann in der Interpretation der einfachen Information und ihrer Ausbildung in entsprechende Merkmale. Der Zusammenhang zwischen genetischer Information und den Merkmalen ist um so schwerer zu interpretieren, je komplexer die Interaktionen der genetischen Information zur Ausbildung der Merkmale werden.
Im Sinne einer einfachen Kodierung ist die binäre Kodierung nicht zu übertreffen. Es gibt nur 2 Zustände jeder einzelnen Einheit. Dies sind weniger, als die 4 Zustände (4 Basen) in der Natur. Der Ansatz, alle Informationen binär zu kodieren, wurde in den frühen Arbeiten der Genetischen Algorithmen propagiert und wird auch heute noch an vielen Stellen verwendet. Der Vorteil ist, daß dieselben Operatoren für jedes Problem verwendet werden können, egal wie komplex die Umwandlung der genetischen Information in Merkmale ist. Der große Nachteil ist gerade dieser sehr komplex werdende Zusammenhang bei großen und komplizierten Problemen.
Die andere Variante stellen Evolutionäre Algorithmen dar, bei denen die genetische Information direkt im Format der Merkmale gespeichert wird. Allerdings müssen für diese merkmalsspezifischen Formate entsprechende Operatoren entwickelt werden. Diese Operatoren lassen sich dann nur für die Manipulation dieses einen Formates einsetzen. Beispiele dafür sind die in dieser Arbeit vorgestellten Rekombinations- und Mutationsoperatoren für reelle Variablen und die Operatoren, die auf Baumstrukturen anwendbar sind, wie sie im Bereich der Genetischen Programmierung verwendet werden.
Zwischen diesen beiden Extremen, Speicherung der genetischen Information in binären Variablen und Speicherung der genetischen Information im Format der Merkmale, gibt es noch eine Reihe von Zwischenstufen, bei denen eine teilweise Umsetzung zwischen den Formaten stattfindet. Diese Zwischenstufen werden im Moment bei Evolutionären Algorithmen nur selten eingesetzt.
Welche Variante der Kodierung im Endeffekt bei der Bearbeitung eines Problems angewendet wird, hängt sehr stark von der Art des Problems und der Zielstellung der Bearbeitung ab. Bei der Optimierung von Systemen nach einer Zielfunktion hat sich die Anwendung merkmalsspezifischer Formate für die Kodierung der Informationen an vielen Stellen durchgesetzt. Durch die stärkere Spezialisierung und Fokussierung dieser Kodierung und der korrespondierenden Operatoren sowie das indirekte Einbringen von problemspezifischem Wissen über die Struktur und Interaktion der Variablen konnten bessere Ergebnisse (Ergebnisse in kürzerer Zeit oder mit einem geringeren Aufwand) erreicht werden. Beim Vergleich der Verwendung einer binären Kodierung und der direkten Verwendung der entsprechenden reellen Variablen wurden für die reelle Kodierung und deren Operatoren bessere Ergebnisse berichtet (u.a. [Mic94] und [Dav91]).
Wenn es dagegen um die Erzeugung einer großen Variabilität und möglichst vieler Formen geht, so ergeben sich mit einer einfachen Kodierung, wie der binären Kodierung, die meisten Möglichkeiten, die zudem mit einfachen und universell anwendbaren Operatoren bearbeitet werden können. Und genau diese Variante scheint sich in der Natur durchgesetzt zu haben. Dort geht es ja auch nicht um die ,,Lösung einer einfachen Optimierungsaufgabe".
In direktem Zusammenhang mit der eben besprochenen Kodierung der genetischen Information steht die Frage der Ploidie der Information. Bisher wurde davon ausgegangen, daß die genetische Information in einfacher Form vorliegt, d.h. in einfachen Chromosomensätzen (haploid). Diploidie kennzeichnet den Zustand, daß die genetische Information in doppelter Ausführung vorliegt, bei Polyploidie ist die genetische Information noch öfter vorhanden (triploid, tetraploid, usw.).
In der Natur kommen alle diese Formen vor. Die meisten niederen Lebewesen sind haploid, die genetische Information liegt einfach vor. Aber so gut wie alle höheren Lebewesen haben einen diploiden oder polyploiden Chromosomensatz. Je komplexer die Organismen sind, um so komplexer ist die zugrundeliegende Struktur - und dies bedeutet insbesondere eine diploide oder polyploide Struktur.
Die bei diploiden Organismen in doppelter Ausführung vorliegende genetische Information ist in beiden Strängen nicht vollständig identisch. Die Frage ist, welcher Teil der doppelten Information zur Ausprägung gelangt. Sind die Bausteine für gleiche Stellen identisch (homozygote Allele), setzt sich diese Information durch. Bei unterschiedlicher Information auf den entsprechenden (homologen) Stellen eines Chromosoms (heterozygote Allele) wird durch einen Dominanzmechanismus entschieden, welche Information für die Ausprägung des Merkmals verwendet wird. Das sich durchsetzende Allel wird als dominant bezeichnet, das andere als rezessiv. Mit anderen Worten, das dominante Allel unterdrückt die Manifestierung des rezessiven Allels. Dieser Mechanismus muß nicht eindeutig sein, es kann auch eine ,,Mischung" zwischen den Informationen der beiden Allele stattfinden.
Daraus ergibt sich die Frage, welche Vorteile diese Vervielfachung der genetischen Information bringt, die auf den ersten Blick die Kodierung der genetischen Information nur noch komplizierter und komplexer macht.
Durch die Vervielfachung wird einmal mehr Information gespeichert. Die Erweiterung der Speicherkapazität ist aber nicht der Hauptaspekt (dies könnte auch durch eine Verlängerung der Information erfolgen). Statt dessen muß gesehen werden, daß die Information, die nicht zur Ausprägung kommt, damit auch nicht der Selektion unterliegt. Es wird ein Speicher von alternativen Informationen gebildet. Erst durch eine Veränderung des Dominanzmechanismus kann diese Information zur Ausprägung kommen und unterliegt dann auch der Selektion. Die zusätzliche Information stellt ein Reservoir dar.
Unter anderen Umständen bzw. in der Vergangenheit kann bzw. konnte diese Information einmal von Vorteil sein (verteilter Langzeitspeicher). Dies bedeutet die Speicherung mehrerer Lösungen, wobei zu einer Zeit immer nur eine dieser Lösungen zur Ausprägung gelangt. Und da die nicht ausgeprägten Lösungen nicht direkt der Selektion unterliegen, werden sie im Speicher vor einer Zerstörung bewahrt. Von Zeit zu Zeit kann an die alten Lösungen ,,erinnert", d.h. diese können unter den neuen Umständen getestet werden.
Fast alle heute verwendeten Evolutionären Algorithmen verwenden eine haploide Darstellung der Information. Die Anzahl der Arbeiten, die eine diploide oder polyploide Implementierung vorstellen, läßt sich noch gut überschauen. Auf einige dieser Arbeiten soll im folgenden kurz eingegangen werden.
Einige der frühen Arbeiten zu Evolutionären Algorithmen benutzten schon eine diploide Darstellung der Informationen. Daran ist unter anderem zu erkennen, wie stark sich frühe Arbeiten am biologischen Vorbild orientierten. Dies betrifft die Arbeiten von Bagley [Bag67] Rosenberg [Ros67], Hollstien [Hol71] und Brindle [Bri81]. Auf diese Arbeiten, auch den Aspekt der diploiden Darstellung der Information, wurde bereits in Kapitel 2.1, ab S., eingegangen. Zusammenfassend kann gesagt werden, daß die Ergebnisse dieser Arbeiten nicht sehr ermutigend waren. Es konnte in den Experimenten kein direkter Vorteil der Verwendung eines diploiden Algorithmus gegenüber einem haploiden Algorithmus gefunden werden. Dies lag vor allem daran, daß mit stationären Zielfunktionen gearbeitet wurde. Der durch die diploide Darstellung vorhandene Speicher vergangener Lösungen konnte mit diesen Zielfunktionen keine Vorteile erbringen. Im Gegenteil, durch die diploide Darstellung der Information wurde eine komplexere Interpretation der genetischen Information in den Algorithmus eingeführt, die zu einer langsameren Entwicklung des Systems führte.
Das von Hollstien [Hol71] eingeführte dreiallelige (triallelic) Schema, bei dem die binäre genetische Information und die Dominanzinformation an jeder Position direkt kodiert wurden, war über viele Jahre hinweg Grundlage weiterer Arbeiten, u.a. auch von Holland in [Hol75].
Goldberg und Smith veröffentlichten in [GS87], [Smi87], [Smi88] und [Gol89] Vergleiche zwischen haploiden und diploiden Genetischen Algorithmen. Die diploiden Algorithmen unterschieden sich in der Art des Dominanzschemas (fixiertes Dominanzschema bzw. das Schema von Hollstien und Holland). Als Testfunktion verwendeten sie eine nicht-stationäre Funktion (blind non-stationary knapsack). Diese Funktion oszillierte mit einer bestimmten Frequenz. Mit den von ihnen verwendeten Parametern des Genetischen Algorithmus war der haploide Algorithmus nicht in der Lage, den Oszillationen zu folgen, der diploide Algorithmus mit fixiertem Dominanzschema konnte den Oszillationen etwas folgen. Aber nur bei Verwendung des dreialleligen Schemas konnte eine schnelle und volle Adaption erreicht werden.
In (NW95( wurde gezeigt, daß die Ergebnisse von Goldberg und Smith in [GS87] nur durch die Wahl ungünstiger Parameter für das haploide Schema zustande kamen. Das dreiallelige Schema hatte keine Vorteile gegenüber dem haploiden Schema, wenn andere Oszillationsfrequenzen der Zielfunktion bzw. höhere Mutationsraten verwendet wurden. In (NW95( wurde ein neues diploides Schema zur Kodierung vorgeschlagen. Außerdem wurde ein drastischer Dominanzwechsel durchgeführt, wenn der Zielfunktionswert eines Individuums sich plötzlich stark verschlechterte. Das neue diploide Schema läßt sich auch auf Variablen anwenden, die mehr als zwei Zustände eines Merkmals haben.
Ryan berichtet in [Rya96] über ein neues diploides Schema, das sich auf Variablen mit 2 und mehr Zuständen ausdehnen läßt und keinen Bias (Bevorzugung) in Richtung eines der Zustände hat. Für binäre Variablen nannte er es `Degree of Oneness', für Variablen mit mehr als 2 Zuständen `Degree of Nness'. Zusätzlich untersuchte er die Verwendung mehrerer diploider Variablen (mehrerer Gene) zur Kodierung eines Merkmals (polygenic inheritance). In seinen Untersuchungen mit einer einfachen nicht-stationären Funktion erzielte diese Variante die besten Ergebnisse.
Ein in verschiedenen Arbeiten immer wieder betonter Aspekt der Anwendung eines diploiden Schemas ist die Erhaltung oder Erhöhung der Verschiedenartigkeit der Individuen der Population (population diversity) (u.a. [CCR96]). In (YA94( wurde ein pseudo-Meiosis GA vorgestellt, der zwei unterschiedliche Chromosomen miteinander zur Erstellung eines Phänotyps kombiniert. Dieser Algorithmus wurde auf ein nicht-stationäres travelling salesman Problem angewendet. In Vergleichen mit einem einfachen Genetischen Algorithmus war der pseudo-Meiosis GA besser. Es wurden nicht nur kürzere Touren gefunden, sondern nach einer Änderung der Zielfunktion konnte die Adaption schneller durchgeführt werden. Die Verschiedenartigkeit in der Population war während des Laufs, insbesondere zum Ende hin, deutlich höher als mit dem einfachen Genetischen Algorithmus.
Lassen sich aus diesen Arbeiten Schlußfolgerungen ziehen, ob, wann und in welchen Bereichen die Anwendung der Diploidie Vorteile für Evolutionäre Algorithmen bringt? Zwei Bereiche wurden öfters erwähnt:
Die Erhaltung der Verschiedenartigkeit der Population ist eine immer wieder aufgestellte Forderung und wird auch durch verschiedene andere Methoden gefördert. Hingewiesen sei nur auf die Anwendung verschiedener Populationsmodelle, die in Kapitel 4, ab S., vorgestellt wurden.
Interessant wird die Erhaltung der Verschiedenartigkeit der Population durch Diploidie allerdings im Zusammenhang mit einer sich verändernden Zielfunktion. Die Verschiedenartigkeit beinhaltet dann nicht nur verschiedene Varianten, sondern insbesondere Varianten, die unter anderen Bedingungen der Zielfunktion schon einmal erfolgreich waren. Durch Diploidie wird in der Population ein Speicher vergangener Lösungen bewahrt, der von Zeit zu Zeit wieder getestet wird. Diese Information muß nicht erst durch Mutation neu erzeugt, sondern nur neu kombiniert bzw. getestet werden. Allerdings sind die meisten heute verwendeten Probleme bzw. Zielfunktionen stationäre Funktionen, ein Speicher vergangener Lösungen bringt damit nur in wenigen Fällen einen Vorteil.
Ein weiterer Aspekt der vervielfachten Information ist die erhöhte Stabilität der Information. Eine Mutation in einem haploiden Chromosom kommt zur Ausprägung. Eine Mutation in einem diploiden Chromosom muß nicht zur Ausprägung gelangen, insbesondere, wenn rezessive Allele verändert werden. Diese Veränderungen können im Verborgenen bleiben und beeinflussen nicht den Phänotyp. In der Natur ist diese erhöhte Stabilität ein wichtiger Aspekt, da gute Informationen nicht durch die ständig stattfindenden Mutationen wieder zerstört werden sollen.
In den künstlichen Welten heutiger Evolutionärer Algorithmen, die beschränkte Populationen, stationäre Zielfunktionen und eine geringe Anzahl von Generationen benutzen, ist kein Bereich erkennbar, in dem ein diploides oder polyploides System einen Vorteil gegenüber einem vernünftig entworfenen haploiden System bringt. Mit der weiteren Entwicklung Evolutionärer Algorithmen werden aber schrittweise immer größere Probleme bearbeitet. Bei diesen können mehrere Zielfunktionen gleichzeitig zum Einsatz kommen; die Entwicklung des Systems verläuft über eine wesentlich längere Zeit und die Populationen sind deutlich größer. In diesen neuen Umgebungen sollte der Einsatz diploider Systeme in Betracht gezogen werden, da dann die Vorteile dieser Systeme gegenüber haploiden Systemen besser zur Wirkung kommen können.
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).