Lineare Gewichtung

Die lineare Gewichtung (englisch: Weighted Sum Method oder Linear Weighting Method) ist ein Verfahren der Mehrzieloptimierung, bei dem mehrere Zielfunktionen zu einer einzigen Zielfunktion zusammengefasst werden.

Dabei wird jeder Zielfunktion ein Gewicht zugeordnet, das ihre relative Bedeutung beschreibt. Die gewichteten Zielfunktionen werden anschließend addiert.

Die lineare Gewichtung gehört zu den einfachsten und am häufigsten verwendeten Verfahren der Mehrzieloptimierung.

Grundidee

Viele Optimierungsprobleme besitzen mehrere konkurrierende Zielgrößen.

Beispiele:

Minimierung von Kosten
Minimierung von Emissionen
Maximierung der Qualität
Minimierung der Laufzeit

Da klassische Optimierungsverfahren meist nur eine Zielfunktion verarbeiten können, werden die einzelnen Ziele zu einer gemeinsamen Zielfunktion kombiniert.

Dies geschieht durch Gewichtungsfaktoren.

Mathematische Formulierung

Ein allgemeines Mehrzielproblem lautet:

$\min (f_{1} (x), f_{2} (x), . . ., f_{k} (x))$

Bei der linearen Gewichtung wird daraus:

$\min Z (x)$

mit:

$Z (x) = \sum_{i = 1}^{k} w_{i} f_{i} (x)$

Dabei gilt:

$f_{i} (x)$ = Zielfunktionen
$w_{i}$ = Gewichtungsfaktoren
$x$ = Entscheidungsvariablen

Die Gewichte erfüllen typischerweise:

$w_{i} \geq 0$

und:

$\sum_{i = 1}^{k} w_{i} = 1$

Bedeutung der Gewichte

Die Gewichte bestimmen die relative Wichtigkeit der einzelnen Ziele.

Beispiel:

Ziel	Gewicht
Kostenminimierung	0,7
Emissionsminimierung	0,3

In diesem Beispiel besitzt die Kostenminimierung eine höhere Priorität.

Beispiel

Ein Unternehmen möchte:

Produktionskosten minimieren
Energieverbrauch minimieren

Die Zielfunktionen lauten:

$f_{1} (x) = K o s t e n (x)$

$f_{2} (x) = E n e r g i e v e r b r a u c h (x)$

Die gewichtete Zielfunktion lautet:

$Z (x) = 0.8 \cdot K o s t e n (x) + 0.2 \cdot E n e r g i e v e r b r a u c h (x)$

Dadurch wird ein einzelnes Optimierungsproblem erzeugt.

Vorgehensweise

1. Definition der Zielfunktionen

Zunächst werden alle relevanten Zielgrößen formuliert.

Beispiel:

Kosten
Qualität
Energieverbrauch
Lieferzeit

2. Wahl der Gewichte

Anschließend wird für jede Zielfunktion ein Gewicht festgelegt.

Die Gewichte spiegeln die Präferenzen des Entscheiders wider.

3. Bildung der Gesamtzielfunktion

Die gewichteten Ziele werden addiert:

$Z (x) = w_{1} f_{1} (x) + w_{2} f_{2} (x) + . . . + w_{k} f_{k} (x)$

4. Lösung des Optimierungsproblems

Das resultierende Einzelzielproblem wird mit klassischen Verfahren gelöst:

Normierung der Zielfunktionen

Die einzelnen Zielfunktionen besitzen häufig unterschiedliche Größenordnungen.

Beispiel:

Kosten in Euro
Emissionen in Kilogramm
Zeit in Sekunden

Ohne Normierung könnten große Zahlenbereiche dominante Effekte erzeugen.

Daher werden Zielfunktionen häufig normiert:

$f_{i}^{n o r m} (x) = \frac{f_{i} (x) - f_{i}^{m i n}}{f_{i}^{m a x} - f_{i}^{m i n}}$

Die gewichtete Zielfunktion verwendet dann die normierten Werte.

Eigenschaften

Einfachheit

Die lineare Gewichtung ist mathematisch einfach und leicht implementierbar.

Gute Solver-Unterstützung

Da nur eine Zielfunktion entsteht, können Standard-Solver verwendet werden.

Direkte Berücksichtigung von Präferenzen

Gewichte ermöglichen eine direkte Priorisierung der Ziele.

Nachteile

Schwierige Wahl geeigneter Gewichte

Die Auswahl sinnvoller Gewichte ist oft problematisch.

Kleine Änderungen der Gewichte können große Auswirkungen auf die Lösung haben.

Unterschiedliche Skalierungen

Ohne Normierung dominieren Ziele mit großen Zahlenwerten.

Probleme bei nicht-konvexen Pareto-Fronten

Die lineare Gewichtung kann bestimmte Pareto-Lösungen nicht finden.

Insbesondere bei nicht-konvexen Pareto-Fronten entstehen Lücken.

Keine vollständige Pareto-Abdeckung

Nicht alle Pareto-optimalen Lösungen sind mit der gewichteten Summe erreichbar.

Zusammenhang mit Pareto-Optimalität

Jede Lösung der gewichteten Summe ist unter bestimmten Bedingungen Pareto-optimal.

Allerdings gilt dies nur vollständig bei konvexen Pareto-Fronten.

Nicht-konvexe Bereiche können durch die lineare Gewichtung nicht erreicht werden.

Geometrische Interpretation

Die lineare Gewichtung kann geometrisch als Verschiebung einer Hyperebene interpretiert werden.

Die Gewichte bestimmen die Steigung dieser Hyperebene.

Die optimale Lösung liegt dort, wo die Hyperebene den zulässigen Lösungsraum zuletzt berührt.

Beispiel einer Pareto-Front

Gewichtung	Ergebnis
$w_{1} = 0.9$ , $w_{2} = 0.1$	Kosten stark priorisiert
$w_{1} = 0.5$ , $w_{2} = 0.5$	Ausgewogene Lösung
$w_{1} = 0.2$ , $w_{2} = 0.8$	Umweltwirkung stark priorisiert

Anwendungen

Die lineare Gewichtung wird in vielen Bereichen eingesetzt.

Produktion

Kosten vs. Qualität
Produktionsmenge vs. Energieverbrauch

Logistik

Lieferzeit vs. Transportkosten
Emissionen vs. Effizienz

Energietechnik

Wirtschaftlichkeit vs. CO₂-Ausstoß
Netzstabilität vs. Kosten

Softwareentwicklung

Laufzeit vs. Speicherverbrauch
Performance vs. Energieeffizienz
Antwortzeit vs. Hardwarekosten

Landwirtschaft

Kostenminimierung
Minimierung von Nährstoffabweichungen
Minimierung von Umweltbelastungen

Beispiel in der Düngemitteloptimierung

In einem Düngemittel-Empfehlungssystem könnte folgende gewichtete Zielfunktion verwendet werden:

$Z (x) = 0.5 \cdot K o s t e n (x) + 0.3 \cdot A_{N} (x) + 0.2 \cdot N_{U} (x)$

Dabei beschreibt:

$K o s t e n (x)$ die Gesamtkosten
$A_{N} (x)$ die Nährstoffabweichung
$N_{U} (x)$ den Stickstoffüberschuss

Durch Veränderung der Gewichte können unterschiedliche Strategien erzeugt werden.

Vergleich mit anderen Verfahren

Verfahren	Grundidee	Vorteile	Nachteile
Lineare Gewichtung	Gewichtete Summe aller Ziele	Einfach und effizient	Probleme bei nicht-konvexen Fronten
ε-Constraint-Methode	Ein Ziel optimieren, andere begrenzen	Gute Pareto-Abdeckung	Mehrfache Optimierung erforderlich
Lexikographische Optimierung	Ziele nach Priorität ordnen	Klare Hierarchie	Niedrige Flexibilität
NSGA-II	Evolutionäre Pareto-Suche	Viele Lösungen gleichzeitig	Hoher Rechenaufwand

Erweiterte Varianten

Adaptive Gewichtung

Die Gewichte werden während der Optimierung dynamisch angepasst.

Nichtlineare Gewichtung

Die Zielfunktionen werden nichtlinear kombiniert.

Goal Programming

Abweichungen von Zielwerten werden minimiert.

Interaktive Gewichtung

Der Entscheider verändert die Gewichte während der Optimierung.

Bedeutung in der Multi-Objective-Optimierung

Die lineare Gewichtung zählt zu den wichtigsten klassischen Verfahren der Mehrzieloptimierung.

Sie wird häufig eingesetzt:

wegen ihrer Einfachheit
wegen der guten mathematischen Eigenschaften
wegen der hohen Solver-Kompatibilität

Trotz ihrer Einschränkungen dient sie oft als Ausgangspunkt für komplexere Verfahren.

Literatur

Ehrgott, M.: Multicriteria Optimization. Springer, 2005.
Miettinen, K.: Nonlinear Multiobjective Optimization. Springer, 1999.
Deb, K.: Multi-Objective Optimization using Evolutionary Algorithms. Wiley, 2001.
Steuer, R. E.: Multiple Criteria Optimization: Theory, Computation and Application. Wiley, 1986.
Marler, R. T.; Arora, J. S.: Survey of Multi-Objective Optimization Methods for Engineering, Structural and Multidisciplinary Optimization, 2004.

Siehe auch

Lineare Gewichtung

Lineare Gewichtung

Grundidee

Mathematische Formulierung

Bedeutung der Gewichte

Beispiel

Vorgehensweise

1. Definition der Zielfunktionen

2. Wahl der Gewichte

3. Bildung der Gesamtzielfunktion

4. Lösung des Optimierungsproblems

Normierung der Zielfunktionen

Eigenschaften

Einfachheit

Gute Solver-Unterstützung

Direkte Berücksichtigung von Präferenzen

Nachteile

Schwierige Wahl geeigneter Gewichte

Unterschiedliche Skalierungen

Probleme bei nicht-konvexen Pareto-Fronten

Keine vollständige Pareto-Abdeckung

Zusammenhang mit Pareto-Optimalität

Geometrische Interpretation

Beispiel einer Pareto-Front

Anwendungen

Produktion

Logistik

Energietechnik

Softwareentwicklung

Landwirtschaft

Beispiel in der Düngemitteloptimierung

Vergleich mit anderen Verfahren

Erweiterte Varianten

Adaptive Gewichtung

Nichtlineare Gewichtung

Goal Programming

Interaktive Gewichtung

Bedeutung in der Multi-Objective-Optimierung

Literatur

Siehe auch

Navigationsmenü

Suche