Archivio tag: problema del commesso viaggiatore

Il problema del bombo viaggiatore…

2 anni fa

Insetti davvero interessanti i bombi. La loro attività di impollinatori li rende un elemento indispensabile per ecosistemi naturali ed agricoltura, e per lungo tempo la loro capacità di volare è stata considerata un mistero dell’aerodinamica, a causa delle (apparentemente) insufficienti ampiezza e frequenza di battito delle ali ([2]).
Più recentemente, uno studio ([1]) realizzato da ricercatori del Queen Mary College di Londra ha evidenziato come i bombi siano in grado di identificare il percorso più breve che unisce i fiori disposti secondo un certo schema, anche quando li raggiungono partendo da un diverso punto iniziale.
In altre parole riescono a risolvere quello che viene definito il Problema del commesso viaggiatore (Travelman Sales Problem, TSP), in cui si ricerca il tragitto più breve possibile che consente di visitare tutte le città di una rete, passando una sola volta per ciascuna di esse.
Gli algoritmi matematici risolvono il problema calcolando e confrontando tutti i possibili cammini, operazione lunga ed onerosa dal punto di vista computazionale; nel 2001 la risoluzione del TSP applicato a 15112 città tedesche ha richiesto l’equivalente di 22.6 anni di computer time (500 MHz).

Per il cervello dei bombi, delle dimensioni di una capocchia di spillo, sembrerebbe quindi un problema impossibile da affrontare.
Nella ricerca di risorse distribuite in modo casuale, la maggior parte degli animali utilizza l’approccio più semplice, seguendo percorsi (sub-)ottimali muovendosi verso i punti più vicini non ancora visitati.
I bombi viceversa adottano, nei loro voli di impollinazione, una strategia più elaborata.

Per studiarla, i ricercatori hanno costruito un’apparato sperimentale contenente sei fiori artificiali, disposti in modo che i movimenti verso il successivo più vicino conducessero i bombi a seguire un percorso non ottimale.

Nel corso degli 80 tentativi, migliorando la conoscenza della disposizione dei fiori, gli insetti hanno ridotto progressivamente la distanza volata.
E, aspetto ancora più sorprendente, non hanno quasi mai adottato la strategia di seguire il fiore più vicino a quello appena visitato, privilegiando cammini alla lunga più vantaggiosi dal punto di vista del consumo energetico.

La conclusione dello studio è che i bombi sono in grado di risolvere complessi problemi di routing basandosi sull’esperienza precedente e non su una sofisticata rappresentazione cognitiva dello spazio.

Questo è il codice R per ottenere i percorsi mediante l’algoritmo 2-opt ed i grafici corrispondenti (con ggplot2):

library(TSP)
library(ggplot2)
bumblebee <- data.frame(c(310,130,30,310,620,680,440),c(220,220,850,600,620,70,200))
names(bumblebee) <- c("x","y")
attach(bumblebee)
bumblebeeDistancematrix <- dist(bumblebee)
bumblebeeDistancematrix.tsp <- TSP(bumblebeeDistancematrix)
# calculate shortest path with 2-opt method
bumblebeeDistancematrix.path <- solve_TSP(bumblebeeDistancematrix.tsp, method="2-opt", control=list(tour=c(1,2,3,4,5,6,7)))
bumblebeeDistancematrix.tour <- as.vector(bumblebeeDistancematrix.path)
# lenght of the tour
as.integer(bumblebeeDistancematrix.tour)
bumblebeeN <- data.frame(bumblebee[as.integer(bumblebeeDistancematrix.tour),], ID=c(1:6,"N"))
base_size <- 9
# shortest path graph
p <- ggplot(bumblebee[as.integer(bumblebeeDistancematrix.tour),], aes(x,y))
p + geom_path() + geom_segment(aes(xend=310, x=440,yend=220, y=200), arrow=arrow(length = unit(0.25, "cm"))) + geom_point(aes(x+25,y+35, shape=bumblebeeN$ID), size=3) + scale_shape_manual(values = as.character(bumblebeeN$ID)) + opts(legend.position = "none", axis.ticks = theme_blank(), axis.text.x = theme_blank(), axis.text.y = theme_blank(), plot.title = theme_blank()) + xlab("") + ylab("")
# longest path
bumblebeeDistancematrix.long.tour <- c(1,2,4,5,6,3,7)
bumblebeeL <- data.frame(bumblebee[as.integer(bumblebeeDistancematrix.long.tour),], ID=c(1,2,4,5,6,3,"N"))
# longest path graph
g <- ggplot(bumblebee[as.integer(bumblebeeDistancematrix.long.tour),], aes(x,y))
g + geom_path() + geom_segment(aes(xend=310, x=440,yend=220, y=200), arrow=arrow(length = unit(0.25, "cm"))) + geom_point(aes(x+25,y+35, shape=as.character(c(1,2,3,4,5,6,"N"))), size=3) + scale_shape_manual(values = as.character(c(1,2,4,5,6,3,"N"))) + opts(legend.position = "none", axis.ticks = theme_blank(), axis.text.x = theme_blank(), axis.text.y = theme_blank(), plot.title = theme_blank()) + xlab("") + ylab("")

Il pacchetto TSP mette a disposizione diversi algoritmi per l’identificazione dei percorsi ottimali, utilizzabili specificandone il nome nella funzione solve_TSP.
È disponibile inoltre un’interfaccia per l’integrazione con Concorde (da installare separatamente), il software più veloce per la soluzione di TSP.

Fonti:
1
Lihoreau M, Chittka L, Le Comber SC, & Raine NE (2012). Bees do not use nearest-neighbour rules for optimization of multi-location routes. Biology letters, 8 (1), 13-6 PMID: 21849311
2
Jane Wang, Z. (2000). Two Dimensional Mechanism for Insect Hovering Physical Review Letters, 85 (10), 2216-2219 DOI: 10.1103/PhysRevLett.85.2216
3
National Geographic Italia
4
Bumblebee image courtesy of Wikipedia