Affiliations: Department of Computer Science, Nanjing University of Aeronautics and Astronautics, Nanjing, 210016, China | Department of Computer Science and Engineering, Yangzhou University, Yangzhou, 225127, China | State Key Lab. of Novel Software Tech, Nanjing University, Nanjing, 210093, China
Abstract: Ant colony optimization (ACO), an intelligential optimization algorithm, has been widely used to solve combinational optimization problems. One of the obstacles in applying ACO is that its search process is sometimes biased by algorithm features such as the pheromone model and the method of constructing the solutions. Due to such searching bias, ant colony optimization cannot converge to the optimal solutions of deceptive problems. The goal of our study is to find an effective method to avoid such searching bias and to achieve high performance of ACO on deceptive problems. In this paper, we present a method for avoiding the searching bias in the first order deceptive problem of ACO taking the n-bit trap problem as an instance. Convergence analysis of our method is also given. Our experimental results confirm the correctness of our theoretical analysis and show that our method can effectively avoid the searching bias and can ensure both the convergence in value and the convergence in solution for the first order deceptive problems.
Keywords: Ant colony optimization, deceptive problems, n-bit trap problem, convergence
