next up previous contents
Nächste Seite: Messy Genetic Algorithms Aufwärts: Genetische Algorithmen (GA) Vorherige Seite: Genetische Algorithmen (GA)   Inhalt


Allgemeine Definition eines genetischen Algorithmus

Der Begriff des ,,genetischen Algorithmus``, kurz als ,,GA`` bezeichnet, wurde von HOLLAND [33] eingeführt. Er definierte ein Verfahren zur Lösung von Optimierungsproblemen unter Verwendung eines Dekodierschemas, das die möglichen Lösungen des Problems als binäre Sequenzen darstellt:

Die möglichen Lösungen $x$ eines gegebenen Problems seien durch Bitsequenzen einer festen Länge $k$ aus der Menge $\{0,1\}^k$ aller binären Sequenzen dieser Länge kodiert. Der genetische Algorithmus agiert auf einer sich in der Zeit $t$ entwickelnden Population $B_M(t)$ einer konstanten Anzahl von $M$ Bitsequenzen $\{x_1,\dots,x_M\}$. Das Testen einer bestimmten Lösung $x_i$ liefert eine Bewertung $f(x_i)$ (als ,,Fitness`` der Lösung zu interpretieren), die zum Mittelwert $\overline{f}(t)$ über die gesamte Population beiträgt. Pro Zeitschritt wird eine vorgegebene Zahl $n \le M/2$ von Paaren von Sequenzen als ,,Eltern`` für die nächste Generation ausgewählt, wobei die Wahrscheinlichkeit $p(x_i)$ für die Wahl eines Individuums proportional zur relativen Bewertung $f(x_i)/\overline{f}(t)$ ist. Während der Replikation dieser Individuen werden Änderungen des genetischen Inhalts durchgeführt. Diese Veränderungen werden durch Anwendung der genetischen Operatoren ,,Crossover`` und/oder ,,Mutation`` bewirkt. Die dadurch erzeugten neuen Bitsequenzen ersetzen im nachfolgenden Zeitschritt die jeweils $2n$ Individuen mit der schlechtesten Bewertung.

Der Operator ,,Crossover`` benötigt zwei Originalsequenzen $x_1$ und $x_2$ und erzeugt daraus zwei neue Sequenzen $x_3$ und $x_4$ nach dem folgenden Verfahren: Eine Zufallszahl $i \in \{1, \dots, k-1\}$ bestimmt die Position in beiden Sequenzen, an der sie auseinandergeschnitten werden. Der erste Teil $A$ von $x_1$ wird mit dem zweiten Teil $D$ von $x_2$ zur neuen Sequenz $x_3$ und der zweite Teil $B$ von $x_1$ mit dem ersten Teil $C$ von $x_2$ zu $x_4$ verbunden. In Abbildung 4 wird dieser Sachverhalt verdeutlicht.

Abbildung: ,,Crossover``-Operator
\begin{figure}
\vspace{1.0cm}
\begin{center}
\unitlength=0.50mm
\special{em:line...
...,120.00){\framebox (70.00,10.00)[cc]{$B$}}
\end{picture}\end{center}\end{figure}

Der Operator ,,Mutation`` setzt den Wert eines zufällig ausgewählten Bits in einer Sequenz auf dessen Komplement, d.h. ein sogenannter ,,bit flip`` $0 \rightarrow 1$ bzw. $1 \rightarrow 0$ findet statt.

Zusammenfassend läßt sich dieser genetische Algorithmus wie folgt darstellen:

  1. Eine zufällige Anfangspopulation von $M$ Bitsequenzen $\{x_1,\dots,x_M\}$ wird erzeugt.
  2. Das Ausmaß, mit dem eine Sequenz $x_i$ das Optimierungsproblem löst, liefert jeweils eine Bewertung $f(x_i)$. In Abhängigkeit von dieser Bewertung wird eine Wahrscheinlichkeit $p(x_i)$ definiert, mit der diese Sequenz in die nachfolgende Generation übernommen wird. Dabei werden insgesamt jeweils $m \le M$ Individuen pro Zeitschritt ausgewählt, deren Inhalt durch Anwendung von genetischen Operatoren verändert wird (Mutation).
  3. Die $m$ schlechtesten Individuen werden durch die neu erzeugten Sequenzen ersetzt. Die übrigen nicht veränderten Originale und die neu erzeugten Sequenzen bilden die Population im nachfolgenden Zeitschritt.

Dieses Verfahren wird bis zur vollzogenen Optimierung oder bis zum Erreichen eines vorgegebenen Zustands in der Nähe des Optimums wiederholt.

Ein so beschriebener genetischer Algorithmus erscheint geeignet für die Simulation von ALife-Systemen, da er einige Vorgänge der Evolution von natürlichen Systemen imitiert. Die Hierarchiestufen der Information müssen dabei aber zusätzlich definiert werden, denn der GA arbeitet nur auf der elementarsten Ebene, vergleichbar der Ebene von Makromolekülen in der Natur. Insbesondere sind ein Wechselwirkungsschema und die konkrete Bewertungsprozedur unabhängig vom GA festzulegen. Einige unnatürliche Eigenschaften des von HOLLAND definierten Originalalgorithmus sind die konstante Bitlänge und die fest vorgegebene Populationsgröße. Es wurde z.B. von EBELING [16] gezeigt, daß auch in einfachen Optimierungsprozessen für verschiedene Probleme eine jeweils vom Problem abhängige Populationsgröße optimal ist. In einer Population variabler Größe könnte sich nach Bedarf ein Optimum für diesen Wert einstellen. Genauere Detailinformationen zu diesem und anderen Aspekten der klassischen genetischen Algorithmen in der Anwendung bei Optimierungsprozessen sind in [30], [60] und [64] zu finden.


next up previous contents
Nächste Seite: Messy Genetic Algorithms Aufwärts: Genetische Algorithmen (GA) Vorherige Seite: Genetische Algorithmen (GA)   Inhalt
RW 2008-07-16