Optimization Algorithms in Physics

Von A. K. Hartmann u. H. Rieger. Wiley-VCH, Weinheim 2001. X + 372 S., Hardcover,  ISBN 3-527-40307-8

Optimierungsprobleme sind von zentraler Bedeutung in Technik und Wirtschaft, und entsprechende Modelle und Algorithmen zu ihrer Lösung sind seit langem eines der zentralen Themen von Informatik und Angewandter Mathematik. Aber auch in der Physik lassen sich manche Probleme, z.B. das Auffinden des Grundzustandes von Modellen für Spingläser, als ein Optimierungsproblem formulieren. Deshalb haben Methoden aus der statistischen Physik in der mathematischen Forschung zur Theorie der Optimierungsprobleme Eingang gefunden und umgekehrt finden zunehmend von Informatikern entwickelte, raffinierte Algorithmen in der statistischen Physik Anwendung. Diese Wechselwirkung wurde allgemein sichtbar, als Kirkpatrick et al. die vom langsamen Abkühlen der Spingläser inspirierte Methode des "simulated annealing" auf das Problem des Handlungsreisenden ("travelling salesman") erfolgreich anwendeten. Auf diesem Gebiet hat in den letzten 20 Jahren eine stürmische Entwicklung in der Forschung stattgefunden, und es ist das große Verdienst der Autoren des vorliegenden Buchs, hierüber die erste Monografie geschrieben zu haben, die sowohl die physikalischen Anwendungen als auch die Grundlagen aus der Informatik etwa gleichgewichtig darstellt.

Nach einer ganz kurzen Einführung in diese Problematik werden in den beiden folgenden Kapiteln die nötigen begrifflichen Grundlagen erläutert (Komplexitätstheorie, Graphentheorie) und anschließend einige diesbezügliche Algorithmen vorgestellt (z.B. um die Konnektivität von Graphen festzustellen, wie der Hoshen-Kopelman-Algorithmus für die "percolation clusters", "shortest path algorithms", etc.). Nach einer kurzen Erinnerung an die Begriffsbildung der statistischen Physik werden Methoden vorgestellt und anhand von Anwendungen entwickelt. Dazu zählen in den folgenden Kapiteln z.B. "Maximum Flow Algo rithms" zum Finden der Grundzustände des "Random Field Ising Modells", "minimum cost flow", um gerichtete Polymere, Vortexlinien etc. in Zufallspotentialen zu behandeln, "genetic algorithms" und "matching algorithms", die unter anderem an Spinglasmodellen exemplifiziert werden.

Nach einem kurzen Verweis auf Monte-Carlo-Methoden und "Branch and bound"-Methoden (hierzu zählt z.B. der "divide and conquer"-Algorithmus für das "vertex cover"-Problem) werden zuletzt auf über fünfzig Seiten diverse praktische Hinweise gegeben, die den Einstieg in die eigene Arbeit mit derartigen Algorithmen erleichtern sollen.

Naturgemäß ist dieses Buch wegen der komplexen Thematik nicht einfach zu lesen, aber es ist eine Fundgrube für Spezialisten, und sollte in keiner Bibliothek von Physik-
Insituten fehlen.

Prof. Dr. Kurt Binder, Institut für Physik, Universität Mainz