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

Stel je voor dat je op zoek bent naar de absoluut beste plek om vijf nieuwe pizzeria's te bouwen in een enorme, vlakke stad. Je wilt de totale afstand minimaliseren die iedereen moet lopen om hun punt pizza te halen. Dit is het Planar p-Median Problem. Het klinkt simpel, maar de stad is een doolhof van vallen. Als je gewoon een plek kiest en rondloopt om te kijken of er een betere is, kun je vast komen te zitten op een kleine heuvel terwijl er net over de volgende rand een enorme berg ligt. In de wiskundige taal worden deze heuvels "lokale optima" genoemd, en voor dit probleem zouden er miljoenen kunnen zijn.

Decennialang hebben onderzoekers een strategie gebruikt genaamd Multi-Start. Denk hierbij aan het inhuren van 800.000 verschillende verkenners (of het starten van 800.000 aparte pizzabezorgroutes) die vanuit willekeurige punten door de stad rennen. Elke verkenner rent totdat hij vast komt te zitten op een lokale heuvel, en dan kies je het beste resultaat uit al die 800.000 verkenners. Het werkt, maar het is alsoal het gooien van een miljoen pijltjes op een bord in de hoop dat er één in de roos landt.

De Nieuwe Truc: Het "Elite Squad" en de "Baby Steps"

De auteurs, Zvi Drezner en Jack Brimberg, stellen een slimme nieuwe meta-heuristiek (een slimme regel voor het vinden van oplossingen) voor genaamd RPT (wat staat voor Repeated POST). Zij betogen dat je, in plaats van alleen het enkel beste resultaat van je 800.000 verkenners te bewaren, een kleine "Elite Squad" van de top 5 beste resultaten die je hebt gevonden, moet bewaren.

Hier is de magie:

1. Het Mix-en-Match-proces: Neem twee verschillende "Elite"-oplossingen (twee verschillende sets locaties voor pizzeria's). Stel je deze voor als ouders.
2. Het Creëren van Nakomelingen: Trek een lijn door de stad. Neem de winkels van Ouder A die aan de ene kant van de lijn liggen, en de winkels van Ouder B die aan de andere kant liggen. Je hebt zojuist een gloednieuwe "kind"-oplossing gecreëerd—een hybride kaart die de beste delen van beide ouders combineert.
3. Het Polijsten: Voer het standaard verbeteringsalgoritme uit op dit nieuwe kind. Misschien komt het vast te zitten op een nieuwe heuvel, maar het zou wel een hogere heuvel kunnen zijn dan voorheen.
4. Herhalen: Als dit nieuwe kind beter is dan je huidige beste resultaat, voeg je het toe aan de Elite Squad en probeer je het opnieuw te mengen met anderen. Je blijft dit doen totdat je geen betere "kinderen" meer kunt vinden.

De auteurs noemen de initiële mengfase POST (een post-optimalisatiestap). De volledige RPT-strategie gaat nog een stap verder. In plaats van één grote batch van 800.000 verkenners te draaien, verdeelt het de arbeid in kleinere batches. Het voert het POST-proces uit op een kleinere groep, vindt de beste 5, mengt ze, en herhaalt deze hele cyclus vele malen (specifiek 700 keer in hun beste tests).

Wat Ze Vonden (en Wat Ze Niet Vonden)

De auteurs hebben dit getest op 48 verschillende stadskaarten (24 met gelijkmatig verspreide klanten, 24 met klonterige, ongelijkmatige clusters). Ze gebruikten twee verschillende "verken"-algoritmen: de klassieke ALT (Cooper's oude methode) en een nieuwere, luxere methode genaamd CLUST.

• Het Resultaat: In elk enkel één van de 48 testgevallen vond de RPT(CLUST)-methode een betere oplossing dan de standaard Multi-Start aanpak. (Opmerking: de standaard RPT(ALT)-methode verbeterde de resultaten aanzienlijk, maar vond niet voor alle 48 instanties de best bekende oplossingen; deze specifieke prestatie behoort toe aan de RPT-methode wanneer deze wordt gecombineerd met het CLUST-algoritme).
• De Snelheid: Hier is de crux. De extra tijd die het kostte om dit mixen en matchen te doen, was bijna verwaarloosbaar. Voor de 24 uniforme instanties was de gemiddelde tijd om de standaard ALT-methode te draaien ongeveer 257,68 minuten. De RPT-methode duurde ongeveer 257,45 minuten. Ze behaalden dus betere resultaten in ongeveer dezelfde tijd.
• De Verbetering: Voor de standaard ALT-methode waren de oplossingen gemiddeld ongeveer 0,80% slechter dan de best bekende resultaten. RPT bracht dat terug naar 0,53%. In sommige specifieke gevallen was de verbetering enorm en werd de fout met meer dan 60% of 70% verminderd.

Toen ze het nieuwere, tragere CLUST-algoritme gebruikten, waren de resultaten nog indrukwekkender. De standaard CLUST-methode vond oplossingen die al erg goed waren, maar RPT vond nieuwe best bekende oplossingen voor alle 24 uniforme instanties en alle 24 niet-uniforme instanties. Sterker nog, voor de uniforme tests vond de RPT-methode met een specifieke instelling (I = 1.000) de best bekende oplossing in 14 van de 24 gevallen op zichzelf. Als je de resultaten van verschillende instellingen combineerde (I=1.000 en I=10.000), werd de nieuwe best bekende oplossing gevonden in 21 van de 24 gevallen. Voor de niet-uniforme tests vond de RPT-methode de best bekende oplossing in 13 van de 24 gevallen op zichzelf, en als je de resultaten van verschillende instellingen combineerde, vond het de best bekende oplossing in alle 24 gevallen.

Wat Ze Uitsluiten

Het artikel is heel duidelijk over wat deze methode niet is.

• Het is geen toverstaf die garandeert dat je elke keer het perfecte globale optimum vindt. De auteurs stellen expliciet: "Als de multi-start heuristiek de optimale oplossing vindt, dan kan RPT deze natuurlijk niet verbeteren." Als je al het absoluut beste mogelijke antwoord hebt gevonden, kan RPT het niet beter maken.
• Het is geen methode die vereist dat je de computer dagenlang langer laat draaien. Ze beweren dat de extra tijd "verwaarloosbaar" is.
• Ze suggereren ook dat je niet obsessief op zoek hoeft te gaan naar de "perfecte" parameters (zoals exact hoeveel verkenners je moet gebruiken). Ze testten verschillende groepsgroottes (zoals 1.000 versus 10.000) en vonden dat deze vergelijkbaar presteerden, wat suggereert dat "elke selectie van redelijke parameters vergelijkbaar goed zal presteren."

Hoe Zeker Zijn Ze?

De auteurs zijn zeer zelfverzekerd over hun cijfers omdat ze daadwerkelijke simulaties hebben gedraaid op een desktopcomputer met een Intel i7-processor. Ze hebben niet alleen geraden; ze hebben de resultaten gemeten.

• Ze gebruikten statistische tests (gepaarde t-toetsen) en vonden dat de verbeteringen statistisch significant waren (met p-waarden zo laag als $6,7 \times 10^{-5}$).
• Ze beweren dat de methode werkt voor "algemene multi-start verbeteringsalgoritmen", maar ze hebben dit alleen gedemonstreerd op het Planar p-Median probleem. Ze suggereren dat het op andere problemen (zoals clustering) zou kunnen werken, maar ze hebben dat nog niet bewezen.

De Kernboodschap

Denk aan de oude manier om deze problemen op te lossen als het gooien van een miljoen pijltjes in de hoop dat er één in de roos landt. De nieuwe RPT-methode is als het nemen van de vijf beste pijltjes die je tot nu toe hebt gegooid, ze doormidden snijden, en de beste helften aan elkaar te plakken om een nieuwe, super-pijl te maken. En dan gooi je die nieuwe pijl. Als hij beter landt, houd je hem en probeer je het opnieuw.

Het artikel suggereert dat deze "mix-en-match"-aanpak een krachtige, goedkope manier is om bestaande algoritmen meer uit te persen zonder dat je dagenlang hoeft te wachten tot de computer klaar is. Het verandert een "goed genoeg" zoektocht in een "geweldige" zoektocht, bijna gratis.