The Genius of Nature
November 19, 2012 3:11 AM Subscribe
Bees and a species of bird can solve the traveling salesman problem "It’s Saturday; you’ve got errands to run. Your spouse wants bread from the bakery, you need to pick up the dry cleaning, your kids need new shoes, and you’ve got a dentist appointment. None of this is any fun, so you might as well do it as quickly as possible by calculating the fastest and most efficient route that takes you to each stop... Menger and Whitney both discovered that the number of possible routes between stops increases exponentially with each additional destination. In a typical model, for instance, three stops yield six routes, while eight stops yield 40,320... By setting up five artificial flowers in a pentagon shape and tracking each bee’s path, researchers discovered that every bee optimized its route, visiting the highest-reward flowers in the shortest possible amount of time."
"The bees were especially keen when faced with the issue of short-term inconvenience for longer-term reward, going slightly out of their way to visit the higher-yield flowers even when it cost them a few seconds of travel time.
And it turns out bees aren’t the only animals that beat humans to solving the traveling salesman problem. Researchers at the University of New Hampshire have suggested that birds called Clark’s Nutcrackers perform a similar algorithm when collecting the 30,000 pine nuts they bury in 5,000 caches throughout the winter. Clark’s Nutcrackers, the researchers speculated, use landmarks to remember the location of each stash and calculate the fastest route between each bush or rock when collecting their nuts. Even more impressively, the birds could use dead reckoning, an ability to return directly to an earlier spot without the use of visual aids."
"The bees were especially keen when faced with the issue of short-term inconvenience for longer-term reward, going slightly out of their way to visit the higher-yield flowers even when it cost them a few seconds of travel time.
And it turns out bees aren’t the only animals that beat humans to solving the traveling salesman problem. Researchers at the University of New Hampshire have suggested that birds called Clark’s Nutcrackers perform a similar algorithm when collecting the 30,000 pine nuts they bury in 5,000 caches throughout the winter. Clark’s Nutcrackers, the researchers speculated, use landmarks to remember the location of each stash and calculate the fastest route between each bush or rock when collecting their nuts. Even more impressively, the birds could use dead reckoning, an ability to return directly to an earlier spot without the use of visual aids."
One of the commonly used heuristics for solving TSPs and related problems (Ant Colony Optimization) is biologically inspired and marks routes with 'pheromone trails', imitating the strategy used by ants.
posted by James Scott-Brown at 3:36 AM on November 19, 2012 [2 favorites]
posted by James Scott-Brown at 3:36 AM on November 19, 2012 [2 favorites]
I always thought there were "good enough" heuristics for most applications of the TSP? Aren't the bees just going to use a heuristic too instead of actually having found a way to solve the general TSP fast?
If so, is their heuristic better than the heuristics we know about? If yes, time to dissect some bee brains and reverse engineer it :)
posted by MSch at 3:39 AM on November 19, 2012 [4 favorites]
If so, is their heuristic better than the heuristics we know about? If yes, time to dissect some bee brains and reverse engineer it :)
posted by MSch at 3:39 AM on November 19, 2012 [4 favorites]
Menger and Whitney both discovered that the number of possible routes between stops increases exponentially with each additional destination. In a typical model, for instance, three stops yield six routes, while eight stops yield 40,320...
I suppose it might be true that those two mathematicians "discovered" that n things can be put into n! different orders, but it's not like that hasn't been known since antiquity. And that's not an "exponential" growth rate.
And people can also solve a 5-vertex TSP just fine, and can do quite well at coming close-to-optimum by heuristics when the number of vertices is large.
In the case of birds optimizing a tour of 5,000 vertices - well, there's an interesting logical point to consider there, right? We couldn't know that they found the optimal solution unless we also knew what the optimal solution was. And solving the TSP doesn't have much to do with being able to "calculate the fastest route between each bush or rock", since the distances are assumed to be part of the given information in the problem. The memory involved there is what's impressive, if you ask me.
Interesting behavior and research, sloppy article.
BTW, there's an online solver that's kind of fun to play with. If you submit a list of points in the plane, it'll return the optimum path and give you a PDF with a drawing of it. It's based on Concorde, which also has a Windows GUI (that I've never tried, but looks pretty cool).
People have used this to make some interesting artwork, too.
posted by Wolfdog at 3:39 AM on November 19, 2012 [14 favorites]
I suppose it might be true that those two mathematicians "discovered" that n things can be put into n! different orders, but it's not like that hasn't been known since antiquity. And that's not an "exponential" growth rate.
And people can also solve a 5-vertex TSP just fine, and can do quite well at coming close-to-optimum by heuristics when the number of vertices is large.
In the case of birds optimizing a tour of 5,000 vertices - well, there's an interesting logical point to consider there, right? We couldn't know that they found the optimal solution unless we also knew what the optimal solution was. And solving the TSP doesn't have much to do with being able to "calculate the fastest route between each bush or rock", since the distances are assumed to be part of the given information in the problem. The memory involved there is what's impressive, if you ask me.
Interesting behavior and research, sloppy article.
BTW, there's an online solver that's kind of fun to play with. If you submit a list of points in the plane, it'll return the optimum path and give you a PDF with a drawing of it. It's based on Concorde, which also has a Windows GUI (that I've never tried, but looks pretty cool).
People have used this to make some interesting artwork, too.
posted by Wolfdog at 3:39 AM on November 19, 2012 [14 favorites]
MSch, yes there are methods that yield a "good enough" result in "most" applications. I suspect that's what's going on here, though I've always thought it was very cool that bees have a heuristic at all that's not just reducible to the greedy algorithm.
posted by monkeymadness at 3:47 AM on November 19, 2012 [1 favorite]
posted by monkeymadness at 3:47 AM on November 19, 2012 [1 favorite]
The Science Daily link from the Slate article describes the computational situation in basic terms, but more accurately, and is worth a look.
posted by Wolfdog at 3:47 AM on November 19, 2012
posted by Wolfdog at 3:47 AM on November 19, 2012
I suppose it might be true that those two mathematicians "discovered" that n things can be put into n! different orders, but it's not like that hasn't been known since antiquity. And that's not an "exponential" growth rate.
Yeah, thanks for pointing that out. I thought there was something fishy about that part.
posted by bookman117 at 3:47 AM on November 19, 2012
Yeah, thanks for pointing that out. I thought there was something fishy about that part.
posted by bookman117 at 3:47 AM on November 19, 2012
Your spouse wants bread from the bakery, you need to pick up the dry cleaning, your kids need new shoes, and you’ve got a dentist appointment
So simply strap yourself to a bee and accomplish all these tasks in the minimum possible time!
Bzzzzzzzzzzzzzzzzzz *bread* zzzzzzzzzzzzzzzzzzzzzzzz *dry cleaning* zzzzzzzzzzzzzzzzz *shoes* zzzzzzzzzzzzzzzzzzzzzz *root canal* zzzzzzzzzzzzzzzz *immersion in a flower's sex parts* zzzzzzzzzzzzzz *pollen-induced anaphylactic shock* zzzzzzzzzzzzzzzzz *sneeze-death* zzzzzzzzzzzz-! *eaten by ravenous pigeon* ---------------- *excretion on a bald man's head* ------ *wipe-off on tissue and disposal in trash can* -------------- *burial in county land-fill* -------------------------------- *long centuries of nothing* -------------------------- *realisation that you forgot to pick up milk with the bread* ---------------- *heat death of the universe*
posted by the quidnunc kid at 3:49 AM on November 19, 2012 [12 favorites]
So simply strap yourself to a bee and accomplish all these tasks in the minimum possible time!
Bzzzzzzzzzzzzzzzzzz *bread* zzzzzzzzzzzzzzzzzzzzzzzz *dry cleaning* zzzzzzzzzzzzzzzzz *shoes* zzzzzzzzzzzzzzzzzzzzzz *root canal* zzzzzzzzzzzzzzzz *immersion in a flower's sex parts* zzzzzzzzzzzzzz *pollen-induced anaphylactic shock* zzzzzzzzzzzzzzzzz *sneeze-death* zzzzzzzzzzzz-! *eaten by ravenous pigeon* ---------------- *excretion on a bald man's head* ------ *wipe-off on tissue and disposal in trash can* -------------- *burial in county land-fill* -------------------------------- *long centuries of nothing* -------------------------- *realisation that you forgot to pick up milk with the bread* ---------------- *heat death of the universe*
posted by the quidnunc kid at 3:49 AM on November 19, 2012 [12 favorites]
It amuses me no end to imagine researchers from Harvard and Princeton cloistered away in their studies muttering "2, 6, 24, 120... there must be a pattern here, but what? what?!"
posted by Wolfdog at 3:50 AM on November 19, 2012 [10 favorites]
posted by Wolfdog at 3:50 AM on November 19, 2012 [10 favorites]
Represent your problem as flowers and let bees solve it for you. Imagine fields of bare grass laid out with grid marks, teams of horticultural assistants running out and planting flowers at precise coordinates, and then a squad of apiarists coming out on the field to release and track the bees. Beats punch cards.
posted by pracowity at 4:41 AM on November 19, 2012 [4 favorites]
posted by pracowity at 4:41 AM on November 19, 2012 [4 favorites]
...until the bees unionize and sting you to death, which, as far as I know, was never a likely problem with punch cards.
posted by Wolfdog at 4:43 AM on November 19, 2012 [1 favorite]
posted by Wolfdog at 4:43 AM on November 19, 2012 [1 favorite]
If bees really do perform optimally on TSP, I'd be willing to reconsider Roger Penrose's The Emperor's New Mind, because I don't see how a bee, or any other non-infinite being really, could solve a problem of that size WITHOUT a quantum computer.
posted by DU at 4:56 AM on November 19, 2012 [3 favorites]
posted by DU at 4:56 AM on November 19, 2012 [3 favorites]
Bees just never stop amazing me. You're pretty cool too, birds.
posted by orme at 4:56 AM on November 19, 2012
posted by orme at 4:56 AM on November 19, 2012
For those interested in the even wider array of areas where animals seem to be doing math, there's a fun book, The Math Instinct, by Stanford math professor and NPR's "Math Guy," Keith Devlin.
posted by twsf at 5:04 AM on November 19, 2012
posted by twsf at 5:04 AM on November 19, 2012
And it turns out bees aren’t the only animals that beat humans to solving the traveling salesman problem
Meh. Every human walking around with a cell-phone is doing this thousands of times a second with the help of the Viterbi Algorithm. Humans never stop amazing me.
posted by three blind mice at 5:04 AM on November 19, 2012 [1 favorite]
Meh. Every human walking around with a cell-phone is doing this thousands of times a second with the help of the Viterbi Algorithm. Humans never stop amazing me.
posted by three blind mice at 5:04 AM on November 19, 2012 [1 favorite]
Pfft - Bees! If bees are so bloody "smart," how come they are mostly sexless drones who slave all day in mindless toil to produce sweet treasure for a distant Queen who doesn't care whether they live or di-hang on, I'm British. FUCK.
posted by the quidnunc kid at 5:35 AM on November 19, 2012 [17 favorites]
posted by the quidnunc kid at 5:35 AM on November 19, 2012 [17 favorites]
...until the bees unionize and sting you to death, which, as far as I know, was never a likely problem with punch cards.Sure, just ask Hostess about that.
(Also, Hostess execs gave themselves some rather unwieldy bonuses, which probably didn't help. But I digress.)
posted by Blue_Villain at 5:38 AM on November 19, 2012
*sighs*
You know who's also good at Traveling Salesman Problems?
Traveling Salesmen.
Hard in the asymptote != actually hard.
posted by effugas at 5:51 AM on November 19, 2012 [1 favorite]
You know who's also good at Traveling Salesman Problems?
Traveling Salesmen.
Hard in the asymptote != actually hard.
posted by effugas at 5:51 AM on November 19, 2012 [1 favorite]
Sure, just ask Hostess about that.
Those were time cards, not punch cards. Also, 50% pay cuts are pretty much guaranteed to rile up the hive.
posted by Kirth Gerson at 6:16 AM on November 19, 2012
Those were time cards, not punch cards. Also, 50% pay cuts are pretty much guaranteed to rile up the hive.
posted by Kirth Gerson at 6:16 AM on November 19, 2012
OK, so you bees may be efficient at optimizing the sales routes of travelling salemen, but how good are you at actually selling? Prospective customers don't want the threat of being stung to death: they want the E-Z-Suck deluxe vacuum cleaner (TM) - even if they just don't know it yet. Remember, no other vacuum cleaner sucks harder than the E-Z-Suck! (TM)
posted by wolfdreams01 at 6:21 AM on November 19, 2012 [1 favorite]
posted by wolfdreams01 at 6:21 AM on November 19, 2012 [1 favorite]
I once tried use genetic algorithms to experiment with solving it (albeit mostly as a visualisation exercise.) You end up having issues with local minima, but that seems to be the common case.
posted by secretdark at 6:24 AM on November 19, 2012
posted by secretdark at 6:24 AM on November 19, 2012
We should observe that NP-completeness says only that we believe hard problems exist within the general problem, but says nothing about the density of hard vs. easy problems, good average case solutions, or approximation algorithms/schemas.
In fact, we do public key cryptography using factoring rather than NP-complete problems specifically because factoring lets us find hard instances confidently while no NP-complete problems provides the same confidence.
In a metric space, Christofides' algorithm provides us a polynomial-time 1.5-approximation algorithm for the traveling salesmen problem, not sure if a full PTAS exists though.
If we drop the metric space restriction, then traveling salesmen becomes APX-hard, but that generality won't interest the bees.
posted by jeffburdges at 6:51 AM on November 19, 2012 [2 favorites]
In fact, we do public key cryptography using factoring rather than NP-complete problems specifically because factoring lets us find hard instances confidently while no NP-complete problems provides the same confidence.
In a metric space, Christofides' algorithm provides us a polynomial-time 1.5-approximation algorithm for the traveling salesmen problem, not sure if a full PTAS exists though.
If we drop the metric space restriction, then traveling salesmen becomes APX-hard, but that generality won't interest the bees.
posted by jeffburdges at 6:51 AM on November 19, 2012 [2 favorites]
Menger and Whitney both discovered that the number of possible routes between stops increases exponentially with each additional destination
In fact n! grows superexponentially with n. But I'll let it slide because you almost always see "exponentially" used in the media to describe growth which is fast but not exponential.
Implicit big omegas for all!
posted by madcaptenor at 6:56 AM on November 19, 2012 [1 favorite]
In fact n! grows superexponentially with n. But I'll let it slide because you almost always see "exponentially" used in the media to describe growth which is fast but not exponential.
Implicit big omegas for all!
posted by madcaptenor at 6:56 AM on November 19, 2012 [1 favorite]
A: (Stares into space)
B: What are you thinking about?
A: The travelling salesman problem.
B: ...What is it? Illegitimate children?
posted by nebulawindphone at 7:05 AM on November 19, 2012
B: What are you thinking about?
A: The travelling salesman problem.
B: ...What is it? Illegitimate children?
posted by nebulawindphone at 7:05 AM on November 19, 2012
OK, so you bees may be efficient at optimizing the sales routes of travelling salemen, but how good are you at actually selling? Prospective customers don't want the threat of being stung to death: they want the E-Z-Suck deluxe vacuum cleaner (TM) - even if they just don't know it yet. Remember, no other vacuum cleaner sucks harder than the E-Z-Suck! (TM)
You're talking about what. You're talking about... Bitching about that pollen you shot, some son of a drone who don't wanna build combs, some wax pot you're trying to construct, so forth. Let's talk about something important. They all here?
All but one.
I'm going anyway. Let's talk about something important. Put. That nectar. Down. Nectar's for closers only. You think I'm fucking with you? I am not fucking with you. I'm here from down in the hive. I'm here from the queen. And I'm here on a mission of mercy. Your name's 30336-A? You call yourself a worker, you son of a bitch?
I don't gotta sit here and listen to this shit.
You certainly don't pal, 'cause the good news is: You're fired. The bad news is, you've got, all of you've got just one week to regain your jobs starting with tonight. Starting with tonight's gather. Oh? Have I got your attention now? Good. 'Cause we're adding a little something to this month's pollen-gathering contest. As you all know, first prize is a Cadillac El Dorado. What you'd do with that, I have no idea, because you're a bee, but I don't ask questions. Anyone wanna see second prize? Second prize is a huge pot of royal jelly. Third prize is: You're fired. Get the picture? You buzzing in a laughing sort of way now? You got leads. The queen paid good money, get their pollen and gather it. You can't close the leads you're given, you can't close shit. You ARE shit. Hit the bricks pal, and beat it 'cause you are going OUT.
The leads are weak.
The leads are weak? Fucking leads are weak. You're weak. I've been in this business three weeks...
What's your name?
[Angry buzzing]. That's my name. You know why, mister? You flew into the window of a Hyundai to get here. I flew into the window of an eighty-thousand dollar BMW. THAT'S my name. And your name is you're wanting. You can't play in the bee's game, you can't close them - go home and tell your wife your troubles. Well, I mean, don't, because marriage isn't really a thing for us. Because only one thing counts in this life: Get them to give you pollen. You hear me, you fucking pupae? A-B-G. A - Always, B - Be, G - Gathering. Always be gathering. ALWAYS BE GATHERING. A-I-D-A. Attention, Interest, Dancing, Action. Attention - Do I have your attention? Interest - Are you interested? I know you are, because it's fuck or walk. You gather pollen or you hit the bricks. Dancing - are you doing that weird sort of dance we do that communicates where the pollen is, for Christ? And Action. A-I-D-A. Get out there - you got the prospects coming in. You think they grew in to get into the rain? A flower don't open her petals lest she wants to get gathered on. They're sitting out there waiting to give you their pollen. Are you gonna take it? Are you bee enough to take it? What's the problem, pal?
posted by FAMOUS MONSTER at 7:12 AM on November 19, 2012 [23 favorites]
You're talking about what. You're talking about... Bitching about that pollen you shot, some son of a drone who don't wanna build combs, some wax pot you're trying to construct, so forth. Let's talk about something important. They all here?
All but one.
I'm going anyway. Let's talk about something important. Put. That nectar. Down. Nectar's for closers only. You think I'm fucking with you? I am not fucking with you. I'm here from down in the hive. I'm here from the queen. And I'm here on a mission of mercy. Your name's 30336-A? You call yourself a worker, you son of a bitch?
I don't gotta sit here and listen to this shit.
You certainly don't pal, 'cause the good news is: You're fired. The bad news is, you've got, all of you've got just one week to regain your jobs starting with tonight. Starting with tonight's gather. Oh? Have I got your attention now? Good. 'Cause we're adding a little something to this month's pollen-gathering contest. As you all know, first prize is a Cadillac El Dorado. What you'd do with that, I have no idea, because you're a bee, but I don't ask questions. Anyone wanna see second prize? Second prize is a huge pot of royal jelly. Third prize is: You're fired. Get the picture? You buzzing in a laughing sort of way now? You got leads. The queen paid good money, get their pollen and gather it. You can't close the leads you're given, you can't close shit. You ARE shit. Hit the bricks pal, and beat it 'cause you are going OUT.
The leads are weak.
The leads are weak? Fucking leads are weak. You're weak. I've been in this business three weeks...
What's your name?
[Angry buzzing]. That's my name. You know why, mister? You flew into the window of a Hyundai to get here. I flew into the window of an eighty-thousand dollar BMW. THAT'S my name. And your name is you're wanting. You can't play in the bee's game, you can't close them - go home and tell your wife your troubles. Well, I mean, don't, because marriage isn't really a thing for us. Because only one thing counts in this life: Get them to give you pollen. You hear me, you fucking pupae? A-B-G. A - Always, B - Be, G - Gathering. Always be gathering. ALWAYS BE GATHERING. A-I-D-A. Attention, Interest, Dancing, Action. Attention - Do I have your attention? Interest - Are you interested? I know you are, because it's fuck or walk. You gather pollen or you hit the bricks. Dancing - are you doing that weird sort of dance we do that communicates where the pollen is, for Christ? And Action. A-I-D-A. Get out there - you got the prospects coming in. You think they grew in to get into the rain? A flower don't open her petals lest she wants to get gathered on. They're sitting out there waiting to give you their pollen. Are you gonna take it? Are you bee enough to take it? What's the problem, pal?
posted by FAMOUS MONSTER at 7:12 AM on November 19, 2012 [23 favorites]
Gah; that common misuse of "grows exponentially" to mean "grows fast", or just "grows", really frustrates me! (Seriously: half the time I see "exponentially" used as a modifier, it seems to be completely devoid of meaning, like "literally", used in contexts where it clearly (literally!) doesn't even apply.)
Different rates of growth really make a difference. As another mathematician once pointed out, be glad that the amount of carbon dioxide in the atmosphere is only growing quadratically. If it were growing exponentially, we'd have been totally screwed well before today. (On the plus side, there would be no more climate change deniers?)
posted by eviemath at 7:42 AM on November 19, 2012
Different rates of growth really make a difference. As another mathematician once pointed out, be glad that the amount of carbon dioxide in the atmosphere is only growing quadratically. If it were growing exponentially, we'd have been totally screwed well before today. (On the plus side, there would be no more climate change deniers?)
posted by eviemath at 7:42 AM on November 19, 2012
Dear bees,
No credit will be given for your TSP solution. Next time, show your work.
posted by klarck at 7:43 AM on November 19, 2012 [5 favorites]
No credit will be given for your TSP solution. Next time, show your work.
posted by klarck at 7:43 AM on November 19, 2012 [5 favorites]
Represent your problem as flowers and let bees solve it for you. Imagine fields of bare grass laid out with grid marks, teams of horticultural assistants running out and planting flowers at precise coordinates, and then a squad of apiarists coming out on the field to release and track the bees. Beats punch cards.
A more reasonable approach, and one that is actually used, is to represent the problem in terms of a chemical reaction and solve it near-instanteously by pouring the right mixture in a beaker.
The problem is that there are relatively few specific instances for which determining the setup (chemicals or flowers) is faster than solving the problem with brute force. But when you score, you score....
posted by Tell Me No Lies at 9:22 AM on November 19, 2012
A more reasonable approach, and one that is actually used, is to represent the problem in terms of a chemical reaction and solve it near-instanteously by pouring the right mixture in a beaker.
The problem is that there are relatively few specific instances for which determining the setup (chemicals or flowers) is faster than solving the problem with brute force. But when you score, you score....
posted by Tell Me No Lies at 9:22 AM on November 19, 2012
The universe solves the n-body problem for n = infinity every moment of every day.
posted by Tell Me No Lies at 9:24 AM on November 19, 2012 [2 favorites]
posted by Tell Me No Lies at 9:24 AM on November 19, 2012 [2 favorites]
Wolfdog: "...until the bees unionize and sting you to death, which, as far as I know, was never a likely problem with punch cards."
Yeah, but you've never gotten a papercut from a bee.
posted by radwolf76 at 10:21 AM on November 19, 2012 [1 favorite]
Yeah, but you've never gotten a papercut from a bee.
posted by radwolf76 at 10:21 AM on November 19, 2012 [1 favorite]
I am disappointed that this post is not about training bees and wasps to attack door-to-door salesmen who bother you in the comfort of your own home.
posted by elizardbits at 12:59 PM on November 19, 2012 [2 favorites]
posted by elizardbits at 12:59 PM on November 19, 2012 [2 favorites]
« Older The Problem With Innovation | The New Sound of Music Newer »
This thread has been archived and is closed to new comments
posted by Kirth Gerson at 3:36 AM on November 19, 2012