Kombination von physikalischen Algorithmen mit Methoden aus der Informatik zur Optimierung geometrischer Packprobleme

Das Ziel unseres Projektes besteht darin, einen Höchstleistungsalgorithmus zur Optimierung von allgemeinen Packproblemen zu entwickeln. Derartige Probleme sind zumeist so komplex, dass dafür keine exakten mathematischen Optimierungsverfahren existieren. Insofern soll ein heuristisches Verfahren erstellt werden, in dem bereits bekannte Optimierungsmethoden aus der Physik und der Informatik vereint und für diese Problematik weiterentwickelt werden. Hauptsächlich sollen geometrische Problemstellungen betrachtet werden, bei denen die Koordinaten für die zu packenden Objekte kontinuierliche Werte annehmen können, wodurch es erforderlich ist, globale Optimierungsverfahren, wie Simulated Annealing, mit lokalen Methoden, wie dem Gradientenabstieg, zu verbinden.

Als erstes Problem wurde hierfür eine in einem internationalen Wettbewerb definierte Aufgabenstellung betrachtet, die darin bestand, unterschiedlich große Kreisscheiben in einen Umkreis mit minimalem Radius zu packen. Es gelang uns, sämtliche während des Wettbewerbs von den daran teilnehmenden 155 Gruppen aus 32 Ländern aufgestellten Weltrekorde einzustellen bzw. zu schlagen, und dies zum Großteil deutlich. Damit konnten wir die Überlegenheit unseres neuen Algorithmus gegenüber den bisherigen Methoden nachweisen.

Wir planen nun, mit diesem Algorithmus weitere Packprobleme aus der Physik und der Informatik zu studieren. So sollen bidisperse Systeme kolloidaler Teilchen mit unterschiedlich großen Radien betrachtet und ihre optimale Anordnung unter der Nebenbedingung eingeschränkter Geometrie gefunden werden. Auf der anderen Seite wollen wir grundlegende Fragestellungen aus der Informatik und der Mathematik betrachten, wie das Kissing Number Problem, bei dem die maximale Zahl von gleich großen Kugeln in D Dimensionen gefunden werden soll, die eine Kugel in ihrer Mitte gleichzeitig berühren können.

Beitrag im Forschungsmagazin ...>