Abstract
This paper presents a method to improve the search rate of Max-Min Ant System for the traveling salesman problem. The proposed method gives deviations from the initial pheromone trails by using a set of local optimal solutions calculated in advance. This method aims to build a near optimal solution at high speed by combining the candidate partial solutions contained in the set. Max-Min Ant System has demonstrated impressive performance, but the search rate is relatively low. Considering the generic purpose of stochastic search algorithms, which is to find near optimal solutions subject to time constraints, the search rate is important as well as the solution quality. The experimental results using benchmark problems with 51 to 1002 cities suggested that the proposed method has a faster search rate than Max-Min Ant System; the additional computation cost for calculating local optimal solutions is negligibly small.