Information Technology Reference
In-Depth Information
Sie koordinieren sich ohne eine zentrale Steuerung nur anhand von Selbstorganisa-
tion. Ganz wichtig für eine Kooperation ist der Austausch von Informationen zwi-
schen den einzelnen Individuen. Deswegen klassifizieren wir die Verfahren nach
der Art des Informationsaustausches. Ein nahezu vollständiger, wenn auch jeweils
knapper Überblick auf naturinspierierte Algorithmen und deren Implementierun-
gen wird von Brownlee [2011] gegeben.
Die bereits erwähnten genetische bzw. evolutionäre Algorithmen nehmen sich
die Evolution der Lebewesen als biologisches Vorbild. Der Informationsaustausch
findet durch Rekombination der Genotypen statt. Jedes Individuum repräsentiert
einen Lösungskandidaten.
Populationsbasiertes inkrementelles Lernen hat auch die Evolution der Lebewe-
sen als biologisches Vorbild. Allerdings verzichten wir hier auf eine Population. Viel-
mehr findet der Informationsaustausch durch Häufigkeiten in der Population statt,
die sich über die Generationen hinweg anpassen. Auch hier ist jedes Individuum ein
Lösungskandidat. Im Abschnitt 12.5.1 diskutieren wir diese Art von Algorithmen
kurz.
Ameisenkoloniealgorithmen nutzen die Wegesuche von Ameisen zu Futterquel-
len als biologisches Vorbild. Der Informationsaustausch hier wird über eine Verän-
derung der Umgebung geregelt. Dies entspricht der Stigmergie, dem erweiterten
Phänotyp nach Dawkins [1989, 1998]. Die Individuen
konstruieren
den Lösungskan-
didaten. Ameisenkolonieoptimierung besprechen wir noch im Abschnitt 12.5.2.
Die Teilchenschwarmoptimierung benutzt die Futtersuche von Fisch- und Vogel-
schwärmen als biologisches Vorbild. Hier passiert der Informationsaustausch über
einfache Aggregation der Einzellösungen. Jedes Individuum ist wie bei EA und PBIL
ein Lösungskandidat. Dieses Verfahren behandeln wir noch genauer im Abschnitt
12.5.3.
12.5.1 Populationsbasiertes inkrementelles Lernen
Populationsbasiertes inkrementelles Lernen (PBIL) [Baluja 1994] ist ein geneti-
scher Algorithmus ohne jegliche Population. Stattdessen wird nur eine Populati-
onsstatistik abgespeichert, die für jedes der
L
Bits die Häufigkeit der „1“ darstellt.
Benötigt man reale Individuen (z. B. zur Bewertung), dann passiert die Erzeugung
eines Individuums zufällig durch die gespeicherten Häufigkeiten. Eine Rekombina-
tion durch uniformes Crossover benutzt man ebenfalls implizit bei der Erzeugung
eines neuen Individuums. Die Selektion wählt das besten Individuums
s
für die
Aktualisierung der Populationsstatistik
P
(
t
)
k
·
+
P
(
t
1)
k
s
(
1
)
.
k
Eine Mutation erfolgt über das Ändern eines Bits, wodurch man eine leichte, zufälli-
ge Verschiebung der Populationsstatistik bewirken kann. Der Pseudocode für PBIL
ist in Algorithmus 18 gelistet. Eine niedrige Lernrate
dient der Erforschung des
Suchraums, während ein hohes
einer Exploration nahekommt. Für gewöhnlich
verwendet man folgende Parameter für PBIL [Weicker 2007]: eine Populationsgröße
von 20-100, eine Lernrate
von 0.05-0.2, eine Mutationsrate
p
m
von 0.001-0.02
und eine Mutationskonstante
von 0.05.
