hide
Free keywords:
slime mold, natural algorithm, natural adaptive networks
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 s_0 and s_1. We prove that, under this model, the mass of
the mold will eventually converge to the shortest s_0-s_1 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.
