next up previous contents index
Next: Unterarten Up: Grundlagen genetischer Algorithmen Previous: Genetische Evolution   Contents   Index

Grundlagen evolutionärer Algorithmen (EA)

Evolutionäre Algorithmen arbeiten auf einer Menge (Population) von potentiellen Lösungen (Individuen), die das gegebene Problem mehr oder weniger gut lösen bzw. der optimalen Lösung mehr oder weniger nahe kommen. Von diesen Lösungen werden dann Neue geschaffen, indem einige bis alle zufällig verändert werden. Von allen (potentiellen) Lösungen, Neue und Alte, werden dann in einem Selektionsschritt einige gelöscht. Dabei haben weniger gute Lösungen eine höhere Wahrscheinlichkeit gelöscht zu werden. Dies führt im Allgemeinen dazu, dass die guten Lösungen eine höhere "Überlebenschance" (Fitness), also eine höhere Wahrscheinlichkeit, nicht gelöscht zu werden, haben und damit in der Menge bessere Lösungen zunehmen. Diesen Prozess der Veränderung und Selektion wird dann solange wiederholt, bis eine Endbedingung (Terminalkondition) zutrifft. Die Endbedingung ist meist: Eine bestimmte Anzahl von Durchläufen wurde ausgeführt oder/und eine Lösung überschreitet eine festgelegte Grenze (z. B. wenn die Lösung gut genug ist).


\begin{lstlisting}[ numbers=left, frame=single, caption={Allgemeiner Algorithmus...
... nicht geloescht zu werden
until (Terminalkondition erfuellt)
\end{lstlisting}

Im Listing 1 ist schematisch der allgemeine Algorithmus eines evolutionären Algorithmus in pseudo-C dargestellt.

Bei der Selektion von Individuen findet oft die weel-selection Anwendung. Dabei haben Lösungen/Individuen mit einer niedrigeren Fitness eine höhere Wahrscheinlichkeit, gelöscht zu werden. Der Name weel-selection hat seinen Ursprung darin, dass Wahrscheinlichkeiten für Individuen grafisch in einem Kreis angeordnet werden können (Individuen mit geringerer Fitness bekommen einen größeren Kreisausschnitt). Auf diesem Kreis (bzw. seinem Rand) wird bei der Selektion zufällig ein Punkt ausgewählt und das zugehörige Individuum gelöscht.


next up previous contents index
Next: Unterarten Up: Grundlagen genetischer Algorithmen Previous: Genetische Evolution   Contents   Index
Betti Österholz 2013-02-13