25

There exist many computational intelligence algorithms based on the observation that ants deposit pheromones in such a way that they find the shortest path to food sources. This logic is used to optimize computer networks.

I cant really relate to that. I have seen ants take an extremely long path to food. This is not always for safety reasons either. What do biologists have to say about this?

Nav
  • 507
  • 5
  • 11
  • Look on Wikipedia for "ant mill", or YouTube for "ant death spiral" and you will find they make paths that are not only sub-optimal, but are in fact invalid paths altogether. – Keeta - reinstate Monica Aug 04 '17 at 19:18

1 Answers1

29

Short answer

Do ants really find the shortest path to a food source?

No! But they can find a decent path

Longer answer

Optimization algorithms are used to search through a possibility space that is too large to explore every single possibility. Such algorithms attempt to find a good enough solution, often without necessarily knowing how 'good' the found solution is to the best possible solution. So optimization algorithms don't always find the best solution. Actually, most of the time, they do not find the best path but a good enough one in a reasonable amount of time.

Same holds true for ants. In the analogy, an ant colony is an agent based algorithm where agents leave pheromone trails. The concentration of the pheromone depends upon the length of the trail. By following the trails that smells the strongest and by regularly making small errors (so that they can keep exploring other paths), they end up with a decent solution. For more info, just google How do ants find their path?.

Remi.b
  • 67,828
  • 10
  • 138
  • 230
  • 1
    If we don't know how good the found solution compares to the best, then how do we know it is good enough? – Ooker Aug 04 '17 at 11:24
  • 2
    @Ooker How do you judge what path to take to places? I think you'll find that you don't relate it to the "best" path (which you might not know) but to the situation instead, such as "is it okay to spend this amount of time". – Pimgd Aug 04 '17 at 11:45
  • 2
    Similarly, when you take your car to go to some place, the path you take is generally "good enough" and not the best. It is good enough because it takes a reasonable time to go to destination... – Jean-Baptiste Yunès Aug 04 '17 at 11:47
  • 2
    @Remi.b "Such algorithms attempt to find a good enough solution usually without ever knowing how 'good' the found solution is to the best possible solution." - Optimization problems *do* in fact (generally) know what the true solution is, however, can't always acheive this *through calculation*. When implementing an optimization function, there is generally some epsilon that is defined, to where if the error of the computed solution is less than epsilon, then the optimization algorithm's solution will be accepted as "close enough". –  Aug 04 '17 at 12:57
  • 2
    @Remi.b If an optimization algorithm isn't aware of the true solution that it's trying to acheive, then it has no way of validating a potential solution. I will admit, there definitely *are* many cases where no true solution is known, however, this is much more prevalent in theoretical work, as apposed to the much more practiced, applied computational approaches. –  Aug 04 '17 at 13:04
  • @Charles Thanks, I brought a small modification to avoid stating that an optimization algorithm never know what the best solution is. – Remi.b Aug 04 '17 at 14:08
  • 9
    @Charles I don't agree. You can test the strength of a solution against other possible solutions. You don't need to know the distance of the best route possible to a location, if you work out 1,000 potential routes and then take the shortest of those – Tom Bowen Aug 04 '17 at 14:42
  • 1
    @Tom.Bowen89 If you have a collection of solutions, and you are just testing one solution against others, how can you be sure that any of those solutions are anywhere close to the output that's needed? A type of "most desired output" must be defined, otherwise you "cannot see the forest from within the trees". Which is to say, an ideal solution, or minimum error tolerance, *must* be defined. If not, there can be no confidence as to how accurate your algorithm is and the outputs it's producing. –  Aug 04 '17 at 15:43
  • @Tom.Bowen89 I will also add that in many optimization problems, they take a probabilistic approach, so *multiple* instances (collections of solutions that stem from different initial conditions) of the algorithm must be had. Which is to say that, each instance of the algorithm running will produce completely different solution sets. That being said, again, some kind of desired result must be defined in order to assess the accuracy of these solutions. –  Aug 04 '17 at 15:45
  • @Tom.Bowen89 So, to go off of your example of the shortest path.. what if the true shortest path is 10 miles, however, the best solution your algorithm produces is 50 miles? How would you be able to assess the accuracy if you don't have an idea about the true shortest path? This is important because, as stated in my most previous comment, if the best solution is still very far off from the true solution, the algorithm will need to be ran again in order to obtain different potential solutions. There *must* be some kind of "outside" assessment as to your algorithm's performance and accuracy. –  Aug 04 '17 at 15:51
  • @Tom.Bowen89 I recommend you looking into simulated annealing algorithms, as it's a common platform in computer science for introducing the dynamics of optimization and approximation algorithms. https://en.wikipedia.org/wiki/Simulated_annealing –  Aug 04 '17 at 15:54
  • @Charles is there a way to calculate the confidence of the accuracy of the calculated path? Correct me if I'm wrong, but isn't that in statistics the confidence of a guess can be calculated independently with the correct value? – Ooker Aug 04 '17 at 16:25
  • 1
    @ooker You cannot calculate the confidence in whether you have the best path from just sampling (trying solutions and seeing which ones work) unless you can brute force the entire state space. However, if you know something about your state space, then you can use that problem-specific information to determine how good your solution is. For example, if you know the space is differentiable, you can use any information you might know about the maximum derivatives to create an upper/lower bound. – Cort Ammon Aug 04 '17 at 16:42
  • 1
    @Charles: "If an optimization algorithm isn't aware of the true solution that it's trying to acheive, then it has no way of validating a potential solution." - That's not true - very often in real life the criterion is "Solution must cost less than X". If a solution is found that has a cost less than X, it is "good enough", and hence valid. If it is a lot less than X, so much the better. There's no need to know the absolute best achievable value. The value of X depends on the (external) constraints of the project, not on the parameters of the optimisation problem itself. – psmears Aug 04 '17 at 17:10
  • That's exactly what I said in a previous comment, lol. Please read all comments before trying to correct someone. "When implementing an optimization function, there is generally some epsilon that is defined, to where if the error of the computed solution is less than epsilon, then the optimization algorithm's solution will be accepted as "close enough"." –  Aug 04 '17 at 17:15
  • 1
    @Charles: I did read that comment, and it is different from what I'm saying. I'm not saying that you define an epsilon that gives an acceptable (proportional or absolute) difference between the true optimal value and the best found - that still requires *a priori* knowledge of the optimal value. I'm saying instead that you define a threshold X that's *independent* of the optimal value - i.e. you don't actually care at all how close you are to the true optimum, just whether you find a solution that "works" in whatever context you're operating in. – psmears Aug 04 '17 at 17:21
  • @psmears How you define the heuristic isn't always consistent, and is too difficult to generalize, which is why your statements aren't valid. It's different from algorithm to algorithm, which is ultimately based on information you've already obtained going into the development of the algorithm. –  Aug 04 '17 at 17:23
  • 1
    Comments are not for extended discussions. Please follow this up in the chat (and eventually on some CS SE site). – Remi.b Aug 04 '17 at 17:27
  • @Charles: You're confusing the algorithm with the problem domain, and specifically the problem's acceptability criterion (for the ants, perhaps: does the energy in the food at the end of this path exceed the energy expended taking the path by enough to ensure survival?) with the stopping criterion/heuristic of a particular algorithm ("OK we've spent enough time & energy checking out paths, now let's get on and eat."). The former will likely influence the choice of the latter, but it's important to be aware of the distinction. Good luck with your studies, your protein project sounds cool :) – psmears Aug 04 '17 at 21:25
  • @Pimgd https://xkcd.com/85/ – jpmc26 Aug 05 '17 at 03:02