211service.com
Krimpende blob computes oplossingen voor reizende verkopers
Het handelsreizigersprobleem is een van de bekendere uitdagingen in de wiskunde. Dit is het probleem van het vinden van de kortste route om een aantal steden één keer te bezoeken en vervolgens terug te keren naar de plaats van herkomst.
Natuurlijk is het eenvoudig om routes te vinden die elke stad op deze manier bezoeken. De grote uitdaging is om de kortste te vinden.
Er is één veilige manier om dit te doen: door pure brute kracht. Dat betekent het meten van de lengte van elke toer en uitzoeken welke het kortst is. Het probleem is dat deze taak steeds langer wordt naarmate het aantal steden toeneemt. Inderdaad, voor grote aantallen steden is het rekenkundig onhaalbaar.
Het is gemakkelijk voor te stellen dat er een soort slimme wiskundige snelkoppeling is die dit probleem oplost. Niet zo. In feite zijn wiskundigen het erover eens dat er nooit een algemene kortere weg zal worden gevonden (dit is het zogenaamde P=NP-debat).
In plaats daarvan zijn ze aangewezen op optimalisatieprocessen die zoeken naar korte oplossingen, maar niet kunnen bewijzen dat dit inderdaad de kortste zijn.
De uitdaging voor alle praktische doeleinden is dus om algoritmen te vinden die goede resultaten opleveren en die rekenkundig efficiënt zijn.
Vandaag onthullen Jeff Jones en Andrew Adamatzky van de University of the West of England in het VK een ongebruikelijke benadering. Deze jongens zeggen dat een redelijke oplossing kan worden gevonden door de steden weer te geven als een reeks stippen in een virtuele petrischaal, de stippen onder te dompelen in een klodder virtuele slijm en vervolgens de klodder te verkleinen.
In vereenvoudigde termen, de klodder klampt zich vast aan de stippen als deze krimpt, en verbindt ze met een minimaal oppervlak, een beetje zoals een zeepbeloppervlak. Naarmate de klodder kleiner wordt, past hij zich morfologisch aan aan de configuratie van de steden, zeggen ze.
Wanneer alle stippen op het oppervlak van de klodder zitten, is het resulterende oppervlak een oplossing voor het handelsreizigerprobleem die over het algemeen redelijk goed is.
Het magische ingrediënt in dit alles is de speciale goo. Het bestaat uit vele deeltjes die elk bewegen volgens een reeks eenvoudige regels, zoals autonome agenten. Deze zitten in een zee van chemoattractant, een virtuele geur waar de deeltjes door worden aangetrokken. In elke fase van de berekening detecteert elk deeltje de chemoattractant eromheen en beweegt vervolgens naar het gebied met de hoogste concentratie. Terwijl het beweegt, laat het zijn eigen spoor van de chemoattractant achter zodat andere deeltjes kunnen volgen.
Het resultaat is een soort intelligente blob die opkomend gedrag vertoont, zoals het vermogen om het oppervlak te minimaliseren.
Jones en Adamatzky hebben deze intelligente goo op de proef gesteld door het los te laten op handelsreizigersproblemen bestaande uit 20 willekeurig verdeelde steden in een virtuele petrischaal. Ze hebben geplaatst video's van het krimpproces hier .
De resultaten zijn goed, maar niet perfect. Ze creëerden 20 verschillende scenario's van 20 steden en voerden de blob 6 keer uit op elk. Vervolgens vergeleken ze de kortste route van de blob met het daadwerkelijke kortste pad dat met brute kracht werd gevonden. Jones en Adamatzky zeggen dat als deze kortste route lengte 1 heeft, de intelligente blob tours heeft gevonden met een gemiddelde beste tourlengte van 1,04, een gemiddelde gemiddelde tourlengte van 1,07 en een gemiddelde slechtste tourlengte van 1,09.
Dat is niet slecht. Maar het echte voordeel zit in de eenvoud van de aanpak die in wezen opduikt en geen speciale optimalisatieprocessen omvat. Het produceert ook een kaart van de route aan het einde (hoewel enige menselijke interpretatie vereist is om het te begrijpen).
Er zijn natuurlijk nadelen. Er zijn enkele configuraties van steden die de blob niet aankan. Deze treden op wanneer de kortste route een soort zeestraat vormt tussen twee steden in plaats van een verbinding, zoals de Straat van Gibraltar tussen de Atlantische Oceaan en de Middellandse Zee. In plaats daarvan heeft de blob de neiging om ze te verbinden.
Desalniettemin is dit een interessante vorm van onconventioneel computergebruik die een fascinerend alternatief oplevert voor conventionele handelsreizigeralgoritmen. Het vertoont de grootste gelijkenis met benaderingen van rubberen banden die de steden met een rubberen band omringen en vervolgens geleidelijk proberen de band uit te rekken om steden binnenin met elkaar te verbinden. Het grote verschil is dat de materiaaleigenschappen van de blob emergent zijn in plaats van voorgeprogrammeerd.
Jones en Adamatzky zeggen dat de volgende stap zou zijn om een fysiek model van dit systeem te maken waarin een echte klodder het werk doet, misschien met behulp van visco-elastische minimalisering van vrije energie. Het ontwerpen van een dergelijk materiaal kan echter lastig zijn.
Een andere benadering, die een bredere toepassing zou kunnen hebben, zou zijn om de eigenschappen van deze onconventionele berekening in een klassiek algoritme te distilleren.
Het beste van alles is het vooruitzicht van logistiek managers die leveringsroutes plannen door wegennetwerkmodellen in vaten met intelligente slijm te dompelen. We wachten dus met spanning af op deze nieuwe wetenschap van de handelsreiziger-alchemie.
Referentie: arxiv.org/abs/1303.4969 : Berekening van het handelsreizigersprobleem door een krimpende klodder