The State Space of Complex Systems

In dieser Arbeit wird eine Beschreibung von Monte-Carlo-Verfahren zur Lösung komplexer Optimierungsaufgaben mit Hilfe von Markov-Ketten durchgeführt. Nach einer kurzen Einführung werden Lösungsmenge solcher Aufgaben und der physikalische Zustandsraum komplexer Systeme identifiziert. Zunächst wird die Dynamik von Zufallswanderern im Zustandsraum mit Hilfe von Master-Gleichungen modelliert. Durch Einführung von Performanzkriterien können verschiedene Optimierungsstrategien quantitativ miteinander verglichen werden. Insbesondere wird das Verfahren Extremal Optimization vorgestellt, dass ebenfalls als Markov-Prozess verstanden werden kann. Es wird bewiesen, dass eine im Sinne der genannten Kriterien beste Implementierung existiert. Da diese von einem sogenannten Fitness Schedule abhängt, wird dieser für kleine Beispielsysteme explizit berechnet. Daran anschließend wird die Zustandsdichte komplexer Systeme betrachtet. Nach einem kurzen Überblick über vorhandene Methoden folgt eine detaillierte Untersuchung des Verfahrens von Wang und Landau. Numerische und analytische Hinweise werden gegeben, nach denen dieser Algorithmus innerhalb seiner Klasse wahrscheinlich der Optimale ist. Eine neue Methode zur Approximation der Zustandsdichte wird vorgestellt, die insbesondere für die Untersuchung komplexer Systeme geeignet ist. Abschließend wird ein Ausblick auf zukünftige Arbeiten gegeben