Next generation of algorithms inspired by problem-solving ants

http://www.physorg.com/news/2010-12-algorithms-problem-solving-ants.html

by droid • 16 years ago

40 8 16 years ago

jerf• 16 years ago

These articles are disappointing. First, people have already long since explored this design space for things like network routing and holding it up like it's a new idea is academically fraudulent. (I don't know whether it's the journalist or the scientists without more research, but I'd lay money on the journalist.) Second, the real world inspiration of ants is somewhat limited by the fact that the ants have been thrown at problems where, in computational terms, they have a lot more ants than complexities in the problem. A naive translation of the "ant algorithms" to computer programs would produce a very, very, very slow solution.

It's sort of cool, it's a nifty technique with limited applicability, but can we please stop acting like antlike-automata is some sort of cutting-edge brilliant breakthrough rather than a relatively standard tool in the belt for some domains? It's not the next generation and arguably not even the "current" generation.

abhikshah• 16 years ago

This is par for the course with physorg (and to a slightly lesser degree, newscientist).

RiderOfGiraffes• 16 years ago

Same "news" different source: http://news.ycombinator.com/item?id=1989565

drtse4• 16 years ago

Nothing new, they should check the work of Marco Dorigo, http://en.wikipedia.org/wiki/Ant_colony_optimization

hasenj• 16 years ago

> An ant colony is the last place you'd expect to find a maths whiz

I actually remember seeing something very similar to this on TV when I was a kid, and the program I was watching was even older than me; probably produced before I was even born.

stan_rogers• 16 years ago

I could have sworn I read about this in GEB in '79, and I don't think Hofstaedter would argue that he was postulating anything new with Aunt Hillary.

merraksh• 16 years ago

I doubt this could be an efficient way to compute a shortest path. All of this amounts to a (very inefficient) parallel implementation of an algorithm that checks whether the Bellman-Ford conditions apply to a suboptimal path, as the path is gradually improved.

The Bellman-Ford condition on an arc (i,j) of a graph G constrains the difference of potential between the two nodes i and j, (y_j - y_i), to be no more than the length c_ij of the arc. When it is violated, a better path can be found by modifying the potentials.

The inefficiency here lies in the random nature of these checks, which (if I correctly understood) modify. A much more intuitive algorithm is Bellman-Ford's algorithm, which works even when some arc costs are negative, while Dijkstra's algorithm, much more efficient, can only be applied on non-negative arc costs.

Networks with millions of nodes (such as GPS road networks) could hardly benefit from this ant-colony algorithm, and there are already better algorithms -- see the work by Andrew Goldberg, for instance (http://www.avglab.com/andrew).

geuis• 16 years ago

The other problem with this article is that it really says nothing about algorithms. The title, "Next gen algorithms inspired by..." implies that someone actually wrote new algorithms. That didn't happen. Instead its a lengthy pronouncement of how ants explored a maze, with the author throwing on the normal uninformed speculation statement at the end to add some keywords to the text.

Next generation of algorithms inspired by problem-solving ants

Related Stories