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;

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.

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.