First Order Deceptive Problem of ACO and Its Performance Analysis

Abstract

Ant colony optimization(ACO), which is one of the intelligential optimization algorithm, has been widely used to solve combinational optimization problems. Deceptive problems have been considered difficult for ant colony optimization. It was believed that ACO will fail to converge to global optima of deceptive problems. This paper proves that the first order deceptive problem of ant colony algorithm satisfies value convergence under certain initial pheromone distribution, but does not satisfy solution convergence. We also present a first attempt towards the value-convergence time complexity analysis of ACO on the first-order deceptive systems taking the n-bit trap problem as the test instance. We prove that time complexity of MMAS, which is an ACO with limitations of the pheromone on each edge, on n-bit trap problem is O(n2m.log n), here n is the size of the problem and m is the number of artificial ants. Our experimental results confirm the correctness of our analysis.