next up previous contents
Nächste Seite: Selbstentwickelte Evolutionsmodelle Aufwärts: Genetische Algorithmen (GA) Vorherige Seite: Allgemeine Definition eines genetischen   Inhalt


Messy Genetic Algorithms

Der Begriff ,,messy genetic algorithms`` (mGA) wurde von GOLDBERG et al. [29] erfunden. Er stellt eine spezielle Abwandlung des Original-Algorithmus von HOLLAND dar, in dem die Zahl der Bits in den einzelnen Sequenzen sowie die Populationsgröße variabel sind. Der Grund für die Einführung von mGA ist unter anderem in der Tatsache zu sehen, daß ein einfacher GA ein zu starres Gerüst für viele Optimierungsprobleme darstellt. In Analogie zur Natur, die von kurzen, einfachen Bausteinen (,,building blocks``) ausgehend komplexe Strukturen entwickelt hat, ist bei Anwendung von mGA diese Möglichkeit ebenfalls gegeben: Eine Simulation kann mit einer Initialisierung von kurzen Sequenzen beginnen und durch Anwenden von genetischen Operatoren komplexere spezialisierte Sequenzen erzeugen, die schon nahe an die Lösung des Problems heranreichen. Bei einer Initialisierung mit komplexen (langen) Sequenzen sind möglicherweise schon Zwänge in das System eingebaut, die das Aufsuchen des Optimums erschweren. GOLDBERG teilt aus diesem Grund die Simulation von mGA-Systemen in zwei Phasen auf:

  1. eine Anfangsphase, in der gute kurze Bausteine (,,building blocks``), d.h. überdurchschnittliche Sequenzen aus der Initialpopulation ausgewählt werden ohne Anwendung von anderen genetischen Operatoren, und

  2. eine Phase der Selektion und Veränderung der erzeugten Sequenzen durch Anwendung von ,,Cut and Splice`` und eventuell durch Punktmutationen.

Der Begriff ,,messy`` wird in GOLDBERGs Algorithmus im Sinne von ,,unordentlich`` verwendet, weil die einzelnen Bits einer Sequenz durch zwei Eigenschaften definiert werden: a) ihre Position innerhalb der Sequenz (die Nummer) und b) den Wert oder das Allel ($0$ oder $1$). Eine solche Sequenz läßt sich beispielsweise darstellen als $(1,0)(2,1)(3,1)(3,0)\dots$, wobei Bit $1$ den Wert $0$, Bit $2$ den Wert $1$ usw. hat. Im Gegensatz zu den einfachen genetischen Algorithmen wird hier das $k$-Bit-Problem nicht nur mit $k$-Bit-Sequenzen, sondern auch mit kürzeren oder längeren Sequenzen bearbeitet. Die variable Bitlänge der Gene erlaubt Über- und Unterspezifikationen der Sequenzen bezogen auf das gegebene Problem. Bei Überspezifikation der Sequenz (z.B. ist das Bit $3$ als $(3,1)$ und als $(3,0)$ in der obigen Sequenz vorhanden) wird der zuerst auftauchende Wert (also $1$ für Bit $3$ im obigen Bsp.) verwendet. Die Bewertung einer unterspezifizierten Sequenz erfolgt als Teilbewertung der Teilsequenz, die sie relativ zum Problem darstellt.

Die zeitliche Entwicklung in einer mGA-Population vollzieht sich analog zur Entwicklung im einfachen GA. Der Operator ,,Mutation`` läßt sich unverändert übernehmen, jedoch wird aus ,,Crossover`` nun ,,Cut and Splice`` (,,zerschneiden und zusammenkleben``). Dieser Operator, der Längenänderungen in den resultierenden Bitsequenzen ermöglicht, ist in Abbildung 5 dargestellt.

Abbildung: ,,Cut and Splice`` - Operator
\begin{figure}
\vspace{1.0cm}
\begin{center}
\unitlength=0.50mm
\special{em:line...
...){\makebox(0,0)[cc]{nach Cut and Splice:}}
\end{picture}\end{center}\end{figure}

Das Verlängern und Verkürzen von Bitsequenzen bei Anwendung von ,,Cut and Splice`` in einem Evolutions-System ermöglicht eine Anpassung der Population an ein gegebenes Optimierungsproblem. So können beispielsweise ,,überflüssige`` (d.h. zur Lösung nicht benötigte) Gene im Lauf der Zeit aus der Population verschwinden sowie andere, anfangs nicht vorhandene aber brauchbare Gene entstehen. Aus diesem Grund wird auch in der vorliegenden Arbeit in verschiedenen realisierten Modellen der Einfluß der Implementierung dieses Operators auf die Dynamik untersucht.


next up previous contents
Nächste Seite: Selbstentwickelte Evolutionsmodelle Aufwärts: Genetische Algorithmen (GA) Vorherige Seite: Allgemeine Definition eines genetischen   Inhalt
RW 2008-07-16