基于蚁群优化算法的0-1背包问题求解  

Solving 0-1 knapsack problem based on ant colony optimization algorithm

作　　者：胡小兵[1] 黄席樾[2] 

机构地区：[1]重庆大学数理学院,重庆400044 [2]重庆大学自动化学院,重庆400044

出　　处：《系统工程学报》2005年第5期520-523,529,共5页Journal of Systems Engineering

基　　金：重庆大学基础及应用基础研究基金资助项目(717411061);重庆大学高层次人才科研启动基金资助项目(0208001104201);重庆大学数理学院青年科研启动基金资助项目;重庆市自然科学基金资助项目(CSPC;2005BB2197)

摘　　要：蚁群优化算法在求解旅行商问题、指派问题、Job-shop调度问题和网络路由问题等获得了极大的成功.将蚁群优化算法应用于0-1背包问题,首先将0-1背包问题表示成相应的构造图,并针对该图设计了两个状态转移公式,蚂蚁根据这两个状态转移公式在带权图中移动直到死亡.此时,蚂蚁所走过的路径即构成背包问题的一个可行解.仿真实验对该算法的参数进行了讨论,再与遗传算法进行比较,结果显示该算法具有较高的性能.Ant colony optimization （ACO） algorithm is successfully applied to traveling salesman problems （TSP）, quadratic assignment problem （QAP）, job-shop scheduling problem （JSP） and network routing problem （NRP） etc.. In this paper ACO 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 has walked is one feasible solution of KP problem. The parameters of the algorithm and the comparison with genetic algorithm （GA） have been performed. Experimental results show that our algorithm is effective and with higher performance.

关 键 词：0—1背包问题 蚁群优化算法 组合优化 

分 类 号：TH116[机械工程—机械设计及理论]