A New Meta-Heuristic for Improving General Multi-Start Procedures

In der Welt der Optimierung stehen Wissenschaftler und Ingenieure oft vor einem Problem, das einfach aussieht, aber ein Labyrinth von Möglichkeiten verbirgt: wie man eine Gruppe von Einrichtungen, wie etwa Lagerhäuser oder Funkmasten, platziert, um eine verstreute Bevölkerung so effizient wie möglich zu bedienen. Das Ziel ist es, die zurückgelegte Gesamtdistanz zu minimieren, die Menschen zurücklegen müssen, um die nächstgelegene Einrichtung zu erreichen. Dies ist als das p-Median-Problem bekannt. Da die Landschaft der möglichen Lösungen so weitläufig und uneben ist, gefüllt mit unzähligen lokalen Gipfeln, die wie die beste Antwort aussehen, aber eigentlich nur Fallen sind, verlassen sich Forscher auf eine Strategie, die man Multi-Start-Verfahren nennt. Stellen Sie sich vor, Sie versuchen, den höchsten Punkt in einer nebligen Gebirgskette zu finden, indem Sie einen Wanderer an einem zufälligen Ort absetzen, ihn aufsteigen lassen, bis er nicht mehr höher steigen kann, und diesen Prozess dann tausende Male von verschiedenen Startpunkten aus wiederholen. Der beste Gipfel, der unter all diesen Versuchen gefunden wurde, ist meistens die Antwort. Doch selbst mit tausenden Versuchen könnten die Wanderer den wahren Gipfel verpassen, weil das Gelände so komplex ist.

Zwei Forscher, Zvi Drezner und Jack Brimberg, haben eine neue Methode vorgeschlagen, die diesen digitalen Wanderern helfen soll, bessere Gipfel zu finden, ohne dass sie wesentlich mehr Zeit für die Suche benötigen müssen. Sie nennen diese neue Technik POST. Anstatt einfach nur die Suche tausende Male durchzuführen und das einzelne beste Ergebnis auszuwählen, nimmt POST die besten paar Ergebnisse aus einer Gruppe von Suchen und nutzt diese, um neue, hybride Startpunkte zu erstellen. Es ist ein wenig so, als würde man die stärksten Eigenschaften der besten Wanderer nehmen und sie kombinieren, um einen neuen Führer zu erschaffen, der den Aufstieg von einem vielversprechenderen Ort aus beginnt. Die Forscher testeten diese Methode an achtundvierzig verschiedenen Szenarien, die bis zu zehntausend Nachfragepunkte und einhundert Einrichtungen umfassten. Sie fanden heraus, dass dieser neue Ansatz die besten bekannten Lösungen in jedem einzelnen Testfall konsistent verbesserte und bessere Antworten in etwa der gleichen Zeit fand, die für die Standard-Suche benötigt wurde.

Die Kernherausforderung liegt in der Natur des Problems selbst. Wenn man versucht, Einrichtungen auf einer flachen Ebene zu platzieren, um eine Gruppe von Punkten zu bedienen, ist die mathematische Landschaft unglaublich zerklüftet. Sie enthält Millionen von lokalen Optima – das sind Lösungen, die besser sind als ihre unmittelbaren Nachbarn, aber nicht die besten insgesamt. Standardalgorithmen bleiben oft an diesen lokalen Gipfeln hängen. Der traditionelle Weg, um dies zu überwinden, besteht darin, den Suchalgorithmus einfach viele Male auszuführen, wobei man von zufälligen Orten aus startet, in der Hoffnung, dass einer dieser zufälligen Starts nah genug am wahren globalen Optimum landet, um den Algorithmus den Aufstieg nach oben ermöglichen zu können. Die Forscher verwendeten einen leistungsstarken Verbesserungsalgorithmus namens CLUST, der derzeit eines der effektivsten Werkzeuge für diese Aufgabe ist, und führten ihn aus achtzigtausend verschiedenen Startpunkten in ihren ersten Tests aus.

Die Innovation in POST liegt in dem, was nach diesen anfänglichen Durchläufen geschieht. Anstatt aufzuhören, sobald das beste Ergebnis gefunden wurde, nehmen die Forscher die fünf besten unterschiedlichen Lösungen aus einer kleineren Gruppe von Durchläufen und behandeln sie als „Eltern“. Sie erschaffen dann neue „Nachkommen“-Lösungen, indem sie die Standorte der Einrichtungen dieser Eltern mischen. Um dies zu tun, ziehen sie eine imaginäre Linie durch das Zentrum der kombinierten Gruppe von Einrichtungen. Einrichtungen des ersten Elternteils, die auf einer Seite der Linie liegen, werden mit Einrichtungen des zweiten Elternteils gepaart, die auf der anderen Seite der Linie liegen. Dies erzeugt eine neue Konfiguration, die die Stärken beider Elternteile in sich vereint. Die Forscher generieren mehrere dieser neuen Konfigurationen, führen den Verbesserungsalgorithmus auf ihnen aus und sehen nach, ob diese zu noch besseren Lösungen führen. Wenn dies der Fall ist, wiederholt sich der Prozess und nutzt die neuen besten Lösungen als Eltern für die nächste Runde des Mischens.

Dieser Zyklus aus Mischen und Verbessern wird in mehreren Batches (Chargen) wiederholt. Die Forscher testeten verschiedene Möglichkeiten, diese Batches zu organisieren. In einem Aufbau führten sie die initiale Suche tausendmal durch, nahmen die fünf besten Ergebnisse, mischten sie und wiederholten diesen gesamten Zyklus siebzigmal. In einem anderen Fall führten sie die Suche zehntausendmal durch und wiederholten den Zyklus achtmal. In einem dritten Fall führten sie die vollen achtzigtausend Durchläufe in einem einzigen Batch durch. Die Ergebnisse zeigten ein klares Muster: Das Aufteilen der Suche in kleinere Batches und das wiederholte Verfeinern der in jedem Batch gefundenen besten Ergebnisse lieferte bessere Resultate als das Ausführen der vollständigen Suche auf einmal. Die Methode, die tausend initiale Suchen durchführte und den Verfeinerungsprozess siebzigmal wiederholte, erzielte die konsistentesten Verbesserungen und fand bessere Lösungen als jede bisherige Methode für alle achtundvierzig Testfälle.

Die Forscher stellten sorgfältig sicher, dass die zusätzliche Zeit, die für diesen Mischprozess aufgewendet wurde, vernachlässigbar war. Da die durch das Mischen neu erzeugten Startpunkte bereits qualitativ hochwertige Lösungen sind, konvergiert der Verbesserungsalgorithmus viel schneller auf ein lokales Optimum als bei einem zufälligen Startpunkt. Die gesamte Zeit, die für die POST-Methode benötigt wurde, war nur geringfügig länger als die der Standard-Multi-Start-Suche, doch sie fand konsistent überlegene Ergebnisse. Für die uniformen Testfälle verbesserte die neue Methode die besten bekannten Lösungen um durchschnittlich 0,062 Prozent, und für die nicht-uniformen Fälle um 0,[]0,068 Prozent. Während diese Prozentsätze klein erscheinen mögen, stellen sie im Kontext der großflächigen Logistik und Anlagenplanung signifikante Einsparungen bei Distanz und Kosten dar.

Die Studie untersuchte auch die Grenzen dieses Ansatzes. Die Forscher merkten an, dass, wenn das Multi-Start-Verfahren bereits die absolut optimale Lösung gefunden hätte, die POST-Methode diese nicht weiter verbessern könnte. Da das p-Median-Problem jedoch dafür bekannt ist, Millionen von lokalen Optima zu besitzen, ist es höchst unwahrscheinlich, dass eine Standard-Suche durch Zufall die perfekte Antwort findet. Die Tatsache, dass POST die Ergebnisse in jedem einzelnen Fall verbesserte, deutet darauf hin, dass die Standard-Suchen tatsächlich an lokalen Gipfeln hängen blieben, denen POST in der Lage war zu entkommen. Die Forscher beobachteten auch, dass eine Erhöhung der Anzahl der initialen Suchen in einem einzelnen Batch nicht immer zu besseren Ergebnissen führte; tatsächlich schnitten die kleineren Batches mit mehr Wiederholungen besser ab. Dies stützt ein Prinzip, das sie „Less is More“ nennen, welches besagt, dass es effektiver ist, einige vielversprechende Bereiche tiefgehend und wiederholt zu erforschen, als einmal ein möglichst weites Netz auszuwerfen und auf das Beste zu hoffen.

Der Erfolg von POST war nicht auf eine Art von Problem beschränkt. Die Forscher testeten es sowohl auf uniformen Instanzen, bei denen die Nachfragepunkte gleichmäßig verteilt sind, als auch auf nicht-uniformen Instanzen, bei denen die Punkte auf bestimmte Weise geclustert sind. In beiden Szenarien übertraf die Methode bisherige Techniken, einschließlich der besten Ergebnisse anderer aktueller Studien, die Monate an Rechenzeit beansprucht hatten. Die neue Methode erreichte diese Ergebnisse in einem Bruchteil der Zeit, wobei die gesamte Laufzeit für die effektivste Konfiguration etwa dreizehn Tage für den gesamten Satz von Tests betrug. Die Forscher lieferten auch eine Formel, um abzuschätzen, wie die Laufzeit mit der Größe des Problems skaliert, wobei sie feststellten, dass bei einer Verzehnfachung der Anzahl der Nachfragepunkte die benötigte Zeit um etwa das Fünfzehn- bis Siebzehnfache anstieg, während die Verdoppelung der Anzahl der Einrichtungen die Zeit um weniger als den Faktor zwei erhöhte.

Mit Blick auf die Zukunft schlagen die Autoren vor, dass diese Technik auf andere Optimierungsprobleme angewendet werden könnte, die derzeit mittels Multi-Start-Ansätzen gelöst werden, wie etwa das Clustering von Datenpunkten oder die Partitionierung von Netzwerken. Sie schlagen vor, dass die zukünftige Forschung verschiedene Wege der Auswahl der „Eltern“-Lösungen untersuchen könnte, indem sie diese nicht nur nach ihrer Qualität, sondern auch nach ihrer Differenz zueinander auswählt, um eine vielfältigere Suche zu gewährleisten. Sie schlagen auch vor, dass die Erhöhung der Anzahl der Lösungen im Elite-Set, das zum Mischen verwendet wird, noch bessere Ergebnisse erzielen könnte, was jedoch mehr Rechenleistung erfordern würde. Die Studie kommt zu dem Schluss, dass durch das Hinzufügen eines einfachen Post-Optimierungs-Schritts zu bestehenden Algorithmen Forscher die Qualität der Lösungen signifikant verbessern können, ohne einen prohibitiven Mehraufwand zu betreiben, was ein leistungsstarkes neues Werkzeug zur Bewältigung einiger der komplexesten räumlichen Planungsprobleme bietet.