Beta
×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Bees Beat Machines At 'Traveling Salesman' Problem

CmdrTaco posted more than 3 years ago | from the they're-in-my-mouth dept.

Education 394

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?"

Sorry! There are no comments related to the filter you selected.

great... (5, Funny)

MagicMerlin (576324) | more than 3 years ago | (#34012906)

now you get a faster computer that makes honey!

Re:great... (5, Funny)

Anonymous Coward | more than 3 years ago | (#34013476)

No, you get a beeowulf cluster.

Bees have a guide (2, Interesting)

Anonymous Coward | more than 3 years ago | (#34012950)

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.

Wait, whut? (3, Funny)

MyLongNickName (822545) | more than 3 years ago | (#34012960)

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...

Re:Wait, whut? (5, Funny)

fractoid (1076465) | more than 3 years ago | (#34013462)

Oh, beehave.

Re:Wait, whut? (1)

The Archon V2.0 (782634) | more than 3 years ago | (#34013714)

Oh, beehave.

Thet's whare bies go efter vesiting tha fluwers?

Not for long... (1)

colmore (56499) | more than 3 years ago | (#34012964)

Hah! They may be on top now, but thanks to CCD [wikipedia.org] we won't have to be #2 for long. Goooooooooo humans!

Evidence (0, Flamebait)

DarkKnightRadick (268025) | more than 3 years ago | (#34012968)

Simply evidence that our algorithms need work. God has worked out these issues long before we even thought of them. (:

Re:Evidence (3, Insightful)

pitdingo (649676) | more than 3 years ago | (#34012994)

who/what is god?

Re:Evidence (-1, Flamebait)

InsaneProcessor (869563) | more than 3 years ago | (#34013090)

The creator of the universe. Anyone who doubts that lacks the wisdom He gave you. He gives proof but only the blind and ignorant insist that there is other answers. Please keep looking though. You will only find more of His proofs and that is good.

Re:Evidence (1)

revlayle (964221) | more than 3 years ago | (#34013208)

Kirk says he need a spaceship... also, I have no idea what this has to do with bees

Re:Evidence (5, Funny)

tverbeek (457094) | more than 3 years ago | (#34013212)

It's an abbreviation for Good Old Darwinism.

Re:Evidence (4, Funny)

Anonymous Coward | more than 3 years ago | (#34013620)

Thereby substituting one guy with a beard who must be worshipped for another.

Re:Evidence (1)

WrongSizeGlass (838941) | more than 3 years ago | (#34013320)

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!".

Re:Evidence (1, Funny)

Anonymous Coward | more than 3 years ago | (#34013308)

God has worked out these issues long before we even thought of them.

You know he doesn't like to be called that.

Solving a different problem (5, Informative)

goombah99 (560566) | more than 3 years ago | (#34013748)

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).

In Other ( Two ) Words: ( +1, Helpful ) (5, Interesting)

Anonymous Coward | more than 3 years ago | (#34012974)

Simulated annealing [wikipedia.org] .

Yours In Akademgorodok,
Kilgore Trout.

I'd mod you up if I could. (0)

Anonymous Coward | more than 3 years ago | (#34013276)

It was at least an interesting read.

How a tiny insect can figure it out on the fly (0)

Anonymous Coward | more than 3 years ago | (#34012984)

Anyone can look smart when they're cribbing notes from flies.

Heuristic (4, Insightful)

Sonny Yatsen (603655) | more than 3 years ago | (#34012988)

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.

Re:Heuristic (1)

SuperHighImpact (463360) | more than 3 years ago | (#34013138)

Good point. And I'd also like to know how many flowers we are talking about. Solving the traveling salesman problem for 5 flowers isn't really the same as solving it for 100 cities.

Re:Heuristic (2, Insightful)

gumbi west (610122) | more than 3 years ago | (#34013426)

I beg to differ. If it takes a supercomputer 4 days to solve it for 5 flowers... we have huge problems.

Re:Heuristic (1, Funny)

Dunbal (464142) | more than 3 years ago | (#34013516)

Your tax dollars at work...

Re:Heuristic (5, Funny)

ubersoldat2k7 (1557119) | more than 3 years ago | (#34013742)

It's called Ruby, and it's not a problem, it's a feature, a trendy one.

What makes you think (1)

turkeyfish (950384) | more than 3 years ago | (#34013698)

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.

Re:Heuristic (2, Insightful)

Anonymous Coward | more than 3 years ago | (#34013146)

your just playing word games... if i've developed a method of figuring out how to catch a ball without using newtonian physics, I've still solved the problem.

Re:Heuristic (1, Informative)

thePig (964303) | more than 3 years ago | (#34013342)

Indeed - especially considering the fact that one of the major class of solutions based on simulated annealing is actually a heuristics based solution. It really doesnt matter how you solve it at all - any way is welcome - as long as it reaches close to the optimal solution.

Re:Heuristic (3, Interesting)

Anonymous Coward | more than 3 years ago | (#34013376)

Nope. You've solved one small set of problems, which is related to the bigger problem. Does your method work for just balls? What about anvils? Churches? Very small rocks? How about when thrown through water, or over a hill? Can it be applied to every situation where Newtonian physics works?

The travelling salesman problem is a very specific definition of a problem. Solving it for one specific set (a given graph, size, or even geometry) does not solve the whole problem. Similarly, I know of no non-euclidean bees, so this research still doesn't solve the traveling salesman problem. As the grandparent said, the bees are likely employing some new rule we haven't thought of yet. The research might lead to new insight, though, and for that it's valuable.

Re:Heuristic (0)

Anonymous Coward | more than 3 years ago | (#34013390)

No, you're just playing word games...

Re:Heuristic (1)

Dunbal (464142) | more than 3 years ago | (#34013542)

I've still solved the problem.

      For yourself. However you are unable to break that problem down into tokens that can be taught to someone else or, say, programmed into a robot. Therefore although you might be good at catching a ball as an individual, you haven't solved the problem that those less adept than you face when put in the same situation.

Re:Heuristic (1)

rhsanborn (773855) | more than 3 years ago | (#34013552)

I think the point of the GP is that you haven't really "solved the problem", but rather came up with a close approximation, whereas those super computers are solving the problem absolutely.

Re:Heuristic (1)

smartr (1035324) | more than 3 years ago | (#34013594)

You don't solve a NP-Hard or NP-Complete mathematical problem by using a heuristic. Good heuristics for the TSP have existed for quite some time, and I'm sure they're faster than bees. https://secure.wikimedia.org/wikipedia/en/wiki/Travelling_salesman_problem#Heuristic_and_approximation_algorithms [wikimedia.org] I feel it's really deceptive that they claim this problem takes a supercomputer to solve the problem in days, when they certainly haven't proven the bees always get the best solution (I think at best, we could disprove this - not prove it). Anyhow, it is interesting that so little neural circuitry is needed to solve this kind of problem.

Re:Heuristic (2, Interesting)

Liquidrage (640463) | more than 3 years ago | (#34013196)

That was pretty much my thought. Do the bees ever get it wrong or at least not perfect? Seems obvious they world. I'd imagine the power lies in "good enough" thinking vs "perfect" thinking. Kinda an analog vs digital approach. If bees are able to map out where they are and which flower is closest to them at the time and head to that one next, they won't always get the perfect route, but it'll be close enough and sometimes be the best route based on a few variables in the layout.

Re:Heuristic (0, Troll)

corbettw (214229) | more than 3 years ago | (#34013284)

Do the bees ever get it wrong or at least not perfect? Seems obvious they world. I'd imagine the power lies in "good enough" thinking vs "perfect" thinking.

How apropos of the "good enough" thinking you seem to espouse!

Re:Heuristic (1)

bsDaemon (87307) | more than 3 years ago | (#34013546)

Unfortunately, when it comes to NP-complete, they world is not enough :-/

Different Spaces (4, Insightful)

eldavojohn (898314) | more than 3 years ago | (#34013220)

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.

Re:Different Spaces (1)

Sonny Yatsen (603655) | more than 3 years ago | (#34013362)

Good point, but what I meant by the baseball analogy isn't about the unrestrictedness or complexity of the problem so much as simply an example of a heuristic that we naturally have (although dependent on our personal levels of coordination). We're descended from tree-living ancestors who naturally developed the ability to judge an object's distances and movement (otherwise, our ancestors would've just fallen out of trees or failed to grab a branch as it jumps). Likewise, a mountain goat will be able to naturally able to make very complicated jumps on steep terrain without needing actual calculation of variables. And, of course, likewise the bees with their ability to go from flower to flower in efficient ways.

Re:Different Spaces (2, Insightful)

Americano (920576) | more than 3 years ago | (#34013520)

I'd be interested to read the full paper... looks like it won't be published until this week.

I have to wonder if it's simply local optimization that the bees are using - i.e., "Fly to a close flower not yet visited" - that starts looking like they're solving a much more complex problem? Are they visiting *every* flower on the "map"? Are they ever skipping some? Do they visit the flowers in exactly the same order, or is there variance from bee to bee (or between two trips from the same bee?)

It seems to me that a few simple rules ("visit closest flower from current flower that you haven't visited yet") might approximate the correct TS solution for small maps & limited nodes, but that it would become quite a bit harder to generalize that solution to larger sets of nodes & longer distances.

Re:Different Spaces (1)

bluefoxlucid (723572) | more than 3 years ago | (#34013718)

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

No, the problem with his analogy is that he's analogizing solving a problem ahead of time versus solving a problem in real time as it occurs. Adjusting slightly to catch a baseball as it gets closer eventually ends in the perfect position for catch; adjusting your path as you travel eventually ends in "oh shit, if I went to Dallas before Austin my total distance traveled would be shorter."

Not the TSP (5, Interesting)

sco08y (615665) | more than 3 years ago | (#34013382)

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.

Re:Heuristic (4, Interesting)

Dutch Gun (899105) | more than 3 years ago | (#34013480)

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.

You should read "On Intelligence" if you're at all interested in that subject. Jeff Hawkins (Palm inventor) proposes a fascinating theory of the inner workings of the brain.

Re:Heuristic (1)

Sonny Yatsen (603655) | more than 3 years ago | (#34013536)

Thanks, man, I'll check it out.

Re:Heuristic (3, Informative)

IICV (652597) | more than 3 years ago | (#34013566)

That's pretty much what I was going to post. The bees almost certainly aren't solving the Traveling Salesman problem, they're getting good enough approximations of a solution. Our computers don't chug for days trying to figure out the answer to TSPs, they chug for a couple of seconds and produce a close-to-optimal solution.

And the thing is, not all instances of the TSP are necessarily NP-Hard (for instance: if there was only one road between each city + 1 extra road between the first and last cities, the optimal solution is obvious), and the cases of it found in practical applications are generally far easier to handle than the cases found in more esoteric theoretical constructs (for instance: if you move east, you move closer to all the flowers in the east; this is not necessarily true in the general TSP). Most real instances of the TSP can be handled well enough with simple, quick greedy algorithms; they won't necessarily give you the best answer, but it'll be pretty close.

Re:Heuristic (1, Insightful)

Anonymous Coward | more than 3 years ago | (#34013614)

This seems likely to me. If the answer were simply the power of neurons, one might expect that -we- would be better at solving the traveling salesman problem than we are.

Actually, the problem is probably that human salesmen over-think the problem. If only there was some form of zen-like meditations that would allow humans to stop trying to employ math and algorithms, I'm sure our salesmen would be breezing effortlessly from town to town in the shortest possible route just like the wise bees.

It don't matter what you call it (1)

SmallFurryCreature (593017) | more than 3 years ago | (#34013634)

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.

Re:Heuristic (0)

Anonymous Coward | more than 3 years ago | (#34013700)

This is not even a new idea in terms of heuristics! Ant colony optimization [wikipedia.org] has been around for a while and is also based on the premise that ants solve optimization problems "on the fly".

Also, the phrase:

Such a problem is NP-Hard and keeps our best machines thinking for days searching for a solution

is totally INCORRECT. There are very good TSP heuristics that run very fast. It takes years of computing power to essentially prove that you get the OPTIMAL solution. But a very good one can be obtained really quickly.

A good reference if you want to know more is:
http://www.tsp.gatech.edu/methods/index.html

I highly doubt that the bees find the optimal solution to an 85,000 node instance of the TSP!

Re:Heuristic (1)

Nethemas the Great (909900) | more than 3 years ago | (#34013722)

What you're suggesting is actually a rather hot topic in AI at the moment. Traditionally computer algorithms have searched for the mathematically correct solution. It is believed that in most cases we don't require a mathematically correct solution but just one that is "close enough." Properly done we'd never notice the difference in output but we'd realize orders of magnitude improvement in time to solution. The algorithm would be able to put the mitt in the air at a reasonable spot and catch the ball either by a single "best guess' or a series of guesses refined each time by updated input.

Particle Swarm Optimization (0)

Anonymous Coward | more than 3 years ago | (#34012992)

I took a class with one of the inventors of particle swarm optimization (PSO) at Purdue. He claimed that PSO could could finish the traveling salesman problem faster than more traditional algorithms. The problem is that PSO is so random (as it attempts to emulate flocking behavior) that you really can't prove that it's faster. Similarly, you really couldn't formally prove that a bee is faster besides just doing empirical testing.

I doubt it (2, Insightful)

MozeeToby (1163751) | more than 3 years ago | (#34013000)

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).

Re:I doubt it (4, Insightful)

wed128 (722152) | more than 3 years ago | (#34013056)

I think you mean genetic algorithms. Genetic engineering is...something else.

Re:I doubt it (5, Funny)

Anonymous Coward | more than 3 years ago | (#34013246)

Hulk smash traveling salesman!

(I assuming we can engineer Hulks.)

Re:I doubt it (0)

Anonymous Coward | more than 3 years ago | (#34013564)

It may also be worth noting that many of the current TSP computer algorithms work like bees. They leave virtual pheromones and the solution is the most traveled paths. Thats a gross oversimplification, but I find it funny (ie, wrong) that the bees are better than computers doing the same thing that bees do.

Re:I doubt it (1)

revlayle (964221) | more than 3 years ago | (#34013578)

You're just jealous that bees are getting smarter than human and really and truly figure this stuff out when we are still stumped by this problem.

I, for one, welcome, our mathematically superior bee overlords.

(Help me! The bees have me prisoner, there are three workers, each with a stinger at my neck, telling me what to type. Luckily, due to a problem with their "odd" vision organs, they cannot see ANYTHING in parenthesis. Send help, and maybe some Raid or at least some Off.)

Traveling Salesman?? (0)

Anonymous Coward | more than 3 years ago | (#34013008)

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.

Re:Traveling Salesman?? (1)

boristdog (133725) | more than 3 years ago | (#34013102)

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.

Re:Traveling Salesman?? (2, Funny)

Dachannien (617929) | more than 3 years ago | (#34013638)

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?

Re:Traveling Salesman?? (1)

MaskedSlacker (911878) | more than 3 years ago | (#34013694)

So long as it's not the Crushinator, you ALWAYS sleep with the farmer's daughter.

The answer is obvious (4, Funny)

eln (21727) | more than 3 years ago | (#34013024)

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.

Re:The answer is obvious (0, Troll)

alta (1263) | more than 3 years ago | (#34013668)

Yeah, and unfortunately they would deserve that tenure more than many that already have it.

Shortcuts (4, Interesting)

Imagix (695350) | more than 3 years ago | (#34013026)

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.

Re:Shortcuts (5, Insightful)

MozeeToby (1163751) | more than 3 years ago | (#34013144)

Which makes the problem more difficult, not less. The way it is usually presented in CS the distance between the nodes is the minimum cost path, the bees would also have to 'calculate' that in addition to solving for the correct order. Think about it this way, imagine trying to solve the traveling salesman path between 100 cities, but you can take any route you want between cities. You could take all the back roads, the freeway, you could hop on a train or an airplane, you could kayak down the river between two cities. It doesn't make the problem any easier, in fact it adds a ton more variables to the mix, effectively increasing the number of routes that would need to be checked using a brute force solution.

Re:Shortcuts (0)

Anonymous Coward | more than 3 years ago | (#34013412)

Geeze. What would you imagine the shortest path between two flowers to be for a bee?

Re:Shortcuts (1)

brusk (135896) | more than 3 years ago | (#34013558)

It's not obvious, for example, if there are trees blocking a straight line path, if there are elevation differences, etc.

Re:Shortcuts (5, Funny)

MaskedSlacker (911878) | more than 3 years ago | (#34013726)

I dunno. If only we had a word for this....something like the line that a bee would travel...

Re:Shortcuts (4, Funny)

T Murphy (1054674) | more than 3 years ago | (#34013532)

Well duh that makes the problem harder. It would take years just to train the bees how to kayak, not to mention refitting airport body scanners- in 100 cities even! Can't we just simplify things and teach these bees how to send viagra spam so they don't have to travel to play salesman?

Re:Bee Spam! (1)

TaoPhoenix (980487) | more than 3 years ago | (#34013720)

I want it!

Hello Man.
I am Bee #32653. Do you want better flowers for your mate?
Click here!

Re:Shortcuts (0)

Anonymous Coward | more than 3 years ago | (#34013216)

The bee isn't constrained to fly along predefined paths between nodes, the travelling salesman is.

TSP only defines that fact that links exist between nodes. The general TSP is a fully connected graph. A bee flying from Node 1 to Node 5 can follow an arbitrarily complex path in between, but still arrives at Node 5 after some time (i.e. cost). The same is true of the TSP. So no, it's not different.

p=np (1, Insightful)

Anonymous Coward | more than 3 years ago | (#34013054)

Maybe P=NP and the solution is easy?

Re:p=np (0)

Anonymous Coward | more than 3 years ago | (#34013180)

P is indeed = NP,

when N = 1, or P = 0.

Well... (5, Funny)

Kufat (563166) | more than 3 years ago | (#34013068)

Does this mean that B >= NP?

Entomoengineering? (4, Interesting)

schmidt349 (690948) | more than 3 years ago | (#34013082)

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. [uwyo.edu] 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.

Re:Entomoengineering? (5, Funny)

$RANDOMLUSER (804576) | more than 3 years ago | (#34013306)

Many researchers are worried that the baculovirus isn't as benign as first thought. Some even claim it killed the Star Trek franchise.

Re:Entomoengineering? (3, Funny)

kvezach (1199717) | more than 3 years ago | (#34013524)

You must have it confused with the Bermagavirus.

Oh, really? (3, Interesting)

SoapBox17 (1020345) | more than 3 years ago | (#34013124)

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.

Re:Oh, really? (0)

Anonymous Coward | more than 3 years ago | (#34013280)

The real discovery here is that bees can write front-page Slashdot articles!
Something apparently relevant science is not capable of doing.

Re:Oh, really? (0)

Anonymous Coward | more than 3 years ago | (#34013534)

[quote]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.[/quote]

A brute force approach to the travelling salesman problem would look at all the different orderings for visiting the nodes. That's essentially n! (ignoring optimisations). 100! is 9.3e157. Your cell-phone is not going to be solving that, by brute force, in a couple of minutes.

Re:Oh, really? (5, Insightful)

gumbi west (610122) | more than 3 years ago | (#34013688)

100 flowers=100! possibilities. Using brute force on a 1 GHz processor and computing one solution per cycle (quite optimistic), it would take you 3 times 10 to the 141 years to complete. Even if your cellphone had a helaflop [slashdot.org] processor, it would still take longer than the age of the universe to compute this way.

Re:Oh, really? (1)

tibit (1762298) | more than 3 years ago | (#34013728)

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.

Iterating over a "few hundred" factorial in a couple minutes? I want your cellphone. Heck, better not, I think that quite a few of world's intelligence organizations are looking for you just now, maybe I'll let you see how it pans out first ;)

hierarchical models (2, Informative)

allawalla (1030240) | more than 3 years ago | (#34013164)

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...

Wild Guess (1)

Tsiangkun (746511) | more than 3 years ago | (#34013172)

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.

Re:Wild Guess (0)

Anonymous Coward | more than 3 years ago | (#34013402)

A trail of hormones in the wind? That would a hilarious path to watch anything follow.

Re:Wild Guess (1)

Sarten-X (1102295) | more than 3 years ago | (#34013486)

Like ants with wings!

Of course, the ant solution still isn't very fast, or reliable, and is usually far slower than algorithmic solutions. Nice try, though.

Re:Wild Guess (1)

bob0the0mighty (904854) | more than 3 years ago | (#34013572)

That's Ant Colony Optimazation [wikipedia.org] . Why would bees stoop to such levels?

Re:Wild Guess (3, Interesting)

smoothnorman (1670542) | more than 3 years ago | (#34013640)

...or even simpler, the scent of the flowers themselves. those antennae on the bees' heads aren't just for a sense of fashion. so to all you NP-mathematicians out there: suppose our traveling salesman had a means to follow a concentration gradient to the nearest sales point?

Re:Wild Guess (1)

gumbi west (610122) | more than 3 years ago | (#34013716)

Just a suggestion: you could try coding that up and see if you can solve the problem in seconds.

Euclidean TSP is easier (0)

Anonymous Coward | more than 3 years ago | (#34013182)

Presumably, bees take advantage of the triangle equality. In this case, they are solving an easier problem, one for which computer scientists already have very fast approximation schemes.

Re:Euclidean TSP is easier (1)

markov_chain (202465) | more than 3 years ago | (#34013550)

Also, there is a constrained version of the problem called Bitonic Tours [wikipedia.org] which is solvable in poly time, which might match the flower scenario well.

Re:Euclidean TSP is easier (1)

gumbi west (610122) | more than 3 years ago | (#34013744)

equals/not equals or equality/inequality. What is the difference, right?

What this really shows (1, Funny)

Anonymous Coward | more than 3 years ago | (#34013230)

What this really shows is how efficient society would be if we sterilized all workers.

Nearest Neighbor? (1)

wandazulu (265281) | more than 3 years ago | (#34013244)

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.

The numbers are a nice touch (1)

countertrolling (1585477) | more than 3 years ago | (#34013312)

In the number 8 bee... Yaritza Burgos!

Gentlemen, we have a race

Grass seed? You mean CORN? (4, Funny)

SmallFurryCreature (593017) | more than 3 years ago | (#34013396)

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.

Well... (0, Redundant)

rlanctot (310750) | more than 3 years ago | (#34013418)

I suppose we finally have the proof that Bee = NBee.... /ducks algorithm analysis text

The computer isnt going to die (2, Insightful)

192939495969798999 (58312) | more than 3 years ago | (#34013432)

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.

Natural selection at work (1)

gmuslera (3436) | more than 3 years ago | (#34013440)

The bees that didn't knew how to somewhat "solve" that are the dead ones.

Any colony optimisation (1)

comcn (194756) | more than 3 years ago | (#34013488)

Or just use Ant Colony Optimisation, which has been doing this for 18 years.

Kinda reminds me (1, Interesting)

Anonymous Coward | more than 3 years ago | (#34013662)

Kinda reminds me of the Geek shopping team [xkcd.com] . 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.

Not really news (1)

Thyamine (531612) | more than 3 years ago | (#34013674)

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.

165 million years of evolution, anyone? (1)

grikdog (697841) | more than 3 years ago | (#34013676)

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.
Load More Comments
Slashdot Login

Need an Account?

Forgot your password?