利用改进的二进制狼群算法求解多维背包问题  

Improved binary wolf pack algorithm for solving multidimensional knapsack problem

作　　者：吴虎胜[1,2] 张凤鸣[2] 战仁军[1] 李浩[2] 梁晓龙[3] 

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

出　　处：《系统工程与电子技术》2015年第5期1084-1091,共8页Systems Engineering and Electronics

基　　金：国家自然科学基金(71401178;61472443);陕西省自然科学基金(2013JQ8042)资助课题

摘　　要：狼群算法启发于狼群群体生存智慧,已被用于复杂函数寻优和0-1普通背包问题求解。针对多维背包问题特点,设计了试探装载式的修复机制有效修复和改进人工狼群中的不可行解,改进了传统基于大惩罚参数的目标函数,减小了由于惩罚参数过大而导致算法陷入局部最优的风险;并受狼群的繁衍方式的启发,在二进制狼群算法的基础上提出了求解多维背包问题的改进二进制狼群算法(improve binary wolf pack algorithm,IBWPA)。通过求解19组不同规模的典型多维背包算例和与其他算法的对比分析,例证了算法的有效性和计算稳定性。The wolf pack algorithm has been proposed based on inspiration by group survival swarm intelli- gence of the wolf pack, and successfully applied to complex function optimization problems and the normal 0-- 1 knapsack problem. To solve the multidimensional knapsack problem （MKP）, a trying-loading repair operator based on the MKP specific knowledge is designed to effectively repair and improve infeasible solutions. Then, traditional objective function based on large penalty parameters has been improved so as to reduce the risk of easily trapping in the local optima. Meanwhile, inspired by the reproductive rule of the wolf pack, an improved binary wolf pack algorithm （IBWPA） is proposed for solving the MKP. Simulation results based on 19 bench- mark MKP instances with different scales and comparative demonstrate the effectiveness and computational robustness analysis between the IBWPA and other algorithms of the proposed algorithm.

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

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