next up previous contents
Nächste Seite: Verhalten von Crossover-Operatoren bei Aufwärts: Universität Heidelberg/Fachhochschule Heilbronn Deutsches Vorherige Seite: Hillclimber   Inhalt

Fazit

In den vorangehenden sechs Kapiteln wurde das Untersuchungsgebiet ``Genetische Algorithmen zur Molekülstrukturoptimierung'' erörtert und in Bezug auf die gestellte Aufgabe vertieft. Altbekannte und neu entwickelte Operatoren für Genetische Algorithmen wurden in extensiven Testläufen untersucht und die praktisch ermittelten Ergebnisse unter Zuhilfenahme theoretischer Überlegungen bewertet. Zuletzt wurde ein genetischer Multipopulationsalgorithmus entwickelt, dessen Leistungsfähigkeit die von bekannten Einfachpopulationsalgorithmen übertrifft und Optima für ein gegebenes Molekül reproduzierbar ermittelt.

Neben vielen kleinen Teilergebnissen stehen vier wichtige Erkenntnisse als Fazit dieser umfassenden theoretischen und empirischen Untersuchungen:

  1. Wie auch schon von L. Altenberg in [1] dargestellt, können die zwei wichtigsten Fundamente der GA-Forschung - Hollands Schema-Theorem& 3 & 126 & 21,74 & 1,73 & 18,07 & 27,36 & 36584
    & & 5 & 126 & 21,34 & 1,67 & 17,81 & 28,42 & 34981
    0,01 & & $\approx$ 2-48 & 252 & 22,29 & 1,89 & 17,86 & 28,78 & 41635
    & RndWlk&$\approx$ 10& 126 & 21,41 & 1,66 & 16,97 & 26,21 & 34920
    & &$\approx$ 20& 126 & 21,40 & 1,60 & 17,56 & 27,63 & 34289
    & &$\approx$ 120&189 & 22,26 & 1,84 & 15,99 & 28,50 & 35233
    &Uniform&$\approx$ 180&63 & 22,11 & 2,05 & 18,18 & 27,47 & 32346
    
    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.



Unterabschnitte
next up previous contents
Nächste Seite: Verhalten von Crossover-Operatoren bei Aufwärts: Universität Heidelberg/Fachhochschule Heilbronn Deutsches Vorherige Seite: Hillclimber   Inhalt
2001-07-08