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

In de wereld van optimalisatie worden wetenschappers en ingenieurs vaak geconfronteerd met een probleem dat er eenvoudig uitziet, maar een labyrint van mogelijkheden verbergt: hoe plaats je een reeks faciliteiten, zoals magazijnen of zendmasten, om een verspreide populatie zo efficiënt mogelijk te bedienen. Het doel is om de totale afstand die mensen moeten afleggen om de dichtstbijzijnde faciliteit te bereiken, te minimaliseren. Dit staat bekend als het p-mediaanprobleem. Omdat het landschap van mogelijke oplossingen zo uitgestrekt en ongelijkmatig is, vol met talloze lokale pieken die lijken op het beste antwoord maar eigenlijk slechts vallen zijn, vertrouwen onderzoekers op een strategie die een multi-start-procedure wordt genoemd. Stel je voor dat je probeert de hoogste top in een mistig berglandschap te vinden door een wandelaar op een willekeurige plek te laten beginnen, hem te laten klimmen tot hij niet hoger kan, en dit proces vervolgens duizenden keren te herhalen vanaf verschillende startpunten. De beste piek die tijdens al die pogingen wordt gevonden, is meestal het antwoord. Zelfs met duizenden pogingen kunnen de wandelaars de ware top missen omdat het terrein zo complex is.

Twee onderzoekers, Zvi Drezner en Jack Brimberg, hebben een nieuwe methode voorgesteld om deze digitale wandelaars te helpen betere pieken te vinden zonder dat ze aanzienlijk meer tijd nodig hebben voor het zoeken. Ze noemen deze nieuwe techniek POST. In plaats van simpelweg de zoektocht duizenden keren uit te voeren en het enkel beste resultaat te kiezen, neemt POST de beste paar resultaten uit een batch zoekopdrachten en gebruikt deze om nieuwe, hybride startpunten te creëren. Het is een beetje alsoals het nemen van de sterkste eigenschappen van de beste wandelaars en deze combineren om een nieuwe gids te creëren die de klim vanuit een veelbelovendere locatie begint. De onderzoekers hebben deze methode getest op achtenveertig verschillende scenario's met tot wel tienduizend vraagpunten en honderd faciliteiten. Ze kwamen tot de conclusie dat deze nieuwe aanpak consequent de best bekende oplossingen verbeterde voor elk enkele testgeval, waarbij betere antwoorden werden gevonden in ongeveer dezelfde tijd als de standaardzoekopdracht.

De kern van de uitdaging ligt in de aard van het probleem zelf. Wanneer je probeert faciliteiten op een vlak vlak te plaatsen om een groep punten te bedienen, is het wiskundige landschap ongelooflijk ruig. Het bevat miljoenen lokale optima, wat oplossingen zijn die beter zijn dan hun directe buren, maar niet de beste overall zijn. Standaardalgoritmen blijven vaak steken op deze lokale pieken. De traditionele manier om dit te overwinnen is door de zoekopdracht simpelweg vele malen uit te voeren, beginnend vanaf willekeurige locaties, in de hoop dat een van die willekeurige starts dicht genoeg bij het ware globale optimum landt om het algoritme de top te laten beklimmen. De onderzoekers gebruikten een krachtig verbeteringsalgoritme genaamd CLUST, dat momenteel een van de meest effectieve instrumenten voor deze taak is, en voerden het uit vanaf tachtigduizend verschillende startpunten in hun initiële tests.

De innovatie in POST is wat er gebeurt na die initiële runs. In plaats van te stoppen zodra het beste resultaat is gevonden, nemen de onderzoekers de vijf beste onderscheidende oplossingen uit een kleinere batch runs en behandelen deze als "ouders". Ze creëren vervolgens nieuwe "afstammelingen"-oplossingen door de locaties van de faciliteiten van deze ouders te mengen. Om dit te doen, trekken ze een denkbeeldige lijn door het midden van de gecombineerde groep faciliteiten. Faciliteiten van de eerste ouder die aan één kant van de lijn liggen, worden gekoppeld aan faciliteiten van de tweede ouder die aan de andere kant van de lijn liggen. Dit creëëert een nieuwe configuratie die de sterktes van beide ouders overneemt. De onderzoekers genereren verschillende van deze nieuwe configuraties, voeren het verbeteringsalgoritme erop uit en kijken of deze tot nog betere oplossingen leiden. Als dat het geval is, herhaalt het proces zich, waarbij de nieuwe beste oplossingen als de ouders dienen voor de volgende ronde van menging.

Deze cyclus van mengen en verbeteren wordt in verschillende batches herhaald. De onderzoekers testten verschillende manieren om deze batches te organiseren. In één opstelling voerden ze de initiële zoekopdracht duizend keer uit, namen de vijf beste resultaten, mengden deze en herhaalden deze hele cyclus zeventig keer. In een andere setup voerden ze de zoekopdracht tienduizend keer uit en herhaalden de cyclus acht keer. In een derde scenario voerden ze de volledige tachtigduizend keer uit in één enkele batch. De resultaten toonden een duidelijk patroon: het opdelen van de zoekopdracht in kleinere batches en het herhaaldelijk verfijnen van de beste resultaten gevonden in elke batch leverde betere uitkomsten op dan het uitvoeren van de volledige zoekopdracht in één keer. De methode die één duizend initiële zoekopdrachten uitvoerde en het verfijningsproces zeventig keer herhaalde, produceerde de meest consistente verbeteringen en vond betere oplossingen dan welke eerdere methode dan ook voor alle achtenveertig testgevallen.

De onderzoekers waren zorgvuldig om ervoor te zorgen dat de extra tijd die aan dit mengproces werd besteed, verwaarloosbaar was. Omdat de nieuwe startpunten die door menging worden gecreëerd al van hoge kwaliteit zijn, convergeert het verbeteringsalgoritme veel sneller dan het doet vanaf een willekeurig startpunt. De totale tijd die nodig was voor de POST-methode was slechts iets langer dan de standaard multi-start-aanpak, terwijl het consistent superieure resultaten vond. Voor de uniforme testgevallen verbeterde de nieuwe methode de best bekende oplossingen met gemiddeld 0,062 procent, en voor de niet-uniforme gevallen met 0,068 procent. Hoewel deze percentages klein lijken, vertegenwoordigen ze in de context van grootschalige logistiek en facilitaire planning aanzienlijke besparingen in afstand en kosten.

De studie onderzocht ook de grenzen van deze aanpak. De onderzoekers merkten op dat als de multi-start-procedure al de absoluut optimale oplossing had gevonden, de POST-methode deze niet verder kon verbeteren. Aangezien het p-mediaanprobleem bekend staat om het hebben van miljoenen lokale optima, is het zeer onwaarschijnlijk dat een standaardzoekopdracht door toeval de perfecte oplossing zou vinden. Het feit dat POST de resultaten in elk geval verbeterde, suggereert dat de standaardzoekopdrachten inderdaad vastliepen op lokale pieken waar POST in staat was uit te breken. De onderzoekers observeerden ook dat het verhogen van het aantal initiële zoekopdrachten in een enkele batch niet altijd tot betere resultaten leidde; sterker nog, de kleinere batches met meer herhaling presteerden beter. Dit ondersteunt een principe dat zij "Less is More" noemen, wat suggereert dat het effectiever is om een paar veelbelovende gebieden diepgaand en herhaaldelijk te verkennen dan om een breed net uit te werpen en op het beste te hopen.

Het succes van POST was niet beperkt tot één type probleem. De onderzoekers testten het op zowel uniforme instanties, waarbij de vraagpunten gelijkmatig verspreid zijn, als niet-uniforme instanties, waarbij de punten op specifieke wijzen geclusterd zijn. In beide scenario's presteerde de methode beter dan eerdere technieken, inclusclusief de beste resultaten van andere recente studies die maanden aan rekentijd hadden gekost. De nieuwe methode behaalde deze resultaten in een fractie van de tijd, waarbij de totale looptijd voor de meest effectieve configuratie ongeveer dertien dagen was voor de gehele set tests. De onderzoekers boden ook een formule aan om te schatten hoe de looptijd zou schalen met de grootte van het probleem, waarbij ze opmerkten dat wanneer het aantal vraagpunten tienvoudig toenam, de benodigde tijd met ongeveer vijftien tot zeventien keer toenam, terwijl het verdubbelen van het aantal faciliteiten de tijd met minder dan een factor twee verhoogde.

Vooruitblikkend suggereren de auteurs dat deze techniek kan worden toegepast op andere optimalisatieproblemen die momenteel worden opgelost met multi-start-benaderingen, zoals het clusteren van datapunten of het partitioneren van netwerken. Ze stellen voor dat toekomstig onderzoek verschillende manieren kan verkennen om de "ouder"-oplossingen te selecteren, bijvoorbeeld door ze niet alleen te kiezen op basis van hun kwaliteit, maar ook op basis van hoe verschillend ze van elkaar zijn, om een meer diverse zoektocht te garanderen. Ze suggereren ook dat het vergroten van het aantal oplossingen in de elite-set die voor menging wordt gebruikt, nog betere resultaten kan opleveren, hoewel dit meer rekenkracht zou vereisen. De studie concludeert dat door een eenvoudige, post-optimalisatiestap toe te voegen aan bestaande algoritmen, onderzoekers de kwaliteit van oplossingen aanzienlijk kunnen verbeteren zonder een evenredige toename in inspanning, wat een krachtig nieuw instrument biedt voor het aanpakken van sommige van de meest complexe ruimtelijke planningsproblemen.