Il problema del bombo viaggiatore…

3 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

4 pensieri su “Il problema del bombo viaggiatore…

  1. Luca

    Complimenti per il bellissimo post. L’argomento è molto interessante, ho solo una curiosità.
    I bombi utilizzati per il test erano isolati o in qualche modo comunicavano? La mia curiosità è se ci sia qualche sorta di intelligenza collettiva al servizio di un problema comune. Complimenti ancora!

    1. Marco Autore articolo

      @Luca: Grazie, troppo gentile! :-)
      Ogni bombo ha visitato l’apparato da solo, e tra un insetto e l’altro i fiori artificiali sono stati lavati con etanolo al 70% per rimuovere eventuali tracce olfattive, e quindi eventuali “suggerimenti”.
      Il che dovrebbe escludere in questo specifico caso l’ipotesi (davvero affascinante e non rara nel mondo animale :-) della comunicazione e dell’intelligenza collettiva.
      Sarebbe interessante osservare cosa succede però quando sono presenti più bombi contemporaneamente, e come la strategia del singolo possa essere influenzata dalle informazioni spaziali supplementari fornite dagli altri :-)

      1. Luca

        La prima cosa che avevo pensato era proprio un apprendimento comune, visto che a prima vista i bombi in basso sembrano più bravi di quelli in alto.
        Poi ho letto meglio il post e ho capito quanto mi confermi.
        Sarebbe veramente interessante rifare l’esperimento confrontando l’apprendimento isolato con quello collettivo. Bisognerebbe scrivere ai ricercatori

        1. Marco Autore articolo

          @Luca: mi ero perso questo su PlosOne, “Conspecific and Heterospecific Information Use in Bumblebees” :-)

I commenti sono chiusi.