改进的人工蜂群算法在作业调度中的应用

邵金平，陈 亮，周 庆

(泰山职业技术学院，山东 泰安 271000)

1 引入

当今时代，人们更多的关注优化问题，并做了大量的工作，发明很多有效的算法，如遗传算法、人工蜂群算法、神经网络、鱼群算法等等［1］。人工蜂群算法是较新的一个人工智能算法，由Dervis Karaboga在2005发明，人工蜂群算法比较容易实现和应用，只需要一些常用的参数，如群体规模、最大循环次数［4］。

在本文中，改进了经典的人工蜂群算法，在蜜蜂搜索食物源的过程中增加了变异操作和杂交操作，以提高食物源搜索的优化程度。实验表明，改进人工蜂群算法在工作调度中的应用是有效的。

2 人工蜂群算法

在人工蜂群算法中，蜂群分为三蜜蜂:雇用蜂、跟随蜂和侦查蜂，在没有任何提示的情况下随机搜索食物源的蜜蜂叫侦查蜂，在一定的前提下自行出去找食物的蜜蜂叫雇用蜂，等待目标食物源出现后才去食物源的蜜蜂叫跟随蜂［1］。每个食物源只有一只雇用蜂，换句话说，雇用蜂的数量等于食物源的数量。当食物源被消耗完后(或食物源达不到最低要求)，雇用蜂(或跟随蜂)升级为侦查蜂［5］。人工蜂群算法的主要步骤如下:

(1)初始化

(2)Repeat

(3)将雇用蜂放在一个食物源

(4)将跟随蜂放在一个食物源

(5)将侦查蜂放在搜索区域搜索新的食物源

(6)Until(满足预先设定的要求)

在人工蜂群算法中，每个循环分三步:发出雇用蜂到食物源并计算蜂蜜的数量;跟随蜂分享雇用蜂的食物信息，并判断蜂蜜数量是否达到要求;找不到达到最低要求的食物源时，发出侦查蜂，查找可能存在的食物源。在初始化阶段，根据蜜蜂和食物源的蜂蜜数量决随机选择食物源，以位置的形式记录下食物源，然后蜜蜂进入蜂巢与跟随蜂共享食物源的蜂蜜数量的信息;在第二阶段，每只雇用蜂进入食物源区域，根据上次循环的得到的食物源位置，在该位置的邻域内搜索一个新的食物源;在第三阶段，跟随蜂根据雇用蜂的提供的食物源的蜂蜜数量的信息来到食物源，食物源的蜂蜜数量越大，这个食物源被跟随蜂选中的概率也越大［2］。到达选中的食物源区域，在选中的食物源的邻域内搜索一个新的食物源。当一个食物源被消耗尽，由侦查蜂随机的选择一个新的食物源，并代替消耗尽食物源。

在人工蜂群算法中，每个食物源的位置代表问题的一个候选解，每个解都有一个适合度，该适合度决定解的优劣，食物源的蜂蜜的数量即是候选解的适合度［6］。一般的雇用蜂或跟随蜂的数量与解的数量相同。人工蜂群算法或随机生成一个初始解或用蜜蜂的数量NF代替。每个解代表一个食物源的位置记为xij，i代表一个特解(i=1，2，…，NF)，每个解是一个 D-维向量，因此 j代表特解的“特维”(j=1，2，…，D)。初始化完成后，雇用蜂在前一个食物源的附近开始搜索新食物源，如果新食物源的蜂蜜数量(适应度)比前一个食物源大，则用新食物源代替前一个食物源。

当所有雇用蜂完成搜索过程，所有蜜蜂分享食物源的蜂蜜数量信息及跟随蜂得到食物源的位置信息［3］。跟随蜂选择某个食物源与Pi有关，

其中，fi、fn是解i的适应度(或蜂蜜的数量)，NF是食物源的数量。雇用蜂访问食物源后对其蜂蜜数量进行估算，从而确定了Pi的值，跟随蜂根据Pi决定访问的食物源。

可使用如下公式从前后选解生成新的后选解:

其中，j是列(或维)下标(j=1，2，…，D)，k 是某个特解的下标(k=1，2，…，NF)，i是某个特解的下标(i=1，2，…，NF)，i和 k 是不同的，k 是随机生成的，而 i不是，Φij∈［-1，1］是一个随机数，决定 xij邻域的大小。xij和xkj的参数差别越小，两者位置越近。因此，最优解的搜索的步长减小了。生成后选解νij后，计算相应的适应度并进行比较。

如果新后选解的适应度更高，则用新后选解代替原后选解，否则保留原后选解。如果经过一个循环后没有找到更好的解，则设该食物源被消耗尽。然后放出侦查蜂，找新食物源来代替它。

3 带变异和杂交操作的人工蜂群算法

首先，标准人工蜂群算法中添加了新动作——变异操作。变异操作是在雇用蜂之后插入的。人工蜂群算法分为四阶段:初始化阶段、雇用蜂阶段、跟随蜂和侦查蜂阶段、变异和杂交阶段。雇用蜂阶段完成局部搜索，雇用蜂之后的变异用于突破搜索空间，并完成在新空间的搜索。因此变异改变了搜索空间，提供了改变局部最优的条件，防止陷于局部最优。在人工蜂群算法中，每次食物源搜索操作完成后，按一定的概率执行变异操作。按随机方式从满足一定条件食物源中选择食物源，并执行变异操作。用新后代代替原后代。在本文中，当执行变异操作时，随机选择一个食物源xij，用一个随机数替换它的某个列值。

下面是添加变异操作的人工蜂群算法。第一阶段是初始化阶段，完成单个食物源的搜索。

算法:添加变异操作的人工蜂群算法

(初始化阶段)

步骤1:随机产生NF个D-维向量，作为初始食物源位置xij，(i=1，…，NF，j=1，…，D)

步骤2:根据公式:

计算每个食物源的适应度，并选择最好的作为初始解

(雇用蜂阶段)

步骤3:根据公式(1)计算概率Pi，按公式(2)计算生成新的后选解

步骤4:按公式(3)计算每个新后选解的适应度fit(bi)，根据适应度判断，如果新解优于原解，则用新解替换原解

步骤5:根据公式(1)重新每个食物源的概率Pi

(杂交阶段)

步骤6:如果没有产生新的解，并且原解不能达到最目标要求，则随机选择2个解，按公式(2)进行杂交，生成新解

步骤7:按公式(3)计算每个新后选解的适应度，用适应度最高的代替父解

(跟随蜂阶段)

步骤8:对每只跟随蜂，根据Pi选择新的食物源，生成食物源xij的新的后选解，并计算适应度，并选择适应度最高的作为新的解

(变异阶段)

步骤9:如果没有产生新的解，并且原解不能达到最目标要求，则采用遗传算法的变异公式对现存解进行变异，并计算变异后各解的适应度

(侦查蜂阶段)

步骤10:如果根据适应度选出的新解达到最优或循环次数达到最大要求，则结束，

步骤11:如果食物源没有消耗尽，则转(步骤3)，否则，由侦查蜂随机搜索一个新食物源，转(步骤3)

4 实验

实验在某企业内的作业调度环境下进行的。实验中涉及的参数有:最大循环次数为20000，最大食物源数为40，最大流程数为30，维数为30.变异概率值0.7。

实验1:实验设有5个工作点，17个任务，对比算法为遗传算法，执行时间如下:

表1 实验1执行时间对照表Table 1Experimental1execution time table

遗传算法的产生序列:14，9，0，15，4，13，6，1，3，8，11，16，12，10，2，7，5.

基本人工蜂群算法产生序列:7，14，5，6，4，2，13，15，1，9，16，0，8，3，10，11，12

本文算法的产生序列:0，3，9，5，12，2，13，4，1，6，16，7，8，11，10，14，15.

实验2:实验设有10个工作点，27个任务，对比算法为遗传算法，执行时间如下:

表2 实验2执行时间对照表Table 2 experimental2execution time table

遗传算法的产生序列:

24，9，7，2，26，1，8，13，3，18，10，0，23，5，17，14，4，15，12，6，16，20，11，22，25，19，21.

基本人工蜂群算法产生序列:

10，25，15，18，14，4，19，8，5，3，23，6，1，20，16，17，12，2，21，11，22，7，26，13，24，0，8

本文算法的产生序列:

0，5，1 5，9，23，4，19，8，7，3，26，6，1，14，16，2，12，11，21，17，22，25，18，13，24，10，20

实验3:实验设有12个工作点，30个任务，对比算法为遗传算法，执行时间如下:

表3 实验3执行时间对照表Table 3 experimental3execution time table

遗传算法的产生序列:

28，24，20，25，10，7，17，4，9，22，6，11，14，18，0，29，15，13，26，12，1，19，21，5，3，27，2，29，16，8.

基本人工蜂群算法产生序列:

22，25，4，16，19，1，21，26，2，24，29，23，6，15，12，7，13，8，14，10，9，28，18，5，3，27，11，20，0，17

本文算法的产生序列:

0，5，1 9，16，24，1，21，9，2，4，29，3，6，15，17，7，13，8，23，10，26，28，18，14，25，27，11，20，12，22.

从表1、表2、表3很容易得出结论，本文改进的人工蜂群算法比遗传算法执行时间较少，从后选解产生的序列易知，搜索到的解相同，只是顺序不同。

5 结论

本文分析了人工蜂群算法的运行原理，在传统的人工蜂群算法的雇用蜂阶段后和跟随蜂阶段后插入了遗传算法的变异和杂交操作。在满足条件时，按一定的概率用变异操作选择食物源。实验在某企业的环境下以工作调度问题为目标进行的。在没有设置特别的变异概率的情况下，得到了最佳工作调度序列。

［1］ 毕晓君，王艳娇.加速收敛的人工蜂群算法［J］.计算机与数字工程.2011，33(12):76-79

［2］ 李小平，郑世杰.基于遗传算法和拓扑优化的结构多孔洞损伤识别［J］.振动与冲击，2011，32(1):88-93

［3］ 龙 泓，向 勇.P2P工作流系统的调度框架设计和实现［J］.计算机工程与设计，2012，33(1):54-67

［4］ 高卫峰，刘三阳.混合人工蜂群算法［J］.系统工程与电子技术，2011，33(5):84-86

［5］ 陈 亮.基于混合蛙跳算法的背包问题求解算法［J］.河南城建学院学报，2011，20(3):41-44

［6］ Lei D.Simplified multi-objective genetic algorithms for stochastic job shop scheduling.Appl.Soft Comput.2011，doi:10.1016/j.asoc.2011.06.001.