An Improved Ant Colony Optimization with Subpath-Based Pheromone Modification Strategy

The performance of an ACO depends extremely on the cognition of each subpath, which is represented by the pheromone trails. This paper designs an experiment to explore a subpath's exact role in the full-path generation. It gives three factors, sequential similarity ratio (SSR), iterative best similarity ratio (IBSR) and global best similarity ratio (GBSR), to evaluate some selected subpaths called r-rank subpaths in each iteration. The result shows that r-rank subpaths keep a rather stable proportion in the found best route. And then, by counting the crossed ants of a subpath in each iteration, a subpath-based pheromone modification rule is proposed to enhance the pheromone depositing strategy. It is combined with the iteration-best pheromone update rule to solve the traveling salesman problem (TSP), and experiments show that the new ACO has a good performance and robustness.