A short convergence proof for a class of ant colony optimization algorithms
Tóm tắt
We prove some convergence properties for a class of ant colony optimization algorithms. In particular, we prove that for any small constant /spl epsiv/ > 0 and for a sufficiently large number of algorithm iterations t, the probability of finding an optimal solution at least once is P*(t) /spl ges/ 1 - /spl epsiv/ and that this probability tends to 1 for t/spl rarr//spl infin/. We also prove that, after an optimal solution has been found, it takes a finite number of iterations for the pheromone trails associated to the found optimal solution to grow higher than any other pheromone trail and that, for t/spl rarr//spl infin/, any fixed ant will produce the optimal solution during the tth iteration with probability P /spl ges/ 1 /spl epsiv//spl circ/(/spl tau//sub min/, /spl tau//sub max/), where /spl tau//sub min/ and /spl tau//sub max/ are the minimum and maximum values that can be taken by pheromone trails.
Từ khóa
#Convergence #Ant colony optimization #Approximation algorithms #Heuristic algorithms #Resource management #Optimal control #Learning #Stochastic processes #Terrorism #HumansTài liệu tham khảo
10.1007/0-306-48056-5_9
grassé, 1959, la reconstruction du nid et les coordinations interindividuelles chez <emph>bellicositermes natalensis et cubitermes sp. </emph> la théorie de la stigmergie: essai d'interprétation du comportement des termites constructeurs, Insectes Sociaux, 6, 41, 10.1007/BF02223791
10.1016/S0020-0190(01)00258-7
gutjahr, 1999, A generalized convergence result for the graph-based ant system metaheuristic
10.1016/S0167-739X(00)00044-3
10.1287/moor.13.2.311
10.1162/106454602320184202
romeo, 1991, a theoretical framework for simulated annealing, Algorithmica, 6, 302, 10.1007/BF01759049
10.1109/ICEC.1997.592327
stützle, 2000, <formula><tex>${\cal max}$</tex></formula>-<formula> <tex>${\cal min}$</tex></formula> ant system, Future Gener Comput Syst, 16, 889, 10.1016/S0167-739X(00)00043-1
10.1016/S0167-739X(00)00042-X
dorigo, 1992, Optimization learning and natural algorithms
10.1162/106454699568728
10.1109/CEC.1999.782657
dorigo, 1991, Positive feedback as a search strategy
10.1109/4235.585892
bullnheimer, 1999, a new rank-based version of the ant system: a computational study, Central Eur J Oper Res Econom, 7, 25
birattari, 2000, For a formal foundation of the ant programming approach to combinatorial optimization Part 1 The problem the representation and the general solution strategy
10.1109/3477.484436