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.

- Advertisement -

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
- Advertisement -

“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

- Advertisement -

+ 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

Sturgill Simpson Stops Struggling

Sturgill Simpson has always seemed to struggle. He would prefer being listened to as opposed to just being heard....

Climate change ultimately caused the demise of Transoxania

Climate change doomed the ancient Transoxania civilization, suggests a new study.  An international team of scientists analyzed sediment samples from...

Arecibo Observatory in Puerto Rico collapses

The Arecibo Observatory in Puerto Rico witnessed the crash of its pathbreaking telescope on late Tuesday morning. One of...

Next Step: Jurassic Park? Scientists digitally reconstruct dinosaur brain

As the blockbuster Jurassic Park/World franchise taught us--despite being extinct for more than 60 million years--"Life finds a way", and there...

A tsunami-like mechanism in mice brains teach us more about migraines

A migraine with aura is a severe headache that accompanies symptoms like dizziness, zigzag line vision, blind spots, tingling...

Joseph R. Biden and Kamala D. Harris elected to the White House

At around 11:25 a.m. on November 7, 2020, after nearly 90 hours since polls first closed throughout the United...

Comment Below

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...