Can we please stop with these articles, that with due consideration I will refer to as "fucking pieces of shit"? My HP48-G could probably brute-force the instance size of the problems that they threw at these bees in less time than the bees took, and there is also no particular reason to believe that the bees actually solve the problem, which is to say, 100% of the time find the perfectly optimal solution. Anything less is not a solution.
Bees may not be dumb, but they work at the speed of living things. In one flap of the wings of one of the bees I bet a naive brute-force algorithm could have solved the entire instance these researchers threw at the bees with time to spare. TSP is exponential to truly solve, but I guarantee the researchers didn't throw a very big instance at the bees, because if they had I guarantee at some point the bees would have chosen a non-optimal path.
This isn't even abstractly cool; it's anti-knowledge of a kind with quantum mysticism, if not quite as toxic. Reading these types of reports and taking them at face value leaves you with a less accurate understanding of the world.
Bees have evolved for 100M years. During this time an enormous amount of bees have lived and finding a shorter path between flowers is obviously a very strong evolutionary pressure.
Generally the bee species is a genetic algorithms supercomputer that have worked for a very long time to find good solutions to the traveling salesman problem. I'd guess your suggestion, that we should not even try to find the results of that 100M years computation, is based on some personal feelings ;-)
Bees no doubt have a very good biological implementation of some heuristic algorithm to the traveling salesman problem. It is extremely unlikely (as in aliens in area 51 unlikely -- wishful thinking unlikely) that they have a biological implementation of an exact algorithm. The Daily Galaxy article makes it seem as if the bees are solving the problem using an exact algorithm, and, moreover, that they are faster at doing so than a modern supercomputer, which is all complete wishful-thinking nonsense.
First of all, the travelling salesman problem is not actually about travelling salesmen; a solution has to work on an arbitrary graph, not just one that is constrained to the actual geometry of space.
Secondly, the bees' solution to the problem is heuristic; there is no guarantee they will always find the optimal solution, though they'll almost always be very close. Computers can apply heuristics too (with the same caveat), and when they do so it's much faster than verifying an algorithmic solution.
> First of all, the travelling salesman problem is not actually about travelling salesmen; a solution has to work on an arbitrary graph, not just one that is constrained to the actual geometry of space.
Not quite true, Euclidean TSP is also NP complete, so in a sense, working with real distances doesn't make the problem any easier to solve. Euclidean TSP is, however, easier to approximate, and that's really the point here: a good approximation is all that matters in practice, bees won't starve just because their solution is 0.5% worse than the optimal route.
Yeah, the bumble-bee thing is unfortunate. But there is something to this: we can trade away a verifiably optimal solution for something more useful, like a timely one. (Coincidentally, I submitted an article on that general theme this very morning: http://news.ycombinator.com/item?id=2371977) If that concept entered the public mind it would be a great thing.
Unfortunately the article never touched on that, and all we get is "bees > supercomputers!!!".
I like how the bees are said to figure out the answer faster than a supercomputer, when the problem involves "several" flowers. Unless "several" is 15+ flowers, a supercomputer is going to have an optimal solution within milliseconds, before the first bee has even reached the first flower. Now, if the bees had 1000 flowers to visit, I would be more interested.
Wow, how many different paths is that? Somewhere around 256 at a guess? So a computer could work out the optimal solution in microseconds purely by testing all possible combinations. Though I'm guessing the bees don't just sit there at the start working through all possible routes they're going to take that day, it's surely something that they work out as they go along. Maybe that's where they gain some efficiency advantage.
Though four flowers is hardly likely to be a real world scenario for bees. Surely bees would encounter tens of thousands or more flowers in a field, so it is there performance here that ultimately counts. Though perhaps four flowers is better for determining how they make their actual decisions?
The bees are probably faster if you include the time it takes to code a program for the supercomputer to run to actually solve the problem.
I'm saying 'probably faster' because that would depend on the algorithm and the speed of the coder or coders. I still bet a couple of talented well coordinated coders with a simplistic heuristic algorithm would still beat the bees in a realistic simulation (IE having to fly a distance to find said flowers similar to real nesting conditions, not through a hole or something 3' from the artificial flowers).
The article seems to mention a heuristic method the bumblebees use to improve their path, which consists of changing subpaths. A heuristic doesn't necessarily give the optimal solution, while there are methods that do give the optimum. An example is Concorde at GAtech, that solved problems with 15k nodes: http://www.tsp.gatech.edu/concorde.html
"Bees need lots of energy to fly, so they seek the most efficient route among networks of hundreds of flowers using angles of sunlight, which helps them find their way home, researchers say."
How much energy do bees really need to fly? Is there any data available on the subject?
I don't understand either. I see this more frequently lately, that (informative, on topic) posts are randomly killed. It's not like the poster was a negative-karma user, either. Who decides which posts get killed?
Often it's because a user accidentally double-posts, the second post gets auto-killed, the user can't see their own dead posts, and they delete the live one rather than the dead one (because they can't tell which is which).
bbatsell hit this correctly. I saw two replies appear and immediately killed one. It surprises me to see replies on the dead one, there were no replies when I did the kill.
After given the "travelling salesman" optimization assignment, on the handup, I handed up my KD-tree implementation and at the end of the write up I suggested the lecturer check out a similar article on bees to this (may have been the same one, was a while ago)
There is a long history of people simply assuming that things could solve an NP-hard problem when in fact you only get an approximation: http://www.scottaaronson.com/papers/npcomplete.pdf
Bees may not be dumb, but they work at the speed of living things. In one flap of the wings of one of the bees I bet a naive brute-force algorithm could have solved the entire instance these researchers threw at the bees with time to spare. TSP is exponential to truly solve, but I guarantee the researchers didn't throw a very big instance at the bees, because if they had I guarantee at some point the bees would have chosen a non-optimal path.
This isn't even abstractly cool; it's anti-knowledge of a kind with quantum mysticism, if not quite as toxic. Reading these types of reports and taking them at face value leaves you with a less accurate understanding of the world.