Stage-oe-small.jpg

Thema3854

Aus Aifbportal
Wechseln zu:Navigation, Suche



Theory and Algorithms for Identifying Knees in Multi-Objective Optimization


Marlon Braun



Informationen zur Arbeit

Abschlussarbeitstyp: Master
Betreuer: Pradyumn Kumar ShuklaHartmut Schmeck
Forschungsgruppe: Effiziente Algorithmen

Archivierungsnummer: 3854
Abschlussarbeitsstatus: Abgeschlossen
Beginn: 01. September 2013
Abgabe: 28. Februar 2014

Weitere Informationen

Multikriterielle Optimierungsprobleme sind von herausragender Bedeutung in ökonomi- schen, betriebswirtschaftlichen und ingenieurwissenschaftlichen Kontexten. Die gleichzeiti- ge Optimierung mehrerer Ziele, die oft widersprüchlich zueinander sind, beinhaltet schwie- rige Herausforderungen, die einem nicht bei der Optimierung einer einzigen Funktion be- gegnen. Die Lösung eines multikriteriellen Problems liefert für gewöhnlich eine große Menge optimaler Punkte, die lediglich in einem Funktionswert verbessert werden können, wenn sich ein anderer gleichzeitig verschlechtert. Diese Punkte bilden eine sogenannte Pareto- optimale Front im Lösungsraum. Allerdings verfügen nicht alle Lösungen über gleichwertig wünschenswerte Eigenschaften. Die Verbesserung eines Funktionswertes kann zu einer er- heblichen Verschlechterung eines anderen Funktionswertes führen. Lösungen, die über eine ausgewogene Balance zwischen den einzelnen Zielen verfügen, finden sich an Wölbungen der Pareto-optimalen Front. In der Literatur wurden viele Herangehensweisen vorgestellt, um diese Bereiche der Pareto-optimalen Front zu finden, die auch als Knieregionen be- zeichnet werden. Pareto-Optimalität im engeren Sinne (proper Pareto optimality) ist ein mathematisches Konzept, das es erlaubt, die Differenzen der Funktionswerte zu begren- zen. Diese Abschlussarbeit schlägt ein neues Maß vor, das jedem Punkt auf der Pareto- optimalen Front einen qualitativen Zahlenwert zuordnet, und zwar auf Basis der Pareto- Optimalität im engeren Sinne. Das Konzept stellt eine praktische Herangehensweise dar, um Knie und bevorzugte Bereiche der Pareto-optimalen Front zu identifizieren. Die Ei- genschaften des Maßes werden in dieser Arbeit untersucht und es wird mit existierenden Definitionen von Kniepunkten verglichen. Evolutionäre Algorithmen werden seit langer Zeit für die erfolgreiche Lösung multikriterieller Optimierungsprobleme verwendet. Wir entlehnen evolutionäre Lösungsverfahren, die auf dem neuesten Stand der wissenschaft- lichen Erkenntnis sind, um neuartige Optimierungsalgorithmen zu entwickeln, die in der Lage sind Knieregionen zu identifizieren. Unsere Algorithmen erfüllen eine Vielzahl an Kriterien, die von besonderem Interesse sind, um Lösungen mit ausbalancierten Zielfunk- tionswerten zu finden. Sie sind fähig globale Knie zu finden, Knieregionen zu identifizieren oder beide Aufgaben gleichzeitig durchzuführen und hierbei noch immer eine repräsentati- ve Approximation der gesamten Pareto-optimalen Front abzuliefern. Wir verwenden meh- rere Testprobleme, die in der wissenschaftlichen Literatur häufig Anwendung finden, um die Leistungsfähigkeit unserer Algorithmen zu untersuchen. Diese Testprobleme verfügen über verschiedene Herausforderungen, die alle bei der Optimierung realer Problemstellun- gen angetroffen werden können. Wir zeigen, dass unsere Algorithmen erfolgreich die ihnen angedachten Aufgaben erfüllen und eine praktische Methode darstellen um Lösungen zu finden, die eine ausgewogene Balance zwischen ihren einzelnen Funktionswerten besitzen.