Investigating Distributed Approaches for Solving Discrete, Multistage Optimization Problems

Diploma Thesis from the year 2004 in the subject Computer Science - Commercial Information Technology, grade: 1,3, University of Siegen, language: English, abstract: Im Mittelpunkt dieser Diplomarbeit steht die Optimierung mehrstuger Probleme. Hinführend werden zunächst die theoretischen Hintergründe der Optimierung erläutert. Im Fokus der Erläuterungen steht die Unterscheidung der simulationsbasierten und der verteilten Optimierung. Simulationsbasierte Optimierungen lassen keine algebraische Berechnung von Zielfunktionswerten zu. Diese erfordern besondere Lösungsstrategien, da bei der Auswertung keine Ableitungsinformationen entstehen. Des Weiteren beschäftigt sich diese Diplomarbeit mit der Untersuchung und Implementierung von Lösungsstrategien für die Auswertung der Problemklasse der ableitungsfreien oder auch direkten Suchverfahren. Weiterhin wird auf die spezielle Problemstellung der Mehrstugkeit eingegangen, bei welcher nicht nur Zielfunktionswerte, sondern auch eine optimale Stufenzahl ermittelt werden müssen. Dabei sind die Ergebnisse der nächsten Stufe stets abhängig von denen der Stufen davor. Die bei der Auswertung von Punkten erforderliche hohe Rechenleistung bei der simulationsbasierten Optimierung lässt Einprozessorsysteme während der Optimierung schnell an zeitliche Grenzen stoÿen. Aus diesem Grund werden in der vorliegenden Arbeit zwei Algorithmen vorgestellt und implementiert, die vollständig verteilt rechnen und skalierbar sind. Kapitel 5 beschäftigt sich mit Scatter Search, einem etablierten Verfahren zur Lösung nichtlinearer, ableitungsfreier Probleme. Im Zuge dieser Arbeit wurde das Verfahren zur Lösung zweier Testprobleme eingesetzt, die Ergebnisse nden sich in Kapitel 6. [...]