基于二进制象群优化算法求解0-1背包问题

张 潼，朱晓斌

(1. 河北地质大学 信息工程学院，河北 石家庄 050031；2. 石家庄文化传媒学校，河北 石家庄 050000)

0 引言

背包问题（Knapsack Problems，KPs）[1]是一类著名的NP-Complete问题，在决策投资、资源分配、预算控制、物流、材料学等领域[2-3]具有重要的理论与应用价值。求解0-1KP的传统方法是精确算法[4]，如分支定界法、动态规划法、割平面法等。精确算法虽然可求得精确解，但它们的时间复杂度都是伪多项式时间的，随着0-1KP问题规模的增大，求解效率迅速降低，不适于求解大规模0-1KP实例。演化算法作为一类特殊的随机近似算法,既不需要计算目标函数的导数和梯度,也不要求目标函数具有连续性,而且具有内在的隐含并行性和全局寻优能力，已成求解 0-1KP问题的最重要方法[1]。

除了经典的遗传算法（Genetic algorithm，GA）[5]、粒子群优化（Particle swarm optimization，PSO）[6]、差分演化（Differential evolution，DE）[7]等算法以外，近年来一系列新的演化算法被提出，如正弦余弦算法（Sine cosine algorithm，SCA）[8]、藤壶交配优化（Barnacles mating optimizer，BMO）[9]、象群优化算法（Elephant herding optimization，EHO）[10]等，已被用于求解工程管理、金融、医药、制造、化学等的优化问题。

EHO是Wang等人[10]根据大象放牧行为，提出的一种新演化算法，用于求解连续优化问题，有高效的全局搜索能力，较少的控制参数和结构简单易于实现的优点。本文基于EHO提出一种针对 0-1KP设计的二进制象群优化算法（Binary elephant herding optimization，BEHO），在 EHO基础算法框架内，利用传递函数将操作算子转化为适合于离散问题的算法求解步骤，扩展EHO在组合优化问题上的应用，为大规模的0-1KP提供了高效简洁的解决方案，并通过与6个算法的比较验证了算法的有效性。

本文其余内容组织如下：在第 1节中，给出了0-1KP的定义与数学模型，以及相关算法概述，介绍了原始象群优化算法；……