3 ms·

Decoding the Remarkable Algorithms of Ants

42 points by digital55 11y ago

yeureka 11y ago
Back in 2001 I was working on an new app that was designed to generate efficient routes for garbage collection trucks for a region of Portugal. The government of that region wanted to minimize fuel consumption and travel times. This is basically the classical Traveling Salesman Problem. We soon realized that using brute force to try all possible combinations would be impossible and someone handed me a research paper on using Ant Colony Systems to solve the Travelling Salesman problem. I was skeptical, but after implementing it and comparing the results with the brute force generated data ( that took a LOT more time to produce ) I was blown away. The results weren't perfect but good enough to be a vast improvement on the routes used before. Emergent behavior can be amazing.
- andy_ppp 11y ago
  Was it this paper? http://people.idsia.ch/~luca/acs-bio97.pdf http://people.idsia.ch/~luca/acs-bio97.pdf
jcr 11y ago
While looking for an accessible copy of the paywalled Nature paper, "The rewards of restraint in the collective regulation of foraging by harvester ant colonies," I spotted the following paper which might be useful to some: "Dispersion and Line Formation in Artificial Swarm Intelligence" http://arxiv.org/abs/1407.0014 http://arxiv.org/abs/1407.0014
- irickt 11y ago
  http://web.stanford.edu/~dmgordon/articles/doi/10.1038-nature12137/nature12137.pdf http://web.stanford.edu/~dmgordon/articles/doi/10.1038-natur...
cristianpascu 11y ago
This is yet another example of concept that is widely used but, AFAIK, has no clear definition and falls into the larger picture of consciousness: instinct. Actions that animals just do without any prior learning period. Examples are everywhere in nature. And this is puzzling to say the least. Standard evolutionary picture posits that behavior is emergent on underling neurological structures, basically all the way down to chemical reactions. This is a premise and in no way yet proven. But, as far as we know, physical laws do now allow behavior and functions, that is result-oriented actions (series of events and causal interactions). Many confuse complexity (as in "many things brought together in fancy patterns [1]), with complexity of systems that perform a function. The best definition that I could come up with for the latter has to do with a consistent transformation of one form of energy into another form with a clear result that is not just a mere physical consequence of the reactions initianing the process (such as pressure inside earth that cause a vulcano erruption). It should be clear to anyone that ants digging trough the dirt is categorically different than water flowing down the hill. [1] https://www.youtube.com/watch?v=YedgubRZva8 https://www.youtube.com/watch?v=YedgubRZva8

42 points by digital55 11y ago

Back in 2001 I was working on an new app that was designed to generate efficient routes for garbage collection trucks for a region of Portugal. The government of that region wanted to minimize fuel consumption and travel times. This is basically the classical Traveling Salesman Problem. We soon realized that using brute force to try all possible combinations would be impossible and someone handed me a research paper on using Ant Colony Systems to solve the Travelling Salesman problem. I was skeptical, but after implementing it and comparing the results with the brute force generated data ( that took a LOT more time to produce ) I was blown away. The results weren't perfect but good enough to be a vast improvement on the routes used before. Emergent behavior can be amazing.

andy_ppp 11y ago
Was it this paper? http://people.idsia.ch/~luca/acs-bio97.pdf http://people.idsia.ch/~luca/acs-bio97.pdf

jcr 11y ago

While looking for an accessible copy of the paywalled Nature paper, "The rewards of restraint in the collective regulation of foraging by harvester ant colonies," I spotted the following paper which might be useful to some: "Dispersion and Line Formation in Artificial Swarm Intelligence" http://arxiv.org/abs/1407.0014 http://arxiv.org/abs/1407.0014

irickt 11y ago
http://web.stanford.edu/~dmgordon/articles/doi/10.1038-nature12137/nature12137.pdf http://web.stanford.edu/~dmgordon/articles/doi/10.1038-natur...

cristianpascu 11y ago

This is yet another example of concept that is widely used but, AFAIK, has no clear definition and falls into the larger picture of consciousness: instinct. Actions that animals just do without any prior learning period. Examples are everywhere in nature. And this is puzzling to say the least. Standard evolutionary picture posits that behavior is emergent on underling neurological structures, basically all the way down to chemical reactions. This is a premise and in no way yet proven. But, as far as we know, physical laws do now allow behavior and functions, that is result-oriented actions (series of events and causal interactions). Many confuse complexity (as in "many things brought together in fancy patterns [1]), with complexity of systems that perform a function. The best definition that I could come up with for the latter has to do with a consistent transformation of one form of energy into another form with a clear result that is not just a mere physical consequence of the reactions initianing the process (such as pressure inside earth that cause a vulcano erruption). It should be clear to anyone that ants digging trough the dirt is categorically different than water flowing down the hill. [1] https://www.youtube.com/watch?v=YedgubRZva8 https://www.youtube.com/watch?v=YedgubRZva8