Information Technology Reference
In-Depth Information
die Anzahl der dargestellten Schemata abnimmt, womit auch die Parallelisierung
der Suche abnimmt.
Die Analogie des zweiarmigen Banditen besagt, dass ein GA mit exponentiell
steigender Anzahl an Versuchen mit überlegenen Schemata sich einer optimalen
Strategie annähert. Ein GA spielt allerdings mit vielen Banditen. Die Reihenfolge,
um die Banditen zu lösen, ist wahrscheinlich von Bedeutung. Das Finden einzelner
Schemata, die am Gewinnspiel teilnehmen ist alles andere als einfach. So kann z. B.
1
**
mit
0
**
bzw.
*
1
*
mit
*
0
*
verglichen werden. In beiden Fällen ist nicht eindeu-
tig klar, ob eine exponentielle Anzahl an Versuchen optimal ist. Somit erreicht ein
GA die exponentiell steigende Zahl von Versuchen nicht.
Das Prinzip der kleinsten Alphabete besagt, dass eine Binärkodierung optimal
sei für das Schematheorem. Dabei ist doch klar, dass eine extrem große Anzahl an
Schemata ineffektiver verarbeitet wird als eine kleine Anzahl.
Abschließend erwähnen wir, dass das Schematheorem immer nur für ein Schema
unabhängig von anderen Schemata in der Population gilt. Diese anderen Schemata
werden sich auch vermehren. Da mit der Zeit die Population konvergiert, was den
Selektionsdruck senkt, wird die relative Fitness eines Schemas gegen
1
/
|pop|
streben.
Schließlich wird auch die erwartete Anzahl an Kopien durch die zerstörende Wir-
kung der genetischen Operatoren abnehmen.
Ganz streng genommen ist das Schematheorem nur bei |pop| gültig. An-
sonsten treten nicht vernachlässigbare Abweichungen von den Erwartungswerten
auf. Diese Annahme ist in der Praxis jedoch nicht erfüllbar. Somit wird es stets eine
Abweichungen vom idealen Verhalten (den sogenannten stochastische Drift) geben.
Implizit wird auch angenommen, dass es kaumWechselwirkungen zwischen Genen
gibt (also eine geringe Epistasie vorhanden ist) und somit die Fitness von Chromoso-
men, die zum Schema passen, sehr ähnlich sei. Eine weitere implizite Annahme ist,
dass interagierende Gene im Chromosom eng zusammen liegen müssen, um kleine
Bausteine zu bilden. Dieser Einwand jedoch betrifft nur die Beschränkung auf das
Ein-Punkt-Crossover und nicht den Ansatz an sich. Andere Maße als die definieren-
de Lange sind möglich, die operationenspezifisch sind. Die Entscheidung, welche
Maße für andere Rekombinationsoperatoren benutzt werden könnten, obliegt dem
Leser.
12.2 Lokale Suchverfahren
Neben dem GA gibt es viele aus der Optimierung bekannte Verfahren, die zur Lö-
sung eines Optimierungsproblems genutzt werden können. Viele dieser Verfahren
gehören zur Klasse der lokalen Suchverfahren. Dafür weisen wir noch einmal kurz
auf das Lösen von Optimierungsproblemen hin (siehe Abschnitt 10.2.1). Gegeben ein
Optimierungsproblem
(
,
f
,
)
,essolleinElement
x
gefunden werden, das
f
optimiert (maximiert oder minimiert). O.B.d.A. sei ein Element
x
zu finden, das
f
maximiert. Ist
f
zu minimieren, dann kann stets
f
f
betrachtet werden. Ist
bei solch einem Optimierungsproblem vorausgesetzt, dass
f
(
x
1
)
und
f
(
x
2
)
sich für
ähnliche
x
1
,
x
2
nicht zu sehr unterscheiden (also, dass es keine großen Sprünge
in
f
gibt), dann können
lokale Suchverfahren
zum Finden von lokalen Optima in
verwendet werden. Diese sind anwendbar bei beliebigen .
