Next Generation of Algorithms Inspired by Ants 106
letsurock writes "Ants' capability to find the shortest route through a maze in an hour, and to find the second shortest route when the first path was obstructed, has inspired researchers creating algorithms for the future. From the article: 'Finding the most efficient path through a busy network is a common challenge faced by delivery drivers, telephone routers and engineers. To solve these optimization problems using software, computer scientists have often sought inspiration from ant colonies in nature — creating algorithms that simulate the behavior of ants who find the most efficient routes from their nests to food sources by following each other's volatile pheromone trails. The most widely used of these ant-inspired algorithms is known as Ant Colony Optimization (ACO).'"
Oh really? (Score:2, Informative)
I thought it was called Dykstra's algorithm.
Re: (Score:1, Informative)
I thought it was called Dijkstra's algorithm.
Fixed that for you
Re:Oh really? (Score:4, Informative)
"y" is an old, alternative spelling for the Dutch digraph "ij".
http://en.wikipedia.org/wiki/IJ_(digraph) [wikipedia.org]
Re: (Score:3)
"We"? Do you have a mouse in your pocket?:
Re: (Score:1)
Funny, yes, but your humor could still unintentionally harm future potential users of the exclusive first-person plural subject pronoun, who might prefer not to use the more general and impersonal "people" or too-subjunctive "one" in certain contexts. Of course, the parent actually seemed to be using the inclusive, as a means to clear up an orthographic disparity from the norm - in which case, your rejoinder has no precedent in grammar humor.
pre-emptive disclaimer here: yes, I am aware that there are [x] g
Re: (Score:1)
Re: (Score:2)
I'm sure that the TSA agent will be enthralled by your knowledge of ... whatever it is ... when the name on the boarding card doesn't match the one on your passport.
Re: (Score:2)
Re: (Score:3, Funny)
Anthill inside
Really not new (Score:5, Informative)
Ok guys. I did my Ph D on this subject some years ago. ACO was formalized in 1996 (by Marco Dorigo), and the modeling of ants behavior dates back to 1989 (J.-L. Deneubourg). So really nothing new here.
Re: (Score:1)
Yeah...thank you. Although interesting, not really new. Pretty standard material in an undergraduate operations research course.
Re: (Score:2, Insightful)
Yeah, sorry, but what the fuck? Slashdot had a story about the "discovery" of ACO a few months back, there was a similar one a year or two prior also, now it's been "discovered" again? How can something from the 90s be "Next Generation". How many times do we have to have stories on ACO? It's been around so so long, it's taught in undergraduate AI classes across the world.
Perhaps Slashdot needs to create it's own ant inspired algorithm to handle submissions because at least ants probably wouldn't post a stor
Re: (Score:3)
How can somethimg from the 90s be "Next Generation?"
Um... Star Tek?
Re: (Score:2)
I guess that's what I get for posting from my Kindle.
Re: (Score:1)
Re:Really not new (Score:5, Informative)
TFA says "Provided by University of Sydney."
This wasn't a computer science paper, this is a biology paper bublished a few days ago based on an experiment with actual ants. From the paper's abstract:
Contrary to previous studies, our study shows that mass-recruiting ant species such as the Argentine ant can forage effectively in a dynamic environment. Our results also suggest that novel optimisation algorithms can benefit from stronger biological mimicry.
http://jeb.biologists.org/cgi/content/abstract/214/1/50 [biologists.org]
Re: (Score:1)
Actually, their paper suggests that biologists should either (a) stick to biology and stay away from mathematical optimization, or (b) at least read about the No Free Lunch theorem in optimization.
Re: (Score:2)
And let's not forget about the Bellman-Ford [wikipedia.org] algorithm. 1958!
Re: (Score:2)
ACO was formalized in 1996
There's even a MATLAB function for it. [mathworks.com]
Ant algorithms are old (Score:3, Informative)
has been done since at least 1992. https://secure.wikimedia.org/wikipedia/en/wiki/Ant_colony_optimization
"Anthill Inside" (Score:1)
Hex [wikipedia.org]
Terry Pratchett was right...
Re: (Score:1)
I *like* Pratchett, but Salomon came first :-)
Re: (Score:1)
"Terry Pratchetts Diskworld, in association with X" is a possibility that I did not yet even consider. Some things are too horrific even to think about.
But the day that people so completely lost their cultural roots that Salomon is forgotten, will be a black day indeed.
Re: (Score:2)
Re: (Score:1)
To begin with, a sucessor/collaborator for Pratchett would have to be sixtyish, like Pratchett himself (and yours truly). That is because he draws so heavily from his experiences as an very intelligent observer of the second half of the 20th century, including the fifties and sixties. I *know* that my 25 and 28 years old daughters are Pratchett adepts, and I always wonder in how far they get the allusions, and if not, why they can enjoy the books so much.
You mentioned Good Omens, which certainly is one of
Old news? (Score:4, Insightful)
Re:Old news? (Score:5, Informative)
Some may laugh at this technology but sniffing the pheromone trails of frat boys may very well be the shortest path to beer.
Re: (Score:1)
Re: (Score:2)
Borderline?
Not after a few beers. There is a definite "line" that gets crossed more often than most realise... ;)
Re: (Score:2)
Dammit, I know there has to be a pun here! (Score:2)
Re: (Score:2)
How's that?
Re: (Score:1)
I hope the ant computer will also be usable by Ant Tillie.
This may spur an aunty-computer movement!
Re: (Score:1)
Damn, I should better proofread when trying puns! I of course meant an anty-computer movement.
Re: (Score:2)
Well when I read the first sentence of the summary I assumed it was about the well known software tool.
But then I ant nevver been good at comprehension, even though I'm an opteramist. I guess we'll have to larva it at that.
novely? (Score:2)
Re: (Score:2)
But thinking up new stuff is hard. You can just re-publish old work every few years to keep your funding coming, then you have more free time to harass the admin office poppets.
Physicists figured this out in 1930 or so, but computer scientists foolishly kept inventing new things until fairly recently - glad to see we've finally smartened up.
Binary Pheremones (Score:5, Interesting)
As someone in the comments of TFA pointed out, "The interesting thing here is the 'secondary explore state' (seeming second pheromone state) found by the mathematicians.". So, they basically walk around trailing either a 1 a zero or both. I wonder if it is a single bit at a time like a code that goes along in a track or if it is more diffuse than that.
Its not an algorithm! (Score:1)
It's a heuristic!
Re: (Score:1)
So a heuristic algorithm isn't an algorithm?
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
Further, even solutions to convex problems don't provide the 'answer', but rather a value close to the solution, to some measure epsilon.
Re: (Score:1)
Next Generation of Ants inspired by Algorithms.
Re: (Score:1)
Heuristics from nature ... (Score:2)
This is also a variation of the number one lesson of graduate school: go to the "library" and start reading, someone smarter than you has probably thought about your problem already. The "library" is not just academic journals and such but it is
Re: (Score:2)
Artificial Neural Networks is 'based' upon how the brain works.
Genetic Algorithms are inspired by evolution
Ant colony optimisations are inspired by ants...
Lets face it, nature has a far more powerful computer than we do.
Re: (Score:1)
Obviously. After all, it's able to run all our computers at once in real time besides all that other stuff!
Re: (Score:1)
Sure, it's got billions of them loosely networked, and they've been running for billions of years. You'd expect some impressive results to be accumulated.
Scent trails? (Score:2)
Good luck (Score:2)
I'm behind 7 pheromones.
err..
Ants Anonymous (Score:2, Interesting)
In a more complete Ant networking model: If the source of information "food" the ants crave is threatened the ant "packets" themselves retaliate with the only tool they have, themselves.
Now, if only these network ants could cover their natural foes in stinging, embarrassing, information "bite" marks to warn other ants of their enemies... Oh, right, Wikileaks.
Carry on, our welcome Ant Overlords.
I was gonna make another 'old news' comment... (Score:5, Informative)
I have personally done research using ACO, so I was all ready to point out with the rest of the /. mob that this is nothing new... then I actually RTFA.
Not entirely novel, but TFA is not about ACO. It's about using REAL LIVE ANTS to solve Hanoi.
Bad summaries strike again.
Re: (Score:2)
Re: (Score:2)
Ant that a shame. Leave it to the ped-ants to point it out.
OT - fun iOS app for ant behavior (Score:2)
disclosure: i know the author of the app.
"antograph" is a nifty interactive app written by scott snibbe back in 1998 and recently ported to the iDevices.
it's a nice demo of some of the concepts of ant simulation.
Previous art (Score:5, Funny)
Re: (Score:1)
They are not bugs, they are undocumented features!
that's nothing (Score:1)
not efficient (Score:2)
If your solution includes generating an exponentially large graph from a small problem, then you don't have an efficient algorithm for solving the problem, no matter whether you use real ants or simulated ants.
Human Readable? (Score:1)
Bad example (Score:2)
Both solutions to the example maze could be solved by simply favouring left turns whenever possible.
I'd like to see an example that challenges the ants in different ways.
Something to Ponder (Score:1)
Already Done (Score:2)
Prior Ant Art (Score:2)
Haven't RTFA'd, but I've always been interested in the MUTE project [sourceforge.net] ), which is a truly anonymous p2p filesharing system which is based on how ants find food: http://mute-net.sourceforge.net/howAnts.shtml [sourceforge.net]
(I've never tried it and it hasn't been updated for a while but it's always sounded cool to me as an anonymous method of filesharing, even though there's obvious issues)
Terry Pratchett foresaw this (Score:1)
Terry Pratchett forsaw this with his hex computer that ran on ants.
The logo was Anthill Inside!
They used bees for long term storage and it was secure. If anyone tried to get into the hive, they would be stung to death!
Ooooold news is ooooold. (Score:2)
I read about this in Scientific American in the middle of the 90ies. Way to go.
But I hear someone invented trapezoid approximation for calculating the area below curves, recently. If they patented it, we can VC the hell out of that one.
'Not new' isn't the issue. Renouncing thinking is! (Score:2)
I see many are underlying these strategies already were identified years ago.
This is true, but indeed, what is important in the present information is that like many others at this time, it reflects an evolution in thinking.
Basically, we won't sit analyzing a problem before proposing a solution.
Maybe we consider we don't have time, maybe we are confident in superfast computing: we throw in some random algorithm (ants everywhere, and then the fastest are detected), and go.
Such an approach indeed was describe
Thants (Score:2)
Cory doctorow wrote a short story about this... (Score:1)
AI using ants for model (Score:1)
very old news!!!