Travelling salesman problem:if a travelling salesman wishes to visit exactly once each of a list of m cities (where the cost of travelling from city i to city j is cij) and then return to the home city, what is the least costly route a salesman can take?
Ant Colony Optimisation
The ACO algorithm is based on the behaviour of ants, attempts to find the optimal path between two points.
This is achieved by sending a number of waves of ants to traverse the graph. The first wave of ants traverse the graph either randomly or based on a simple heuristic approach (such as taking the shortest path from any node).
Pheromone is then distributed along successful paths such that the paths determined to be better by a scoring function will receive a higher amount of pheromone. Further generations of ants are then sent to traverse the graph, taking into account pheromone levels and heuristic, and again laying pheromone on paths proportionally to the paths score.
In this way, the most optimal paths will accumulate the highest amounts of pheromone and are more likely to be chosen by subsequent generations of ants.
1. Generating a route for each ant. This route is generated by:
a. Randomly choosing a starting location
b. Selecting the next location to visit based on a combination of the pheromone map and the heuristic factor. Specifically, each unvisited location is given a score using the following formula:
𝑠𝑐𝑜𝑟𝑒 = 𝑝ℎ𝑒𝑟𝑜𝑚𝑜𝑛𝑒𝛼**α ∗ ℎ𝑒𝑢𝑟𝑖𝑠𝑡𝑖𝑐**β
P[i]=(Tau[currNode,tempnextnode]**alpha)*(Eta[currNode,tempnextnode]**beta)
Where: 𝑝ℎ𝑒𝑟𝑜𝑚𝑜𝑛𝑒 = Quantity of pheromone on the path from the current location to the unvisited location.
α = Scaling factor for the impact of pheromone weights.
ℎ𝑒𝑢𝑟𝑖𝑠𝑡𝑖𝑐 = heuristic value (in this solution 1/distance) from the current location to the unvisited location.
β = Scaling factor for the impact of the heuristic information.
c. Adding the next location to the route and removing it from the list of unvisited locations.
2. Scoring the route based on the total distance travelled to traverse it.(cost= fun.decodingFun(RouteData,popsize,dmat,N))
3. Update the best found solution if any of the new solutions are improvements.
4. Normalise the scores into the range [100, 200].
5. Generate a map of pheromone to be distributed along the routes of the ants. This value is determined by 𝑞 / 𝑠𝑐𝑎𝑙𝑒𝑑 𝑠𝑐𝑜𝑟𝑒pheromone to each path on the route, where q is some scaling factor.
6.Decay the existing pheromone and add the required new pheromone using the following equation:
𝑝ℎ𝑒𝑟𝑜𝑚𝑜𝑛𝑒 = 𝑐𝑢𝑟𝑟𝑒𝑛𝑡𝑃ℎ𝑒𝑟𝑜𝑚𝑜𝑛𝑒 ∗ (1 − ⍴) + 𝑛𝑒𝑤𝑃ℎ𝑒𝑟𝑜𝑚𝑜𝑛𝑒(Tau=Tau*(1-rho)+detaTau)
Where:
𝑝ℎ𝑒𝑟𝑜𝑚𝑜𝑛𝑒 = Updated pheromone value for the path.
𝑐𝑢𝑟𝑟𝑒𝑛𝑡𝑃ℎ𝑒𝑟𝑜𝑚𝑜𝑛𝑒 = Pheromone currently on the path.
⍴ = Pheromone decay constant.
𝑛𝑒𝑤𝑃ℎ𝑒𝑟𝑜𝑚𝑜𝑛𝑒 = Pheromone to be added based on the route score.