We found out that it is possible to solve mathematical difficult question 'traveling salesman problem' using a kind of ameba 'mojikokori'

by The Lazy Artist Gallery

Ameba is a generic name of protists that do not have cartilage or cilia and move using temporary paws with protruding cytoplasm. A Japanese research team announced that it succeeded in solving the " traveling salesman problem " known as mathematical difficulty using a kind of ameba called modjocori .

Remarkable problem-solving ability of unicellular amoeboid organism and its mechanism | Royal Society Open Science
https://royalsocietypublishing.org/doi/full/10.1098/rsos.180396

Amoeba finds approximate solutions to NP-hard problem in linear time
https://phys.org/news/2018-12-amoeba-approximate-solutions-np-hard-problem.html

An Amoeba-Based Computer Calculated Approximate Solutions to a Very Hard Math Problem - Motherboard
https://motherboard.vice.com/en_us/article/gy7994/an-amoeba-based-computer-calculated-approximate-solutions-to-a-very-hard-math-problem

Research teams such as Mr. Masami Aono, Associate Professor of the Faculty of Environmental Information at Keio University, used a type of amoeba "Mojikokori" which migrates by protoplast flow and lives on the surface of fallen leaves and decayed trees, and traveling salesman problem We made an experiment to hurry to resolve the problem. Modjocori is a unicellular organism known for having memory and judgmental ability comparable to advanced intelligence despite having no brain.

A mysterious power of the yellow slime "Mojihokori" which solves the maze and merging by fusing without the brain and nerve - GIGAZINE

The traveling salesman problem is a kind of combination optimization problem , it is to visit all the cities without visiting the same city twice and to derive the shortest route returning to the departure point. The Traveling Salesman problem is known as the number of cities to be circulated increases, the computer increases exponentially with the time required to solve the problem. For example, if there are four visiting cities, there are only three routes for optimal solutions, but if the number of visited cities increases to 8, the route of the optimal solution will increase to 2520 routes.

The research team placed an agar plate as a nutrient source of modifier on the bottom of a star plate with a total of 64 narrow routes, and put a modifier on it. In the experiment, the research team gave Mojikokori "an algorithm to solve the traveling salesman problem", and Modjocori plays a kind of computer role of deriving a solution according to the algorithm. This is a movie that summarizes the experiment.

Physarum: Remarkable problem-solving ability of unicellular amoeboid organism and its mechanism


Mojikori can move the protoplasm at a speed of 1 mm per second, extend the temporary foot, and move freely on the plate. Modjocori attempts to maximally absorb nutrients by contacting as much area as possible with the agar plate, but because it has the property of disliking light, it can not spread the body to the part illuminated with light. The research team developed a device that can selectively illuminate the route of the star plate with light and was able to retreat the mojocori from the aimed route.

In the experiment, the numbers from "A1" to "H8" were assigned to each route.

It is like this when mojikokori shows the part where the temporary legs are newly extended red, the parts where the temporary feet are retracted are shown in blue.

Although it is modjocori that extends to the route to maximally take nutrition, the research team uses the nature of mojiko called "hate light" in order to solve the traveling salesman problem. The research team feeds back the appearance of mojikokori with the camera, switching light irradiation to the route every 6 seconds.

For example, if Modjo core occupies the route of "A3", the route of A1 · A2 · A4 ~ A8 will be irradiated with light and the modifier can not be invaded. In addition, the route of B3 · D3 ...... H3 is also irradiated with light, so to prevent invasion of mojokori, Modjochori will choose one of B · H, 1, 2, 4 ~ 8 respectively I will.

According to this algorithm, Modifocor is a combination of A to H alphabets and combinations of 1 to 8 (for example, B1 - D2 - H3 - A4 - C5 - G6 - F7 - E8) You will be stretching. In other words, the alphabet represents the city to visit, the number represents the order to visit, each being used only once indicates that modjocori visit the same city only once.

In addition, because the research team represents distances between cities, "When Modjochori occupies route" B 2 "and further temporarily stretches to" C 3 "and" D 3 "at the same pace, the distance from city B is far "I will irradiate the light to the route of city C that was set". As a result, although the tentative foot is retreated from the route C 3 by the light, it is possible to extend the tentative foot to D 3 which is close to the distance from B as before.

By hitting specific routes in response to mojiko movements, Modjocori will be able to find the shortest distance route to visit all cities. This is the algorithm that the research team gives to mojoko, and by moving the modifier according to the algorithm, approximate value of the traveling salesman problem can be derived.

In the traveling salesman problem, as the number of cities increases, the complexity of the problem increases exponentially, but the speed at which Modjocori solves the traveling salesman problem increases exponentially even as the number of cities increases There was not.

At the moment it is possible for computers to solve the problem much faster than in Ameba, but the research team will continue to improve the computing capacity of Ameba in the future. In the future, researchers expect that they will be able to solve the traveling salesman problem using hundreds of cities by manufacturing large-scale ameba computers.