Thursday, August 11, 2022
SCIENMAG: Latest Science and Health News
No Result
View All Result
  • Login
  • HOME PAGE
  • BIOLOGY
  • CHEMISTRY AND PHYSICS
  • MEDICINE
    • Cancer
    • Infectious Emerging Diseases
  • SPACE
  • TECHNOLOGY
  • CONTACT US
  • HOME PAGE
  • BIOLOGY
  • CHEMISTRY AND PHYSICS
  • MEDICINE
    • Cancer
    • Infectious Emerging Diseases
  • SPACE
  • TECHNOLOGY
  • CONTACT US
No Result
View All Result
Scienmag - Latest science news from science magazine
No Result
View All Result
Home SCIENCE NEWS Technology and Engineering

“Electronic amoeba” finds approximate solution to traveling salesman problem in linear time

December 10, 2020
in Technology and Engineering
0
Share on FacebookShare on Twitter

IMAGE

Credit: Masashi Aono

Researchers at Hokkaido University and Amoeba Energy in Japan have, inspired by the efficient foraging behavior of a single-celled amoeba, developed an analog computer for finding a reliable and swift solution to the traveling salesman problem — a representative combinatorial optimization problem.

Many real-world application tasks such as planning and scheduling in logistics and automation are mathematically formulated as combinatorial optimization problems. Conventional digital computers, including supercomputers, are inadequate to solve these complex problems in practically permissible time as the number of candidate solutions they need to evaluate increases exponentially with the problem size — also known as combinatorial explosion. Thus new computers called “Ising machines,” including “quantum annealers,” have been actively developed in recent years. These machines, however, require complicated pre-processing to convert each task to the form they can handle and have a risk of presenting illegal solutions that do not meet some constraints and requests, resulting in major obstacles to the practical applications.

These obstacles can be avoided using the newly developed “electronic amoeba,” an analog computer inspired by a single-celled amoeboid organism. The amoeba is known to maximize nutrient acquisition efficiently by deforming its body. It has shown to find an approximate solution to the traveling salesman problem (TSP), i.e., given a map of a certain number of cities, the problem is to find the shortest route for visiting each city exactly once and returning to the starting city. This finding inspired Professor Seiya Kasai at Hokkaido University to mimic the dynamics of the amoeba electronically using an analog circuit, as described in the journal Scientific Reports. “The amoeba core searches for a solution under the electronic environment where resistance values at intersections of crossbars represent constraints and requests of the TSP,” says Kasai. Using the crossbars, the city layout can be easily altered by updating the resistance values without complicated pre-processing.

Kenta Saito, a PhD student in Kasai’s lab, fabricated the circuit on a breadboard and succeeded in finding the shortest route for the 4-city TSP. He evaluated the performance for larger-sized problems using a circuit simulator. Then the circuit reliably found a high-quality legal solution with a significantly shorter route length than the average length obtained by the random sampling. Moreover, the time required to find a high-quality legal solution grew only linearly to the numbers of cities. Comparing the search time with a representative TSP algorithm “2-opt,” the electronic amoeba becomes more advantageous as the number of cities increases. “The analog circuit reproduces well the unique and efficient optimization capability of the amoeba, which the organism has acquired through natural selection,” says Kasai.

“As the analog computer consists of a simple and compact circuit, it can tackle many real-world problems in which inputs, constraints, and requests dynamically change and can be embedded into IoT devices as a power-saving microchip,” says Masashi Aono who leads Amoeba Energy to promote the practical use of the amoeba-inspired computers.

###

This is a Joint Release between Hokkaido University and Amoeba Energy Co., Ltd.

Media Contact
Naoki Namba
[email protected]

Original Source

https://www.global.hokudai.ac.jp/blog/electronic-amoeba-finds-approximate-solution-to-traveling-salesman-problem-in-linear-time/

Related Journal Article

http://dx.doi.org/10.1038/s41598-020-77617-7

Tags: BiotechnologyComputer ScienceHardwareMicrobiologyResearch/DevelopmentSoftware EngineeringTechnology/Engineering/Computer Science
Share26Tweet16Share4ShareSendShare
  • Quaise_Energy_Gyrotron.png

    Experts optimistic about converting coal plants to production of clean geothermal energy

    111 shares
    Share 44 Tweet 28
  • Order up: new study reveals importance of liquid structural ordering in crystallization

    79 shares
    Share 32 Tweet 20
  • Study finds second primary lung cancer is 4 percent and as high as 8 percent among surgery patients

    78 shares
    Share 31 Tweet 20
  • United Kingdom-based smoking cessation program reports that 30 percent of support in a lung cancer screening program: the Yorkshire Enhanced Stop Smoking Study (YESS)

    77 shares
    Share 31 Tweet 19
  • NELSON trial protocol more sensitive than NLST and may increase the benefits of lung cancer screening, while reducing unnecessary follow-up procedures

    77 shares
    Share 31 Tweet 19
  • Sub-lobar surgery for peripheral non-small cell lung cancer non-inferior to lobectomy

    76 shares
    Share 30 Tweet 19
ADVERTISEMENT

About us

We bring you the latest science news from best research centers and universities around the world. Check our website.

Latest NEWS

Experts optimistic about converting coal plants to production of clean geothermal energy

A role for cell ‘antennae’ in managing dopamine signals in the brain

The walk of Japanese children develops differently from children in other countries

Subscribe to Blog via Email

Enter your email address to subscribe to this blog and receive notifications of new posts by email.

Join 193 other subscribers

© 2022 Scienmag- Science Magazine: Latest Science News.

No Result
View All Result
  • HOME PAGE
  • BIOLOGY
  • CHEMISTRY AND PHYSICS
  • MEDICINE
    • Cancer
    • Infectious Emerging Diseases
  • SPACE
  • TECHNOLOGY
  • CONTACT US

© 2022 Scienmag- Science Magazine: Latest Science News.

Welcome Back!

Login to your account below

Forgotten Password?

Retrieve your password

Please enter your username or email address to reset your password.

Log In