Die Modellierung adaptiver Prozesse durch Evolutionäre Algorithmen - Modellierung komplexer Prozesse durch naturanaloge Verfahren - page 87

Grund, andere Berechnungen zu verwenden, deren Nutzen für einen SA-Algorithmus nicht
erforscht ist. Hingewiesen werden muss jedoch darauf, dass die Standardformel zur Wahr-
scheinlichkeitsberechnung nicht notwendig eine monoton fallende Funktion ergibt, da der Wert
von 'E zumindest kurzfristig auch steigen kann. Mathematisch lässt sich jedoch leicht zeigen,
dass bei unendlich langsamer Absenkung der Temperatur immer das globale Minimum erreicht
wird. Bei der praktischen Simulation kann man allerdings solange nicht warten.
(3) In der Standardliteratur zu SA wird, wie wir es auch getan haben, eine topologische Struk-
tur des Lösungsraums gefordert, aufgrund derer man entscheiden kann, welche möglichen
Lösungen der anfänglich ausgewählten Lösung „benachbart“, also ähnlich sind (vgl. z. B. Sa-
lamon u. a. 2002). Dabei ist zu beachten, dass die Definition einer derartigen Nachbarschafts-
struktur unabhängig von der jeweiligen objective function erfolgen muss; Ähnlichkeit im Lö-
sungsraum ist demnach nicht zwingend eine Ähnlichkeit des Energieniveaus. Was eine derarti-
ge Ähnlichkeit bedeuten kann, kann man sich z. B. anhand von Permutationen einer Menge
klar machen: Nimmt man die sog. Grundmenge (1, 2, 3, 4, 5) als Anfangslösung für ein be-
stimmtes Problem (siehe unten Kapitel 3.6.4), dann ist eine Permutation P dieser Menge mit P
= (1, 2, 3, 5, 4) der Grundmenge sicher ähnlicher, also benachbarter, als eine Permutation P'
mit P' = (1, 3, 2, 5, 4), da im Falle von P nur eine Komponente verändert - mutiert - wurde und
im Falle von P' zwei. Ähnlichkeit wird hier also definiert als die Anzahl der Mutationsschritte,
die erforderlich sind, aus der Grundmenge die jeweilige Permutation zu erzeugen. Bei diesen Ope-
rationen handelt es sich übrigens um die beim GA erwähnte Inversion.
Nehmen wir nun z. B. das menschliche Genom, um wieder in die Biologie zu gehen, und be-
trachten zwei Genotypen, die sich lediglich in einem Gen unterscheiden. Man wird intuitiv
diese beiden Genotypen als „benachbart“ im Raum der Genotypen ansehen. Für die biologi-
sche Fitness der entsprechenden Phänotypen kann diese kleine Differenz jedoch dramatische
Unterschiede bedeuten. Der Sprachpsychologe Pinker (1995) berichtet beispielsweise von einer
Familie, bei deren Mitgliedern ein einziges Gen beschädigt war und die deswegen unfähig
waren, grammatisch korrekte Sätze zu bilden. Ihre (sozio-kulturelle) Fitness war demnach
drastisch eingeschränkt, obwohl ihre Genotypen nur marginal von den physisch in dieser Hin-
sicht normalen Menschen differierten. Ein menschlicher Genotyp enthält ca. 30.000 Gene, so
dass die Abweichung bei der entsprechenden Familie lediglich 0,03 Promille beträgt. Entspre-
chende Phänomene lassen sich in der Dynamik sozialer Gruppen beobachten, bei denen der
Austausch nur eines Mitglieds drastische Veränderungen in der Leistungsfähigkeit der jeweili-
gen Gruppen bewirken kann.
Es ist deshalb durchaus zu fragen, ob es für Optimierungsverfahren zwingend einer topologi-
schen Strukturierung des Lösungsraums bedarf. Es zeigt sich, dass es manchmal genügt, die
neuen Lösungen per Mutation oder entsprechenden Verfahren aus der Gesamtheit aller mögli-
chen Lösungen zu generieren. Wir werden unten ein Beispiel vorstellen, das ohne topologische
Strukturierung auskommt. Allerdings ist in den meisten Fällen zu empfehlen, eine topologische
Strukturierung des Lösungsraums vorzunehmen. Die mathematischen Gründe dafür werden wir
unten in 3.5.4 anhand eines Vergleichs der drei etablierten Optimierungsalgorithmen behan-
deln, nämlich GA, ES und SA.
(4) Bei einem Vergleich von SA mit den evolutionären Algorithmen fällt sofort dessen Ähn-
lichkeit mit den ES auf. In beiden Fällen wird bei dem jeweiligen Basismodell ein Grundtyp
generiert, anschließend wird ein zweiter Typ erzeugt und dieser wird aufgrund einer entspre-
chenden Bewertungsfunktion mit dem Grundtyp verglichen. Welcher Typ anschließend in den
nächsten algorithmischen Schritt übernommen wird, hängt sowohl bei einer ES als auch beim
SA von entsprechenden Festlegungen ab. Bei beiden Algorithmen ist es ja möglich, entweder