Kurs:Genetische Algorithmen/Kapitel 8

Dieses Kapitel gehoert zum Kurs Genetische Algorithmen des Fachbereichs Informatik.

Übersicht:

In diesem Kapitel schauen wir uns mögliche Verbesserungen für genetische Algorithmen an. Insbesondere betrachten wir die Möglichkeit, die Varianz und die Bevölkerungsgrösse zu steuern. Wir zeigen, unter welchen Umständen Anpassungen sinnvoll sein können und was sie für Auswirkungen haben.

Lernziele

• Sie wissen, dass es verschiedene Möglichkeiten gibt, die Leistung eines genetischen Algorithmus' zu verbessern.
• Sie wissen, dass Sie über die Steuerung der Varianz eine bessere Konvergenz erreichen können.
• Sie wissen, dass Sie über die Steuerung der Bevölkerungsgrösse eine bessere Konvergenz erreichen können.

Fortgeschrittene Themen

Die genetischen Algorithmen, wie sie hier vorgestellt wurden, sind nicht der Weisheit letzten Schluss. Je nach Problemstellung sind eine Vielzahl Verbesserungen möglich oder sogar nötig, um den Algorithmus in der Praxis brauchbar zu machen. Im Folgenden werden ein paar Ansätze gezeigt, mit denen die Konvergenz genetischer Algorithmen verbessert werden kann.

Definition:

Als Konvergenz bezeichnen wir die Geschwindigkeit, mit der die Lösungen besser werden. Bei guter Konvergenz werden die Lösungen schneller besser als bei schlechter Konvergenz.

Varianzsteuerung

Bis jetzt war in allen Beispielen die Varianz (sprich das Maß der Veränderung) bei jeder Mutation oder Rekombination für alle Parameter einer Lösung konstant.

Definition:

Als Varianz bezeichnen wir das Maß der Veränderung einer Variablen. Man spricht auch über die Streuung einer Variablen. Allgemein bezeichnet die Varianz die erwartete Abweichung vom Mittelwert einer Variablen und berechnet sich für $n$ Variablen $x_{i}$, $i=1\dots n$ mit dem Mittelwert ${\bar {x}}$ aus

${\sqrt {\frac {\sum _{i=1}^{n}(x_{i}-{\bar {x}})}{n-1}}}.$

Beim Problem des Handelsreisenden wurden alle Städte mit der gleichen Wahrscheinlichkeit vertauscht. Beim Damenproblem wurden alle Damen mit gleicher Wahrscheinlichkeit verschoben und beim Klassifikationsproblem wurden schließlich beide Unbekannten nicht nur mit gleicher Wahrscheinlichket verändert, sondern auch immer um den gleichen Betrag.

Bei der Diskussion der Mutation haben wir stets betont, dass es wichtig ist, dass Mutationsoperatoren wirklich zufällig agieren um zu gewährleisten, dass die Menge aller möglichen Lösungen möglichst gut abgetastet wird. Es ergibt aber wenig Sinn, bei einer Unbekannten einer Lösungen immer wieder große Änderungen zu machen, wenn diese immer wieder scheitern. Analog dazu ergibt es wenig Sinn, bei einer Variablen, die maßgeblich zur Verbesserung der Lösung trägt, nur in sehr kleinen Schritten Veränderungen zu erproben.

Definition:

Bei der Varianzsteuerung versuchen wir, das Maß der Veränderung für jede Unbekannte individuell oder als Ganzes so zu wählen, dass sich Variablen, bei denen große Veränderungen zu besseren Lösungen führen, mehr verändern als Variablen, bei denen große Veränderungen zu schlechteren Lösungen führen.

Wie aber erkennen wir, ob bei einer Unbekannte viel Veränderung gut ist oder nicht? Wir schauen uns als Beispiel die Zielfunktion

$f(a,b)=|a|+5b^{2}$

an. Wie wir von Hand errechen oder von Auge sehen können (vgl.~Abbildung~\ref{fig:f}), ist diese Funktion bei ($a=0$, $b=0$) minimal.

   \begin{figure}
       \centerline{\epsfig{file=plotoutfile.eps,width=0.6\linewidth,angle=-90}}
       \caption{Graphische Darstellung der Zielfunktion $f(a,b)=|a|+5b^{2}$.}
       \label{fig:f}
   \end{figure}

Wir fangen bei einem Punkt ($a=10$, $b=10$) an und lassen einen genetischen Algorithmus laufen, der als Mutationoperator die Werte $a$ und $b$ um 0.5 erhöht oder verkleinert. Nach ein Paar wenigen Schritten sind die Meisten Lösungen um den Punkt ($a=10$, $b=0$) zentriert, sozusagen in der Talsole von $f(a,b)$. Dies ruht daher, dass die Zielfunktion auf Änderungen in $b$ viel stärker reagiert als auf Änderungen in $a$ und sich die Lösungen mit $b$ näher bei null schneller durchsetzen, unabhängig vom Wert von $a$. Die Streuung der Werte von $b$ in der Bevölkerung wird entsprechend klein sein, denn Werte, die zu weit von null abweichen, würden eine zu hohe Zielfunktion ergeben und scheiden aus. Umgekehehrt ist die Streuung der Werte von $a$ in der Bevölkerung groß, da Unterschiede in $a$ nur unwesentlich zur Lösung beitragen.

Anstatt bei der Mutation die Werte immer um 0.5 zu erhöhen oder verkleinern, können wir sie um die Streuung oder die Standardabweichung der Werte vergrößern oder verkleinern. Seien $b_{i}$, $i=1\dots n$ die Werte von $b$ in der Bevölkerung von $n$ Lösungen, und ${\overline {b}}$ der Mittelwert dieser $b$, so mutieren wir $b$ wie folgt:

$b_{\mathsf {neu}}=b_{\mathsf {alt}}\pm {\sqrt {\sum _{i=1}^{n}{\frac {(b_{i}-{\overline {b}})^{2}}{n-1}}}}$

Sind die Werte von $b$ also weit verstreut, so werden große Schritte gemacht. Liegen sie hingegen eng beeinander, werden nur kleine Schritte gemacht.

Genetische Algorithmen/Kapitel 8

Bevölkerungsgrösse

Bis jetzt haben wir in allen Beispielen die Grösse der Bevölkerung sowie die Anzahl neuer Lösungen durch Mutation und Rekombination ohne Begründung angegeben. Diese Grössen haben aber einen sehr grossen Einfluss auf das Verhalten unseres genetischen Algorithmus. Im Folgenden schauen wir uns ein paar Grössenkombinationen an und diskutieren, was sie für Auswirkungen auf unseren genetischen Algorithmus haben.

Eine relativ kleine Bevölkerung, verglichen mit der Anzahl Lösungen, welche durch Mutation und Rekombination erzeugt werden, hat zur Folge, dass der Selektionsoperator mehr Lösungen verwerfen muss. Dadurch erhöht sich der Selektionsdruck auf die Bevölkerung und suboptimale Lösungen haben eine kleinere Wahrscheinlichkeit die Selektion zu überleben. Diese Strategie kann kurzfristig schnell zu besseren Lösungen führen. Der Nachteil ist jedoch, dass die Selektion mit kleiner werdender Bevölkerungsrösse zunehmend elitär wird. Was dies zur Folge haben kann haben wir schon im Kapitel zu den Selektionsoperatoren gesehen.

Ist die Bevölkerung gross verglichen mit der Anzahl Lösungen, die durch Mutation und Rekombination erzeugt werden, so muss die Selektion pro Generation nur wenige Lösungen eliminieren. Der verminderte Selektionsdruck hat einerseits zur Folge, dass weniger gute Lösungen eine kleinere Wahrscheinlichkeit haben, aus der Bevölkerung zu scheiden. Die Breite der Lösungen, die somit in Betracht gezogen werden, wird grösser und es können ungeahnt gute Lösungen entstehen. Der Nachteil eines solchen Ansatzes ist, dass die Lösungen sich nur sehr langsam entwickeln.

Beispiel:

Wir können uns diesen Selektionsdruck bei unseren Hasen so vorstellen, dass die Bevölkerungsgrösse der Wölfe schwankt. Sind mehr Wölfe vorhanden, so überleben nur die allerbesten Hasen, welche sich dann sehr einseitig spezialisieren -- d.h.~es überleben nur Mutationen und Rekombinationen die sofort zu ``besseren Hasen führen. Sind weniger Wölfe vorhanden, können sich immer exotischere Varianten fortpflanzen und überleben, und damit neue Strategien für das Problem des Nichtgefressenwerdens entwickeln.

Die zwei Varianten -- relativ kleine bzw.~relativ grosse Bevölkerung -- sind je nach Situation sinvoll oder nicht. Ist in einer Bevölkerung eine grosse Bandbreite an Lösungen vorhanden und es entstehen schnell immer bessere Lösungen, so können wir uns eine hartere Selektion, und somit eine kleinere Bevölkerung, leisten (vgl.~Abbildung~\ref{fig:f2}a). Ist in einer Bevölkerung jedoch keine grosse Bandbreite an Lösungen vorhanden, so muss man mehr in die Breite suchen und müssen dafür den Selektionsdruck verringern und können deswegen die Bevölkerung vergrössern (vgl.~Abbildung~\ref{fig:f2}b).

Um zu entscheiden, in welcher dieser beiden Situation unser Algorithmus gerade steckt, können wir die Entwicklung der Lösungen von Generation zu Generation anschauen. Wurden in den letzten paar Generationenen die Lösungen stets besser, so können wir davon ausgehen, dass wir in einem steilen Bereich der Zielfunktion stehen. Wurden umgekehrt in den letzten paar Generationen keine wesentlichen Verbesserunen festgestellt, so befindet man sich in einem flacheren Bereich der Zielfunktion, wo dann die Breite erhöht werden muss.

Je nach Situation ist eine strengere oder laschere Selektion von Vorteil. Bei $a$ ist die Zielfunktion $f(x)$ steil und es werden somit schnell bessere Lösungen gefunden. Bei $b$ stehen mehrere unterschiedliche Minima nebeneinander, weswegen an dieser Stelle eine grössere Bandbreite von Lösungen probiert werden sollte.

In der Praxis wird oft als Kompromiss die Bevölkerungsgrösse nach diesem Schema von Generation zu Generation angepasst.