Mainzer Wissenschaftler schlagen Weltrekorde zur besten Anordnung von Kreisscheiben
23.03.2009
Wie belade ich ein Auto, damit alles hineinpasst? Wie kann ich ein Päckchen so packen, dass es gut ausgefüllt ist? Wie viel Geschirr geht in einen Küchenschrank? Wenn es ums Packen geht, sind Mainzer Wissenschaftler unschlagbar. Die Weltrekorde, die bei einem internationalen Wettbewerb um die beste Lösung für ein spezielles Packproblem aufgestellt wurden, konnten sie allesamt einstellen oder schlagen. "Wir arbeiten in einem interdisziplinären Projekt zwischen theoretischer Physik und Informatik seit einiger Zeit daran, einen möglichst optimalen Computer-Algorithmus für Packprobleme zu entwickeln", erklärt Dr. Johannes Josef Schneider vom neu gegründeten Schwerpunkt für rechnergestützte Forschungsmethoden in den Naturwissenschaften an der Johannes Gutenberg-Universität Mainz.
Als die Wissenschaftler dann eher zufällig von dem Wettbewerb kurz vor dessen Ende erfuhren, konnten sie nur noch einen Weltrekord aufstellen, ansonsten waren die Ergebnisse einiger anderer Gruppen etwas besser. Getrieben vom Ehrgeiz, die weltweit besten Gruppen, die teilweise schon seit vielen Jahren an derartigen Problemen arbeiteten, schlagen zu wollen, entwickelten sie ihre Computer-Algorithmen weiter und konnten nun die während des Wettbewerbs aufgestellten Weltrekorde unterbieten, und dies zum Großteil deutlich. Die Arbeit wurde in dem renommierten Fachjournal für statistische Physik Physical Review E veröffentlicht.
Bei dem Wettbewerb ging es darum, runde Scheiben von unterschiedlicher Größe so in einem Kreis anzuordnen, dass sie möglichst wenig Platz brauchen. Der Radius des großen Kreises, in den die kleineren Kreisscheiben hineingepackt werden, sollte also möglichst klein sein. 155 Gruppen aus 32 Ländern haben an dem Wettbewerb teilgenommen und ihre Lösungen eingereicht. Für die Problemstellungen mit 24 bis höchstens 50 unterschiedlich großen Kreisscheiben haben Schneider, Prof. Dr. Elmar Schömer vom Institut für Informatik und der Diplomand André Müller die mit Abstand besten Lösungen gefunden. Bei den kleineren Problemstellungen mit 23 Kreisscheiben und weniger lagen sie mit den bisher besten Lösungen gleichauf – was nahelegt, dass es dafür keine noch bessere Lösung geben kann. "Für diese Problemstellung mit den unterschiedlich großen Kreisscheiben haben wir somit den weltbesten Pack-Algorithmus entwickelt", fasst Schneider zusammen.
Jedoch betrachten die Wissenschaftler nicht nur derartige wissenschaftliche Problemstellungen, sondern übertragen ihre Algorithmen auch auf praktische Anwendungen. So untersucht die Gruppe beispielsweise für einen großen deutschen Automobilhersteller, wie das Volumen eines Kofferraums am besten gemessen werden kann. Nach der von der Europäischen Union vorgegebenen Norm müssen Tetrapaks einer bestimmten Größe so in einen vorgegebenen Kofferraum gepackt werden, dass der Raum so gut es geht ausgefüllt ist. "Bisher wird noch mit Holzklötzen von Hand ausprobiert, so viele Tetrapaks wie möglich unterzubringen", erklärt Schneider. In den USA müssten dagegen Koffersets von Superreichen möglichst optimal in den Kofferraum gepackt werden, weshalb die Angabe, wie viel Platz im Kofferraum ist, zwischen deutschen und amerikanischen Werbeprospekten nicht ganz übereinstimme. Die Wissenschaftler haben nun aufgrund des Vergleichs mit den Wettbewerbsergebnissen die Gewissheit, dass ihr Algorithmus auch diese Kofferraum-Packprobleme optimal lösen kann.
Aber auch für ganz andere Fragestellungen lassen sich derartige Optimierungsalgorithmen einsetzen. So können zum Beispiel die Fahrten eines Milchwerks zu den Bauernhöfen so optimiert werden, dass die Strecken, die die Lastwagen zur Milchabholung zurücklegen, möglichst kurz sind – je nachdem, in welcher Reihenfolge die Bauernhöfe angefahren werden. Ein anderes Beispiel aus der Automobilindustrie ist die Endmontage von Fahrzeugen: Mit Hilfe des Computers kann ermittelt werden, in welcher Reihenfolge die einzelnen vorgefertigten Karosserien aufs Fließband gebracht werden müssen, damit möglichst kostengünstig produziert werden kann. Auch für derartige Problemstellungen gibt es Wettbewerbe, die teilweise sogar von Firmen veranstaltet werden. So belegte Schneider bereits als Doktorand in Regensburg im Alleingang in einem Wettbewerb, den ein bayerischer Automobilhersteller vor einigen Jahren ausgeschrieben hatte, den vierten Platz und ließ dabei Firmen, die im Optimierungsbereich etabliert sind und ganze Gruppen von Mitarbeitern für den Wettbewerb beschäftigten, weit hinter sich.
Das beste Lösungsverfahren finden die Mainzer Wissenschaftler, indem sie sich durch Annäherung an die Lösung herantasten. Dazu werden mit Monte-Carlo-Simulationen – benannt nach Monacos Stadtteil mit dem berühmten Spielcasino – zufällige Ereignisse am Computer simuliert. "Das geht wie im Casino, wo zufällig die Zahl zwölf am Roulette-Tisch fällt, so erzeugt der Computer zufällig eine Anordnung", erläutert Schneider. Im Beispiel mit den Kreisscheiben versetzt der Rechner dann eine der Scheiben irgendwo hin und vergleicht diese neue Lösung mit der vorherigen. Diese Veränderung wird rückgängig gemacht, wenn das Ausmaß der Verschlechterung zu groß ist, ansonsten bleibt es bei der neuen Lösung. "Auf diese Weise verändert man die Anordnung der Kreisscheiben Schritt um Schritt, so lange, bis das Endergebnis vorliegt."
Auffallend ist, dass unterschiedliche Lösungen, die fast so gut sind wie die beste Lösung, oft etwas gemeinsam haben. Schneider zufolge findet man bei verschiedensten Problemstellungen derartige identische Strukturen bei unterschiedlichen Lösungen, was er auch in dem gemeinsam mit Prof. Scott Kirkpatrick von der Hebrew University of Jerusalem, Israel, verfassten Buch "Stochastic Optimization" (Springer-Verlag, 2006) beschrieb. Im Kreisscheiben-Wettbewerb etwa liegen bei den guten Lösungen die größten Kreisscheiben häufig nahe beieinander. Was genau die guten Lösungen und die beste Lösung gemeinsam haben, untersuchen die Wissenschaftler in einer eigenen Arbeit, die eben in der Physical Review E erschienen ist.
Der Schwerpunkt für rechnergestützte Forschungsmethoden in den Naturwissenschaften wurde von der Johannes Gutenberg-Universität neu eingerichtet, um die herausragende Stellung der Naturwissenschaften in Mainz durch eine leistungsfähige und innovative Informatik noch besser zu unterstützen.