求解0-1背包问题的二进制狼群算法  

A binary wolf pack algorithm for solving 0-1 knapsack problem

作　　者：吴虎胜[1,2] 张凤鸣[1] 战仁军[2] 汪送[2] 张超[1] 

机构地区：[1]空军工程大学装备管理与安全工程学院,陕西西安710051 [2]武警工程大学装备工程学院,陕西西安710086

出　　处：《系统工程与电子技术》2014年第8期1660-1667,共8页Systems Engineering and Electronics

基　　金：国家自然科学基金(71171199)资助课题

摘　　要：狼群算法(wolf pack algorithm,WPA)源于狼群在捕食及其猎物分配中所体现的群体智能,已被成功应用于复杂函数求解。在此基础上,通过定义运动算子,对人工狼位置、步长和智能行为重新进行二进制编码设计,提出了一种解决离散空间组合优化问题的二进制狼群算法(binary wolf pack algorithm,BWPA)。该算法保留了狼群算法基于职责分工的协作式搜索特性,选取离散空间的经典问题——0-1背包问题进行仿真实验,具体通过10组经典的背包问题算例和BWPA算法与经典的二进制粒子群算法、贪婪遗传算法、量子遗传算法在求解3组高维背包问题时的对比计算,例证了算法具有相对更好的稳定性和全局寻优能力。The wolf pack algorithm （WPA）,inspired by swarm intelligence of wolf pack in their prey hun-ting behaviors and distribution mode,has been proposed and successfully applied in complex function optimiza-tion problems.Based on the designing of the move operator,the artificial wolves’position,step-length and in-telligent behaviors are redesigned by binary coding,and a binary wolf pack algorithm （BWPA）is proposed to solve combinatorial optimization problems in discrete spaces.BWPA preserves the feature of cooperative search-ing based on job distribution of the wolf pack and is applied to 10 classic 0-1 knapsack problems.Moreover,the 3 high-dimensional 0-1 knapsack problems are tested.All results show that BWPA has better global convergence and computational robustness and outperforms the binary particle swarm optimization algorithm,the greedy genetic al-gorithm and the quantum genetic algorithm,especially for high-dimensional knapsack problems.

关 键 词：进化计算 群体智能 二进制狼群算法 组合优化 0-1背包问题 

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