基于蚁群优化算法0_1背包问题求解_胡小兵.pdf

20 5 Vol. 20 No. 5 2005 10 JOURNAL OF SYSTEMS ENGINEERING Oct. 2005 ¹ 0- 1 1,2 2 胡小兵 , 黄席樾 ( 1. , 400044; 2. , 400044) : 蚁群优化算法在求解旅行商问题指派问题Job-shop 调度问题和网络路由问题等获得了极大的成 . 将蚁群优化算法应用于0- 1 背包问题, 首先将0- 1 背包问题表示成相应的构造图,并针对该图设计了两 个 状态转移公式, 蚂蚁根据这两 个状态转移公式在带权图中移动直到死亡. 此时,蚂蚁所走过的路径即构成背包 问题的一个可行解. 仿真实验对该算法的参数进行了讨论, 再与遗传算法进行比较, 结果显示该算法具有较高 的性能. : 0- 1 ; ; : TH116 : A : 1000- 5781(2005)05- 0520- 04 Solving 0-1knapsack problem based on ant colony optimization algorithm 1, 2 2 HU Xiao-bing , HUANGX-i yue ( 1. School of Science, hongqing University, hongqing 400044, hina; 2. School of Automation, hongqing University, hongqing 400044, hina) Abstract: Ant colony optimization (A O) algorithm is successfully applied to traveling salesman prob- lems (TSP) , quadratic assignment problem (QAP) , job-shop scheduling problem ( JSP) and network routing problem (NRP) etc. . In this paper A O algorithm is applied to 0-1 knapsack problem (KP) . First KP problem is represented as weighted graph and then two state transition formulas are designed by which ants move from node to node in the graph until dying. So the path on which the ant haswalked is one feasible solution of KP problem. The parameters of the algorithm and the comparison with genetic al- gorithm (GA) have been performed. Experimental results show that our algorithm is eff