Effiziente parallelisierbare physikalische Optimierungsverfahren

Betreuer: Prof. Dr. Ingo Morgenstern
Eingereicht: 14. Mai 1999
Kolloquium: 21. Juli 1999


Zusammenfassung der Dissertation von Johannes Josef Schneider

In dieser Arbeit wurde aufgezeigt, wie man mit Hilfe neuer parallelisierbarer Algorithmen im Bereich der physikalischen Optimierung effizient optimale Lösungen für verschiedene Probleme erhält. Dabei decken die untersuchten Aufgabenstellungen einen weiten Bereich von der Touren- und Produktionsplanung über die Verteilungs- und Personaleinsatzplanung bis hin zu Spinglas-Modellen und Problemen aus der Volkswirtschaft und der Nachrichtentechnik ab. Für viele Benchmark-Instanzen konnten die exakten Optima reproduziert bzw. die bisherigen Weltrekorde gebrochen werden.

Im ersten Teil der Arbeit wurden nach einer Einordnung der physikalisch motivierten Verfahren Simulated Annealing, Threshold Accepting und Great Deluge Algorithm in den Bereich der herkömmlichen Optimierungsmethoden die Unterschiede zwischen diesen drei Algorithmen diskutiert und die im folgenden betrachteten thermodynamischen Größen eingeführt. Zudem wurden verschiedene Möglichkeiten zur Behandlung von Nebenbedingungen von der Einarbeitung bei der Modellierung bis hin zur Methode der Straffunktionen und Strategien zur Parallelisierung dieser Algorithmen, wie z.B. der Aufteilung der Problemstellung oder dem Arbeiten auf Kopien, präsentiert.

Im zweiten Teil wurde zunächst das Problem des Handlungsreisenden vorgestellt, anhand dessen alle in dieser Arbeit verwendeten Algorithmen auf ihre Eigenschaften und auf die mit ihnen erreichbare Güte der Ergebnisse hin untersucht wurden. Ausgehend von den klassischen Methoden Random Walk, Greedy, Simulated Annealing, Threshold Accepting und Great Deluge Algorithm wurden verschiedene neue Möglichkeiten zur Effizienzsteigerung dieser Algorithmen eingeführt. Dabei wurde aufgezeigt, daß das in Computational Physics oft verwendete Bild eines temperaturähnlichen Kontrollparameters, mit dessen Hilfe ein zu optimierendes System schrittweise in einen optimalen Zustand übergeführt wird, viel weiter als bislang gefaßt werden kann: anstatt dem Monte Carlo-Wanderer die Möglichkeit zu geben, über Barrieren in der Energielandschaft zu klettern, kann man durch eine Suchraumglättung diese Energiebarrieren auch entfernen, sodaß man bereits mit dem Greedy-Verfahren, das nur Verbesserungen erlaubt, sehr gute Ergebnisse erhalten kann. Des weiteren wurden verschiedene Möglichkeiten betrachtet, wie man durch das Einführen weiterer konstanter oder variabler Kontrollparameter Optimierungsergebnisse sukzessive verbessern kann. So wurde eine Bouncing-Temperatur eingeführt, bis zu der das System immer wieder instantan aufgewärmt und dann langsam wieder abgekühlt wurde. Bei geeigneter Wahl dieser Temperatur unterhalb des Peaks der spezifischen Wärme konnten deutliche Verbesserungen erzielt werden. Die ebenfalls neu entwickelte Methode, einen größeren Teil des Systems zu zerstören und gezielt wiederaufzubauen, erbrachte einen deutlichen Vorsprung vor dem gewöhnlichen Local Search-Ansatz. Anschließend wurde gezeigt, daß man diesen Wiederaufbau genausogut von den klassischen Methoden erledigen lassen kann. Dabei kann das Ausmaß der Zerstörung selbst als Kontrollparameter dienen, wovon die Qualität der Ergebnisse abhängt. Danach wurde für einige der verwendeten Methoden exemplarisch aufgezeigt, wie man durch einen einfachen Parallelisierungsansatz, der ein Konzept zur Feststellung eines Gleichgewichts verwendet, große Mengen an Rechenzeit einsparen und dabei die Qualität der Ergebnisse zumindest in etwa konstant halten kann. Bei einem vergleichbaren Aufwand von Rechenzeit lassen sich sogar deutliche Verbesserungen erzielen. Schließlich bildet das neu entwickelte Searching for Backbones-Verfahren den Höhepunkt dieser Arbeit: es vergleicht unterschiedliche gute Lösungen für ein Problem und sucht darin nach gleichen Teilstücken. Diese werden in der Folge als optimal angesehen, wodurch sie nicht mehr verändert werden dürfen. Dadurch wird die Komplexität eines Problems so weit reduziert, daß sich relativ schnell große Verbesserungen erzielen lassen. Mit diesem Verfahren wurden mehr als eine Million verschiedener optimaler Lösungen für das hochentartete Problem der 442 Bohrlöcher auf einer Computerplatine erzeugt, mit denen die 89 Teilstücke gefunden werden konnten, aus denen sich alle optimalen Lösungen zusammensetzen lassen.

Im dritten Teil dieser Arbeit wurden dann diese Verfahren auf weitere Problemstellungen aus Operations Research und Physik angewendet. Für das Tourenplanungsproblem mit Kapazitätsrestriktionen konnten dabei mit Hilfe des Searching for Backbones-Algorithmus viele neue Weltrekorde für Benchmark-Instanzen aufgestellt werden. Dann wurde für aus der Praxis stammende Aufgaben aus der Produktions-, Verteilungs- und Personaleinsatzplanung vorgeführt, wie es bei geschickter Modellierung bereits mit herkömmlichen Methoden wie Simulated Annealing und Threshold Accepting möglich ist, gültige und in der Praxis umsetzbare Lösungen zu erzielen. Ferner wurde für eines der am meisten betrachteten Optimierungsprobleme aus dem Bereich Computational Physics, das Problem der Grundzustandssuche von Spingläsern, aufgezeigt, wie man die im zweiten Teil eingeführten Verfahren Ruin & Recreate und Searching for Backbones so für diese Problemstellung abwandeln kann, daß man damit verbesserte Lösungen erzielt. Sodann wurde anhand des Bernasconi-Modells demonstriert, daß sich physikalische Optimierungsverfahren auch für schwierige Probleme eignen, deren Energielandschaft einem Golfplatz ähnelt. Durch das Ramsey-Problem, das die einzelnen Teile einer Volkswirtschaft nach ihrer Wichtigkeit ordnet, konnte danach eine Brücke von den anfangs betrachteten Abfolge-Problemen zum Spinglas-Bereich geschlagen werden. Schließlich wurde für die Error Correcting Codes noch vorgeführt, daß man Bouncing auch dazu verwenden kann, die Größe eines Systems selbst zu optimieren.

Insgesamt wurde damit aufgezeigt, wie sich effiziente parallelisierbare physikalische Optimierungsverfahren universell zur Suche nach der günstigsten Lösung für die unterschiedlichsten Problemstellungen einsetzen lassen.


Komprimierte PostScript-Version der Doktorarbeit

Homepage von Johannes Schneider


Mail an Johannes Schneider