Optimierungsverfahren
Optimierungsverfahren
Definition
Optimierungsverfahren sind mathematische und algorithmische Methoden zur Bestimmung einer optimalen Lösung aus einer Menge möglicher Lösungen unter gegebenen Nebenbedingungen. Ziel ist es, eine Zielfunktion zu minimieren oder zu maximieren.
Grundlagen
Zielfunktion
Die Zielfunktion beschreibt das Kriterium, das optimiert werden soll.
Beispiele:
- Minimierung von Kosten
- Maximierung von Gewinn
- Minimierung von Laufzeit
Entscheidungsvariablen
Variablen, die im Optimierungsprozess verändert werden können.
Nebenbedingungen
Einschränkungen, die eingehalten werden müssen.
Beispiel:
- Budgetgrenzen
- physikalische Grenzen
- Kapazitäten
Lösungsraum
Die Menge aller möglichen Lösungen, die die Nebenbedingungen erfüllen.
Optimale Lösung
Eine Lösung ist optimal, wenn sie den besten Wert der Zielfunktion im Lösungsraum erreicht.
---
Klassifikation von Optimierungsverfahren
Nach Anzahl der Zielgrößen
Single-Objective Optimierung
- Nur eine Zielfunktion
- Eindeutige optimale Lösung
- Totale Ordnung möglich
Beispiel:
- Minimierung der Produktionskosten
Multi-Objective Optimierung
- Mehrere Zielgrößen
- Zielkonflikte möglich
- Ergebnis ist eine Pareto-Front
Beispiel:
- Minimierung von Kosten und Maximierung der Qualität
---
Nach Problemstruktur
Lineare Optimierung
- Zielfunktion und Nebenbedingungen sind linear
- Beispiel: Simplex-Verfahren
Nichtlineare Optimierung
- Mindestens eine Funktion ist nichtlinear
- Komplexer Lösungsraum
Diskrete Optimierung
- Variablen sind ganzzahlig oder diskret
Kombinatorische Optimierung
- Suche nach optimaler Kombination
- Beispiel: Traveling Salesman Problem
---
Nach Lösungsstrategie
Exakte Verfahren
- Finden garantiert optimale Lösungen
- Oft hoher Rechenaufwand
Beispiele:
- Branch-and-Bound
- Simplex-Verfahren
Heuristische Verfahren
- Finden gute, aber nicht zwingend optimale Lösungen
- Schneller als exakte Verfahren
Beispiele:
- Greedy-Algorithmen
- Lokale Suche
Metaheuristische Verfahren
- Allgemeine Strategien zur Lösung komplexer Probleme
Beispiele:
- Genetische Algorithmen
- Simulated Annealing
- Ant Colony Optimization
- Particle Swarm Optimization
---
Pareto-basierte Optimierung
Bei Mehrzielproblemen wird oft das Konzept der Pareto-Optimalität verwendet.
Pareto-Dominanz
Eine Lösung A dominiert B, wenn:
- A ist in allen Zielen mindestens gleich gut
- A ist in mindestens einem Ziel besser
Pareto-Front
Menge aller nicht dominierten Lösungen.
Eigenschaften:
- Kein eindeutiges Optimum
- Entscheidung erfolgt nach Präferenzen
---
Single Objective Ranking
Bei Single-Objective Problemen können Lösungen eindeutig sortiert werden.
Eigenschaften:
- Totale Ordnung
- Vergleichbarkeit aller Lösungen
- Eindeutige beste Lösung
---
Typische Algorithmen
Deterministische Verfahren
- Gradientenverfahren
- Newton-Verfahren
Evolutionäre Algorithmen
- Genetische Algorithmen
- NSGA-II
- SPEA2
Stochastische Verfahren
- Simulated Annealing
- Random Search
---
Anwendungsgebiete
- Maschinenbau (Leichtbau vs. Stabilität)
- Logistik (Routenoptimierung)
- Informatik (Scheduling, KI)
- Wirtschaft (Portfolio-Optimierung)
- Energie (Netzoptimierung)
- Landwirtschaft (z. B. Düngemitteloptimierung)
---
Vergleich: Single vs. Multi Objective
| Kriterium | Single Objective | Multi Objective |
|---|---|---|
| Anzahl Ziele | 1 | mehrere |
| Ergebnis | eine Lösung | mehrere Lösungen (Pareto-Front) |
| Ordnung | total | partiell |
| Entscheidungsfindung | eindeutig | abhängig von Präferenzen |
---
Herausforderungen
- Hohe Rechenkomplexität
- Lokale Optima
- Skalierbarkeit
- Modellierungsaufwand
- Zielkonflikte
---
Begriffe
- Zielfunktion
- Lösungsraum
- Nebenbedingungen
- Pareto-Optimalität
- Heuristik
- Metaheuristik
---
Literatur
- Papadimitriou, C.: Combinatorial Optimization
- Deb, K.: Multi-Objective Optimization using Evolutionary Algorithms
- Nocedal, J.: Numerical Optimization
---