Slime Mold Can Solve Exponentially Complicated Problems in Linear Time

Researchers from Lanzhou University in China have shown that the slime mold Physarum polycephalum is able to solve the Traveling Salesman Problem, a combinatorial test with exponentially increasing complexity, in linear time. Using focused light stimulus as negative feedback to maintain the criteria of the task, the authors demonstrated that this model was able to reliably output a high-quality solution. This is the latest development among many biology-inspired approaches for advanced processing in the evolution of computing.

Physarum polycephalum on an oak log. Image credit: Mushroom Observer / CC BY-SA 3.0.

A salesman must visit n cities, going to each city only once, and then return to their starting point — what is the shortest possible route that they can take? This is the premise for the Traveling Salesman Problem (TSP), first described in the 1800s and later developed into a computational test of combinatorial optimization.

The relative locations of the cities are randomized, so the solution is different each time, making this a non-deterministic system. As n gets larger, the number of possible routes increases exponentially, thus requiring massive computing power to find efficient solutions.

While the TSP has just three possible tours when there are four cities, increasing this parameter to eight cities yields 2,520 possibilities. Traditional electronic computers only investigate one potential route at a time, and operate slowly in very large systems.

Efforts to improve conventional computers’ restraint on serial processing (one at a time) have led to the development of parallel processor computers, which can run commands simultaneously. By dividing the labor of tasks among multiple processors, parallel-computation systems dramatically increase the speed of problem solving.

There have been many creative efforts to engineer parallel processors that rely on biological systems, including DNA fragments, biomolecular motors, and slime molds.

A single cell body with many nuclei, Plasmodium is a type of slime mold that is repelled by light. This model organism has underlying oscillatory movements, and exhibits negative phototaxis, allowing it to be easily manipulated in the lab. As shown in the model below, light can be shone on the cell’s branched extensions, which retract and cause a volume-conserving corresponding elongation of other branches.

Left: the chip used in the experiment has 64 lanes that the Plasmodium cell body can extend into. Right: light can be exposed specifically to different branches in order to favor their retraction. Image credit: Zhu et al, doi: 10.1098/rsos.180396.

Plasmodium’s propensity to optimize comes from its intrinsic effort to grow as efficiently as possible, while making its own decisions. This approach is innovative in diminishing the role of human intervention, as even the work of digital computers is built on the foundation of human-written code.

Plasmodium has proved its applicability in many examples, from solving mazes to recreating the map of the Tokyo rail system (shown below). They are capable of anticipating periodic events, and even habituation, a type of learning, despite their complete lack of a nervous system.

By placing food on the location of major cities, and using light gradients to recapitulate geographic obstacles, slime mold mimicked the design of the Tokyo rail map. Image credit: adapted from Atsushi Tero et al, doi: 10.1126/science.1177894.

The authors had previously shown that the slime mold exhibits regularly oscillating contraction rhythms, which redistribute its intracellular contents and alter its shape. This degree of random variation independent of light stimulus provides flexibility to find maximally efficient solutions.

The light stimulus feedback of the experiment incorporated the following parameters: each city can be visited only once, only one city can be visited at a time, and the total distance of the route is minimized.

Programmed using recurrent neural network dynamics derived from the Hopfield-Tank-Amari model, the current state of the system (the order of cities the extensions correspond to) influences the illumination of the branches.

By contracting so as to minimize the intensity of light exposure, other extensions are probed by the volume displacement, adjusting the feedback. Integrating signals across the entire cell, the organism is continually correcting its search.

This study showed that the route found was consistently below the mean length of a randomly chosen tour, demonstrating successful optimization. The first experiment investigated the efficiency of the route and the time required to find a feasible solution as the number of cities in the trial increased. Although the number of possible solutions increases exponentially with the number of cities, the time that the amoeba took to find a feasible one increases only linearly (shown below).

Left: the number of feasible routes between all cities of the TSP increases exponentially as the number of cities increases. Right: time required for Plasmodium to find a feasible route increases linearly as the number of cities increases. Image credit: Zhu et al, doi: 10.1098/rsos.180396.

Further, the authors found that the spatio-temporally regulated oscillations of the Plasmodium improve the quality of its search for a solution.

Noise was introduced to the provided feedback mechanism by randomly applying additional light across the branches.

With noise, the success rate and efficiency of the found solution dramatically declined (shown below, left).

Left: the introduction of random light stimulus (noise) impaired the ability of the Plasmodium to find a feasible route. Right: AmoebaTSP approximately recapitulates the time-to-solution trend of the Plasmodium model. Image credit: Zhu et al, doi: 10.1098/rsos.180396.

In order to scale up these findings in silico, the authors developed AmoebaTSP, a computing system model of the Plasmodium that can handle highly complex problems using Monte Carlo simulation. By incorporating the real-life constraint of a constant growth/retraction rate of the branches relative to the cell body, AmoebaTSP found high quality solutions over iterations that also increased linearly with n, as was seen in vivo (shown above, right).

Amoeba-based computing that relies on the principles of Plasmodium response has been used in electrical engineering nano-architecture and has been applied to multi-leg robot mobility. Researchers in the EU have attempted to harness the problem-solving capabilities of the molds in computer chips.

Early iterations of biology-based computing systems include DNA-based parallel processing and ant colony simulations used to solve the TSP. Parallel computation has also been achieved using biomolecular motors myosin and actin filaments in a nanofabricated network, resembling a brute-force method.

There remain many open-ended fields that will benefit from advances in parallel computing, including chemical engineering, astrophysics, climate modeling, and predicting protein function. As the questions that we explore in our world increase in complexity, so too must the computers that we rely on for the answers.

The findings were recently published in the journal Royal Society Open Science.

_____

Liping Zhu et al. 2018. Remarkable problem-solving ability of unicellular amoeboid organism and its mechanism. R. Soc. open sci 5 (12): 180396; doi: 10.1098/rsos.180396