Mit vereinten Kräften intelligent rechnen

News: Mit vereinten Kräften intelligent rechnen

Wenn jemand wissen möchte, wie gut und schnell ein Computer rechnen kann, dann gibt er ihm eine harte Nuss zu knacken. Mitunter sind solche Rätsel allerdings auch für moderne Elektronenhirne zu schwierig, um sie mal eben an einem Wochenende zu lösen. In diese Kategorie fällt auch das Problem NUG30 - eine einzelne Workstation hätte dafür mehr als 100-mal länger gebraucht, als das Universum existiert. Ein Verbund von mehreren Hundert Computern fand dagegen mit einem intelligenten Algorithmus innerhalb weniger Tage die optimale Lösung.

NUG30 erblickte im Jahre 1968 das Licht der Welt. Seine Zweck war es, die Fähigkeiten von Computern zu testen, doch alle Kandidaten kapitulierten sang- und klanglos vor der enormen Komplexität dieses Optimierungsproblems. Dabei scheint die Aufgabenstellung recht einfach: Im Wesentlichen sollen 30 Anlagen so auf 30 feste Orte verteilt werden, dass die Kosten für den Transport von Gütern zwischen ihnen minimal ausfallen. Solche als quadratic assignment problem (QAP, etwa "quadratisches Zuweisungsproblem") bekannten Fragestellungen sind durchaus realitätsnah. Sie treten zum Beispiel bei der Planung von Krankenhäusern oder Fabriken auf.

Die Schwierigkeit von NUG30 lag in der großen Zahl der Punkte, denn die Menge der Möglichkeiten berechnet sich mit der Fakultät. Für NUG30 gibt es folglich 30!, also ungefähr 2,7*10³² Varianten. "Selbst wenn wir in jeder Sekunde eine Billion Anordnungen überprüfen könnten, würde der Vorgang rund 140-mal so lange dauern, wie es das Universum gibt", sagt dazu Kurt Anstreicher von der University of Iowa. Vor einem Jahr noch erschien es daher undenkbar, dass die aktuellen Generationen von Computern und Algorithmen eine optimale Lösung finden kann.

In der Tat erweist sich einfaches Durchprobieren schon bei viel kleineren Anzahlen unter 30 als ungeeignet. Zusammen mit seinem Kollegen Nate Bruxius entwickelte Anstreicher daher eine besondere Suchtechnik nach dem Prinzip des branch-and-bound. Bei dieser Methode wird der ursprüngliche Suchraum in kleinere Stücke zerteilt und in jedem davon die beste lokale Lösung ermittelt. Auf diese Weise fallen unsinnige und schlechte Varianten sehr schnell heraus.

Der Algorithmus war so gut, dass er die potentielle Rechenzeit auf einem Computer auf rund sieben Jahre reduziert hätte. Das war zwar schon deutlich weniger als das Alter des Universums, kam den beiden Wissenschaftlern aber immer noch zu lang vor. Noch schneller ging es, als die Forscher mit dem System Condor der University of Wisconsin die Arbeit auf eine Vielzahl von Rechnern an den verschiedensten Instituten und Universitäten verteilten. Im Durchschnitt nahmen 650 Computer, die gerade nichts anderes zu tun hatten, an der Mammutaufgabe teil, zeitweise waren es sogar über 1000.

Dieser geballten Intelligenz konnte selbst NUG30 nichts mehr entgegensetzen, und so war die optimale Lösung nach etwas weniger als einer Woche gefunden. "Das war eine der größten und komplexesten Berechnungen, die jemals durchgeführt wurden, um ein einzelnes Optimierungsproblem zu lösen", meint Steve Wright vom Argonne National Laboratory. "Es signalisiert eine neue Ära der Anwendung von Computernetzen, um komplizierte numerische Probleme zu lösen."

Siehe auch

Spektrum der Wissenschaft 4/99, Seite 76
"Die optimierte Odyssee"
(nur für Heft-Abonnenten online zugänglich)
Spektrum der Wissenschaft 3/93, Seite 42
"Toleranzschwelle und Sintflut: neue Ideen zur Optimierung"
(nur für Heft-Abonnenten online zugänglich)

Der Heidelberger Verlag Spektrum der Wissenschaft ist Betreiber dieses Portals. Seine Online- und Print-Magazine, darunter »Spektrum der Wissenschaft«, »Gehirn&Geist« und »Spektrum – Die Woche«, berichten über aktuelle Erkenntnisse aus der Forschung.