Diskussion der Ergebnisse

Abb. 5.1 und Abb. 5.2 zeigen eine grafische Gegenüberstellung des Simple Genetic Algorithm und des Steady State Algorithm. Der erste Eindruck vermittelt eine weitgehende Gleichheit der Ergebnisse bei fast allen Parametereinstellungen. Als sehr deutlicher Unterschied jedoch sind beim Simple GA regelmäßig wiederkehrende Piks zu erkennen, welche beim Steady State nicht oder nur sehr undeutlich ausgeprägt sind. Die Regelmäßigkeit ist auf die Parameterkonstellation ``scaling none'' und ``selection rss'' bzw. ``selection rms'' zurückzuführen. Hier treffen genau die Faktoren zusammen, welche proportionale Selektionsschemata ungünstig erscheinen lassen: die ungehemmte Selektion eines Superindividuums führt in vielen Fällen zu einer verfrühten Konvergenz, wobei durch diesen Takeover zu viele potentiell gute Building-Blocks anderer Individuen vernichtet werden und der Genetische Algorithmus in einem Suboptimum stecken bleibt. Weitere Einzelheiten zu diesem Thema werden in den Abschnitten über Selektion (5.8) und Skalierung (5.9) besprochen.

Abbildung: Simple GA Energiewerte: Ersetzungsgröße- 0,1:0,5:0,9 (840); Mutationsrate - 0,001:0,01 (420). Ergebnisse aus Basisuntersuchung 1.

Abbildung: Steady State GA Energiewerte: Ersetzungsgröße - 0,1:0,5:0,9 (840); Mutationsrate - 0,001:0,01 (420). Ergebnisse aus Basisuntersuchung 1.

Interessant dabei ist, dass der Steady State Algorithmus je nach Mutationsrate diese Übernahmen abschwächt oder sogar fast komplett verhindern kann (Abb. 5.1 und Abb. 5.2). Die charakteristischen Piks sind bei genauer Betrachtung für die Mutationsrate von 0,001 noch als solche zu erkennen, für eine Mutationsrate von 0,01 hingegen kaum noch. Diese Beobachtung läßt sich auch theoretisch durch das Zusammenspiel von Steady State GA und hoher Mutation bei Superindividuen erklären: taucht ein solches Individuum auf, so wird es fast komplett die gesamten Nachkommen für die nächste Generation produzieren. Bei einer durchschnittlichen Mutation von 2,4 Bit pro Genom ist jedoch zu erwarten, dass ein Teil der Nachkommen schlechter sein wird als die schon in der Population vorhandenen Individuen. Letztere werden bei einem Simple GA bedingungslos ersetzt, bei einem Steady State GA jedoch nur, wenn sie schlechter sind als die Nachkommen. Deshalb werden beim Steady State GA immer einige Individuen mit einem wesentlich anderen Genom als das des Superindividuums noch in die nächste Generation hinübergerettet. Dies verzögert die Konvergenz und verhindert eine vollständige Übernahme einer Population innerhalb nur einer Generation. Damit bleibt der Genpool über längere Zeit variabel, womit auch die Suche in andere Richtungen als die des Superindividuums nicht aufgegeben wird.

Um noch bessere Vergleichsmöglichkeiten zu erhalten, können die oben genannten schlechten Kombinationen ausgeblendet und beide Algorithmen dann verglichen werden. Tabelle 5.1 zeigt die Ergebnisse eines Wilcoxon 2-Stichprobentests für diese gesäuberten Parameterkombinationen beider Algorithmen.

Tabelle 5.1: Vergleich von Steady State Algorithm und Simple GA unter Auslassung der Ergebnisse bei proportionaler Selektion ohne Skalierung.

Algorithmus	N	$\varnothing$ En.	$\sigma$	Min	Max	nEvals	$\vert$Z$\vert$
Simple	2280	25,02	3,68	14,79	39,07	31601
Steady State	2280	24,83	3,90	15,99	39,30	25609	0,0082

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 beiden Distributionen

Tab. 5.1 ist zu entnehmen, dass der Hypothesentest auf Ungleichheit der Ergebnisdistributionen bei einer Fehlerwahrscheinlichkeit von unter 1% als richtig angenommen wird. Dies bedeutet, dass - aufgrund des besseren Mittelwerts - der Steady State Algorithmus auch unter Auslassung von für den Simple GA ungünstiger Parameterkombinationen besser ist als der Simple Genetic Algorithm. Bemerkenswert hierbei ist, dass die Zahl der notwendigen Evaluationen beim Steady State Algorithmus um fast 19% niedriger als beim Simple Genetic Algorithm liegt. Einen visuellen Vergleich der benötigten Evaluationen liefern die Abbildungen 5.3 und 5.4.

Abbildung: Anzahl Evaluationen Simple GA: Ersetzungsgröße - 0,1:0,5:0,9 (840); Mutationsrate - 0,001:0,01 (420)

Abbildung: Anzahl Evaluationen Steady State GA: Ersetzungsgröße - 0,1:0,5:0,9 (840); Mutationsrate - 0,001:0,01 (420)

Um eine weitere Aufschlüsselung eventueller Gemeinsamkeiten und Unterschiede zu erhalten, können verschiedene Parameter gruppiert dargestellt werden. Dies geschieht in den Tabellen 5.2 und 5.3, welche die Ergebnisse nach Ersetzungsgröße und Mutation bzw. nach Selektionsschemata gruppiert zeigen. Die Ergebnisse sind insofern erstaunlich, als sie eine Ungleichheit beider Algorithmen über weite Teile der Parameterkombinationen nicht bestätigen können, da diese Hypothesen wegen zu großen Fehlerwahrscheinlichkeiten meist abgelehnt werden müssen.

Tabelle: Vergleich von Steady State GA und Simple GA unter Berücksichtigung der Ersetzungsgröße und der Mutationsrate.

pRepl	pMut	GA	N	$\varnothing$ En.	$\sigma$	Min	Max	nEvals	$\vert$Z$\vert$
		SI	380	29,22	3,06	21,06	39,07	11749
		SI	380	27,09	2,44	20,36	35,68	21283
		SI	380	26,80	2,15	20,98	33,20	33762

pRepl:Populationsersetzungsgröße; pMut:Mutationswahrscheinlichkeit; 

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

Min:Minimaler Mittelwert; Max:Maximaler Mittelwert; 

GA:Genetischer Algorithmus: SI=SImple GA, SS=Steady State GA; 

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 beiden Distributionen;

Tabelle 5.3: Vergleich von Steady State GA und Simple GA unter Berücksichtigung der Selektionsschemas.

Selekt	GA	N	$\varnothing$ En.	$\sigma$	Min	Max	nEvals	$\vert$Z$\vert$
	SGA	600	24,92	3,48	14,79	36,68	33063	rms

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

Min:Minimaler Mittelwert; Max:Maximaler Mittelwert; 

GA:Genetischer Algorithmus: SI=SImple GA, SS=Steady State GA; 

Selekt:Selektionsschema: rms=Roulette Multi Spin, rss=Roulette Single Spin; 

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 beiden Distributionen;

In Tabelle 5.2 wird gezeigt, dass nur bei einer Ersetzungsgröße von 0,9 und einer Mutationsrate von 0,01 eine Ungleichheit beider Distributionen angenommen werden kann. Eine Ungleichheit der Distributionen für eine Ersetzungsgröße von 0,9 und einer Mutation von 0,001 wird hingegen schon knapp abgelehnt. Alle Hypothesen auf Ungleichheit anderer Kombinationen von Ersetzungsgröße und Mutation werden deutlich abgelehnt. Tabelle 5.3 zeigt, dass auch die Crossover Parameter unter beiden Algorithmen weitgehend gleich arbeiten. Nur der Uniform Crossover wird beim Hypothesentest auf Ungleichheit der Distributionen nicht abgelehnt. Somit arbeitet dieser Operator mit dem Steady State Algorithm besser zusammen als mit dem Simple Genetic Algorithm.

Auch in diesen beiden Tabellen ist die Anzahl der durchschnittlich notwendigen Evaluationen beim Simple Genetic Algorithm immer - zumeist sogar deutlich - höher als beim Steady State Algorithm. Dies und die weiter oben genannten Erkenntnisse lassen sich folgendermaßen zusammenfassen: Ein Steady State Ersetzungsalgorithmus wird zumindest gleich gute Ergebnisse erzielen wie ein Simple Genetic Algorithmus, in den meisten Fällen sogar bessere. Auch wird ein Steady State GA für diese Ergebnisse weniger Evaluationen brauchen als ein Simple GA und kann somit als effektiver angesehen werden.