4 ms·

Ant Colony Optimization Algorithms

56 points by Kapura 12y ago

leoplct 12y ago
Yep, so?
- gamegoblin 12y ago
  While I think you're getting downvoted due to the brevity (and perhaps attitude) of your comment, in large part I agree with the sentiment. I've been HN-ing for a year and change, now. The posts that just link to a wikipedia article about a topic that > 90% of the HN crowd is probably familiar with do get a little tiresome. Check out ( https://hn.algolia.com/?q=wikipedia#!/story/sort_by_date/0/wikipedia.org https://hn.algolia.com/?q=wikipedia#!/story/sort_by_date/0/w... ) to see recent wikipedia submissions. Just recently someone linked to the wikipedia article for "Code Golf". At didn't get any upvotes, which is great, but I just don't understand the mindset behind submitting it. I guess easy karma? I don't know. I'd much rather see content like "Here is my solution to problem X using ant colony optimization". This is the first time I've made a comment like this, because usually I just flag and move on. I guess I just needed to vent a little.
  - prezjordan 12y ago
    Because articles like this (and maybe even code golf) might spark an interesting discussion.
  - danbruc 12y ago
    The posts that just link to a wikipedia article about a topic that > 90% of the HN crowd is probably familiar with do get a little tiresome. I bet this is not the case in this case. I can understand the attitude against plain Wikipedia links but at least I learned a new idea because of this link.
  - jes5199 12y ago
    I think a thing that has happened is that the community is actually full of people who have not learned all the fun computer science stuff that people like you and me take for granted, and that's why they're voting it up. On the one hand, it's frustrating because, damn it, if you don't already know how to play with these concepts then why on earth are you calling yourself a "hacker", but then on the other hand http://xkcd.com/1053/ http://xkcd.com/1053/
    - gamegoblin 12y ago
      I definitely agree with you. It's guess it's just difficult with the HN community growing every day, both in population and the diversity of backgrounds. I think I'll write a little plugin that will hide all wikipedia links and I'll be happy. Maybe something like "hide all wikipedia links unless #comments > N" would work nicely.
  - nitrogen 12y ago
    I'd much rather have these articles than yet another 300+ comment thread about the latest tempest in a teacup linkbait drama.
MrGando 12y ago
That's why you may want to get a CS degree... if you are interested in things like this... well, this is just the tip of the iceberg.
juliangamble 12y ago
The Clojure language was introduced with an ant Colony demo by Rich Hickey. He was using it to demonstrate concurrency primitives in Clojure. You can see screenshots and read code here: http://juliangamble.com/blog/2011/12/28/clojure-gui-demo-of-ants/ http://juliangamble.com/blog/2011/12/28/clojure-gui-demo-of-...
diziet 12y ago
For those interested in algorithms and optimizations of paths, check out www.pathery.com/home for an NP complete longest path most vital node puzzle.
14113 12y ago
The inventor of the algorithm actually has a really good website with a good overview and history: http://www.aco-metaheuristic.org/ http://www.aco-metaheuristic.org/
yeureka 12y ago
Back in 2001 I was working on an app used in planning optimal routes for city garbage trucks. We quickly found out that this was equivalent to the Traveling Salesman Problem and the initial brute force solution was not fast enough to get results in useful time. A colleague stumbled upon a paper on Ant Colony Systems and gave it to me to try to implement it and to check if the results were as good as the paper promised. It was amazing how the solutions were so close to optimal ( we checked the results from the ACS algorithm against the brute-force solutions that took hours to compute ) and how fast the algorithm stabilized on the solutions. It was also the first time I had used an algorithm that does not really stop, it just converges to a solution and another heuristic decides when to accept a final result. I learned a lot from it.
- patmcguire 12y ago
  Garbage trucks have to visit every edge (street segment) once, not every vertex (intersection) once, correct? Can you use Eulerian Paths? http://en.m.wikipedia.org/wiki/Eulerian_path http://en.m.wikipedia.org/wiki/Eulerian_path Or is the process to make a non-Eulerian graph Eulerian NP?
  - mvanotti 12y ago
    Once you have a mixed graph (One-way streets and two-way streets), the problem is known as the Mixed Chinese Postman Problem and is NP.

56 points by Kapura 12y ago

leoplct 12y ago

Yep, so?

gamegoblin 12y ago
While I think you're getting downvoted due to the brevity (and perhaps attitude) of your comment, in large part I agree with the sentiment. I've been HN-ing for a year and change, now. The posts that just link to a wikipedia article about a topic that > 90% of the HN crowd is probably familiar with do get a little tiresome. Check out ( https://hn.algolia.com/?q=wikipedia#!/story/sort_by_date/0/wikipedia.org https://hn.algolia.com/?q=wikipedia#!/story/sort_by_date/0/w... ) to see recent wikipedia submissions. Just recently someone linked to the wikipedia article for "Code Golf". At didn't get any upvotes, which is great, but I just don't understand the mindset behind submitting it. I guess easy karma? I don't know. I'd much rather see content like "Here is my solution to problem X using ant colony optimization". This is the first time I've made a comment like this, because usually I just flag and move on. I guess I just needed to vent a little.
- prezjordan 12y ago
  Because articles like this (and maybe even code golf) might spark an interesting discussion.
- danbruc 12y ago
  The posts that just link to a wikipedia article about a topic that > 90% of the HN crowd is probably familiar with do get a little tiresome. I bet this is not the case in this case. I can understand the attitude against plain Wikipedia links but at least I learned a new idea because of this link.
- jes5199 12y ago
  I think a thing that has happened is that the community is actually full of people who have not learned all the fun computer science stuff that people like you and me take for granted, and that's why they're voting it up. On the one hand, it's frustrating because, damn it, if you don't already know how to play with these concepts then why on earth are you calling yourself a "hacker", but then on the other hand http://xkcd.com/1053/ http://xkcd.com/1053/
  - gamegoblin 12y ago
    I definitely agree with you. It's guess it's just difficult with the HN community growing every day, both in population and the diversity of backgrounds. I think I'll write a little plugin that will hide all wikipedia links and I'll be happy. Maybe something like "hide all wikipedia links unless #comments > N" would work nicely.
- nitrogen 12y ago
  I'd much rather have these articles than yet another 300+ comment thread about the latest tempest in a teacup linkbait drama.

MrGando 12y ago

That's why you may want to get a CS degree... if you are interested in things like this... well, this is just the tip of the iceberg.

juliangamble 12y ago

The Clojure language was introduced with an ant Colony demo by Rich Hickey. He was using it to demonstrate concurrency primitives in Clojure. You can see screenshots and read code here: http://juliangamble.com/blog/2011/12/28/clojure-gui-demo-of-ants/ http://juliangamble.com/blog/2011/12/28/clojure-gui-demo-of-...

diziet 12y ago

For those interested in algorithms and optimizations of paths, check out www.pathery.com/home for an NP complete longest path most vital node puzzle.

14113 12y ago

The inventor of the algorithm actually has a really good website with a good overview and history: http://www.aco-metaheuristic.org/ http://www.aco-metaheuristic.org/

yeureka 12y ago

Back in 2001 I was working on an app used in planning optimal routes for city garbage trucks. We quickly found out that this was equivalent to the Traveling Salesman Problem and the initial brute force solution was not fast enough to get results in useful time. A colleague stumbled upon a paper on Ant Colony Systems and gave it to me to try to implement it and to check if the results were as good as the paper promised. It was amazing how the solutions were so close to optimal ( we checked the results from the ACS algorithm against the brute-force solutions that took hours to compute ) and how fast the algorithm stabilized on the solutions. It was also the first time I had used an algorithm that does not really stop, it just converges to a solution and another heuristic decides when to accept a final result. I learned a lot from it.

patmcguire 12y ago
Garbage trucks have to visit every edge (street segment) once, not every vertex (intersection) once, correct? Can you use Eulerian Paths? http://en.m.wikipedia.org/wiki/Eulerian_path http://en.m.wikipedia.org/wiki/Eulerian_path Or is the process to make a non-Eulerian graph Eulerian NP?
- mvanotti 12y ago
  Once you have a mixed graph (One-way streets and two-way streets), the problem is known as the Mixed Chinese Postman Problem and is NP.