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!

Source: Phys.org

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

Low-cost lead adsorbing water filter designed by Indian students

Two students from India have designed a low-cost lead water filter that can be made with locally sourced materials....

Make it Rain! Dubai uses drones to conjure rain from the skies

You can order food, hail a driver, and even find a spouse with the click of a button; but...

Physicists have created the world’s thinnest magnet. Just one atom thick!

Can you guess the size of the thinnest magnet? It is just one atom thick. Scientists from the University of...

Boris Johnson and Rishi Sunak reverse decision to avoid self-isolation following ping by NHS contact tracing

Following the Health Secretary's diagnosis with COVID-19, the Prime Minister and Chancellor were notified by NHS Test and Trace...

India is one of the largest producers of COVID vaccine and yet faces major internal shortages

The worsening situation in India finally gained some stabilization around September 2020. Usually, when things start getting better, people...

The US supports easing patent rules on Covid-19 after intense internal debate…

Since the coming of the pandemic, there has been a lot of debates and questions around the Covid-19 vaccines....