Information Technology Reference
In-Depth Information
Population 1
Population 2
1
1
0
0
Individuum 1
1
0
1
0
1
1
0
0
Individuum 2
0
1
1
0
0
0
1
1
Individuum 3
0
1
0
1
0
0
1
1
Individuum 4
1
0
0
1
0.5
0.5
0.5
0.5
Populationsstatistik
0.5
0.5
0.5
0.5
Tabe l l e 12 . 1 : Gl e i che Popu l a t i ons s t a t i s t i ken be i ve r s chi edenen Popu l a t i onen .
Während ein GA die Abhängigkeit zwischen einzelnen Bits lernen kann, betrach-
tet PBIL einzelne Bits isoliert voneinander. So können ganz unterschiedliche Popu-
lationen zu gleichen Populationsstatistiken führen. Dies ist in Tabelle 12.1 verdeut-
licht [Weicker 2007].
Wir müssen demnach bessere Techniken zur Schätzung der Verteilung guter Lö-
sungskandidaten verwenden. Eine grundlegende Verbesserung käme z. B. mit der
Modellierung von Abhängigkeiten zwischen den Individuen zum tragen. Dies könn-
te mittels Bayes-Netze durchgeführt werden. Bayes-Netze gehören zur Klasse der
graphischen Modelle und werden in diesem Buch im Teil IV ab Seite 347 ausgiebig
diskutiert. Der sogenannte Bayes-Optimierungsalgorithmus (BOA) [Pelikan u. a. 2000]
erzeugt eine zufällige Anfangspopulation. Diese Population wird für eine bestimm-
te Anzahl von Iterationen aktualisiert durch Selektion (wie bei PBIL) und Variation.
Die Variation konstruiert nach der Selektion ein Bayes-Netz als Modell von vielver-
sprechenden Lösungskandidaten. Neue Lösungskandidaten werden dann durch ei-
ne Stichprobe vom Bayes-Netz generiert. Mehr Details zum BOA findet der geneigte
Leser in [Brownlee 2011].
12.5.2 Ameisenkolonieoptimierung
Ameisenkolonieoptimierung (engl. ant colony optimization )[Dorigou.Stützle2004,
Döring u. a. 2006] orientieren sich an biologischen Ameisen einiger Arten, die die
kürzesten Wege zu Futterquellen durch das Legen und Verfolgen von Pheromon-
markierungen („Duftmarken“) finden. Intuitiv erhalten kürzere Wege in der glei-
chen Zeit mehr Pheromon. Die Wege werden zufällig nach der vorhandenen Phero-
monmenge gewählt. Es ist umso wahrscheinlicher, dass wir einen Weg wählen, je
mehr Pheromon sich auf dem Weg befindet. Die Menge des ausgebrachten Phero-
mons kann von der Qualität und der Menge des gefundenen Futters abhängen. Das
Grundprinzip ist die Stigmergie (engl. stigmergy ). D. h., zur Wegesuche kommuni-
zieren Ameisen indirekt über die Pheromonablagerungen. Die Stigmergie (also die
indirekte Kommunikation durch die Veränderung der Umgebung) ermöglicht ein
global angepasstes Verhalten durch lokale Informationen.
Um dies zu verdeutlichen wurde von Goss u. a. [1989] das sogenannte Doppel-
brückenexperiment durchgeführt. Ameisennest und Futterquelle werden durch eine
Doppelbrücke verbunden. Die beiden Zweige der Brücke sind verschieden lang. Das
Experiment wurdemit der argentinischen Ameise IridomyrmexHumilis durchgeführt.
Diese Ameisenart ist (wie fast alle anderen auch) fast blind. Die Ameisen können also
nicht sehen, welches der kürzereWeg ist. In den meisten Versuchen benutzten schon
nach wenigen Minuten fast alle Ameisen den kürzeren Weg. Die Erklärung hierfür
Search WWH ::




Custom Search