Pheromone Model Selection in Ant Colony Optimization for the Travelling Salesman Problem

摘要

As a meta-heuristic approach, Ant colony optimization (ACO) has many applications. In the algorithm selection of pheromone models is the top priority. Selecting pheromone models that don't suffer negative biases is a natural choice. Specifically for the travelling salesman problem, the first order pheromone is widely recognized.When come across travelling salesman problem, we study the reasons for the success of ant colony optimization from the perspective of pheromone models,and unify different order pheromone models. In tests, we have introduced the concept of sample locations and the similarity coefficient to pheromone models. The first order pheromone model and the second order pheromone model are compared and are further analysed. We illustrate that the second order pheromone model has better global search ability and diversity of population than the former. With appropriate-scale travelling salesman problems, the second order model performs better than the first order pheromone model.