Want to read Slashdot from your mobile device? Point it at m.slashdot.org and keep reading!

 


Forgot your password?
Close
typodupeerror
×
Math Programming Science

Next Generation of Algorithms Inspired by Ants 106

Posted by samzenpus from the bugs-for-bugs dept.
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).'"
This discussion has been archived. No new comments can be posted.

Next Generation of Algorithms Inspired by Ants More

Next Generation of Algorithms Inspired by Ants

Comments Filter:

  • Oh really? (Score:2, Informative)

    by Anonymous Coward

    I thought it was called Dykstra's algorithm.

  • Really not new (Score:5, Informative)

    by Anonymous Coward on Sunday December 12, 2010 @02:56PM (#34529802)

    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)

      by Anonymous Coward

      Yeah...thank you. Although interesting, not really new. Pretty standard material in an undergraduate operations research course.

    • Re: (Score:2, Insightful)

      by Xest ( 935314 )

      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

    • Same here, I implemented an ACO (4 years ago) for finding the shortest path to send media over the internet efficiently. Nothing new... Just Google, it and you will find many people using that approach.

    • Re:Really not new (Score:5, Informative)

      by Anonymous Coward on Sunday December 12, 2010 @05:20PM (#34530474)

      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)

        by Anonymous Coward

        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.

    • And let's not forget about the Bellman-Ford [wikipedia.org] algorithm. 1958!

    • ACO was formalized in 1996

      There's even a MATLAB function for it. [mathworks.com]

  • Ant algorithms are old (Score:3, Informative)

    by Anonymous Coward on Sunday December 12, 2010 @02:57PM (#34529810)

    has been done since at least 1992. https://secure.wikimedia.org/wikipedia/en/wiki/Ant_colony_optimization

  • "Anthill Inside" (Score:1)

    by Anonymous Coward

    Hex [wikipedia.org]

    Terry Pratchett was right...

    • Re: (Score:1)

      by paai ( 162289 )

      I *like* Pratchett, but Salomon came first :-)

  • Old news? (Score:4, Insightful)

    by The Dancing Panda ( 1321121 ) on Sunday December 12, 2010 @03:05PM (#34529860)
    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?
    • Meh, this story 'ant' so new after all.

      How's that?

    • I hope the ant computer will also be usable by Ant Tillie.
      This may spur an aunty-computer movement!

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

  • I could be wrong, but shouldn't novely be a criterion for submission? ACO has been used since the early 1990s [wikipedia.org].

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

    by Mr Bubble ( 14652 ) on Sunday December 12, 2010 @03:13PM (#34529908)

    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)

    by Anonymous Coward

    It's a heuristic!

    • So a heuristic algorithm isn't an algorithm?

      • Re: (Score:2)

        by fatphil ( 181876 )
        It's not the heuristics that are the problem. If the heuristics may lead to the steps never terminating, then those steps do not define an algorithm. Algorithms must be finite.

        • Re: (Score:2)

          by doshell ( 757915 )
          Not only that, but arguably a heuristic cannot be considered an algorithm since it is not guaranteed to solve the problem --- in the same way that most people would not call shuffle sort a sorting algorithm.
          • A genetic algorithm is not an algorithm? That doesn't make sense. In fact, most processes where you are searching for a solution to a non-convex problem don't guarantee to 'solve' the problem. As for making in terminate, that's trivial: stop when the last 3 iterations did not improve by more than epsilon.

            Further, even solutions to convex problems don't provide the 'answer', but rather a value close to the solution, to some measure epsilon.
  • 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
    • Heuristics and many AI techniques are - in many cases based on nature. This is probably because we see how nature works very well in these cases.

      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.

      • Lets face it, nature has a far more powerful computer than we do.

        Obviously. After all, it's able to run all our computers at once in real time besides all that other stuff!

      • Lets face it, nature has a far more powerful computer than we do.

        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.

  • Does this mean IP packets will leave scent trails all over the internet?

  • Ants Anonymous (Score:2, Interesting)

    by VortexCortex ( 1117377 )

    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)

    by Anonymous Coward on Sunday December 12, 2010 @03:45PM (#34530096)

    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.

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

    by gmuslera ( 3436 ) on Sunday December 12, 2010 @04:54PM (#34530374) Homepage Journal
    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.

  • Isn't this the plot of Human Readable by Cory Doctorow? Human Readable [craphound.com]

  • Even simple mass-recruiting ants have much more complex and labile problem solving skills than we ever thought

    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.
  • It's called Hex. Check it up on Wikipedia [wikipedia.org].

  • 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 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 describe

  • Thanks, Ants.... Thants.
  • 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!!!

Slashdot Top Deals

Our OS who art in CPU, UNIX be thy name. Thy programs run, thy syscalls done, In kernel as it is in user!

Close