Ants and the Traveling Salesman

While doing a little research on the Traveling Salesman Problem, I found a short article in a journal about evolutionary computation. In this specific issue, the author discussed how ants are capable of finding the shortest path from a food source to their nest.

The article explains how, at one point, an ant will have to choose between going right or left. They are ants, so obviously they choose randomly. However, this means that about half of the ants will choose correctly.  If, for example, one path is on a downward slope and the other on an upward slope,  it is probable that more ants will choose to go down.

Keep in mind, as each ant walks towards its’ food source, they are releasing pheromones on the ground.  This leaves a trail for the other ants to follow, which is much like the line segments connecting the vertices in a traditional Traveling Salesman Problem.  As each ant travels towards the food source, one of them will find the shortest path, given the number of ants per path.

https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=585892

One Reply to “Ants and the Traveling Salesman”

  1. I find this to be very interesting. I looked up ants an the TSP and found something on a similar note about the pheromones that ants leave behind. Ants in an artificial colony are able to create shorter tours by using information accumulates in the form of the pheromone trails. The artificial ant colony is also capable of creating solutions to both symmetric and asymmetric problems of the TSP.

    https://doi.org/10.1016/S0303-2647(97)01708-5

Leave a Reply