Slashdot Mirror
An Amoeba-Based Computer Found Solutions To 8-City Traveling Salesman Problem (vice.com)
dmoberhaus shares a report from Motherboard: A team of Japanese researchers from Keio University in Tokyo have demonstrated that an amoeba is capable of generating approximate solutions to a remarkably difficult math problem known as the "traveling salesman problem." The traveling salesman problem goes like this: Given an arbitrary number of cities and the distances between them, what is the shortest route a salesman can take that visits each city and returns to the salesman's city of origin. As these Japanese researchers demonstrated, a certain type of amoeba can be used to calculate nearly optimal solutions to the traveling salesman problem for up to eight cities. Even more remarkably, the amount of time it takes the amoeba to reach these nearly optimal solutions grows linearly, even though the number of possible solutions increases exponentially. The reason this amoeba is considered especially useful in biological computing is because it can extend various regions of its body to find the most efficient way to a food source and hates light.
To turn this natural feeding mechanism into a computer, the Japanese researcher placed the amoeba on a special plate that had 64 channels that it could extend its body into. This plate is then placed on top of a nutrient rich medium. The amoeba tries to extend its body to cover as much of the plate as possible and soak up the nutrients. Yet each channel in the plate can be illuminated, which causes the light-averse amoeba to retract from that channel. To model the traveling salesman problem, each of the 64 channels on the plate was assigned a city code between A and H, in addition to a number from 1 to 8 that indicates the order of the cities. To guide the amoeba toward a solution to the traveling salesman problem, the researchers used a neural network that would incorporate data about the amoeba's current position and distance between the cities to light up certain channels. The neural network was designed such that cities with greater distances between them are more likely to be illuminated than channels that are not. When the algorithm manipulates the chip that the amoeba is on it is basically coaxing it into taking forms that represent approximate solutions to the traveling salesman problem.
To turn this natural feeding mechanism into a computer, the Japanese researcher placed the amoeba on a special plate that had 64 channels that it could extend its body into. This plate is then placed on top of a nutrient rich medium. The amoeba tries to extend its body to cover as much of the plate as possible and soak up the nutrients. Yet each channel in the plate can be illuminated, which causes the light-averse amoeba to retract from that channel. To model the traveling salesman problem, each of the 64 channels on the plate was assigned a city code between A and H, in addition to a number from 1 to 8 that indicates the order of the cities. To guide the amoeba toward a solution to the traveling salesman problem, the researchers used a neural network that would incorporate data about the amoeba's current position and distance between the cities to light up certain channels. The neural network was designed such that cities with greater distances between them are more likely to be illuminated than channels that are not. When the algorithm manipulates the chip that the amoeba is on it is basically coaxing it into taking forms that represent approximate solutions to the traveling salesman problem.
With genetic algorithms, you can come up with a solution in linear time (as in 100 seconds for 100 cities, 200 seconds for 200 cities, etc.) that is "good enough". It won't come out with the best one, proven mathematically, but if you are looking for a useful answer rather than _the_ answer, it works.
This work with the amoeba seems like it can give a passable solution, but it would be interesting if it did give the actual shortest out there.
"An Amoeba-Based Computer Found Solutions To 8-City Traveling Salesman Problem" = Nope, Japanes AI still can't write headlines for a damn, dame desu
also requires that each city is visited exactly once. So did the amoebae solve a different problem, or was the article not accurate?
The amoeba didn't solve it did it... the nutrient solved it.
The nutrient gradient would be the solution, the amoeba simply followed that.
How much money was wasted on this?
but can it run Crysis?
Hi! I make Firefox Plug-ins. Check 'em out @ https://addons.mozilla.org/en-US/firefox/addon/youtube-mp3-podcaster/
The travelling salesman problem is not difficult if you're willing to settle for "approximate solutions".
Smarter and more useful than Trump.
If u dont mind a little Slime. :)
[($)]
So basically - we designed a method to make an amoeba respond in the way we wanted, then lo and behold, the amoeba - when "coaxed" by our model, responded the way we wanted... It's a miracle I tell you.
Seven puppies were harmed during the making of this post.
So if you know the outcome you desire you can coax a biological creature to conform to your desired outcome.
In other words, Pavlov did this with Dogs.
I think there are horses that do this as well.
It is all just a matter of voltage.
...a Beowulf cluster of these?
- First they ignore you, then they laugh at you, then ???, then profit.
Nowhere does it say the amoeba did the thinking, and if the amoeba does no compooting, it's not amoeba-based.
"4-Dimensional Bags of Mostly Water Evolve Sentience and Create An Amoeba-Based Computer Which Found Solutions To 8-City Traveling Salesman Problem"
There is an O(1) solution to this NP-complete problem.
From the title, I thought maybe this was about the Amoeba Operating System . No such luch, alas.
The challenge of the Traveling Salesman Problem is the combinations. The amoeba is trying all solutions at once, and the light is telling it where not to go. The real question is, "Given the preconditions, and the behavior of an amoeba, could it not create an approximate solution?" Clearly not.
So we can now replace salemen with amoebas? I might even listen to an amoeba.
A paramecium and an amoeba are walking down the street. The amoeba asks “So, lacking any pseudopodia, how do you manage to get around? The paramecium replies “A cilia question I’ve never heard!”
-----
Why did the amoeba flunk the math test?
Because it multiplied by dividing.
Hm, is the intelligent part the amoeba or actually the neural network coaxing them towards the solution?
...but it largely shied away from the limelight and never gobbled up much market share.
I thought Slashdot just posted its annual Amoeba elegy post last week.
(Sorry.)
An octagon of cities is the (global) optimal solution of the 8-city TSP.
Why? Because the human reasoning believes it until that it is definitively perfect.
My theory seems to be correct. Humans are just like amoebas for the gods. Solving tough questions with minimal input.
https://play.google.com/store/apps/details?id=amusement.arcade
42.