Value-convergence Time Estimation of the First Order ACO on Deceptive Problems

摘要

This paper presents a first attempt towards the value-convergence time complexity analysis of colony optimization (ACO) on the first-order deceptive systems taking the n-bit trap problem as the test instance under consideration. 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.