Slashdot Mirror
Next Generation of Algorithms Inspired by Ants
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).'"
!news
I thought it was called Dykstra's algorithm.
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.
has been done since at least 1992. https://secure.wikimedia.org/wikipedia/en/wiki/Ant_colony_optimization
Hex
Terry Pratchett was right...
I have a textbook from 4 years ago with this algorithm in it. It was being taught in my Biologically Inspired Computing class.
"Ant" is one of the most pun-capable words in the English language. Why can't I (or anyone else, apparently) come up with a decent pun on this story?
I could be wrong, but shouldn't novely be a criterion for submission? ACO has been used since the early 1990s.
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.
"The world is a construct of forceful imagination. Those who don't know walk around in the reailties of those who do"
It's a heuristic!
That algorithm is so old soooo a better title would have been "Ants inspired by Next Generation of Algorithms".
In other words someone realized that nature is full of heuristic based problem solving and that perhaps a heuristic that is the result of millions of years of evolution could be pretty good. Not exactly a new idea but the more people who consider this the better.
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 also nature.
Does this mean IP packets will leave scent trails all over the internet?
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.
made at home, it's been doing good stuff for 1000's of years, almost unnoticed. yet another pattern? whatever really works?
Shit's old
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.
Thants!
FFS samzenpus - you can't even get the first word of the summary correct.
Barring a select few words for which that was actually true in a distant past, the "y" and "ij" are completely different in origin and use.
I'm behind 7 pheromones.
err..
meep
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.
http://www.youtube.com/watch?v=2fFgHUL8Oiw&feature=related
Windows already was based on algorithms based on ants... or maybe other kind of bugs
put a group of politicians in a maze and tell them to find the money as fast as possible, .................. bingo - best algorithm ever
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.
*Ants'
Isn't this the plot of Human Readable by Cory Doctorow? Human Readable
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.
Clearly a rip-off of the work of Ponder Stibbons at UU. The HEX architecture using ants is now well established. Good thing the researchers didn't decide to use chickens - recent history shows that would not end well.
Artificial Intelligence, still not as smart as an ant.
It's called Hex. Check it up on Wikipedia.
I'll see your Constitution and raise you a Queen.
Haven't RTFA'd, but I've always been interested in the MUTE project ), which is a truly anonymous p2p filesharing system which is based on how ants find food: http://mute-net.sourceforge.net/howAnts.shtml
(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)
Who's there?
Ant.
Ant who?
Ant you upset no one is working on a dung beetle algorithm...
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!
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.
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 described years ago, but at the time it got no consideration, be it for inefficiency or lack of wit.
Today, it's of the essence.
Sincerely, I fear this is terribly telling about how science is considered today. There is no expectation that someone comes with an idea anymore. We expect, and accept, that some throwing ants at random is a fair way to solve issues. We don't expect anything better.
To me it's really a revolution happening.
Don't misunderstand me: there are real reasons for this approach to work today and not yesterday (computer power, better simulations, whatnot). I'm not saying this is Good and that Bad. :-/
But still, it means there is no special expectation (nor respect?) for Science anymore.
Hope the same won't happen in medicine or philosophy
Herve S.
The ants are in it with big government.
Thanks, Ants.... Thants.
splunge (n) -- A good idea.. but it could be lousy... and I'm not being indecisive!
In his latest SS collection, CD has written a story called Human Readable that discusses the implications of Ant Colony algorithm if it is applied to all walks of life..Free download from craphound.com
very old news!!!