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

吴虎胜, 张凤鸣, 战仁军, 李　浩, 梁晓龙

(1. 武警工程大学装备工程学院, 陕西 西安 710086;

2. 空军工程大学装备管理与安全工程学院, 陕西 西安 710051;

3. 空军工程大学空管领航学院, 陕西 西安 710051)



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

吴虎胜1,2, 张凤鸣2, 战仁军1, 李浩2, 梁晓龙3

(1. 武警工程大学装备工程学院, 陕西 西安 710086;

2. 空军工程大学装备管理与安全工程学院, 陕西 西安 710051;

3. 空军工程大学空管领航学院, 陕西 西安 710051)

摘要：狼群算法启发于狼群群体生存智慧,已被用于复杂函数寻优和0-1普通背包问题求解。针对多维背包问题特点,设计了试探装载式的修复机制有效修复和改进人工狼群中的不可行解,改进了传统基于大惩罚参数的目标函数,减小了由于惩罚参数过大而导致算法陷入局部最优的风险;并受狼群的繁衍方式的启发,在二进制狼群算法的基础上提出了求解多维背包问题的改进二进制狼群算法(improve binary wolf pack algorithm, IBWPA)。通过求解19组不同规模的典型多维背包算例和与其他算法的对比分析,例证了算法的有效性和计算稳定性。

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

0引言

背包问题是经典的NP-hard问题,旨在寻求背包容积限制下具有最大价值的物品装载方案。如金融产品组合投资、无人机任务分配、物料资源分配、货运装载等很多实际问题都可抽象为背包问题,应用非常广泛[1]。背包问题有多种形式:如普通背包问题[2]、多维背包问题[3]、多选择背包问题[4]、多选择多维背包问题[5]、多目标背包问题[6]和二次背包问题[7]等。……