Shrinking Blob Computes Traveling Salesman Solutions

Problemet med den rejsende sælger er en af ​​de mere berømte udfordringer i matematik. Dette er problemet med at finde den korteste vej til at besøge en række byer én gang og derefter vende tilbage til oprindelsesstedet.

Det er selvfølgelig ligetil at finde ruter, der besøger hver by på denne måde. Den store udfordring er at finde den korteste.

Der er én fejlsikker måde at gøre dette på – ved ren og skær kraft. Det betyder, at man skal måle længden af ​​hver tur og træne, hvilken der er kortest. Problemet er, at denne opgave bliver mere og mere langvarig i takt med, at antallet af byer stiger. Faktisk, for et stort antal byer, er det beregningsmæssigt umuligt.

Det er let at forestille sig, at der kan være en form for smart matematisk genvej, der løser dette problem. Ikke så. Faktisk har matematikere en tendens til at være enige i, at en generel genvej aldrig vil blive fundet (dette er den såkaldte P=NP-debat).

I stedet er de nødt til at stole på optimeringsprocesser, der søger efter korte løsninger, men som ikke er i stand til at bevise, at disse faktisk er de korteste.

Så udfordringen for alle praktiske formål er at finde algoritmer, der giver gode resultater, og som er beregningsmæssigt effektive.

I dag afslører Jeff Jones og Andrew Adamatzky ved University of the West of England i Storbritannien en usædvanlig tilgang. Disse fyre siger, at der kan findes en fornuftig løsning ved at repræsentere byerne som en række prikker i en virtuel petriskål, nedsænke prikkerne i en klat virtuel goo og derefter skrumpe klatten.

Forenklet set klæber klatten sig til prikkerne, når den krymper, og forbinder dem med en minimal overflade, snarere som en sæbebobleoverflade. Efterhånden som klatten krymper, tilpasser den sig morfologisk til byernes konfiguration, siger de.

Når alle prikkerne sidder på klattens overflade, er den resulterende overflade en løsning på det rejsende sælgerproblem, der generelt er ret godt.

Den magiske ingrediens i alt dette er den specielle goo. Den består af mange partikler, som hver bevæger sig i henhold til et sæt enkle regler, som autonome agenter. Disse sidder i et hav af kemoattraktant, en virtuel duft, som partiklerne tiltrækkes af. På hvert trin i beregningen mærker hver partikel kemoattraktanten omkring sig og bevæger sig derefter mod området med højeste koncentration. Når den bevæger sig, efterlader den sit eget spor af kemoattraktanten, så andre partikler kan følge efter.

Resultatet er en slags intelligent klat, der viser emergent adfærd, såsom evnen til at minimere dens overfladeareal.

Jones og Adamatzky har sat denne intelligente goo igennem sine trin ved at sætte den til at tabe på rejsende sælgerproblemer bestående af 20 byer tilfældigt fordelt i en virtuel petriskål. de har placeret videoer af krympningsprocessen her .

Resultaterne er gode, men ikke perfekte. De skabte 20 forskellige scenarier med 20 byer og kørte klatten 6 gange på hver. De sammenlignede derefter klattens korteste rute med den faktiske korteste vej fundet ved brute force. Jones og Adamatzky siger, at hvis denne korteste rute er af længde 1, fandt den intelligente klat ture med en gennemsnitlig bedste turlængde på 1,04, en gennemsnitlig turlængde på 1,07 og en gennemsnitlig værste turlængde på 1,09.

Det er ikke dårligt. Men den virkelige fordel ligger i enkelheden af ​​tilgangen, som i det væsentlige er fremkommet og ikke involverer særlige optimeringsprocesser. Det producerer også et kort over ruten i slutningen (selvom der kræves en vis menneskelig fortolkning for at give mening ud af det).

Der er selvfølgelig ulemper. Der er nogle konfigurationer af byer, som klatten ikke kan klare. Disse opstår, når den korteste rute danner en slags stræde mellem to byer snarere end en forbindelse, som Gibraltarstrædet mellem Atlanterhavet og Middelhavet. I stedet har klatten en tendens til at forbinde dem.

Ikke desto mindre er dette en interessant form for ukonventionel databehandling, der producerer et fascinerende alternativ til konventionelle rejsende sælgeralgoritmer. Det ligner tættest på gummibåndstilgange, som omgiver byerne med et gummibånd og derefter gradvist forsøger at strække båndet for at forbinde byer indenfor. Den store forskel er, at klattens materialeegenskaber fremstår frem for forprogrammerede.

Jones og Adamatzky siger, at det næste skridt ville være at skabe en fysisk model af dette system, hvor en rigtig klat gør arbejdet, måske ved at bruge viskoelastisk, fri energiminimering. Det kan dog være vanskeligt at designe et sådant materiale.

En anden tilgang, som kunne have bredere anvendelse, ville være at destillere egenskaberne af denne ukonventionelle beregning til en klassisk algoritme.

Det bedste af det hele er udsigten til, at logistikchefer planlægger leveringsruter ved at dyppe vejnetmodeller i beholdere med intelligent goo. Så vi venter med spænding på denne nye videnskab om rejsende sælger alkymi.

Ref: arxiv.org/abs/1303.4969 : Beregning af det rejsende sælgerproblem af en skrumpende klat

skjule