《1 前言》

1 前言

人工蜂群[1~4] (artificial bee colony，ABC)算法是由Karaboga于2005年提出的一种基于群体智能的仿生优化算法。实验表明，ABC 算法比遗传算法 (GA)、差分进化算法(DE)、粒子群优化算法(PSO)具有更好的优化性能。由于其具有收敛速度快、控制参数少、易于实现等优点，已引起越来越多的学者关注，并在很多优化问题中取得了成功的应用[5~9] 。传统的ABC算法主要用于求解连续空间的优化问题，对于一些采用二进制编码的0～1整数规划问题却难以处理，这已成为限制其发展的一个瓶颈。为此，Marinakis 等在 2009 年提出了一种二进制人工蜂群(binary artificial bee colony，BABC)算法[10] ，然而其邻域搜索方式存在一些不足：a. 邻域搜索方式是随机的，导致算法的开采能力较弱，收敛速度较慢；b. 邻域搜索公式是单维的，使得候选食物源与原食物源极易相同，导致邻域搜索失败，影响算法性能。Pampará等[11] 又提出了3种BABC算法，重点在于连续域到离散域的映射，但未研究新的邻域搜索方式。

在前人研究的基础上，本文提出一种改进的二进制人工蜂群(modified binary artificial bee colony， MBABC)算法，并将其应用于多维背包问题的求解。MBABC 算法对 ABC 算法中引领蜂和跟随蜂的邻域搜索公式进行重新定义，并利用Bayes公式决定蜜蜂食物源的取值概率。在求解多维背包问题时，加入了贪婪算法这个有效的局部搜索方法，利用启发式信息，加快算法的收敛速度。通过对多维背包问题标准测试库的仿真实验和与其他算法的比较，表明了本文算法在迭代相同次数的情况下更容易找到最优解，体现了算法的可行性和高效性，为多维背包问题的求解提供了一种新的解决办法，拓展了ABC算法的应用领域。

《2 人工蜂群算法》

2 人工蜂群算法

《2.1 传统人工蜂群算法》

2.1 传统人工蜂群算法

ABC 算法主要模拟蜜蜂种群的智能采蜜行为。蜂群主要由引领蜂(employed bees)、跟随蜂(onlookers)和侦察蜂(scouts)三个部分组成。人工蜂群算法在求解优化问题时，食物源代表优化问题的一个可能解，蜂群采蜜(食物源)的过程也就是搜寻优化问题最优解的过程。食物源的优劣取决于优化问题的适应值(函数值)，适应值高的食物源较优。人工蜂群算法中解的个数( SN )等于引领蜂或跟随蜂的个数。用 xi =(xi 1 ，xi 2，⋯，xiD ) 表示第 i 个食物源( i = 1，2，⋯，SN ，D 为搜索空间的维数)。首先，人工蜂群算法随机产生 SN 个解(食物源)，然后蜂群对所有的食物源进行循环搜索，循环次数为 MCN 。引领蜂首先在食物源的邻域生成一个候选食物源，并比较候选食物源与先前食物源的优劣，如果候选食物源的适应值优于先前食物源的适应值，则用候选食物源代替先前的食物源，否则保持先前的食物源不变。结束之后，引领蜂回到舞蹈区把食物源优劣的信息通过跳摇摆舞传达给跟随蜂，跟随蜂根据所得到的信息按照一定概率选择食物源，适应值越高的食物源被选择的概率越大。跟随蜂选中食物源后，也在食物源的邻域生成一个候选食物源，并比较候选食物源与选中食物源的优劣，保留较优的食物源。人工蜂群算法就是通过上述反复循环来最终找到最优解的。当某个蜜蜂个体经过 lim it 次循环食物源没有更新时，个体放弃该食物源变成侦察蜂，寻找新的食物源。

引领蜂和跟随蜂根据式（1）在食物源的邻域生成一个候选食物源

式（1）中， vij 是生成的候选食物源；k ∈{1，2，⋯，SN} ， j ∈{1，2，⋯，D } ，这两个数都是随机选取的，但 k ≠i ； rij 是 [-1，1] 上均匀分布的随机数，它控制 xij 邻域的生成范围。随着迭代次数的增加， xij -xkj ) 之间的距离缩小，搜索的空间也缩小，即搜索的步长缩小，动态地调整步长，有助于算法提高精度，并最终获得最优解。式(1)称为ABC算法的邻域搜索公式。

跟随蜂通过如下概率来选择食物源

式（2）中， fiti 为第 i 个食物源的适应值，即食物源的适应值越优，其被选择的概率就越大。在最大化问题中， fiti 与优化问题目标函数值 fi 的对应关系为

在ABC算法中，某个蜜蜂个体如果连续经过 limit 次循环之后食物源仍然没有得到更新，个体就要放弃食物源，转变为侦察蜂。侦察蜂通过式（4）产生一个新的食物源

式（4）中， 为新的食物源的第 j 维分量，j∈{1，2，⋯，D } ； rand1 为 (0，1) 之间均匀分布的随机数； 分别为第 j 维变量的最小值和最大值。

《2.2 二进制人工蜂群算法》

2.2 二进制人工蜂群算法

Marinakis 等人提出的BABC算法仿照二进制粒子群优化(BPSO)算法 [12] 和二进制差分进化(BDE)算法 [13] 的思想，将初始化得到的 xi 和邻域搜索公式(1)得到的 vi 通过logistic函数转换为二进制的 和 ，转换公式为

式（6）、式（8）中， rand2 和 rand3 均为 (0，1) 之间均匀分布的随机数。

算法的其他流程与传统的ABC算法相同，在此不再赘述。

《3 改进二进制人工蜂群算法》

3 改进二进制人工蜂群算法

BABC算法继续沿用传统ABC算法中的邻域搜索公式(1)得到的 vi 转换成二进制的 的必要性并不是很强，而且采用的logistic函数的主要功能是限界，并没用充分的理由。此外，在BABC算法中采用单维更新，这使得候选食物源与原食物源极易相同，导致邻域搜索失败。为此，本文对邻域搜索公式进行重新定义。首先，在生成候选食物源 vij 时，不采取随机选取一个 j ∈{1，2，⋯，D } ，而是使j 取遍 1，2，⋯，D ，这样可以避免候选食物源与原食物源极易相同的缺陷；其次，从式(1)可以看出，vij 的取值主要由 xij 和 xkj 决定，当xij 和xkj 取0或1后，可以通过设定 xij 和 xkj  判断取0和1的可信度，然后借助Bayes公式来决定 vij 到底取0还是取1。因此，先作如下两个假定。

1）由于优化过程中 vij  的真值是未知的，故假定先验概率 P (vij  =0)=P (vij  =1)=0.5 。

2）在寻找最优值的过程中，假定 xij 和 xkj 对最优值的判定是相互独立的。

记 xij 作出正确判定的概率为 P1 ， xkj 作出正确判定的概率为 P2 ，由Bayes公式可得

xij 和 xkj 发现最优值的概率应与优化问题的适应值成正比，因此不妨假设，由于发生某个事件的概率应小于等于 1，因此当 P2 >1 时，就令P2 =1 。此外，由于 xij 和 xkj 是迭代过程中的历史最好值，它们发现最优值的概率应随迭代次数的增加而逐渐变大，因此不妨令

式（10）中， P1 、 P2 为 xij 发现最优值的概率的终值和初始值；iter为当前迭代次数；MCN为最大迭代次数。

《4 求解多维背包问题的改进二进制人工蜂群算法》

4 求解多维背包问题的改进二进制人工蜂群算法

多维背包问题是组合优化领域中一个经典的 NP难题，在很多实际工程问题中有着广泛的应用。因而，寻找可以有效解决该问题的算法具有重要的研究意义。目前，许多学者利用不同的思想提出了各种各样的算法来对其进行求解。贺一等[14] 借鉴认知心理学有关记忆系统的表述，在禁忌搜索算法中引入长时记忆，构造了基于双禁忌表的禁忌搜索算法，在求解多维背包问题的仿真实验中取得了不错的效果。俞学才等[15] 通过定义新的选择概率的规则和基于背包项的一种序的启发式信息，提出了求解多维背包问题的蚁群优化算法。孔民等[16] 在蚁群优化系统高维立方体结构的基础上，提出一种二进制蚂蚁算法来求解多维背包问题。冀俊忠等[17] 提出基于变异和信息素扩散的多维背包问题的蚁群算法。刘勇等[18] 基于元胞自动机的原理和离散粒子群算法，提出一种元胞粒子群算法，该算法具有较好的全局优化能力。除了上述算法外，还有小世界算法[19] 、DNA计算[20] 、人工鱼群算法[21] 等。

多维背包问题可描述为：有 n 个价值为 wj ( j =1，2，⋯，n ) 的物品， m 个容积为 ci (i = 1，2，⋯，m) 的背包，第 j 个物品占用第 i 个背包的体积大小为 。如何选择物品使其既可以装入这 m 个背包，又能使装入物品的总价值最大。其数学模型为

式(11)中， f (x1 ，x2 ，⋯xn ) 为目标函数； n 为物品数量； m 为背包数量； wj 为第 j 个物品的价值； ci 为第i 个背包的体积； 为第 j 个物品占用第 i 个背包的体积大小； xj 为0～1变量，xj =1 表示第 j 件物品被装入背包， xj =0 表示第 j 件物品没有被装入背包。

采用MBABC算法在求解多维背包问题时通过邻域搜索得到的解不一定可行，为此，引入贪婪算法来修正不可行解，同时在保证解可行的前提下，尽量增加其适应值。若解不可行，则按物品 j 的价值密度 ρj = cj / wj ( j=1，2，⋯，n ) 由小到大的方向将 xj =1 变为 x j =0 ，直到将不可行的解变成可行解；若解可行，则在保证解可行的前提下，按 ρj 由大到小的方向将 xj =0 变成 xj =1 ，尽量增加其适应值。

求解多维背包问题的MBABC算法步骤如下。

1）设置迭代次数 iter ，群体规模 SN ，限定的循环次数 limit ，最大迭代次数 MCN ， xij 发现最优值的概率的终值 P1 和初始值 P2 。

2）初始化种群 X (SN×n ) ，对 X 中的每个向量 xi （ i =1，2，⋯，SN ）用贪婪算法修正并计算适应值。

3）引领蜂按式(9)产生候选食物源，用贪婪算法修正并计算其适应值，如果候选食物源 vi 的函数值优于原有食物源 xi  的函数值，则用其替换 xi  ，否则保留 xi  不变。

4）利用式(2)计算与 xi 有关的概率值 qi 。

5）跟随蜂根据 qi 选择食物源，并按式(9)产生候选食物源，用贪婪算法修正计算其适应值，如果候选食物源 vi 的函数值优于原有食物源 xi 的函数值，则用其替换 xi ，否则保留 xi 不变。

6）判断是否有要放弃的解，如果存在，则按照式(4)随机产生一个满足约束条件的新解来代替它。

7）记录迄今为止最好的解。

8）判断算法是否满足停止条件，如满足则输出最优结果，否则返回步骤3。

《5 仿真实验》

5 仿真实验

为了验证本文算法的性能，采用VC++编程，对文献[18]中的55个标准测试算例进行了仿真实验。限于篇幅，本文仅列出文献[18]和其他算法共同采用的较大规模背包问题的实验结果。表1为本文算法与文献[12]的 BPSO 算法和文献[18]的元胞粒子群算法（CPSO）以及文献[10]提出的 BABC 算法的实验结果对比，BPSO 和 CPSO 的参数设置见文献 [18]，BABC 算法和本文算法中群体规模均为 100 (与BPSO和CPSO的群体规模一致)，lim it = 50 ，在本文算法中的另外两个参数P1 和 P2 分别取值为 P1 = 0.9 ，P2 = 0.1 。仿真实验时，对每个算例独立运行 20 次，记录 20 次实验中获优次数、最优解、最劣解和平均解。

《表1》

表1 BPSO、CPSO、BABC和MBABC的性能比较

Table 1 Comparison results of BPSO，CPSO，BABC and MBABC

从表1的对比数据可以看出，BPSO在很多情况下没有搜索到最优解或者获优次数很少，极易陷入局部最优而停滞不前；BABC凭借人工蜂群算法良好的优化性能，在最终优化结果上相比于BPSO有显著的改善。但由于BABC采用单维更新，这使得候选食物源与原食物源极易相同，容易导致邻域搜索失败，因而其求解效率不是很高。而MBABC克服了BABC容易陷入局部极值的缺陷，能以较快的速度达到全局最优，有较高的全局寻优性能。在对测试算例进行的仿真实验中要优于BABC以及BPSO和CPSO两种优化算法，表明了本文算法在解决多维背包问题上的可行性和有效性。

《6 结语》

6 结语

二进制人工蜂群算法具有收敛速度慢、容易陷入局部最优等问题，针对这一不足，本文提出一种改进的二进制人工蜂群算法，并将其与贪婪算法相结合，应用于多维背包问题的求解。仿真实验结果表明，改进后算法的优化性能明显优于二进制人工蜂群算法和其他一些进化算法，为多维背包问题的求解提供了一个新的思路，并拓展了人工蜂群算法的应用范围。