Information Technology Reference
In-Depth Information
ten Bewertungsfunktion. Man untersucht, wie viele Individuen andere Individuen
dominieren, die dieses Individuum dominieren. Auch spielt der Abstand zum
n
-
nächsten Individuum eine Rolle. Das Archiv wird zur Fitness mit herangezogen und
enthält nicht-dominierte Individuen. Falls es zu klein sein sollte, werden zusätzlich
die besten Individuen das Archiv auffüllen. Ersetzungen im Archiv durch neue Indi-
viduen werden durch die Entfernung zu anderen archivierten Individuen getroffen.
Algorithmus 23
PAES
Eingabe:
Zielfunktionen
F
1
,...,
F
k
,Archivgröße
µ
1:
t
0
2:
A
erzeuge ein zufälliges Individuen
3:
R
(
t
) {
A
}
als mehrdimensionale Hash-Tabelle organisiert
4:
while
Terminierungsbedingung nicht erfüllt
do
5:
B
Mutation auf
A
6: bewerte
B
durch
F
1
,...,
F
k
7:
if
C
R
(
t
) {
A
}
:
not
(
C
>
dom
B
)
then
8:
if
C
R
(
t
)
:
(
B
>
dom
C
)
then
9: entferne alle durch
B
dominierten Individuen aus
R
(
t
)
10:
R
(
t
)
R
(
t
) {
B
}
11:
A
B
12:
else
13:
if
|
R
(
t
)| =
µ
then
14:
g
Hash-Eintrag mit meisten Einträgen
15:
g
Hash-Eintrag für
B
16:
if
Einträge in
g
<Einträgein
g
then
17: entferne einen Eintrag aus
g
18:
R
(
t
) füge
B
in
R
(
t
) ein
19:
end if
20:
else
21:
R
(
t
)
füge
B
in
R
(
t
)
ein
22:
g
A
Hash-Eintrag für
A
23:
g
B
Hash-Eintrag für
B
24:
if
Einträge in
g
B
<Einträgein
g
A
then
25:
A
B
26:
end if
27:
end if
28:
end if
29:
end if
30:
t
t
+
1
31:
end while
32:
return
nicht-dominierte Individuen aus
R
(
t
+
1
)
Schlussendlich existieren Erweiterungen der Evolutionsstrategien für Mehrkri-
terienoptimierungsprobleme, wie z. B.
Pareto-Archived ES (PAES)
[Knowles u. Cor-
ne 1999]. Dieses Verfahren ist in Algorithmus 23 verdeutlicht. Hierbei handelt es
sich um eine
(
1
+
1
)
-Evolutionsstrategie (siehe Abschnitt 12.3). Das neue Individu-
um wird akzeptiert, falls ein Archivindividuum entweder dominiert wird oder der
Funktionswertebereich wenig frequentiert ist. Die Nischen ergeben sich hierbei aus
der Organisation des Archivs als mehrdimensionale Hash-Tabelle.