A New Meta-Heuristic for Improving General Multi-Start Procedures, With an Application to the Planar p-Median Location Problem

Stellen Sie sich vor, Sie versuchen den absolut besten Ort zu finden, um fünf neue Pizzaläden in einer riesigen, flachen Stadt zu bauen. Sie wollen die Gesamtdistanz minimieren, die alle laufen müssen, um ihr Stück zu bekommen. Dies ist das Planare p-Median-Problem. Es klingt einfach, aber die Stadt ist ein Labyrinth voller Fallen. Wenn Sie einfach einen Punkt wählen und herumlaufen, um nach einem besseren zu suchen, könnten Sie auf einem kleinen Hügel stecken bleiben und denken, es sei der höchste Gipfel, während sich direkt hinter dem nächsten Kamm ein massiver Berg befindet. In der mathematischen Fachsprache nennt man diese Hügel „lokale Optima“, und für dieses Problem könnte es Millionen davon geben.

Seit Jahrzehnten nutzen Forscher eine Strategie namens Multi-Start. Stellen Sie sich das so vor, als würden Sie 800.000 verschiedene Kundschafter anheuern (oder 800.000 separate Pizza-Lieferrouten starten), die in verschiedenen zufälligen Punkten der Stadt loslaufen. Jeder Kundschafter läuft, bis er auf einem lokalen Hügel stecken bleibt, und dann wählen Sie das beste Ergebnis aus all diesen Versuchen aus. Es funktioniert, aber es ist, als würde man eine Million Darts auf eine Zielscheibe werfen und hoffen, dass einer das Bullseye trifft.

Der neue Trick: Die „Elite-Truppe“ und die „Baby Schritte“

Die Autoren, Zvi Drezner und Jack Brimberg, schlagen eine clevere neue Meta-Heuristik (eine intelligente Regel zur Lösungsfindung) vor, die RPT heißt (was für Repeated POST steht). Sie argumentieren, dass man, anstatt nur das eine beste Ergebnis Ihrer 800.000 Kundschafter zu behalten, eine kleine „Elite-Truppe“ der 5 besten Ergebnisse behalten sollte, die Sie gefunden haben.

Hier liegt der Zauber:

1. Das Mix-and-Match: Nehmen Sie zwei verschiedene „Elite“-Lösungen (zwei verschiedene Sätze von Standorten für die Pizzaläden). Stellen Sie sie sich als Eltern vor.
2. Das Erzeugen von Nachkommen: Ziehen Sie eine Linie durch die Stadt. Nehmen Sie die Läden von Elternteil A, die auf der einen Seite der Linie liegen, und die Läden von Elternteil B, die auf der anderen Seite liegen. Sie haben soeben eine brandneue „Kind“-Lösung erschaffen – eine hybride Karte, die die besten Teile beider Eltern kombiniert.
3. Das Polieren: Lassen Sie den Standard-Verbesserungsalgorithmus auf diesem neuen Kind laufen. Vielleicht bleibt es an einem neuen Hügel hängen, aber es könnte ein höherer Hügel als zuvor sein.
4. Wiederholung: Wenn dieses neue Kind besser ist als Ihre aktuelle beste Lösung, behalten Sie es in der Elite-Truppe und versuchen erneut, es mit anderen zu mischen. Sie machen so lange weiter, bis Sie keine besseren „Kinder“ mehr finden können.

Das Papier bezeichnet die anfängliche Mischphase als POST (einen Post-Optimierungs-Schritt). Die vollständige RPT-Strategie geht einen Schritt weiter. Anstatt einen einzigen riesigen Block von 800.000 Kundschaftern auszuführen, unterteilt sie die Arbeit in kleinere Chargen. Sie führt den POST-Prozess auf einer kleineren Gruppe aus, findet die besten 5, mischt sie und wiederholt diesen gesamten Zyklus viele Male (speziell 700 Mal in ihren besten Tests).

Was sie herausgefunden haben (und was nicht)

Die Autoren testeten dies auf 48 verschiedenen Stadtkarten (24 mit gleichmäßig verteilten Kunden, 24 mit klumpigen, ungleichmäßigen Clustern). Sie verwendeten zwei verschiedene „Kundschafter“-Algorithmen: das klassische ALT (Coopers altmodische Methode) und eine neuere, ausgefeiltere Methode namens CLUST.

• Das Ergebnis: In jedem einzelnen der 48 Testfälle fand die RPT(CLUST)-Methode eine bessere Lösung als der Standard-Multi-Start-Ansatz. (Hinweis: Die Standard-RPT(ALT)-Methode verbesserte die Ergebnisse zwar signifikant, fand aber nicht für alle 48 Instanzen die bisher besten bekannten Lösungen; diese spezifische Errungenschaft gehört zur RPT-Methode in Kombination mit dem CLUST-Algorithmus).
• Die Geschwindigkeit: Hier ist der entscheidende Punkt. Die zusätzliche Zeit, die für dieses Mischen und Kombinieren aufgewendet wurde, war fast vernachlässigbar. Für die 24 gleichmäßigen Instanzen betrug die durchschnittliche Zeit für die Ausführung der Standard-ALT-Methode etwa 257,68 Minuten. Die RPT-Methode dauerte etwa 257,45 Minuten. Sie erhielten also tatsächlich bessere Ergebnisse in etwa der gleichen Zeit.
• Die Verbesserung: Für die Standard-ALT-Methode waren die Lösungen im Durchschnitt etwa 0,80 % schlechter als die bisher besten bekannten Ergebnisse. RPT reduzierte diesen Wert auf 0,53 %. In bestimmten Einzelfällen war die Verbesserung massiv und senkte den Fehler um über 60 % oder 70 %.

Als sie den neueren, langsameren CLUST-Algorithmus verwendeten, waren die Ergebnisse noch beeindruckender. Die Standard-CLUST-Methode fand bereits sehr gute Lösungen, aber RPT fand neue bestbekannte Lösungen für alle 24 gleichmäßigen Instanzen und alle 24 ungleichmäßigen Instanzen. Tatsächlich fand die RPT-Methode mit einer spezifischen Einstellung (I = 1.000) für die gleichmäßigen Tests in 14 von 24 Fällen die beste bekannte Lösung auf eigene Faust. Wenn man die Ergebnisse aus verschiedenen Einstellungen kombinierte (I=1.000 und I=10.000), fand sie in 21 von 24 Fällen die neue beste Lösung. Für die ungleichmäßigen Tests fand die RPT-Methode in 13 von 24 Fällen die beste bekannte Lösung auf eigene Faust, und wenn man die Ergebnisse verschiedener Einstellungen kombinierte, fand sie die beste bekannte Lösung in allen 24 Fällen.

Was sie ausschließen

Das Papier ist sich sehr klar darüber, was diese Methode nicht ist.

• Sie ist kein Zauberstab, der jedes Mal das perfekte globale Optimum garantiert. Die Autoren stellen explizit fest: „Wenn die Multi-Start-Heuristik die optimale Lösung findet, kann RPT sie natürlich nicht verbessern.“ Wenn Sie bereits die absolut beste Antwort gefunden haben, kann RPT sie nicht besser machen.
• Sie ist keine Methode, die erfordert, dass Sie den Computer tagelang laufen lassen. Sie argumentieren, dass die zusätzliche Zeit „vernachlässigbar“ ist.
• Sie schlagen auch vor, dass man nicht obsessiv nach den „perfekten“ Parametern (wie genau der Anzahl der Kundschafter) suchen muss. Sie testeten verschiedene Gruppengrößen (wie 1.000 vs. 10.000) und fanden heraus, dass diese ähnlich gut funktionierten, was darauf hindeutet, dass „jede Auswahl vernünftiger Parameter ähnlich gut funktionieren wird.“

Wie sicher sind sie sich?

Die Autoren sind sehr zuversichtlich in ihre Zahlen, da sie tatsächliche Simulationen auf einem Desktop-Computer mit einem Intel i7 Prozessor durchgeführt haben. Sie haben nicht nur geschätzt; sie haben die Ergebnisse gemessen.

• Sie verwendeten statistische Tests (gepaarte t-Tests) und fanden heraus, dass die Verbesserungen statistisch signifikant waren (mit p-Werten von bis zu $6,7 \times 10^{-5}$).
• Sie behaupten, dass die Methode für „allgemeine Multi-Start-Verbesserungsalgorithmen“ funktioniert, haben dies jedoch nur am Planaren p-Median-Problem demonstriert. Sie deuten an, dass sie auch für andere Probleme (wie Clustering) funktionieren könnte, haben dies aber noch nicht bewiesen.

Das Fazit

Man kann sich die alte Art, diese Probleme zu lösen, wie das Werfen von einer Million Darts vorstellen, in der Hoffnung, dass einer das Bullseye trifft. Die neue RPT-Methode ist wie das Nehmen der fünf besten Darts, die man bisher geworfen hat, das Halbieren der Darts und das Zusammenkleben der besten Hälften, um einen neuen Super-Dart zu bauen. Dann wirft man diesen neuen Dart. Wenn er besser trifft, behält man ihn und versucht es erneut.

Das Papier legt nahe, dass dieser „Mix-and-Match“-Ansatz eine leistungsstarke, kostengünstige Methode ist, um aus bestehenden Algorithmen bessere Lösungen herauszupressen, ohne Tage darauf warten zu müssen, dass der Computer fertig wird. Es verwandelt eine Suche nach „gut genug“ in eine Suche nach „großartig“ – und das fast umsonst.