22 febbraio 2012

Physarium Polycephalum: la muffa che cerca il cammino più breve. Studio presentato al convegno internazionale Symposium on discrete algorithms, Kyoto.

Physarium polycephalum C'è una muffa che ragiona come Internet. La Physarum Polycephalum, una muffa mucillaginosa che si nutre di spore e batteri, è in grado di trovare il cammino più corto in un labirinto, come accade all'interno della rete Internet. Vincenzo Bonifaci, dell’Istituto di analisi dei sistemi e informatica "Antonio Ruberti" del Consiglio nazionale delle ricerche di Roma (Iasi-Cnr) ha sviluppato un’analisi matematica in base alla quale il "ragionamento" della Physarum Polycephalum è riconducibile a un "algoritmo naturale", frutto di un’evoluzione durata milioni di anni. Lo studio, svolto in collaborazione con ricercatori del Max Planck Institute for Informatics tedesco, offre nuovi strumenti per la comprensione di fenomeni biologici complessi e la loro eventuale applicazione nelle infrastrutture tecnologiche sofisticate.
«In questi esperimenti dell’università giapponese dell'Hokkaidō - ha spiegato Bonifaci - la muffa è stata distribuita uniformemente sopra un labirinto dove sono stati collocati due fiocchi di avena, cibo di cui la muffa è ghiotta. Con il passare delle ore la muffa si ritrae dai percorsi che non portano al cibo, concentrando la massa su quello più corto. Il nostro studio ha analizzato matematicamente il meccanismo biologico che conduce la muffa a riconfigurarsi nel cammino più breve: ogni "capillare" della Physarum si espande o si contrae a seconda del maggiore o minore flusso di sostanze nutritive, secondo precise equazioni identificate dai biologi. A sua volta, la maggiore o minore dilatazione del condotto comporta una variazione del flusso attraverso di esso, dando luogo a un processo dinamico.»
Lo studio, presentato al convegno internazionale "Symposium on discrete algorithms" di Kyoto, evidenzia che «il meccanismo di regolazione dei "capillari" - sottolinea Bonifaci - è una conseguenza indipendente dalla complessità del labirinto sottostante. Si potrebbe dire che l'evoluzione, in milioni di anni, ha messo a punto la regolazione dei capillari della Physarum in modo tale da ottenere l'algoritmo giusto per il problema del cammino più breve.»
Questo tipo di ricerche ha due finalità. «La prima è comprendere i meccanismi alla base del comportamento intelligente degli organismi più semplici: senza questo primo passo non si può sperare di afferrare i medesimi meccanismi negli organismi più evoluti e complessi come gli animali o l'uomo. La seconda finalità è trovare approcci alternativi e potenzialmente fruttuosi per l’ottimizzazione di reti, per esempio il progetto di una rete di connettività a basso costo, ma anche per migliorare i metodi di instradamento del traffico Internet e per provare nuovi approcci applicativi nel settore dei trasporti e delle telecomunicazioni.»
Andrea Mameli www.linguaggiomacchina.it 22 febbraio 2012
Fonte: ufficio stampa CNR

Physarum Can Compute Shortest Paths
Vincenzo Bonifaci, Kurt Mehlhorn, Girish Varma (SODA 2012)
Abstract
Physarum Polycephalum is a slime mold that is apparently able to solve shortest path problems. A mathematical model has been proposed by biologists to describe the feedback mechanism used by the slime mold to adapt its tubular channels while foraging two food sources s0 and s1. We prove that, under this model, the mass of the mold will eventually converge to the shortest s0 - s1 path of the network that the mold lies on, independently of the structure of the network or of the initial mass distribution.
This matches the experimental observations by the biologists and can be seen as an example of a "natural algorithm", that is, an algorithm developed by evolution over millions of years.

Video

Nessun commento: