Convergence of ant colony optimization on first-order deceptive systems

Deceptive problems have been considered difficult for ant colony optimization (ACO) and it was believed that ACO will fail to converge to global optima of deceptive problems. This paper presents a convergence analysis of ACO on deceptive systems. This paper proves, for the first time, that ACO can achieve reachability convergence but not asymptotic convergence for a class of first order deceptive systems (FODS) without assuming a minimum pheromone at each iteration. Experimental results confirm the analysis.