Verhalten von Crossover-Operatoren bei kleinen Populationen

Wie in den Abschnitten 5.3 und 5.6 bereits aufgezeigt wurde, sind kleine Populationsgrößen in Hinsicht auf Exploration stärker auf disruptive Aspekte von GA Operatoren angewiesen als große Populationen. In der ersten Basisuntersuchung wurden aus diesem Grund auch die beiden völlig entgegengesetzten Ansätze des minimalen und maximalen Crossovers untersucht. Als Vertreter des minimalen Ansatzes kann dabei der N-Point Crossover mit 1 bis 5 Kreuzungspunkten angesehen werden. Für den maximalen Ansatz wurde der Uniform Crossover mit bis zu 240 (Genomlänge in Bit) Kreuzungspunkten gewählt. Für eine mittlere Anzahl an Kreuzungspunkten wurde der Randomwalk mit ca. 10 und 20 Punkten eingesetzt.

Tabelle 5.9: Vergleich von Crossover-Operatoren bei verschiedenen Mutationsraten. Populationsgröße 100. Werte stammen aus dem Steady State Algorithmus, sind jedoch für den Simple GA repräsentativ.

pMut	XOvTyp	N	$\varnothing$ En.	$\sigma$	Min	Max	nEvals	$\vert$Z$\vert$
	N-Point	504	28,73	3,04	21,07	40,55	15398	0,001
	N-Point	504	21,95	1,92	16,01	28,80	37945	0,01

pMut:Mutationswahrscheinlichkeit; 

N:Anzahl Beobachtungen; tex2html_wrap_inline$$ En.:Mittelwert der Energie; 

Min:Minimaler Mittelwert; Max:Maximaler Mittelwert; 

XOvTyp:Crossover-Typ (RndWlk=Randomwalk); 

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;

Tabelle 5.9 gibt einen ersten Überblick über die Ergebnisse mit einer Populationsgröße von 100 Individuen. Wie der Spalte mit den Fehlerwahrscheinlichkeiten zu entnehmen ist, sind bei dieser Betrachtungsweise die Ergebnisdistributionen aller Operatoren in ihrer Leistungsfähigkeit nicht sehr weit voneinander entfernt. Bei der schwachen Mutationsrate von 0,001 unterscheiden sich zwar die Verteilungen so deutlich, dass Randomwalk und Uniform eindeutig besser sind als N-Point, doch bei einer höheren Mutationsrate muss die Hypothese auf unterschiedliche Distributionen - wenn auch nur knapp - abgelehnt werden.

Diese Werte lassen jedoch die unterschiedliche Anzahl von Kreuzungspunkten - also den disruptiven Effekt - in der Untersuchung vollkommen unberücksichtigt. In Tabelle 5.10 erfolgt deshalb eine weitere Differenzierung der Crossover-Operatoren.

Tabelle 5.10: Vergleich von Crossover-Operatoren unter Berücksichtigung der Zahl von Kreuzungspunkten bei verschiedenen Mutationsraten. Steady State Algorithmus mit kleinen Populationen (100 Individuen), ist für den Simple GA repräsentativ.

pMut	XOvTyp	# XOvP	N	$\varnothing$ En.	$\sigma$	Min	Max	nEvals
		1	126	30,45	2,69	24,89	37,62	17159

pMutMutationswahrscheinlichkeit;# XOvPAnzahl Kreuzungspunkte;


NAnzahl Beobachtungen;$\varnothing$ En.Mittelwert der Energie;


MinMinimaler Mittelwert;MaxMaximaler Mittelwert;


XOvTypCrossover-Typ (RndWlk=Randomwalk);

$\sigma$Standardabweichung des Mittelwerts;


nEvalsDurchschnittliche Anzahl benötigter Evaluationen;

$\vert$Z$\vert$Fehlerwahrscheinlichkeit bei Annahme der Hypothese auf


Ungleichheit der Distributionen;

Hier zeigt sich ein deutlicher Einfluss der Anzahl der Kreuzungspunkte. Der N-Point Crossover mit nur 1 Punkt ist allgemein bei Molekülstrukturoptimierung mit kleinen Populationen immer schlechter als mit mehreren Kreuzungspunkten. Interessanterweise sind die Distributionen für N-Point Crossover bei 1, 2, 3 und 5 Kreuzungspunkten alle verschieden, bei steigender Anzahl an Kreuzungspunkten sinkt der durchschnittlich gefundene Energiewert. Dies ist bei einer Mutationsrate von 0,001 sehr deutlich ausgeprägt, bei einer Rate von 0,01 ist es immerhin noch quantifizierbar. Dies erhärtet die Aussage, dass bei kleinen Populationsgrößen stärkere Disruption erwünscht ist.

Ein weiteres Indiz für die Richtigkeit dieser Aussage geben die Werte für Randomwalk mit einer durchschnittlichen Anzahl von 10 bzw. 20 Kreuzungspunkten. Im Ergebnis sind die durchschnittlich gefundenen Energiewerte denen des N-Point Crossovers entweder überlegen (bei einer Mutationsrate von 0,001) oder zumindest gleichwertig (bei einer Mutationsrate von 0,01).

Wie bei den Uniform-Operatoren dargestellt, bewirkt dann aber eine zu starke Disruption wieder einen Abfall der Effizienz im Verhalten der Genetischen Algorithmen. Die Erklärung hierfür liegt in der Tatsache, dass Building-Blocks bei diesem Operator kaum jemals komplett vererbt werden. Dadurch wird die Rekombinationshäufigkeit dieser Blöcke drastisch herabgesetzt und somit die Leistung des GA gemindert. Dass trotzdem noch ``akzeptable'' Ergebnisse erzielt werden, spricht für die These, dass die Building-Block-Hypothese allein noch nicht den Erfolg von GAen erklären kann.

Als bemerkenswerte Tatsache am Rande sei noch auf die Anzahl der benötigten Evaluationen hingewiesen. Beim N-Point Crossover sinkt die Zahl der Evaluationen beständig mit der Zunahme der Kreuzungspunkte bzw. der Verminderung des durchschnittlich gefundenen Energiewertes. Wird dies unter Berücksichtigung der Werte für Random Crossover extrapoliert, so kann die Hypothese aufgestellt werden, dass es eine feste Anzahl an Kreuzungspunkten geben muss, bei welcher die durchschnittlichen Energiewerte nicht mehr weiter verbessert werden, aber die Zahl der Evaluationen bei mehr Kreuzungspunkten trotzdem auf demselben Niveau konstant bleibt. Bei der Mutationsrate von 0,01 muss diese Zahl an Kreuzungspunkten zwischen 4 und 5 liegen, da die Anzahl der Evaluationen von N-Point 3 nach N-Point 5 sinkt, aber dann für Randomwalk 10 und Randomwalk 20 konstant geblieben ist. Auch der Uniform Crossover mit durchschnittlich 120 Kreuzungspunkten braucht ungefähr genauso viele Evaluationen, wenn auch mit einem schlechteren Ergebnis. Bei Uniform Crossover mit ca. 180 Punkten sinkt dann die Zahl der Evaluationen noch einmal bei vergleichbaren Werten in den gefundenen Energieminima.