Erweiterungen zu Genetischen Algorithmen

``Probability is a constant: Even if Murphy's Law doesn't work all the time, it is always a good excuse.``& &$\approx$ 120&189 & 28,14 & 3,04 & 22,16 & 38,17 & 14598
&Uniform:; SPMamp;tex2html_wrap_inline$$ 180&63 & 27,00 & 3,11 & 22,68 & 37,30 & 13974

& & 1 & 126 & 22,75 & 2,12 & 16,01 & 28,80 & 41444
& & 2 & 126 & 21,98 & 1,87 & 18,75 & 26,82 & 38773
& N-Point:; SPMamp; 3 & 126 & 21,74 & 1,73 & 18,07 & 27,36 & 36584
& & 5 & 126 & 21,34 & 1,67 & 17,81 & 28,42 & 34981 0
,01 & & tex2html_wrap_inline$$ 2-48 & 252 & 22,29 & 1,89 & 17,86 & 28,78 & 41635
& RndWlk&tex2html_wrap_inline$$ 10& 126 & 21,41 & 1,66 & 16,97 & 26,21 & 34920
& &tex2html_wrap_inline$$ 20& 126 & 21,40 & 1,60 & 17,56 & 27,63 & 34289 ;
SPMamp; &tex2html_wrap_inline$$ 120&189 & 22,26 & 1,84 & 15,99 & 28,50 & 35233
&Uniform:; SPMamp;tex2html_wrap_inline$$ 180&63 & 22,11 & 2,05 & 18,18 & 27,47 & 32346
tabbing ¯ ¯ ¯ ¯ pMut:Mutationswahrscheinlichkeit; # XOvP:Anzahl Kreuzungspunkte;
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;

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.