基于群体智能的0/1背包问题求解研究进展  

The Research on Swarm Intelligence Based on 0/1 Knapsack Problem Solution

作　　者：王潮[1] 时向勇[1] 李昶[1] 汪镭[1] 

机构地区：[1]上海大学通信与信息工程学院

出　　处：《微型电脑应用》2007年第6期1-5,2,共5页Microcomputer Applications

基　　金：上海市科委重大科技攻关项目:无线传感网关键技术攻关及在道路交通中示范应用(05dz15004);973项目:基于群体智能模型的复杂生产过程智能调度理论及应用(2002CB312202);国家自然基金重点项目:组建化可重构多重入复杂制造系统生产计划与调度体系结构及其关键问题研究(70531020)

摘　　要：0/1背包问题是运筹学中一个经典组合优化NP问题。在简要介绍0/1背包问题基础上,分析展望了0/1背包问题的应用前景。结合已有研究成果,总结并详细分析了蚁群算法、微粒群算法等群体智能算法在0/1背包问题求解方面具有的较好收敛速度、健壮性、稳定性、算法简单等优点。最后,针对群体智能算法在求解0/1背包问题过程中所出现的缺陷,提出了群体智能算法在0/1背包问题求解需要进一步解决的几个问题。0/1 Knapsack Problem is an important NP problem which is also a classical kind of combinatorial optimization inoperation research. In the paper, 0/1 Knapsack Problem was introduced briefly at first. And then, applications of 0/1 KnapsackProblem were explained and forecasted. Combining with the existing work, the advantages including higher convergence speed,robustness, stability and simple algorithm of Swarm Intelligence (Ant Colony System and Particle Swarm Optimization) based on0/1 Knapsack Problem solution were discussed and analyzed in detail. Finally, taking account of some limitations of SwarmIntelligence based on 0/1 Knapsack Problem solution, several problems for Swarm Intelligence based on 0/1 Knapsack Problemsolution were put forward to be further solved.

关 键 词：0/1背包问题 群体智能 蚁群算法 微粒群算法 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]