Amoeba inspires solution to the traveling salesman problem

A new analog computer to find a quick and reliable solution to the traveling salesman problem that was formulated in the 1930s.

The traveling salesman problem, or TSP, is one of the most intensively studied problems in computational mathematics. The problem states, “Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?” TSP is a representative combinatorial optimization problem.

Now researchers from Hokkaido University and Amoeba Energy in Japan developed an analog computer, the electronic amoeba, to solve the TSP. They took inspiration from the efficient foraging behavior of a single-celled amoeba for their solution.

A combinatorial problem is an optimization problem rather than a decision problem. The solution to the problem is additionally evaluated for solution quality. Classic examples of combinatorial optimization problems are logistical planning and scheduling.

In this digital age, we think that our digital computers can solve these problems pretty easily; on the contrary, today’s computers, including the supercomputers, are inadequate to solve these in practically permissible time. As the size of the problem increases, the number of solutions to evaluate increases exponentially. Newly developed computers like Ising machines, including quantum annealers, require complicated pre-processing of the task and also run the risk of presenting solutions that do not meet certain constraints.

Circuit diagram of the electronic amoeba (left: amoeba core, right: resistance crossbar). Image: Amoeba Energy

Amoeba is known to employ efficient nutrient-acquisition methodology by deforming their body. This behavior inspired Professor Seiya Kasai at Hokkaido University to design an analog circuit to mimic amoeba’s dynamics. The circuit fabricated on a breadboard by Kenta Saito, a Ph.D. student in Kasai’s lab, successfully found the shortest route for the 4-city TSP. Circuit simulations showed the circuit could reliably find a high-quality legal solution with a significantly shorter route length than the average length obtained by random sampling. Also, the time required to find this solution grew only linearly to the number of complexities giving an advantage over other computing solutions.

Simulation results: Red dot represents Electronic Amoeba, white dot represents conventional computer. Image: Masashi Aono

“The analog circuit reproduces well the unique and efficient optimization capability of the amoeba, which the organism has acquired through natural selection,” said Kasai.

According to Masashi Aono, who leads Amoeba Energy, due to the analog circuit’s simplicity and compactness, it can be used to tackle many real-world problems. Also, it can be embedded in IoT devices as a power-saving microchip.

Do you want to publish on Apple News, Google News, and more? Join our writing community, improve your writing skills, and be read by hundreds of thousands around the world!


More from Science – News Landed

+ Archaeologists… How do they know where to dig?
+ A new app—the iGenomics—makes pocket size DNA analyzer possible

+ Adobe Flash receives final update before shutdown at the end of the year
+ Epigenetic modifications are the cause of memory loss in Alzheimer’s disease

Related Stories

The U.S. reports a rare case of brain-eating amoeba via contaminated water

The United States of America (USA) has already been struggling with the COVID-19 pandemic for months, and the new...

Featured Stories

North Korea’s nuclear test sparks conflict

The United States of America, Japan, and South Korea have collaborated to pressurize "North Korea's nuclear and ballistic missiles...

The molecular underpinning of stem cells to form the kidney seeks attention by the scientists

The mammalian kidney is a distinctive organ, that evolves on basis of an interplay between epithelial and mesenchymal tissues....

Nike blocks all sales and gets a restraining order against rapper Lil Nas X’s ‘Satan Shoes’

Nike has quite literally fought against the devil, trying to get the 'Satan Shoes' to be stopped from being...

Discovery of a new type of black hole bridges the gap between Stellar and Supermassive black holes

A black hole is a region in space where gravity is so strong that no particles, including electromagnetic radiation,...

Goldilock protein which sets for proper immune response remains known, researchers say

There are certainly a lot of abnormal actions produced by the immune cells. It can be of any autoimmune...

A golden mask discovered in China dating back 3 thousand years

A number of Chinese archaeologists have been able to find an archaeological discovery described as historical, while they are...