Information Technology Reference
In-Depth Information
Eine Alternative ist die NSGA-Selektion [Srinivas u. Deb 1994] wobei NSGA für
“Nondominated Sorting Genetic Algorithm” steht. Hierbei wird eine Tu r n i e r a u swa h l
verwendet, bei der der Turniersieger über den Dominanzbegriff und gegebenenfalls
Nischentechniken bestimmt wird. Zuerst wird ein Referenzindividuumgewählt. Da-
nach wird ein nichtdominiertes Individuum selektiert. Ansonsten wird ein Indivi-
duum gewählt, was weniger Individuen in seiner Nische hat. Eine Nische wird hier
durch einen Radius bestimmt. Dieses Selektionsverfahren ist in Algorithmus 21
beschrieben. Trotzdem kommt es nur zu einer schlechten Annäherung der Pareto-
Front. Dies liegt zum einen an der Parametereinstellung von ,zumanderendar-
an, dass die Population für zwei Dinge gebraucht wird: als Speicher für nicht-domi-
nierte Individuen (Pareto-Front) und als lebendige Population (zur Erforschung des
Suchraums).
Algorithmus 22 SPEA2
Eingabe: Zielfunktionen F 1 ,..., F k ,Populationsgröße µ ,Archivgröße µ
1: t 0
2: P ( t ) erzeuge Population mit µ Individuen
3: R ( t )
4: while Terminierungsbedingung nicht erfüllt do
5: bewerte P ( t ) durch F 1 ,..., F k
6: for all A P ( t ) R ( t ) do
7: AnzDom ( A ) |{ B P ( t ) R ( t ) | A > dom B }|
8: end for
9:
for all A P ( t ) R ( t ) do
10:
d Distanz von A und seinen
µ + µ nächsten Individuen in P ( t ) R ( t )
A . F 1
d +2 + B P ( t ) R ( t ), B > dom A AnzDom( B )
11:
12:
end for
R ( t + 1) { A P ( t ) R ( t ) | A ist nicht-dominiert}
13:
while | R ( t + 1)|
14:
> µ do
entferne dasjenige Individuum aus R ( t + 1) mit dem kürzesten/zweitkürzesten Ab-
stand
15:
16:
end while
if | R ( t + 1)|
17:
< µ then
18: fülle R ( t + 1) mit den gütebesten dominierten Individuen aus P ( t ) R ( t )
19: end if
20: if Terminierungsbedingung nicht erfüllt then
21: Selektion aus P ( t ) mittels T URNIER -S ELEKTION
22: P ( t + 1 ) wende Rekombination und Mutation an
23: t t + 1
24: end if
25: end while
26: return nicht-dominierte Individuen aus R ( t + 1 )
Dieses Problem kann behoben werden, wenn nicht-dominierte Individuen von
der Population in einem Archiv getrennt werden. Dieses Archiv hat meist eine end-
liche Größe. Es muss lediglich einen Test aller Individuen auf Dominanz durch Indi-
viduen des Archivs geben. Bei neuen Individuen für das Archiv werden dominier-
te Individuen entfernt. Dieses Verfahren heißt Strength Pareto EA (SPEA2) [Zitzler
u. a. 2001] (siehe Algorithmus 22) und ist ein gewöhnlicher EA mit einer kombinier-
Search WWH ::




Custom Search