Information Technology Reference
In-Depth Information
Um diese Hypothese zu testen, wurden zwei erweiterte Versionen des verwendeten SA-Algo-
rithmus konstruiert, die zusätzlich zu der beschriebenen einfachen Version jeweils eine be-
stimmte Topologie des Lösungsraums enthalten. Die erste Topologie besteht einfach darin,
dass wie in 3.5 bereits angedeutet, „Nähe“ zweier Lösungen, d. h. Zusammensetzung der
Gruppen, über die Anzahl der vertauschten Elemente in den Vektoren definiert wird. Eine
Lösung, bei der in Relation zu einer Ausgangslösung nur eine Person vertauscht wird, ist der
ersten Lösung also näher als eine dritte Lösung, bei der zwei oder mehr Personen vertauscht
werden. Der entsprechende Auswahlalgorithmus im SA generiert demnach gezielt Lösungen,
die nicht mehr als einen Permutationsschritt von der Anfangslösung entfernt sind, und wählt
unter diesen per Zufall aus.
Bei der zweiten Version wird die oben erwähnte Matrix als Kriterium für „Nähe“ herangezo-
gen: Nach der Generation einer Anfangslösung wird in dieser Lösung per Zufall eine Person
ausgewählt. Anschließend berechnet das Programm die Person, deren Matrix-Werte mit denen
der ersten Person am meisten übereinstimmen. Dies geschieht durch Verwendung der Stan-
dardabweichung; ausgewählt wird demnach die Person, die die geringste Standardabweichung
in ihrer Matrix zur ersten Person hat. Das Austauschen dieser zweiten Person mit der ersten
ergibt dann die neue Lösung, mit der das SA wie üblich fort fährt. Eine neue Lösung ist dem-
nach der alten umso ähnlicher, also im Lösungsraum benachbarter, je mehr sich die ausge-
tauschten Personen in ihrer Matrix ähneln. Topologische „Nähe“ kann demnach bei derartigen
Problemen sehr unterschiedliche Sachverhalte repräsentieren; im ersten Fall wird eine rein
formale Definition angewandt, im zweiten Fall werden zusätzlich, ähnlich wie in der Physik,
„inhaltliche“ Kriterien für eine Definition topologischer Relationen verwendet.
Zwei typische Resultate werden in der folgenden Abbildung gezeigt:
Bild 3-14
Topologieänderungen beim SA
Zur Erläuterung muss angemerkt werden, dass in beiden Fällen die elitistischen Versionen des
GA und der ES verwendet wurden, was an der Glätte der Verlaufskurven auch zu erkennen ist.
Bei beiden Graphiken fällt sofort auf, dass nicht nur die Konvergenzkurve des SA deutlich
glatter ist als in der Version ohne Topologie, sondern dass vor allem die Optimierungswerte
des SA sich geradezu dramatisch verbessert haben. Während in der ursprünglichen Version das
SA nie die Werte des GA und der ES erreichte, übertreffen jetzt beide Versionen des SA die
Werte von GA und ES deutlich. Da bis auf die zusätzliche Einfügung einer Topologieversion
alles andere gleich blieb, muss demnach die Topologie die Verbesserung bewirkt haben. Die
erste topologische Version ist übrigens in allen Tests die beste, was das nächste Bild zeigt:
Search WWH ::
Custom Search