5.1 Einleitung
263
Um multikriterielle Optimierungen durchzuführen, betrachten wir einen mdimensionalen Raum X möglicher Lösungen des Optimierungsproblems. Diese
Dimensionen könnten beispielsweise die Anzahl der Prozessoren, die Größen von
Speichern und die Art und Anzahl von Bussen darstellen. Auf diesem Raum X definieren wir eine n-dimensionale Funktion, die Entwürfe in Hinblick auf mehrere
Kriterien oder Ziele (z.B. Kosten und Leistung) hin evaluiert:
f (x) = ( f 1 (x), ..., f n (x)) mit x ∈ X
Sei F der n-dimensionale Werteraum dieser Ziele (der sogenannte Zielraum). Für
jedes der Ziele ist eine Ordnung < und die entsprechende ≤-Ordnung definiert. Im
Folgenden nehmen wir an, dass wir die Minimierung der Ziele erreichen wollen.
Definition 5.4: Ein Vektor u = (u 1 , ..., u n ) ∈ F dominiert einen Vektor v =
(v 1 , ..., v n ) ∈ F genau dann, wenn u in Hinblick auf mindestens ein Ziel „besser” als
v und nicht schlechter als v für alle anderen Ziele ist:
∀ i ∈ {1, ...n} : u i ≤ v i ∧
(5.1)
∃ j ∈ {1, .., n} : u j < v j
(5.2)
Definition 5.5: Ein Vektor u ∈ F wird indifferent zu einem Vektor v ∈ F genannt
genau dann, wenn weder der Vektor u den Vektor v dominiert noch der Vektor v den
Vektor u.
Definition 5.6: Ein Entwurf x ∈ X heißt Pareto-optimal auf X genau dann, wenn
es keinen Entwurf y ∈ X gibt, so dass u = f (x) von v = f (y) dominiert wird.
Die vorstehende Definition definiert Pareto-Optimalität im Lösungsraum. Die folgende Definition liefert die Entsprechung für den Zielraum.
Definition 5.7: Sei S ⊆ F eine Teilmenge von Vektoren im Zielraum. v ∈ F ist
eine nicht dominierte Lösung von S genau dann, wenn v von keinem Element ∈ S
dominiert wird. v heißt Pareto-optimal genau dann, wenn v nicht dominiert wird in
Hinblick auf alle Lösungen F.
Abb. 5.2 verdeutlicht die unterschiedlichen Gebiete in einem Zielraum mit den Optimierungskriterien O1 und O2 relativ zum Entwurfspunkt (1). Abb. 5.2 (links) zeigt
Pareto-Punkte und die obere rechte Fläche beschreibt Entwürfe, die von Entwurf (1)
dominiert werden, da diese „schlechter” in Hinblick auf beide Ziele sind. Entwürfe
im linken unteren Rechteck (wenn sie existieren würden) würden den Entwurf (1)
dominieren, da sie in Hinlick auf beide Ziele „besser” wären. Entwürfe in der linken
oberen und rechten unteren Ecke sind indifferent: sie sind „besser” in Hinblick auf
ein Ziel und „schlechter” in Hinblick auf das andere. Abb. 5.2 (rechts) zeigt eine
Menge von Pareto-Punkten, mit + markiert. Dominierte Entwurfspunkte sind alle
Punkte in diesem Diagramm, die von mindestens einem Pareto-Punkt dominiert
sind. Sie ergeben sich also als Vereinigung aller von einem Pareto-Punkt dominierten Punkte. Die Pareto-Front grenzt diese Punkte vom übrigen Teil des Diagramms
ab. Die Pareto-Front wird durch eine Treppenfunktion dargestellt.
263
Um multikriterielle Optimierungen durchzuführen, betrachten wir einen mdimensionalen Raum X möglicher Lösungen des Optimierungsproblems. Diese
Dimensionen könnten beispielsweise die Anzahl der Prozessoren, die Größen von
Speichern und die Art und Anzahl von Bussen darstellen. Auf diesem Raum X definieren wir eine n-dimensionale Funktion, die Entwürfe in Hinblick auf mehrere
Kriterien oder Ziele (z.B. Kosten und Leistung) hin evaluiert:
f (x) = ( f 1 (x), ..., f n (x)) mit x ∈ X
Sei F der n-dimensionale Werteraum dieser Ziele (der sogenannte Zielraum). Für
jedes der Ziele ist eine Ordnung < und die entsprechende ≤-Ordnung definiert. Im
Folgenden nehmen wir an, dass wir die Minimierung der Ziele erreichen wollen.
Definition 5.4: Ein Vektor u = (u 1 , ..., u n ) ∈ F dominiert einen Vektor v =
(v 1 , ..., v n ) ∈ F genau dann, wenn u in Hinblick auf mindestens ein Ziel „besser” als
v und nicht schlechter als v für alle anderen Ziele ist:
∀ i ∈ {1, ...n} : u i ≤ v i ∧
(5.1)
∃ j ∈ {1, .., n} : u j < v j
(5.2)
Definition 5.5: Ein Vektor u ∈ F wird indifferent zu einem Vektor v ∈ F genannt
genau dann, wenn weder der Vektor u den Vektor v dominiert noch der Vektor v den
Vektor u.
Definition 5.6: Ein Entwurf x ∈ X heißt Pareto-optimal auf X genau dann, wenn
es keinen Entwurf y ∈ X gibt, so dass u = f (x) von v = f (y) dominiert wird.
Die vorstehende Definition definiert Pareto-Optimalität im Lösungsraum. Die folgende Definition liefert die Entsprechung für den Zielraum.
Definition 5.7: Sei S ⊆ F eine Teilmenge von Vektoren im Zielraum. v ∈ F ist
eine nicht dominierte Lösung von S genau dann, wenn v von keinem Element ∈ S
dominiert wird. v heißt Pareto-optimal genau dann, wenn v nicht dominiert wird in
Hinblick auf alle Lösungen F.
Abb. 5.2 verdeutlicht die unterschiedlichen Gebiete in einem Zielraum mit den Optimierungskriterien O1 und O2 relativ zum Entwurfspunkt (1). Abb. 5.2 (links) zeigt
Pareto-Punkte und die obere rechte Fläche beschreibt Entwürfe, die von Entwurf (1)
dominiert werden, da diese „schlechter” in Hinblick auf beide Ziele sind. Entwürfe
im linken unteren Rechteck (wenn sie existieren würden) würden den Entwurf (1)
dominieren, da sie in Hinlick auf beide Ziele „besser” wären. Entwürfe in der linken
oberen und rechten unteren Ecke sind indifferent: sie sind „besser” in Hinblick auf
ein Ziel und „schlechter” in Hinblick auf das andere. Abb. 5.2 (rechts) zeigt eine
Menge von Pareto-Punkten, mit + markiert. Dominierte Entwurfspunkte sind alle
Punkte in diesem Diagramm, die von mindestens einem Pareto-Punkt dominiert
sind. Sie ergeben sich also als Vereinigung aller von einem Pareto-Punkt dominierten Punkte. Die Pareto-Front grenzt diese Punkte vom übrigen Teil des Diagramms
ab. Die Pareto-Front wird durch eine Treppenfunktion dargestellt.