系统工程与电子技术

• 软件、算法与仿真 • 上一篇    下一篇

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

吴虎胜1,2, 张凤鸣1, 战仁军2, 汪送2, 张超1   

  1. 1. 空军工程大学装备管理与安全工程学院, 陕西 西安 710051;
    2. 武警工程大学装备工程学院, 陕西 西安 710086
  • 出版日期:2014-08-22 发布日期:2010-01-03

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

WU Hu-sheng1,2, ZHANG Feng-ming1, ZHAN Ren-jun2, WANG Song2, ZHANG Chao1   

  1. 1. Materiel Management and Safety Engineering College, Air Force Engineering University, Xi’an 710051, China;
    2. Materiel Engineering College, Armed Police Force Engineering University,Xi’an 710086,China
  • Online:2014-08-22 Published:2010-01-03

摘要:

狼群算法(wolf pack algorithm, WPA)源于狼群在捕食及其猎物分配中所体现的群体智能,已被成功应用于复杂函数求解。在此基础上,通过定义运动算子,对人工狼位置、步长和智能行为重新进行二进制编码设计,提出了一种解决离散空间组合优化问题的二进制狼群算法(binary wolf pack algorithm, BWPA)。该算法保留了狼群算法基于职责分工的协作式搜索特性,选取离散空间的经典问题——0-1背包问题进行仿真实验,具体通过10组经典的背包问题算例和BWPA算法与经典的二进制粒子群算法、贪婪遗传算法、量子遗传算法在求解3组高维背包问题时的对比计算,例证了算法具有相对更好的稳定性和全局寻优能力。

Abstract:

The wolf pack algorithm (WPA), inspired by swarm intelligence of wolf pack in their prey hunting behaviors and distribution mode, has been proposed and successfully applied in complex function optimization problems. Based on the designing of the move operator, the artificial wolves’ position, step-length and intelligent 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 searching 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 algorithm and the quantum genetic algorithm, especially for high-dimensional knapsack problems.