An Improved Ant Colony optimization Algorithm: Minion Ant(MAnt) and its Application on TSP

摘要

Ant colony optimization is a simulated evolutionary algorithm which imitates the ants foraging to determine the shortest path between the anthill and a food source. This is a heuristic system with a small degree of randomness. Different combinatorial optimization problems, such as the Traveling Salesman Problem(TSP), the Minimum Spanning Tree problem(MST), the job-shop scheduling problem, etc. have been solved using extensions of the algorithm. While applying these algorithms to solving large-scale tsp problems the major roadblock faced is with respect to the slow rate of convergence and stagnation at a local optimum, i.e. poor exploration tendency. The paper proposes a newer ant colony optimization algorithm that aims to tackle this problem in the domain of TSP solving. The proposed algorithm named the Minion Ant (MAnt) algorithm is based on the principle of a larger number of explorations in a single iteration to facilitate faster convergence to an optimal answer and also aims at preventing conformity of ants to a certain path by using dynamic parameter alteration. The algorithm may be extended into other domains with some tweaks to suit the application. According to the simulation results, the proposed algorithm performs better than the traditional one. The algorithm achieves the best tour length of 96830 for TSPlib pr136 with a relative error of 0.059% which is very close to the ofcial record of 96772.