Affiliations: [a] Division of Information Engineering, Faculty of Engineering, Information and Systems, University of Tsukuba, Ibaraki, Japan | [b] Department of Computer Science, Graduate School of Systems and Information Engineering, University of Tsukuba, Ibaraki, Japan
Correspondence:
[*]
Corresponding author: Hitoshi Kanoh, Division of Information Engineering, Faculty of Engineering, Information and Systems, University of Tsukuba, 1-1-1 Tennoudai, Tsukuba, Ibaraki 305-8573, Japan. E-mail: kanoh@cs.tsukuba.ac.jp
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.
Keywords: Ant colony optimization, traveling salesman problem, search rate, local optimal solution
