Slashdot Mirror
Bees Beat Machines At 'Traveling Salesman' Problem
eldavojohn writes "Recent research on bumble bees has proven that the tiny bee is better than computers at the traveling salesman problem. As bees visit flowers to collect nectar and pollen they discover other flowers en route in the wrong order. But they still manage to quickly learn and fly the optimally shortest path between flowers. Such a problem is NP-Hard and keeps our best machines thinking for days searching for a solution but researchers are quite interested how such a tiny insect can figure it out on the fly — especially given how important this problem is to networks and transportation. A testament to the power of even the smallest batch of neurons or simply evidence our algorithms need work?"
now you get a faster computer that makes honey!
After the genetic vector is put in, all the bees have to do is keep track of the sun. What amazes me though is how they look at another bee and visualize it traveling to a set patch of flowers, by looking at its dance.
quite interested how such a tiny insect can figure it out on the fly
I thought we were talking about bees? I am so confused...
See my journal for slashdot ID's by year. Mine created in 2005. http://slashdot.org/journal/289875/slashdot-ids-by-year
Hah! They may be on top now, but thanks to CCD we won't have to be #2 for long. Goooooooooo humans!
In Capitalist America, bank robs you!
Simulated annealing.
Yours In Akademgorodok,
Kilgore Trout.
Is it possible that the honey bees aren't really solving the Traveling Salesmen problem at all, but rather employ some sort of unknown heuristic that leads to solutions that's close enough to optimal for it to look like that they've solved it? Maybe that's what we should be looking at rather than pondering if bees somehow have some sort of superior calculating ability over a supercomputer.
After all, when we're playing a game of baseball (right, right, I know, this is slashdot), and a ball is coming towards us, we aren't calculating in our heads the velocity, air resistance and other variables involved in catching the ball. We just reach out our arms and our brain makes its best guess based on some sort of heuristic or something to make the catch.
My postings are informational and does not constitute legal advice. Act on it at your risk.
who/what is god?
First and foremost, how many nodes are we talking about here? I highly doubt that the bees are keeping track of hundreds of feeding spots from one trip out to the next but the article doesn't say.
The second problem is this "Computers solve it by comparing the length of all possible routes and choosing the shortest." Who on earth would try to solve the traveling salesman this way? Yeah, a brute force solution will get you the guaranteed best path, but the performance is horrible. There's lots and lots of shortcuts that can save a huge amount of time, things as simple as eliminating crossed paths can make a big difference. You can even use techniques like genetic engineering successfully on such a problem (though you might not reach the absolute best path that way).
We need to expend more effort to recruit bees into computer science. Too many bees are wasting their lives solving these problems on the fly for a little nectar when they could be solving these problems in exchange for tenure at our nation's finest universities.
Was the Travelling Salesman presented with the completely connected graph the way the bees were? The bee isn't constrained to fly along predefined paths between nodes, the travelling salesman is.
Maybe P=NP and the solution is easy?
Does this mean that B >= NP?
We have a lot yet to learn from our six-legged colleagues, from the sound of it. Recently some work was done on optimizing machine vision using an algorithm derived from the way the house fly's vision works. The termite's wood-digesting gut is a prime object of study for those seeking to manufacture fuel from biomass efficiently and cleanly. An insect virus (the baculovirus) is the new hotness for gene transduction in mammalian cells because it can't actually cause disease.
I think this might be the next step in bioengineering. We've been grabbing genes out of various organisms and sticking them in bacteria to produce useful biomolecules like insulin and factor VIII. Maybe the insect is our next stop.
Actually I worked this problem years ago, despite having not found a solution, I was able to determine the problem is fundamentally far simpler than traveling salesman as the nodes are distributed on a sheet with simple calculations.
So what is the solution? Do you sleep with the farmer's daughter or sleep in the barn?
Maybe I'm thinking of a different "traveling salesman" problem.
First TFS and TFA both make reference to problems which "keep super computers busy for days." That's pretty misleading since the bees are only dealing with "a few hundred" flowers. At brute force that would take your cell phone maybe a couple minutes to solve.
But really no details are given. Do the bees still travel to all of the flowers? I'd imagine they might just decide to skip one or two if they don't fall close enough to the path to be worth it. They don't say what they did (probably nothing) to validate that the bees actually found the shortest path. Did the "graph" that they gave the bees include a section where a greedy algorithm would fail? What is more likely is the bees haven't solved it, but found a decent approximation.
I think this is what you get when you let bee researchers write math/computer science articles.
I imagine that the hierarchical models proposed by Scott Graham would be a pretty good candidate. If you break the TSP problem into a series of sub-problems of increasing complexity you get pretty good accuracy with reduced computations. Basically instead of trying to figure out how to move through all the towns in the US you first plan a route through all the states. You could probably derive a few simple heuristics that would give you that sort of behavior from a swarm...
They leave a trail of hormones, the shortest paths get more travelers, over time, it becomes obvious which path to use, it has the strongest scent.
Kirk says he need a spaceship... also, I have no idea what this has to do with bees
It's an abbreviation for Good Old Darwinism.
http://alternatives.rzero.com/
After all, when we're playing a game of baseball (right, right, I know, this is slashdot), and a ball is coming towards us, we aren't calculating in our heads the velocity, air resistance and other variables involved in catching the ball. We just reach out our arms and our brain makes its best guess based on some sort of heuristic or something to make the catch.
I think the problem with your analogy that there are an unlimited number of dimensions and responses where you could put your arm out to make the catch (well, not unlimited if you consider Planck distances to be the smallest possible distance). But when we are talking about computerized flowers with nectar, you pretty much can only go to one of the flowers next. I think they used RFID to track the bees (or at least this researcher has written about doing that before)? So we can sit there and do a star search on all paths of the 50 flowers and find the shortest one to connect all of them in three dimensions in a particular order (we assume the flight paths are straight lines). The difference is not that we have so many fewer things to search than in the ball catching example but that you take a very finite deterministic path (i.e. 2, 34, 23, 6, 18, etc) and the bees seem to be able to find and learn this very quickly. According to the researcher:
"In nature, bees have to link hundreds of flowers in a way that minimises travel distance, and then reliably find their way home - not a trivial feat if you have a brain the size of a pinhead! Indeed such travelling salesmen problems keep supercomputers busy for days. Studying how bee brains solve such challenging tasks might allow us to identify the minimal neural circuitry required for complex problem solving."
If this holds true for hundreds of flowers, I think we're talking about a serious search space with a definite path that is far more specific than the heuristics of moving your arm and hand around dynamically in space to collide with a ball. You could have tons of error when trying to catch a ball and still catch it. You (frequently) only have one optimal path in shortest distance problems. It's probably true these traveling salesman problems look obvious to a bee like catching a ball does to us but something particularly interesting is going on there if it is.
Let's say it is an unknown heuristic. I'd wager the network folks would kill to know how that heuristic is so cheaply computed.
My work here is dung.
What this really shows is how efficient society would be if we sterilized all workers.
I read TFA and it seems more focused on the excitement that the bees can solve the TSP, but the researchers never seem to indicate how the bees are doing it, and given the nature of the problem, how do they know it really is the "optimum" solution. Based on my limited work with the TSP, the only algorithm that, for my purposes, has worked the best is Nearest Neighbor, which is also, I believe, the simplest but also most naive.
Would be interesting to know what the bees' algorithm is.
God has worked out these issues long before we even thought of them.
You know he doesn't like to be called that.
In the number 8 bee... Yaritza Burgos!
Gentlemen, we have a race
For justice, we must go to Don Corleone
who/what is god?
I think it's one of the security modes in Linux ... I know one of the user modes in Windows is called "damn!".
Is it possible that the honey bees aren't really solving the Traveling Salesmen problem at all, but rather employ some sort of unknown heuristic that leads to solutions that's close enough to optimal for it to look like that they've solved it?
This article is fundamentally misstating the TSP. If it were the TSP, the bees wouldn't get to choose their route.
As other bees come in and report their route taken and pollen collected, another bee will put bits of those routes together. (Which would be the surprisingly difficult part to me, since the bees are doing some pretty complicated vector algebra.) But a bee is going to have a budget of so much daylight and will attempt to maximize the amount of nectar it collects in that time, given the bits of routes collected by other bees and its own scouting. But it's not given a list of points it has to hit, it picks its list from a larger list of points. That's fundamentally different from the TSP, even solving it by heuristic.
Gosh, that is one hell of a bee if it has the brain of a piece of corn... or is corn not a grass anymore? At least when you take some idiotic comparison, take one that has a non-changing size. Penny is okay because all pennies at least within a country tend to stay the same. But grass seeds?
Next up is "brain the size of a pinhead". Oh okay, so there are many sizes of pin but at least we can assume some kind of standard. And that is FAR smaller then most grasses I know and see seeds of in Holland.
Otherwise intresting stuff but I loathe this "make it easier" by obuscating the facts.
Number of neurons in honey bee brain = 950,000 (from Menzel, R. and Giurfa, M., Cognitive architecture of a mini-brain: the honeybee, Trd. Cog. Sci., 5:62-71, 2001.)
Now THAT is a fact. We? We got 100 billion. So, while a bee has a tiny brain compared to ours, it is HARDLY simple. And because it is far smaller and far more primitive it doesn't need as as much intelligence to deal with things it doesn't need to. Listening and producing speech is complex, but bees don't bother with that. Living for half a century and remembring everything is complex. But bees don't do that.
This why computers can do math so fast despite being so stupid, because they only do math.
How can the bee do route calculation with close to a million neurons? I have no idea but didn't research show that far fewer rat neurons could fly a plane? I think some people fastly underestimate the complexity of the brain even small ones. We already know that a neuron is far more then a simple transistor so 1 million super transistors would make for a hell of a complex computer. Suddenly it doesn't seem to odd that a bee can do computations far more complex because THAT is what it is designed to do. You could just as easily marvle at the fact that the bee with its tiny brain can fly, while I with my large brain can't. And no I don't just mean I don't have wings, I mean that if you put me in a helicopter you would have a horrible crash in seconds and that is in the passenger seat.
Marvle at nature, learn from it but don't belittle it. It takes us year to program a robot to walk very very slowly. A deer learns it in minutes and this includes learning to control legs locked up in a womb for months. We can either accept that nature is amazing or we are very very poor programmers... as a developer, I choose to believe that nature is amazing.
MMO Quests are like orgasms:
You may solo them, I prefer them in a group.
The computer isn't going to die if it doesn't get the right path, the bee might. Death is a remarkably strong motivator to be efficient.
stuff |
The bees that didn't knew how to somewhat "solve" that are the dead ones.
Or just use Ant Colony Optimisation, which has been doing this for 18 years.
Also, there is a constrained version of the problem called Bitonic Tours which is solvable in poly time, which might match the flower scenario well.
Tsunami -- You can't bring a good wave down!
Thereby substituting one guy with a beard who must be worshipped for another.
The travelling salesman problem is the problem of finding the shortest route between a set of points. It doesn't matter HOW you solve it. You could time all possible journey's, you could do a sorting routine or god knows what. But if you solve it, you solved it.
That is what the bee does. And maybe if we can learn HOW the bee does that, we might learn something from it. It might be a smarter way of solving things. Or maybe Bees have an additional variable from an unknown input that helps solve it.
And as for your brain just GUESSING? Jezus, do you know how FUCKING difficult GUESSING is? Been trying to get computers to make a best guess for ages. It is advanced computer science.
Calculating the path of a ball in flight is actually pretty easy. All I need is a couple of accurate measurements of its position in time and space. Trivial stuff. But GUESSING from in complete and missing data were a ball is going to be AND being right most of the time or at least have moved an appendage in time so that when more accurate data is available I already got the appendage in roughly the right area? THAT is NOT easy. And yet our brain and the brains of many an animal does it. And does it VERY fast indeed. Throw a bouncy ball at a cat and watch it chase it (or in the case of my cat decide in a pico second that "you threw it, you catch it" is the wisest course of action and fall asleep), control a body and CATCH it. Meanwhile we marvel at a robot because it managed to stand upright...
Now if a machine could duplicate the brains method for catching a ball, that would be very handy indeed. Because SOMEHOW our brain does do it. And yes, this DOES include wind velocity correction. We are aware of the wind and we correct for it. Thanks to our brain. It doesn't matter that we don't use a laser ranger finder or dopler radar, that is just details. It is the logic that can use incomplete, unreliable data that results in accurate results that scientists are interested. It would allow for computers to keep functioning even when sensor data goes missing. An essential for computers/robots to come out of the production halls and into our daily lives. If a spell checker could guess as accurately what I meant to write as YOU can read over my mis spellings and lousy grammer, Clippy would be a lot more usefull.
MMO Quests are like orgasms:
You may solo them, I prefer them in a group.
So what is the solution? Do you sleep with the farmer's daughter or sleep in the barn?
Why choose? Haven't you heard of a "roll in the hay" before?
Kinda reminds me of the Geek shopping team. If you want perfect you'll never get close enough to pull the trigger but shoot for close enough and you're off to the races.
Don't we already know that babies can pick out shapes/voices/etc that take computers all sorts of processing power to figure out. Or how we are still trying to refine things like recognizing a face or depth or whatever, when people just 'know'. The brain is still amazing despite all the power computers now have, regardless of human or insect species.
I will shred my adversaries. Pull their eyes out just enough to turn them towards their mewing, mutilated faces. Illyria
I think computer algorithms fail to appreciate the cost-benefit of their suboptimal solutions, and need about 70 million years of evolution to get it right. It's probably also true that these vespids had another use for the algorithm before they evolved into co-adapted pollinators, possibly dating back another 100 million years or so. The earliest honeybees in amber, dating to the Cretaceous, are obviously honeybees, which makes their clade and its adaptations immensely old.
``Tension, apprehension & dissension have begun!'' - Duffy Wyg&, in Alfred Bester's _The Demolished Man_
So long as it's not the Crushinator, you ALWAYS sleep with the farmer's daughter.
an ordinary honey bee only visits 5 flowers over the course of a day? Its probably on the order of hundreds, usually one ever 50-120 seconds, when not spending time in the hive.
I want it!
Hello Man.
I am Bee #32653. Do you want better flowers for your mate?
Click here!
My first Journal Entry ever, in 8 years! http://slashdot.org/journal/365947/aphelion-scifi-fantasy-horror-poetry-webzine
equals/not equals or equality/inequality. What is the difference, right?
The canonical traveling salesman problem usually is states that all cities must be visited. The bee is not under this constraint. This changes the problem from a do-or-fail NP hard problem to a more simple approximate optimization problem. The latter have many many many many many good solution paths in computers. Perhaps the newest and best approach that resembles the bee's agent based learning approach is called Probability Collectives (google it). You'll want to learn it since it works well on parallel computers, distributed computing, and most of all on systems composed on many dumb subunits on a sparsely connected network with no central command and control (think mobile devices).
Some drink at the fountain of knowledge. Others just gargle.
must be isomorphic to genetic algorithm problem solving, which can also solve the traveling salesman problem quickly, if slightly imperfectly. I'm guessing the same imperfections will show up in the bee's solution to this problem.
Please do not read this sig. Thank you.
No "I for one welcome our new insect overlords"? Who are you and what have you done with Slashdot?
Hoist Number One and Number Six.
(A) Bee algorithms - worked out by God (done)
(B) Human (bigger than bees but afraid of them - worked out by God (done)
(A) + (B) = Dead Bee (and order in my universe)
L'esperienza de questa dolce vita (The experience of this sweet life) - Dante Alighieri, The Divine Comedy
Sorry, I already substituted God for a different beard guy, Richard Stallman.
There's no -1 for "I don't get it."
If you build a maze that has multiple routes through it, and two pieces of food in it, and drop a bunch of slime molds into the maze in various places, they will fairly rapidly coalesce into a single slime mold that extends through the maze on the shortest route between the two bits of food. Now, that's no traveling salesman problem -- but slime molds are single-celled animals, so they don't have *any* brains to do the calculations. They just rely on minimizing surface area and maximizing access to food. (And being able to stop being multiple organisms and start being a single organism, but that's an aside.)
Nostalgia's not what it used to be.
A bee will never beat me at Ticket to Ride, the ultimate traveling salesman problem game.
You mean millions of iterations of random chance have selected the most efficient pollen-gatherers.
Click here to find out how this guy made his stamen 50% larger!
There are two types of people in the world: Those who crave closure
Anyone who thinks the bees solved NP-hard problem here does not know what they're talking about...
Those bees did not do an exhaustive search for the optimal path, only one that is 'good enough'. Computers can do the same with any decent algorithm. Only difference here i assume is that the bees have hardware that has gone through natural selection to produce a pretty good 'best effort' algorithm.
If those bees can produce the optimal path for all corner-case setups then I'll be rather impressed.
- These characters were randomly selected.
Hmmm, I don't see any accounting for wind in there.
There are two types of people in the world: Those who crave closure
We need a better algorithm.
Did the giant gorilla lesbian look out from her mountain beyond the horizon and create perfect bees to begin with a million years ago? Or have a million years of natural selection culled the perfect algorithm by providing a reproductive advantage?
If it was the G-L, then how did the bees remain unchanged when so many other species have changed and when we observe natural selection every day.
I can see why G-L let's humans die i such terrible ways tho. She favors animals over man.
She was like chocolate when she drank... semi-sweet at first and then increasingly bitter.
"The second problem is this "Computers solve it by comparing the length of all possible routes and choosing the shortest."
Well they can try, but this does not provide a closed solution since there are too many comparisons to evaluate for optimaliity. In the traveling salesman problem there is a very high rate of generation of subproblems in making any comparison as to which of any possible combination of nodes to discover the optimally correct solution. As one adds more nodes to the graph, the number of their combinations multiply at a faster rate than
does an iterative procedure in counting (compare) them. Consequently, the problem of choosing an optimal solution depends not only upon what one how one defines optimal, but also becomes non-polynomial bounded the as the number of potential additional nodes are considered increases the number of subproblems. Hence, the number of subproblems that must be solved in order to work out the potential optimal solution is enormous even for a few nodes. Get out to 1500 or so and you are talking about more potential combinations than electrons in the known universe. No supercomputer yet devised comes up with that solution in real time of where in space these electrons must be in order to move the least among their positions that won't take millions of years.
It's just goofy thinking that even over a million years, slight advantages in reproduction would make any difference.
Besides, the world was created last tuesday with everything in place as it is anyway. Some folks just talk crazy with this natural selection and evolution stuff. But since G-L created them this way last week, you have to assume it was for a purpose. Probably to test us.
She was like chocolate when she drank... semi-sweet at first and then increasingly bitter.
That's GNU/Linux to you!
There's no -1 for "I don't get it."
So they have proof that these bees solve the travelling salesman problem? Not just get a good approximation? Not just solve a slightly constrained version? Not just solve a slightly different problem? You know all the things that computers do just fine thank you very much, and aren't NP-hard.
I notice the journal is a Naturalist one and the researchers aren't are bioligists and chemists not computer scientists.
I have no difficulty believing bees have evolved (or been designed with if you must for those I don't feel like arguing with) a very efficient way of collecting pollen - it is after all fundamnental to their survival and reproduction. But that they happened to solve an NP-Hard problem that they have no need of solving (does an individual bee really visit *every* location on one trip? surely some imperfection would help in discovering new plants by having bees follow different paths?) - that seems a bit of a stretch.
Maybe they are able to quickly identify distinct groups of flowers on their first pass using their compound eyes, which by necessity would be tightly clustered. Then they just visit the groups in the most obvious order starting at the point they observe the last flower. They could compare 100 runs over the same flower bed and easily find groupings by overlaying the paths.
while [ 1 ]; do echo -n -e "\xe2\x95\xb$((($RANDOM&1)+1))"; done
Oh, this one again. I've seen this claim made for neural nets back in the 1980s, and for DNA computers in the 2000s. It's bogus.
The guaranteed-optimum solution to the TSP is NP-hard. The "gets to the optimum 99% of the time and close to it all the time" solution is easy. It was developed at Bell Labs in the 1960s. Here it is:
This is a particularly efficient way to do it. I once coded this for a PC/AT, and it took less than a second for N=50. Almost any scheme which randomly breaks links and tries to improve the path will eventually converge on a near-optimum solution.
I think Slashdot needs a "+1, Atheist" now.
Gamingmuseum.com: Give your 3D accelerator a rest.
If we had the answer to how bees can do this so much better than computers, we'd have the answer to making self-aware machines - I suspect it has much to do with not being able to effectively program biology, physics, chemistry and a few million years of evolution (the understanding of which we are still far from grasping ourselves) at the microcosmic scale. The bees are not thinking about this, or running a computation. (Have you seen their brains? Me neither. Probably only hobbyists and biologists have seen their brains. That's my point. They're awfully small, and not well suited to algorithms.) They're adapting to their environment in a way we don't -- and can't -- understand; in the same way a computer can't understand the reasons for the rules we program into it. It's too far outside of our frame of reference.
Question is...did the bees evolve to find the corner cases, or did the plants evolve so the damn bees could find them in the first place? After all, plants that are stupid enough to hide from bees while simultaneously needing them to reproduce would stand a good chance of not making it to the next generation ;-)
People replying to my sig annoy me. That's why I change it all the time.
Exactly what straw-man are you arguing against, then?
Gamingmuseum.com: Give your 3D accelerator a rest.
NP-Complete is a much tighter constraint on the computational complexity. Yeah, it's NP-H, but it's also NP-C. NP-Hard must sound harder... I dunno.
Imagine if you weren't allowed to use roads because a bus company complained about your driving 3 times. --skunkpussy
Probability Collectives are interesting because they are one of very few optimization alogorithms born from first principles considerations. For example, Simmulated annealing comes from Metropolis/hastings search and that was a brilliant breakthrough that allowed rapid exploration in a way that guarentees detailed balance. Parallel Tempering is the parallel extension of that first-principles argument. Most other search and optimization algorithms are born from either heurisitics expected to align with a search domain or considerations based on efficient algorithmic implementation (such as genetic algorithms). While one can go back and try to develop rigorous theories around expedients and heuristics, and there's a whole industry of that, in the end it's better I think to start from first principles.
Probability collectives starts with the assumption that that a team of agents will be making decision independently that affect the search path and that each agent is bounded rational. That is, each agent not only can't know everything, but can't be relied on to make optimal choices every time. You then discover what game theory says is the best way to search in this situation. You might visualize a set of airliners trying to negotiate landing times under conditions were some of them have been delayed and you have to reprogram flights in real time with incomplete knowledge.
As the algorithm searches the bound on the rationallity is annealed towards perfect rationality since more information is learned.
The algorithm tends to very efficiently use past information (compared to a GA or simulated annealing) but the per-interation computation effort is higher. Thus it is best applied in cases where agents are distributed (no centralized optimizer) or where the cost of gathering data is high or where the agents have available computing time between samples. One example of it's use in dumb-ditributed systems was the control of wing flaps on UAVs. Many micro flaps were agents which, without a central processor, solve the problem of prevent turbulence instability. presently it has achieved the highest wing speed without turbulence of any method, even ones that try to solve detailed physics equations in a central flight computer.
Most research on this approach is still in academics of the basic theory. very little attention has been placed on efficient coding of the methods. There are no libraries for it available. This would make a great CS master's thesis project for someone or indeed many people since the theory at this point is large.
The travelling salesman problem is nice because the "best" answer is actually the worst answer, in that to arrive at it, you have to perform massive amounts of computation that's difficult to serialize. But bees most certainly do not do this! I'm going to guess that, like people, they automatically factor in the expected cost of computation and look for an answer that's "good enough" - not technically perfect, but an approximation thereof that's cheap to compute.
Look at it this way - you are more likely to go for a software solution that's a button-click or uses off-the-shelf or already available OSS simply because the computational overhead of writing your own webserver is generally considered too difficult, even though you would arrive at a more technically correct or optimum solution by going at it yourself.
Good software design consists of many "good enough" solutions that avoid unnecessary "Expensive" computation (Engineer's time) at the cost of "Cheap" computation. (CPU time) When we apply this idea to the algorithm, we can have similar results. Compare simple literal string matching algorithms to the Boyer-Moore search algorithm - dramatic improvements in performance by pruning the amount of necessary computation!
I have no problem with your religion until you decide it's reason to deprive others of the truth.
Those bees did not do an exhaustive search for the optimal path, only one that is 'good enough'.
How do you know this? I'm not seeing that stated in the article. In fact,
Scientists at Queen Mary, University of London and Royal Holloway, University of London have discovered that bees learn to fly the shortest possible route between flowers even if they discover the flowers in a different order.
This seems to directly contradict what you're saying, so I'll assume you have access to more information and will be linking likewise shortly...
Except that flowers aren't inert. A bee is getting constant feedback to the "closest" flower, because it can see it (albeit in UV), and smell it. There is also reinforcing as bees communicate with each other. So many of you are IT guys - you know that its far easier to track agents and find optimal paths when each agent is sending out a signal that varies in amplitude/time and possible even leaving a gradient. In the traveling salesman problem, locations are essentially just that - non-interactive coordinates. Also the salesman doesn't have an army of other salesmen who will share information with him.
It's very interesting to see how bees work, but this definitely is NOT the classical traveling salesman problem. Same with slime moulds, their strategy is to follow chemical gradients, and then communicate WITH each other, reinforcing that path.
Entia non sunt multiplicanda praeter necessitatem.
That's a fucking awesome idea.
WTF am I doing replying to an AC at 5 A.M on a Friday night?
. . .and can you have it bring me a chicken sandwich?
That's a simple way of saying that evolution created a program in their brains that solves the TSP fairly efficiently under certain constraints.
I always thought it was an abbreviation of Game Overall Director...
I've abandoned my search for truth; now I'm just looking for some useful delusions.
Hmm.. The idea that a mystical beeing hand crafted bees to bee efficient? The need for a supernatural strawman to explain things when we have perfectly good, rational explanations which do not need a G-L to explain why bees are efficient at collecting pollen?
She was like chocolate when she drank... semi-sweet at first and then increasingly bitter.
I'd be willing to bet it has something to do with the fact that you have an entire hive of bees each attempting to find the shortest path and then sharing their experience via that 'bee dance' thing (http://www.youtube.com/watch?v=-7ijI-g4jHg). Each bee is a thread with its own particular solution to the problem. Each bee's behavior contributes random heuristic alterations to the nectar-gathering path based on bee instincts evolved over millions of years. The bees periodically exchange solutions via the bee dance. It's a classic Genetic Algorithm.
The solution to the Traveling Salesman Problem has already been found--it's called a chastity belt.
Set your phasers on "funky"!
Thanks - this is what I was thinking too. It seems like the hard part of TSP is to *prove* that the shortest solution is in fact shortest. I think it's relatively trivial to find a very short solution to the problem (even by hand for a reasonable # of nodes). Demonstrating that the proposed path is in fact the absolute best is where the headaches (NP time) come in?
He created us last Tuesday and then implanted false memories, so we would imagine have existed for the past 6000 years!
I think you are onto something here.
The critically missing corner case is that TSP is not typically a fully connected graph, whereas the open air typically is.
"Who is the Journal of Quantum Physics going to believe?" --Stephen Hawking
I'm a GNU-atheist.
All that is necessary for the triumph of good is that evil men do nothing.
You can't even spell "atheism" correctly?
All that is necessary for the triumph of good is that evil men do nothing.
flowers == advertisements
Deleted
Why on Earth would someone worship an entity that feels the compunction to deceive them from the get-go?!
the preceding comment is my own and in no way reflects the opinion of the Joint Chiefs of Staff
the best algorithms a group of socially inept nerds locked up in flourescently lighted rooms could come up with can't compete with either millions of years of evolution and/or an omnipotent, omnipresent guy who may or may not be bearded...
*boggles*
whooda thunk it?
Anyone who thinks the bees solved NP-hard problem here does not know what they're talking about...
Those bees did not do an exhaustive search for the optimal path, only one that is 'good enough'. Computers can do the same with any decent algorithm.
Solving an NP-hard problem does not mean you do an exhaustive search. In fact, exhaustive searches are rather the bane of NP hard problems. If you could solve an NP hard problem without an exhaustive search, it would be strong evidence that P = NP.
Solving an NP hard problem means you always find the optimal solution. If the bees' "good enough" solution is optimal, they have solved it.
After all, I am strangely colored.
or "miada". In Spanish that would make it Bee Pee.
It's not a "missing case". The TSP just says to visit each of the nodes, in a Hamiltonian circuit. They are always connected graphs.
After all, I am strangely colored.
Not "Darwin"... "Darwinism".
Darwinism is not the worship of a guy called Darwin, but a scientific principle named after a guy called Darwin.
I would have said "Good Old Natural Selection", but that wouldn't have spelled "GOD", so it wouldn't have been funny.
http://alternatives.rzero.com/
Didn't read the article, but it's totally bunk. The two dimensional TSP is not NP complete (unless P=NP), it's actually in P. In order for the 2d TSP to be NP complete, you have to allow crossing paths and arbitrary values (not just the euclidean distance between the nodes) for the lengths of the edges.
Game Over, Dude!
http://fakescience.tumblr.com/post/1367356168/how-are-bees-organized shows how bees are organized to beat machines and anything else. [grin]
Ant(Dude) @ Quality Foraged Links (AQFL.net) & The Ant Farm (antfarm.ma.cx / antfarm.home.dhs.org).
This seems to directly contradict what you're saying, so I'll assume you have access to more information and will be linking likewise shortly...
You must be new here ;)
All going to the same places and adding a few in between as they went...then meeting other salesman on the route and each exchange new locations....by the time all the salesman return to the home office all new data would be synced at the bar over stingers.
Is that similar to an aGNUstic?
This is the second time you've corrected someone with your misunderstanding.
Over air, every node is connected, directly, to every other node. This is a much easier case to solve than a typical TSP where to get from node A to node C, you may have to go through node B .
--Jeremy
Jesus was a liberal
Huh? Plants can choose how they evolve?
But, judging from your other post, you don't believe that. You believe they were magically programmed by an invisible man in the sky for which there is no proof.
I never understood why BeeOS didn't catch on, since it was clearly the most clever of the bunch. I guess their salesmen traveled efficiently, but not effectively.
As Alec Baldwin pointed out in Glengarry Glen Ross: A...B...C - Always Bee Closing!
I wonder if those bees just sniff their way into an optimal solution. A bee gathering pollen will probably lose some in flight. Even more so when 'fully loaded'. Those lost pollen would fan out in time. That would mean that from a certain point/ flower, a bee could find the direction of the best path to take by sniffing the direction where the most pollen come from. Doesn't take much computing power. So I guess my question would be: is the hypotheses tested with different weather conditions? Especially wind direction and force.
"The plants evolved so bees could find them" does not imply intent or decision. It simply means it happened, and pollination by bees, and thus the need for the bees to find them, was the selective pressure that drove the evolution. Similarly, "giraffes evolved to graze from trees other animals couldn't" doesn't mean giraffes were looking longingly at the high up branches and wishing they had long necks. It means that's how they adapted to competition via natural selection.
Similarly, statements like "Bee eyes are designed to see UV wavelengths that flowers reflect strongly in" does not imply a "designer", bee, alien, or god, actually designed their eyes. Their eyes have a design, and it has an apparent purpose.
Sometimes words have implications in common English that do not apply to all situations.
The enemies of Democracy are
No, that's simply not true. The basic form of the TSP consists of a fully connected graph of cities, i.e. you can get from any city directly to any other city.
The non-fully-connected graph is a special case of TSP, and it is these cases that may end up simpler to solve (though often not, other than not being fully connected means there are fewer possible routes to check for the same number of cities).
The enemies of Democracy are
Whether or not it "typically" is fully connected, the standard form wherein it is proven to be NP-hard is fully connected. It is not any easier to solve in that special case; in general it is harder. Any non-fully connected form can be converted to fully connected form by adding in the necessary connections with arbitrarily large lengths.
The enemies of Democracy are
I'm not sure if you mentioned "God" there in jest, or if you are a real believer. If you are, I'd like to know how you reconcile your sig. "Whoever loves instruction loves knowledge, But he who hates correction is stupid." with a blind belief in a doctrine (the whole divine creator thing) that has been "corrected" many times as we've discovered more about the universe. Faith abhors correction - you must believe - despite any evidence to the contrary, in whatever it tells you surely.
If you were joking, and your sig is aimed at pointing this out to the faith guys - please accept my apologies for being a bit slow on the uptake. I don't have the answers around how the bees do this, but that doesn't mean the answer is automatically "There's a god, and he/she/it did it".
Cheers,
Scoot.
"He gives proof". As the whole problem with the belief in god or gods is the lack of any proof, I think we'd all be grateful if you could point us at this proof. It would certainly save a lot of debate!
Your sig. "Athiesm is a religion like not collecting stamps is a hobby." In the words of Doctor Leonard McCoy "I think that's my line". Seriously: Isn't this one for the non-believers? It's a great summary of the way I feel about the term "atheist", which means a non-believer in the whole god thing. I don't believe there is any sort of creator or god, however I fail to see why that should define me as a person. I don't, for example believe refrigerators can be used to transform lead into gold, but I don't go around saying I'm an a-refrigoalchemist either. In fact there's a whole bunch of nonsense I don't believe. I'm a normal guy. It's the people who believe in the whacky stuff with no evidence that need the labels (if only so I can see em coming :P)
Cheers,
Scoot.
A real believer and God has never been proven to not exist. Everyday we see evidence that He does.
The evolutionist view is fairly flawed. The biggest thing they cannot explain is the gaps in the fossil records between those found in the fossil record.
One of the arguments hinted at was that God somehow deceived us into believing that was millions of years old or whatever and that's pure hogwash, too. There is no deception on the part of God.
There is, however, great flaws in human methods, huge assumptions in our dating methods (such as the rate of decay being constant (it isn't and is effected by stellar phenomenon), the amount of any particular element being used to make the measurement being constant even though no one witnessed it's deposit, only that there is some of it there along with some of the element it decays into, etc.), and huge assumptions in any number of subjects that just don't add up.
Yet there is every evidence that a just and loving God does exist. Someone mentioned the Lovecraftian resemblance that Revelation takes on, with it's lake of fire (not blood, and definitely deeper than 6').
They guffaw at God, and any hand He may have had in our creation, by pointing to our current state yet fail to take into account the affect that the corruption of sin has had on us humans as well as the rest of creation.
You may find the idea of God to be foreign and simple-minded (as many on Slashdot apparently do), and that perhaps my sig is some sort of inside joke.
I assure it is not a joke, inside or otherwise. The Bible is the inerrant word of God (2 Timothy 3:16-17). Of that there is no doubt (at least to me). There is also no doubt in my mind to the limitless nature of hubris that humans have built up over the years.
I also generally don't respond because it's not a head-to-head battle, but a heart-to-heart. Either you will respond to the callings of the Spirit and repent, or you'll die and go to hell. I pray it's the former, but in the end God is the ultimate judge over all. (:
"There is a way that seems right to a man, but its end is the way of death." Proverbs 16:25 (NKJV)
Wait, I think I may be an "a-refrigoalchemist" as well!
All that is necessary for the triumph of good is that evil men do nothing.
And you believe that by random chance we all evolved from goop, for which there is no evidence.
Natural selection is non-random process. Only the input(varying genetic structures) is random. Thus, the result is non-random. Your statement reveals a severe lack of understanding. I suggest that, if you are truly interested in learning, you remedy this deficiency. Of course, if your goal is to shelter the particular brand of insipid delusion called "faith," then you are probably not inclined to actually study this area.
All that is necessary for the triumph of good is that evil men do nothing.
No, the aGNUstic does not know for sure if GNU really is or is not Unix.
Common mistake. ;)
I think it requires further analysis.
Simply because human brains do not seem to make use of quantum relativistic effects (like entanglement) due to their size, does not mean that a 15 neuron setup with strong evolutionary pressure to do more with less cannot not do so. Many distantly related species make use of "exotic" bochemistries- Photosyhnthesis makes use of entanglement to help direct photonic energy through the molecule, for instance. (look it up!)
Considering the highly specific evolutionary niche that bumblebees inhabit, (VS the hyper-generalized niche that humans inhabit) it is not that unreasonable to assume that they have evolved dedicated processes to solving this problem as efficiently as possible.
Further analysis needs to be conducted to determine just how efficiently they have been able to satisfy this requirement, and if it can be adapted for human use via computing technology.
Outright refusal without due dilligence is outright hubris.
I missed an article. Natural selection is a non-random process.
All that is necessary for the triumph of good is that evil men do nothing.
Bees and angiosperms are coeval. Just in case you wanted to know. ~100 million years old.
Well said. I strongly suspect that is what confuses the anti-evolution folks the most, not because of religious doctrine. Analyzing topics like this requires true observation without *any* type of invisible hand. Then rational thought can flourish.
But for most people it's almost impossible to remove intent because of their worldview through life-long, every day conditioning. They interact with human endeavors constantly like buildings, computers and airplanes. All constructed from preprocessed materials all laid out on a blueprint.
Then they "intuitively" conclude that life must be the same way; with ultimate intent. It truly is difficult to imagine complex systems assembled without a blueprint. Much less by what works best through adaptation and time, started by random molecular combinations. But of course we now know that's exactly what it was.
Not much different than the flat-earthers but there's hope. It just took a long time for the reality to sink in, thereby changing the mindset.
who/what is god?
He is a /. admin
Well, I might have a way, but it only works on a semi spherical planet in a vacuum.
I doubt that bees are any good at playing Quake so I wonder if a dedicated massively parallel TSPU wouldn't do wonders for running time of the algorithm on silicon. Add fuzzy logic as I doubt bees are interested in the theoretically best path, only one that lets the hive survive.
A theoretical computation book had an example of a 100-city traveling salesman problem in the last pages of the book. I put the numbers into my PC-XT running at 10 MHz programmed for a day and found the exact same solution that was published in the book in just under a minute of CPU time. The authors of the book had spent an hour I believe on a CRAY to prove that my/their solution was indeed the best possible.
Some, if not most NP-Hard problems can be solved in reasonable time provided your problem size is small (e.g. a few tens of cities/flowers) or if you accept that your solution might be a few percent worse than the theoretical optimal solution.
My program simply did "hill climbing". It just used one solution and tested if it could improve on that one solution. This is effectively what the bees are doing as well. They take one solution (fly to that far flower), and if they stumble on a better solution (drain that other flower en route) they proceed to that one....
What Slashdot needs is a write-in moderation option so you can moderate (-1, Wrong) or (+1, Fucking Awesome).
"You're right," Fisheye says. "I should have set it on 'whip' or 'chop.'"
For there to be natural selection, there has to be life. Life does not come from non-life.
Life is not some magical property bestowed upon unliving matter. It is, at root, a chemical reaction. The entire history of life is that of a chemical reaction which started almost 3 billion years ago, and continues today in much greater sophistication due to the operation of natural selection. Calling some collection of molecules "alive" is simply shorthand for recognizing a group of molecules undergoing this chemical process.
Natural selection will kick in automatically as soon as you have replication and a gradient of fitness. It has been proven time and again that replicating agents will spontaneously assemble in nature, and once such agents are in existence, what we call life is all but inevitable. Appeals to some anthropomorphic deity are quite unneeded to explain life, and in my view, childish in the extreme.
All that is necessary for the triumph of good is that evil men do nothing.
You've collected some blue-ish pale icky green chu-chu jelly.
I have literally tons of scientific evidence that says we evolved via natural selection, which is not a random process, and that life arose by non-mystical means.
What do you have besides a self-contradictory book of bronze-age myths?
Cool!
Tho even 10,000 years is said to be enough to evolve a mouse into an elephant sized creature given the right pressures, a hundred million years is such a long period it is difficult for the mind to conceive.
She was like chocolate when she drank... semi-sweet at first and then increasingly bitter.
Works out pretty good. I find it ironic that you hate factual correction.
The Kruger Dunning explains most post on
Maybe, we don't know if that was the pressure the caused the giraffes to evolve long necks, or a frindly byproduct of the long neck.
Humans can play the piano, that doesn't mean we evolved to play the piano.
The Kruger Dunning explains most post on
There's no "maybe" that that's what the statement means, and that it does not imply intent. :)
As to whether it's true, it's a fair observation that we don't really know. However since the long necks provide no clear advantages other than reach, and provide many downsides that required significant other evolutionary adaptations to support (implying adaptations to support a long neck were selected for, vs not having a long neck), I think it's probably safe to say that while it may not have started as a food-reaching adaptation, that quickly became the dominant selective pressure.
And if you replay "playing the piano" with the general "using tools", then I'd say we absolutely evolved in order to do just that. :)
The enemies of Democracy are
I don't hate factual correction.
"There is a way that seems right to a man, but its end is the way of death." Proverbs 16:25 (NKJV)
For life to have arisen by non-mystical means, it would have had to come about by complete and utter random chance.
"There is a way that seems right to a man, but its end is the way of death." Proverbs 16:25 (NKJV)
Or, chemistry. Perhaps you should try keeping abreast of science.
A chemical process that has not been proven to happen anywhere else not only in our own solar system, but in the entire visible universe. If the chances for life are that slim, seems like we either lucked out on the lottery or we were created.
You argument holds no water.
1. We have barely begun to explore this solar system, and will not be in a position to study the larger universe in any great detail for many years, if ever. It has only been recently possible to detect extrasolar planets, let alone determine their atmospheric composition. The fact that we have not found an example of extraterrestrial life is meaningless in that context. However, even within this extremely limited context, we have found organic molecules being formed(such as on Titan). This proves that the requisite organic compounds can exist elsewhere.
2. The fact that this chemistry has been proven to work here is sufficient to prove the case. There is nothing magical about the physics of the Earth as compared to the rest of the universe, regardless of what your adherence to a Bronze Age mythology might lead you to believe.
All that is necessary for the triumph of good is that evil men do nothing.
Sure, chemistry no one has been able to reproduce in the lab under any circumstances.
No, it's based on basic biochemical reactions which are demonstrated on a daily basis in any number of labs. Are you completely ignorant of that field, and simply repeating dogmatic statements with no correlation to reality?
All that is necessary for the triumph of good is that evil men do nothing.
As opposed to a mythical, mystic being for whom there is no evidence, right?
But, wait, the chemistry is being reproduced in the lab.
So, there is evidence for abiogenesis with experiments that are duplicating the chemistry. Where is the evidence of your invisible man in the sky? Where is your evidence that some god created the universe and/or Terra and/or life?
The flowers that are close by have a stronger perfume. Ergo, bees can outwit the computerized travelling salesman problem. Bees do have noses, don't they?
Leslie Satenstein Montreal Quebec Canada
Actually no, I'm not.
Indeed, it is evident.
I'm also fully aware that no scientist (or group of scientists) have been able to get non-living matter to start doing the chemical reactions needed to create organic life from the chemical soup.
You keep making the same mistake in pretending that there is some fundamental difference between chemistry depending on where it is taking place. Scientists can replicate proteins in the lab. They can create entirely new proteins. They can remove the DNA from a bacterial cell and insert an artificially generated DNA sequence, creating a new hybrid species.
The idea that we need to replicate the original conditions of abiogenesis is ludicrous, and makes me suspect that you have no grasp of the scale involved in such a useless project. Work from people like Craig Venter is improving our understanding of cellular chemistry constantly, and the only people who think that we are not within a few years of replicating an entire organism from scratch are those attempting to prop up ancient mythologies.
Oh, and I found your act of changing our relationship status to be "foe" quite amusing. It fits with the petulant and myopic nature of your posts. But, on the other hand, you are quite right. I am anti-theistic, and I am quite happy to do my little part helping to whittle away the various misconceptions and downright lies that keep your fellow theists in mental and moral slavery.
All that is necessary for the triumph of good is that evil men do nothing.
+1 BSG reference!
Sand's overrated... it's just tiny little rocks.
who/what is god?
If the grantparent post is modded Flamebait, then the parent post should be as well. Both posts are about the same topic, but express opposing views towards the subject.
I am not really here right now.