可控搜索偏向的二元蚁群算法.pdf

28 8 2011 8 Control Theory Applications Vol. 28 No. 8 Aug. 2011 : 1000?8152(2011)08?1071?10 , , , ( , 315211) : . , . , , . , , , . 0--1 , . : ; ; ; ; ; 0--1 : TP18 : A Binary ant colony algorithm with controllable search bias HU Gang, XIONG Wei-qing, ZHANG Xiang, YUAN Jun-liang (Institute of Electronic Commerce, Ningbo University, Ningbo Zhejiang 315211, China) Abstract: Ant colony algorithm explores the solution space according to the bias produced by pheromone trail. How- ever, most of the existing improvements concentrate in raising the population diversity, instead of controlling the search bias. On the basis of the controllable search bias and by the update pattern of the current pheromone, we determine for any given iteration the lower bound of the probability of no further improvement in solution up to the convergence. Using the relation between the number of visitors and the ant population, and considering the population diversity, we develop a binary ant colony algorithm with controllable search bias. In the test of function optimization and the application to the 0--1 multiple knapsack problem, the algorithm exhibits a good search ability and a high convergence speed. Key words: ant colony algorithm; binary ant colony algorithm; pheromone update pattern; controllable search; function optimization; 0--1 multiple knapsack problem 1 (Introduction) (swarm intelligence) , . , M. Dorigo (traveling salesman problem, TSP) (ant system, AS)[1], (ant colony optimization, ACO)[2] . . , . [3] , , , . , , . , [4] , . (search bias) , , . , . , ( 4) . , , , . 2 (The basic framework of ACO algorithm) , n , (combinatorial optimization, CO), : 1[5,6] P = : 2009?12?01; : 2010?11?15. : (Y1080364); (Y1100052). 1072 28 (S,Ω, f) . : S , Ω , f : S → R+ . S Ω f s?. S : n Xi(i = 1, 2, · · · , n), Xi Di = {c1i , c2i , c |Di| i }, X i = c j i (i = 1, 2, · · · , n), s, S s . Ω , , P , . s? ∈ S, f(s?)  f(s), ?s ∈ S, s? , S? ? S. S? , cji τ ji , τ . , . SP , Xi , cji P (c j i |SP ) P