Bruno should enjoy this.
Brent
-------- Forwarded Message --------
This is a cool bio hack, but is this approach ever going to be faster
and/or cheaper than an electronic computer for the same precision of
optimization?
https://phys.org/news/2018-12-amoeba-approximate-solutions-np-hard-problem.html
Amoeba finds approximate solutions to NP-hard problem in linear time
December 20, 2018 by Lisa Zyga, Phys.org
Researchers have demonstrated that an amoeba--a single-celled organism
consisting mostly of gelatinous protoplasm--has unique computing
abilities that may one day offer a competitive alternative to the
methods used by conventional computers.
The researchers, led by Masashi Aono at Keio University, assigned an
amoeba to solve the Traveling Salesman Problem (TSP). The TSP is an
optimization problem in which the goal is to find the shortest route
between several cities, so that each city is visited exactly once, and
the start and end points are the same.
https://royalsocietypublishing.org/doi/pdf/10.1098/rsos.180396
Remarkable problem-solving ability of unicellular amoeboid organism
and its mechanism
Choosing a better move correctly and quickly is a fundamental skill of
living organisms that corresponds to solving a computationally
demanding problem. A unicellular plasmodium of Physarum polycephalum
searches for a solution to the travelling salesman problem (TSP) by
changing its shape to minimize the risk of being exposed to aversive
light stimuli. In our previous studies, we reported the results on
the eight-city TSP solution. In this study, we show that the time
taken by plasmodium to find a reasonably high-quality TSP solution
grows linearly as the problem size increases from four to eight.
Interestingly, the quality of the solution does not degrade despite
the explosive expansion of the search space. Formulating a
computational model, we show that the linear-time solution can be
achieved if the intrinsic dynamics could allocate intracellular
resources to grow the plasmodium terminals with a constant rate, even
while responding to the stimuli. These results may lead to the
development of novel analogue computers enabling approximate solutions
of complex optimization problems in linear time.
--
You received this message because you are subscribed to the Google Groups
"Everything List" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to everything-list+unsubscr...@googlegroups.com.
To post to this group, send email to everything-list@googlegroups.com.
Visit this group at https://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/d/optout.
