next up previous contents
Nächste Seite: Selektionsschemata Aufwärts: Fazit Vorherige Seite: Fazit   Inhalt

Verhalten von Crossover-Operatoren bei steigenden und großen Populationen

Als Fortführung der oben gewonnenen Erkenntnisse wurde das Verhalten von Crossover-Operatoren bei steigenden und großen Populationszahlen untersucht. Als Ansatzpunkt diente dabei die Vermutung, dass bei steigender Populationsgröße geringere Disruptionseffekte benötigt würden.

Aus diesem Grund wurden die Crossover-Operatoren N-Point 3 und N-Point 5 als Vertreter geringer Disruption und Randomwalk 10 als Vertreter mittlerer Disruption untersucht. Tabelle 5.11 zeigt eine erste Zusammenfassung der ermittelten Ergebnisse über alle Populationsgrößen hinweg. Es zeigt sich, dass hier genau eine Umkehrung des bei kleinen Populationen beobachteten Trends vorliegt. Je mehr Kreuzungspunkte vorhanden sind, desto schlechter ist das durchschnittlich gefundene Energieniveau.


Tabelle: Vergleich von Crossover-Operatoren mit unterschiedlicher Anzahl an Kreuzungspunkten für Populationsgrößen 500-5000 mit dem Steady State Algorithmus.
XOvTyp # XOvP N $\varnothing$ En. $\sigma$ Min Max nEvals $\vert$Z$\vert$
  3 192 15,27 1,90 9,97 20,14 713506
N-Point
RndWlk $\approx$10 192 17,65 1,20 15,38 20,32 740508  

XOvTyp:Crossover-Typ (RndWlk=Randomwalk); 

# XOvP:Anzahl Kreuzungspunkte;
N:Anzahl Beobachtungen; tex2html_wrap_inline$$ En.:Mittelwert der Energie;
Min:Minimaler Mittelwert; Max:Maximaler Mittelwert;
tex2html_wrap_inline$$:Standardabweichung des Mittelwerts;
nEvals:Durchschnittliche Anzahl benötigter Evaluationen;
tex2html_wrap_inline$|$Ztex2html_wrap_inline$|$:Fehlerwahrscheinlichkeit bei Annahme der Hypothese auf
Ungleichheit der Distributionen;



\begin{sidewaystable}
% latex2html id marker 3098\begin{center}
\renewedcomman...
... der Randomwalk Distributionen;
\par\end{tabbing}\end{center}\end{sidewaystable}

Eine genauere Unterteilung in verschiedene Populationsgrößen (Tabelle 5.12) klärt die Zusammenhänge. Deutlich zu erkennen ist, dass bei steigenden Populationsgrößen die größere Disruption durch mehr Kreuzungspunkte einen eindeutig negativen Effekt hat. Die Randomwalk Distribution mit durchschnittlich 10 Kreuzungspunkten erzielt hier immer schlechtere Ergebnisse als die beiden N-Point Distributionen. Die Hypothese, dass die N-Point 3 und N-Point 5 Distributionen für Populationsgrößen von 500 und 1000 ungleich sind, kann aufgrund zu großer Fehlerwahrscheinlichkeit nicht bestätigt werden. Jedoch wird der bei den Populationsgrößen 500 und 1000 sichtbare Trend, dass N-Point 3 besser ist als N-Point 5, bei den Populationsgrößen 2000 und 5000 durch entsprechend geringe Fehlerwahrscheinlichkeiten bei der Überprüfung der Ungleichheitshypothese der Distributionen vollständig bestätigt.


\begin{sidewaystable}
% latex2html id marker 3166\begin{center}
\renewedcomman...
... der Randomwalk Distributionen;}\par\end{tabbing}\end{center}\end{sidewaystable}

Einer weiteren Aufteilung unter Einbeziehung der Mutationsrate bestätigt sowohl Ergebnisse aus der Beurteilung der Mutationsrate allein (siehe Abschnitt 5.6), als auch Ergebnisse aus der Analyse der Crossover-Operatoren bei einer Populationsgröße von 100 Individuen (Tabelle 5.10). Die in Tabelle 5.13 aufgelisteten Werte weisen die kombinierten Merkmale beider Einflussfaktoren auf: bis zu einer Populationsgröße von 1000 einschließlich liegt die Randomwalk Distribution mit ca. 10 Kreuzungspunkten immer nachweisbar schlechter als die beiden N-Point Distributionen, in beiden Mutationsmodi. Dem entgegen können die Distributionen von N-Point 3 und N-Point 5 sowohl bei einer Mutationsrate von 0,001 als auch bei einer Rate von 0,01 nicht als unterschiedlich angesehen werden. Ab einer Populationsgröße von 2000 Individuen sind alle Distributionen untereinander verschieden. Der in Abschnitt 5.6 schon nachgewiesene schwindende Einfluss der Mutationsrate bei steigenden Populationsgrößen und die relativ geringe Anzahl an Werten - je 24 aus jeweils 8 gemittelten Tests - machen genauere Angaben über die Interaktion von Mutationsrate und Anzahl der Kreuzungspunkte allerdings nicht mehr möglich.


next up previous contents
Nächste Seite: Selektionsschemata Aufwärts: Fazit Vorherige Seite: Fazit   Inhalt
2001-07-08