Information Technology Reference
In-Depth Information
Fairerweise muss gesagt werden, dass selbst modernste Verfahren bei mehr als
drei Kriterien Probleme haben, die Pareto-Front anzunähern. Der Grund dafür ist,
dass es viel zu lange dauert, die Pareto-Front zu approximieren. Dieses Problem
kann umgangen werden, wenn nacheinander bisherige Lösungen dem Anwender
vorgestellt werden. Er oder sie entscheidet dann über die Richtung der Suche in ei-
nem Teilbereich von .
13.3 Parallelisierung
Evolutionäre Algorithmen sind recht teure Optimierungsverfahren, da oft mit ei-
ner großen Population (einige tausend bis einige zehntausend Individuen) mit ei-
ner großen Zahl an Generationen (einige hundert) gearbeitet werden muss, um eine
hinreichende Lösungsgüte zu erreichen. Dieser Nachteil wird zwar durch eine oft et-
was höhere Lösungsgüte im Vergleich zu anderen Verfahren wettgemacht, trotzdem
kann die Laufzeit eines evolutionären Algorithmus unangenehm lang sein. Ein mög-
licher Lösungsansatz für dieses Problem ist eine
Parallelisierung
,d.h.dieVerteilung
der notwendigen Operationen auf mehrere Prozessoren. Wir stellen uns die Fragen,
welche Schritte parallelisiert und welche vorteilhaften Techniken bei der Parallelisie-
rung zusätzlich angewendet werden können?
Das
Erzeugen der Anfangspopulation
ist meist problemlos parallelisierbar, da man
i. Allg. die Chromosomen der Anfangspopulation zufällig und unabhängig vonein-
ander erzeugt. Der Versuch, Duplikate zu vermeiden, kann die Parallelisierung al-
lerdings behindern. Die Parallelisierung dieses Schrittes hat eher geringe Bedeutung,
da wir eine Anfangspopulation nur einmal erzeugen. Die
Bewertung der Chromosomen
ist problemlos parallelisierbar, da wir die Chromosomen i. Allg. unabhängig vonein-
ander bewerten. Die Fitness hängt also nur vom Chromosom selbst ab. Auch beim
Gefangenendilemma (siehe Abschnitt 13.1.1) können Paarungen parallel bearbeitet
werden. Zur
Berechnung der (relativen) Fitnesswerte
oder der Rangordnung der Chro-
mosomen müssen wir die Bewertungen zusammenführen. Ob sich die
Selektion
par-
allelisieren lässt, hängt sehr stark vom verwendeten Selektionsverfahren ab:
Erwar-
tungswertmodell
und
Elitismus
erfordern beide eine globale Betrachtung der Populati-
on und sind daher nur schwer parallelisierbar.
Glücksrad- und Rangauswahl
sind sehr
leicht zu parallelisieren, nachdem man die relativen Fitnesswerte bzw. die Ränge be-
stimmt hat (was allerdings schwer parallelisierbar ist). Ideal für die Parallelisierung
geeignet ist die
Tu r n i e r a u swa h l
,besondersbeikleinenTurniergrößen,dakeinegloba-
le Information bestimmt werden muss, sondern sich der Vergleich der Fitnesswerte
auf die Individuen des Turniers beschränkt. Die
Anwendung genetischer Operatoren
kann man leicht parallelisieren, da jeweils nur ein (Mutation) oder zwei Chromo-
somen (Crossover) betroffen sind. Zusammen mit einer Turnierauswahl kann man
einen Steady-State EA daher sehr gut parallelisieren. Ob man die
Abbruchbedingung
parallelisieren kann, ist von ihr selbst abhängig. Der einfache Test, ob eine bestimm-
te Generationenzahl erreicht ist, bereitet bei einer Parallelisierung keine Probleme.
Abbruchkriterien wie
• das beste Individuum der Population hat eine bestimmte Mindestgüte, oder
• über eine bestimmte Anzahl von Generationen hat sich das beste Individuum
nicht oder kaum verbessert,
