多选择背包问题离散狼群算法研究

Research on discrete wolf pack algorithm of mutiple choice knapsack problem

狼群算法是一种通过模拟狼群的捕食行为和猎物分配方式提出的群体智能算法,为求解复杂组合优化问题提供了一种新的思路。目前狼群算法不能解决离散问题,以NP难中的经典问题——多选择背包问题的求解为研究对象,设计了基于离散空间的狼群算法。对于离散空间的狼群算法,通过将人工狼编码,重新设计了狼群的游走、奔袭和围捕过程,并设计了三个过程中的步长。把学习机制引入离散狼群算法,实现了人工狼之间的交流,且确立了自适应步长公式。结果表明:离散狼群算法成功实现了对离散问题的求解,为组合优化问题的求解提供了新方法。

Wolf pack algorithm is an swarm intelligence algorithm which simulates predation behavior and prey allocation mode of wolf pack,which provides a new method to solve complex combinatorial optimization problems. Wolf pack algorithm can’t solve discrete problems,solving of classical NP-hard problem,multiple choice knapsack problem is research goal,design a wolf pack algorithm based on discrete space. Through artificial wolf coding, redesign wolves,migration,long-range raid,and round up process,and stepsize of three process is designed. The learning mechanism is introduced into discrete wolf pack algorithm（ DWPA ）,which realizes communication between artificial wolves and establish the adaptive step length formula. The results show that DWPA not only implements discrete problem solving,but also provide new method for solving combinatorial optimization problem.