A New Version of Graph-based Ant System for Subset Problems
A new effective graph-based ant system (GBAS) is proposed for solving subset problems. The structure graph and equivalent routes are defined for subset problems. A new updating pheromone strategy based on strengthening the pheromone on equivalent routes is presented. Ants are influenced orderly by the out-of-order information of the problem, and the information for solving the problems is increased. A route mutation mechanism is introduced, so the pheromone distribution is adjusted and the algorithm can be kept from stagnation behavior by amending the routes. After one cycle, updating the best route of this cycle, updating the best mutated route and updating no route are three instances of pheromone updating. As results the convergence speed and searching capability of the algorithm are improved. Finally, the effectiveness and superiority of the algorithm are illustrated with multidimensional knapsack problems.
ant colony algorithm graph-based ant system subset problem knapsack problem mutation
LIANG Shubao CAO Jianjun ZHANG Peilin
Mechanical Engineering College, Shijiazhuang, Hebei, China, 050030
国际会议
第八届国际测试技术研讨会(8th International Symposium on Test and Measurement)
重庆
英文
1719-1722
2009-08-01（万方平台首次上网日期，不代表论文的发表时间）