Home |  ENGLISH |  Kontakt |  Impressum |  Datenschutz |  Anmelden |  KIT

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 ökonomischen, betriebswirtschaftlichen und ingenieurwissenschaftlichen Kontexten. Die gleichzeitige Optimierung mehrerer Ziele, die oft widersprüchlich zueinander sind, beinhaltet schwierige Herausforderungen, die einem nicht bei der Optimierung einer einzigen Funktion begegnen. 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 erheblichen 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 bezeichnet werden. Pareto-Optimalität im engeren Sinne (proper Pareto optimality) ist ein mathematisches Konzept, das es erlaubt, die Differenzen der Funktionswerte zu begrenzen. 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 Eigenschaften 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 wissenschaftlichen 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 Zielfunktionswerten 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äsentative Approximation der gesamten Pareto-optimalen Front abzuliefern. Wir verwenden mehrere 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 Problemstellungen 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.