211service.com
Shrinking Blob Computes Traveling Salesman Solutions
Problemet med resande försäljare är en av de mer kända utmaningarna inom matematik. Detta är problemet med att hitta den kortaste vägen för att besöka ett antal städer en gång och sedan återvända till ursprungsplatsen.
Naturligtvis är det enkelt att hitta rutter som besöker varje stad på detta sätt. Den stora utmaningen är att hitta den kortaste.
Det finns ett felsäkert sätt att göra detta på – genom ren brutal kraft. Det innebär att mäta längden på varje turné och träna vilken som är kortast. Problemet är att denna uppgift blir allt mer långvarig i takt med att antalet städer ökar. För ett stort antal städer är det faktiskt beräkningsmässigt omöjligt.
Det är lätt att föreställa sig att det kan finnas någon form av smart matematisk genväg som löser detta problem. Inte så. Faktum är att matematiker tenderar att hålla med om att en generell genväg aldrig kommer att hittas (detta är den så kallade P=NP-debatten).
Istället måste de förlita sig på optimeringsprocesser som söker efter korta lösningar men inte kan bevisa att dessa verkligen är de kortaste.
Så utmaningen för alla praktiska ändamål är att hitta algoritmer som ger bra resultat och som är beräkningseffektiva.
Idag avslöjar Jeff Jones och Andrew Adamatzky vid University of the West of England i Storbritannien ett ovanligt tillvägagångssätt. Dessa killar säger att en rimlig lösning kan hittas genom att representera städerna som en serie prickar i en virtuell petriskål, sänka ner prickarna i en klot av virtuellt smuts och sedan krympa klumpen.
I förenklade termer klamrar sig klumpen fast vid prickarna när den krymper, och förbinder dem med en minimal yta, snarare som en såpbubblesyta. När klumpen krymper anpassar den sig morfologiskt till städernas konfiguration, säger de.
När alla prickar sitter på ytan av klumpen är den resulterande ytan en lösning på problemet med resande säljare som generellt sett är ganska bra.
Den magiska ingrediensen i allt detta är den speciella gooen. Den består av många partiklar som varje rör sig enligt en uppsättning enkla regler, som autonoma agenter. Dessa sitter i ett hav av chemoattractant, en virtuell doft som partiklarna attraheras av. Vid varje steg i beräkningen känner varje partikel av kemoattraktanten runt den och rör sig sedan mot regionen med högsta koncentration. När den rör sig lämnar den efter sig sina egna spår av kemoattraktanten för andra partiklar att följa efter.
Resultatet är en sorts intelligent blob som visar uppkomstbeteende, som förmågan att minimera sin yta.
Jones och Adamatzky har satt den här intelligenta gooen igenom sina steg genom att sätta den förlora på resande säljarproblem som består av 20 städer slumpmässigt fördelade i en virtuell petriskål. De har placerat videor av krympningsprocessen här .
Resultaten är bra men inte perfekta. De skapade 20 olika scenarier med 20 städer och körde klumpen 6 gånger på varje. De jämförde sedan klumpens kortaste väg med den faktiska kortaste vägen som hittats av brute force. Jones och Adamatzky säger att om den här kortaste rutten är av längd 1, så hittade den intelligenta klumpen turer med en genomsnittlig bästa turlängd på 1,04, en genomsnittlig turlängd på 1,07 och en genomsnittlig sämsta turlängd på 1,09.
Det är inte dåligt. Men den verkliga fördelen ligger i enkelheten i tillvägagångssättet som i huvudsak är framväxande och inte involverar några speciella optimeringsprocesser. Den producerar också en karta över rutten i slutet (även om det krävs en mänsklig tolkning för att förstå det).
Det finns nackdelar såklart. Det finns vissa konfigurationer av städer som klumpen inte klarar av. Dessa uppstår när den kortaste vägen bildar ett slags sund mellan två städer snarare än en förbindelse, som Gibraltarsundet mellan Atlanten och Medelhavet. Istället tenderar klumpen att koppla ihop dem.
Ändå är detta en intressant form av okonventionell datoranvändning som ger ett fascinerande alternativ till konventionella algoritmer för resande försäljare. Det påminner närmast om gummibands-tillvägagångssätt som omger städerna med ett gummiband och sedan successivt försöker sträcka bandet för att förbinda städer inom. Den stora skillnaden är att klumpens materialegenskaper är framträdande snarare än förprogrammerade.
Jones och Adamatzky säger att nästa steg skulle vara att skapa en fysisk modell av detta system där en riktig klump gör jobbet, kanske med hjälp av viskoelastisk, fri energiminimering. Att designa ett sådant material kan dock vara knepigt.
Ett annat tillvägagångssätt, som kan ha bredare tillämpning, skulle vara att destillera egenskaperna hos denna okonventionella beräkning till en klassisk algoritm.
Bäst av allt är möjligheten att logistikchefer planerar leveransrutter genom att doppa vägnätsmodeller i tankar med intelligent goo. Så vi väntar med förväntan på denna nya vetenskap om resande försäljares alkemi.
Ref: arxiv.org/abs/1303.4969 : Beräkning av resandeförsäljarproblemet av en krympande blob