Information Technology Reference
In-Depth Information
f
2
f
2
f
2
f
1
f
1
f
1
Abbildung 13.1: Veranschaulichung Pareto-optimaler Lösungen, der sogenannten
Pareto-Front
.AllePunktedesSuchraumsliegenimgraugezeichnetenBereich.Pareto-
optimale Lösungen liegen auf dem fett gezeichneten Teil des Randes. Je nach Lage
der Lösungskandidaten kann die Pareto-optimale Lösung auch eindeutig bestimmt
sein (siehe rechtes Diagramm).x
13.2.2 Pareto-optimale Lösungen
Ein alternativer Ansatz ist der Versuch, alle bzw. möglichst viele
Pareto-optimale
Lö-
sungen zu finden.
Definition 13.1 (Pareto-Optimum)
Ein Element s
heißt
Pareto-optimal
bezüglich
der Zielfunktionen f
i
,i
=
1, . . . ,
k, wenn es kein Element s
gibt, für das gilt
i
,1
i
k
:
f
i
(
s
)
f
i
(
s
)
und
f
i
(
s
)
>
f
i
(
s
)
.
Anschaulich bedeutet Pareto-optimal, dass der Wert keiner Zielfunktion verbessert
werden kann, ohne den Wert einer anderen zu verschlechtern.
Eine ausführlichere Definition des Begriffs „Pareto-optimal“ kann man wie folgt
angeben: Ein Element
s
1
dominiert
ein Element
s
2
,wenngilt
i
,1
i
k
:
f
i
(
s
1
)
f
i
(
s
2
).
Ein Element
s
1
dominiert
ein Element
s
2
echt
,wenn
s
1
s
2
dominiert und
außerdem gilt
i
,1
i
k
:
i
,1
i
k
:
f
i
(
s
1
)
>
f
i
(
s
2
).
Ein Element
s
1
S
heißt
Pareto-optimal
,wennesvonkeinemElement
s
2
echt
dominiert wird. Somit ergeben sich Vorteile bei der Suche nach Pareto-optimalen
Lösungen: Die Zielfunktionen müssen nicht zusammengefasst werden. Auch müs-
sen keine Gewichte bestimmt werden. Man muss auch die Suche für verschiedene
Präferenzen nur einmal durchführen, da man erst anschließend aus den gefunde-
nen Lösungen eine oder mehrere auswählt. In Abbildung 13.1 sind einige Beispiele
Pareto-optimaler Lösungen dargestellt.
13.2.3 Lösungen mit Evolutionären Algorithmen
Evolutionäre Algorithmen können ebenfalls zur Suche nach Lösungskandidaten in
der Mehrkriterienoptimierung verwendet werden. Dabei ist unser Ziel, eine mög-
lichst breite Verteilung der Population entlang der Pareto-Front zu erhalten. Die