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(n 2 m.log n), here n |
Year | DOI | Venue |
---|---|---|
2009 | 10.4304/jnw.4.10.993-1000 | Journal of Networks |
Keywords | Field | DocType |
Ant colony optimization,Deceptive problems,N-bit trap problem | Ant colony optimization algorithms,Convergence (routing),Binary logarithm,Mathematical optimization,Computer science,First order,Correctness,Algorithm,Optimization algorithm,Time complexity,Optimization problem | Journal |
Volume | Issue | Citations |
4 | 10 | 3 |
PageRank | References | Authors |
0.39 | 26 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Ling Chen | 1 | 108 | 11.93 |
Hai-Ying Sun | 2 | 14 | 1.01 |
Su Wang | 3 | 6 | 2.51 |