An Amoeba-Based Computer Found Solutions To 8-City Traveling Salesman Problem (vice.com) 87
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.
The true solution, or a usable solution? (Score:5, Interesting)
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.
Re: (Score:2)
Re:The true solution, or a usable solution? (Score:4, Informative)
There are tons of simple heuristics for quickly getting "good enough" solutions to optimization problems. So that is not interesting at all, and is not "solving" the TSP. To solve the TSP means to get the absolute shortest path. An amoeba based computer can't do that in polynomial time.
Re: (Score:3)
The computational trick is, it is not about going from one city to another, it is all about the journey itself and what route it takes. So you break up the journey from city to city, into smaller segments along that route and test those smaller segments, with the size of the segments defining accuracy or in journey terms, main intersections along that route. Although it sounds like you are creating more elements to analyse, what you are really doing is analysing the actual route rather than the destinations
Re: (Score:2)
The problem with what you suggest is that there doesn't seem to be any route (or road) in the description of the problem linked in TFA. Imagine you use an airplane. So, it seems like keeping a straight line between cities is optimal.
https://en.wikipedia.org/wiki/... [wikipedia.org]
Otherwise, like in real life where there are roads, you would have a point.
Re: The true solution, or a usable solution? (Score:3)
Re: (Score:2)
Re: The true solution, or a usable solution? (Score:1)
Yeah, that's impressive and all (Score:3)
Re: (Score:3)
Crysis?
I would have gone with "I, for one, welcome our new Amoeba overlords."
Re:Yeah, that's impressive and all (Score:4, Funny)
amateurs.
I have netbsd running on my 'meba cluster.
(systemd-free, too, mind you)
Re:Yeah, that's impressive and all (Score:4, Funny)
but can it run Crysis?
In general, no. Steam kills Amoebas, because boiling water is too hot for them.
That said, by lowering the ambient air pressure, you can make water boil at a lower temperature. Amoebas can survive sustained temperatures of 46 C. An online calculator tells me that water boils at 46C at .11 bar, and another one says that .11 bar is the air pressure at about 51,000 feet above sea level.
Of course, merely being able to survive Steam may still not be sufficient to run Crysis. To determine that with certainty, we need to devise a proper experiment.
Anybody have an SR-71 handy? We need to test this theory. This important question demands an answer.
Re: (Score:2)
Steam kills Amoebas, because boiling water is too hot for them.
That said, by lowering the ambient air pressure, you can make water boil at a lower temperature. Amoebas can survive sustained temperatures of 46 C.
They didn't survive Jack Tramiel.
Re: (Score:2)
Dyslexic much?
Re: (Score:2)
(Note for anybody who doesn't get the meta-joke, 46 C is C64 backwards, and the (Commodore) Amiga killed the C64/128, not the other way around.)
Re: (Score:2)
Re: (Score:2)
No, but it can create a one in the hospital system.
Remarkably difficult (Score:2)
The travelling salesman problem is not difficult if you're willing to settle for "approximate solutions".
Re:Remarkably difficult (Score:5, Interesting)
The travelling salesman problem is not difficult if you're willing to settle for "approximate solutions".
As a general rule, solving most problems is not difficult if you don't actually solve them.
Re: (Score:2)
Re: Remarkably difficult (Score:2)
Tesla needs this... (Score:2)
Right (Score:4, Insightful)
Re: (Score:2)
Re: (Score:2)
Yeah, that was my first though too, since the summary makes it sound that way, but the article explains in depth:
The challenge for the plasmodium to find the shortest tour is that its branches should not enter the frequently illuminated lanes and should elongate into the optimal combination of the least frequently illuminated lanes. However, the optimal combination cannot be found as long as the branches always obey the control principle; if always the branches shrank when illuminated and expanded when not illuminated, the plasmodium would not avoid falling into a local minimum. To better explore the potential energy landscape and locate the global minimum (the shortest tour), the plasmodium needs to misallocate the resource to its branches and the branches must violate the control principle with a certain small probability, because the lengths of the tours can be compared only when the branches operate contrary to their photoavoidance response
so the computer is only really defining where the "bounds" of the problem are. The ameoba really is doing the computational work (going *against* the computer's control) to find a nearly-optimal solution.
Re: (Score:2)
Re: (Score:2)
Not quite... since the water and valves could (I think) only find a "local minimum" or naive solution, not a near-optimal (global minimum) one, like the amoeba does. The lighted areas on the chip don't *prevent* the ameoba from going there, and in fact to find an approximate global minimum solution, the ameoba *has* to sometimes go where it doesn't want to, in order to maximize it's nutrient intake. In other words the water can't "decide" to go through a closed valve, but the ameoba can choose to extend i
Re: (Score:1)
Re: (Score:2)
So the amoeba is just a display? I wondered if I'd missed something when I read it.
Then I asked myself why it was even posted, since it's not really a story, is it?
And then I remembered where I was.
Can you imagine... (Score:3)
"Today" on Meta-Slashdot (News for 11-D Nerds) (Score:2)
Obligatory xkcd quotes (Score:3)
Re: (Score:2)
There is an O(1) solution
There will be when q-computing is efficiently working.
The Operating Syatem. (Score:2)
From the title, I thought maybe this was about the Amoeba Operating System [cs.vu.nl]. No such luch, alas.
Flawed model (Score:2)
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.
Amoebas as Salesmen (Score:2)
So we can now replace salemen with amoebas? I might even listen to an amoeba.
Since we're talking amoeba (Score:2)
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.
Which is the intelligent part? (Score:1)
Hm, is the intelligent part the amoeba or actually the neural network coaxing them towards the solution?
Commodore's Amoeba was a great computer (Score:1)
...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.)