基于转轴法的导向人工蜂群算法

尹雅丽，　熊小峰，　郭肇禄

（江西理工大学理学院，江西赣州341000）

基于转轴法的导向人工蜂群算法

尹雅丽，熊小峰，郭肇禄

（江西理工大学理学院，江西赣州341000）

针对人工蜂群算法在求解复杂多峰问题时容易出现收敛速度慢、开采能力不足的问题，提出了基于转轴法的导向人工蜂群算法（RDABC）.在RDABC算法的搜索过程中，利用方向引导信息来指导个体朝更优方向搜索，并对当前最优解执行转轴法局部搜索，以加快收敛速度.在8个标准测试函数上进行了比较实验，实验结果表明RDABC算法的求解精度更高，收敛速度更快.

人工蜂群算法；方向引导信息；转轴法；局部搜索

0　引言

人工蜂群算法［1］（artificial bee colony，ABC）是土耳其学者Karaboga于2005年提出的一种群智能算法，它通过模拟蜜蜂觅食过程中的智能寻优机制来寻找最优解.自ABC算法提出以来，许多研究人员对其进行了研究，并将其与PSO、ED、PS-EA、EA、GA等演化算法进行了比较，实验结果表明ABC算法具有较好的全局寻优能力，是求解高维、多峰问题的一种有效方法［2-3］.由于ABC算法具有操作简单、易于实现、控制参数少、搜索精度高、鲁棒性较强等优点［4-5］，这使得ABC及其改进算法被不断应用于各种优化问题中，如：Xu等［6］为了避免算法“早熟”和收敛速度慢等问题，将混沌机制引入ABC中用于求解无人作战机的路径规划问题；Dos等［7］为了提高算法的开采能力和收敛速度，在ABC算法的雇佣蜂和观察蜂阶段采用高斯分布的随机数代替均匀分布随机数，用于求解螺线管的基准问题；王慧颖等［8］利用全局最优解和个体极值信息提高算法的局部搜索能力以平衡算法的勘探和开采能力，并提高了解的精度；Akay等［9］将其用于计算最大类间方差和熵从而求解多阈值分割问题，提高了求解精度；周文越等［10］在ABC中引入禁忌搜索提高算法搜索效率用于计算环网断点集；Pan等［11］将离散机制引入至ABC的种群表达和更新操作中用于求解批量流水线调度问题，并且在雇佣蜂阶段采用了最优解邻域值替换较差个体的机制，较好的平衡了算法的勘探和开采能力；阮羚［12］等通过对每次迭代中的最优解进行混沌算子处理形成混沌池，提高算法的局部搜索能力的同时不限制其搜索的全局性，减小“早熟”收敛的可能性用于土壤分层电阻率计算；Mansouri［13］将求解区间不断进行二等分缩小的方法引入至ABC中用于求解非线性函数的不动点，提高了解的精度.

在工程实践中发现，与许多演化算法类似［14-15］，ABC也存在着一定的局限性.如求解单峰问题时，观察蜂阶段只进行单一维度更新，导致进化后期收敛速度慢；求解多峰问题时，进化过程中种群相似度过高，导致算法容易出现“早熟”、易陷入局部最优；求解精度要求较高的工程问题时，求解精度达不到要求等.针对标准ABC算法在求解复杂多峰问题时容易出现收敛速度慢、开采能力不足、求解精度不高的问题，提出了一种基于转轴法的导向人工蜂群算法（RDABC），该算法在进化过程中引入了方向引导信息用于指导个体维度上的数值朝着更优方向进行更新，扩大搜索范围的同时提高算法收敛速度，并在进化过程中针对最优解使用转轴法进行局部搜索，提高求解精度.

1　ABC算法

ABC算法通过模拟蜜蜂采蜜过程中的智能机制处理函数优化问题，其将蜂群划分为雇佣蜂、观察蜂、侦查蜂三类进行进化，且雇佣蜂、观察蜂、蜜源数目相等，蜜源质量即对应优化问题的适应度值［1］.

在算法的初始阶段，通过式（1）产生含SN个个体的初始蜜源，得到初始种群［1］：

其中i=1，…，SN，j=1，…，D，每个个体表示为Xi=（xi1，xi2，…，xiD）.xminj、xmaxj分别表示个体在第j维上的下界和上界，rand∈［0，1］为0～1之间服从均匀分布的随机数.

产生初始种群后，通过式（2）计算蜜源的质量［1］：其中fiti为蜜源的适应值，适应值越大表示该蜜源质量越优，fi为蜜源i的目标函数值.

在演化过程中，ABC通过依次执行雇佣蜂操作、观察蜂操作、侦查蜂操作来使得种群不断向最优解逼近，各操作过程叙述如下.

1.1雇佣蜂操作

在雇佣蜂操作过程中，雇佣蜂根据式（3）对每个蜜源进行一次邻域搜索，产生新蜜源Vi=（vi1，vi2，…，viD）［1］：

其中φij∈［-1，1］，k∈ ｛1，…，SN｝，j∈｛1，…，D｝为随机数，在每次邻域搜索过程中随机更新一个维度上的数值，然后计算新蜜源Vi的质量，当新蜜源Vi优于蜜源Xi时，则蜜源Xi由Vi替代.

1.2观察蜂操作

雇佣蜂操作执行结束后，ABC算法开始执行观察蜂操作.在观察蜂操作中，雇佣蜂先将蜜源信息共享给观察蜂，然后观察蜂根据蜜源质量，按贪婪法选择蜜源进行开采，每个蜜源的选择概率计算方式如下［1］：

Pi表示蜜源i的选择概率，当蜜源被选中之后，观察蜂将按式（3）对所选中的蜜源进行邻域搜索.

1.3侦查蜂操作

在侦查蜂操作过程中，挑选出未被更新次数最大的蜜源，当这些蜜源未被更新的次数大于事先给定的限制次数“limit”时，这些蜜源将按式（1）重新随机产生.

2　基于转轴法的导向ABC算法（RDABC）

标准ABC算法在求解复杂多峰问题时，在个体更新过程中采用随机的方式对某一维度上的数值进行更新，这种机制使得算法在进化后期收敛速度慢.针对这种不足，引入方向引导信息（Directed information）来指导个体朝着更优的方向搜索，从而提高算法的收敛速度.为了提高算法的开采能力，融合改进的转轴法来进行局部搜索，不仅能提高算法的收敛速度，也使得求解精度得以提高.

2.1RDABC的操作算子

基本ABC在求解复杂多峰问题时，在雇佣蜂和观察蜂阶段中，对每个个体的任一维度进行更新，维度的选取通过随机的方式产生，当更新得到的个体优于原个体时，新个体将取代原个体，但这种随机选择更新的机制未记录该个体上此维度的更新方向，即在下次迭代中，若此个体的同一维度被再次选中进行更新时，其更新方向的随机性可能使个体更靠近最优解，也可能使其偏离最优解，这种随机性降低了算法的收敛速度.方向信息指导策略［16］能有效指导个体朝着更优的方向搜索，因此在RDABC中引入方向信息能有效地提高算法的收敛速度.方向信息指导策略为：针对第i个个体在第j维的方向信息设置为diij，其取值为0，1或-1，即个体将朝着三个可能的方向进行更新，但最终个体只选择更具优势的方向进行更新.RDABC在雇佣蜂和观察蜂操作过程中根据方向信息按式（5）进行邻域搜索［16］：

其中diij表示蜜源i在第 j维上的方向信息，φij∈［-1，1］、rij∈［0，1］为随机数，在更新初始阶段设置diij=0，当更新得到的解不优于原解时置diij=0；当更新得到的解优于原解时，若更新解在j维上的值比原解在j维上的值大则置diij=-1，否则置diij=1.

虽然利用了方向指导策略来加速ABC算法的收敛速度，但在求解一些复杂工程优化问题时，ABC算法容易出现勘探和开采搜索能力不平衡的问题.为了进一步提高其开采能力，利用改进的转轴法（RM）［17］来进行局部搜索是一种提高算法开采能力的有效方法.在改进的RM［17］中，采用了一种基于等级的适应值计算方法，并限制指定方向上个体的更新次数，同时要求每个方向上的更新效果达到一定的精度，随着更新次数的增加，最小步长δmin的限制条件也作出动态调整.改进的RM算法流程如下所示：

step1.输入初始点x0，初始搜索方向d，初始更新步长δj，步长调整因子α，β，终止条件a，nl，ε1，ε2，方向更新次数k=0，外部更新次数k2=0

step 2.while k2＜2nlandδmin≥1.0e-（a+nRM）do

step 3.置x=xk，k1=0，z=x

step 4.while k1＜nldo

step 5.for j=1 to Ddo

step 6.y=x+δjdj

step 7.if y优于x then set，x=y，δj=αδj；else

δj=βδj

step 8.end for

step10.k1=k1+1

step11.end while

step12.if f（x）＜f（xk）andδmin≥1.0e-（a+nRM） then set k=k+1，xk=x，更新搜索方向d

step13.end while

其中δ1，δ2，…，δD为每个维度上的搜索步长，a为常数，nRM表示调用RM的次数.

2.2RDABC的总体框架

RDABC算法在ABC的雇佣蜂和观察蜂阶段中引入方向指导策略，通过对每个个体的每个维度都设置一个方向信息来指导个体朝着更具优势的方向进行搜索，为了提高算法的开采能力，针对最优个体引入了转轴法（RM）用于局部搜索.转轴法，是求解最优值处于狭小、弯曲的“山谷”内的一种有效方法，其通过在某一方向上进行步长调整来指导个体在此方向上向最优解靠近，当此方向无法使个体得到改进时，则重新调整方向并以当前获得的最优个体作为初始点继续通过调整步长的方式进行个体更新，这种搜索方法可以使个体快速向最优解逼近［18］.引入方向信息和RM局部搜索的RDABC算法在提高收敛速度的同时提高算法的求解精度和开采能力，其算法流程如下所示：

step 1.初始化种群Xi，i=1，…，NS，iter=1

step 2.计算各个体的函数值及适应值，并保存最优个体xbest.

step 3.计算改进RM中的初始步长δj

step 4.将xbest作为改进RM的初始点调用RM，获得最优个体x′best

step 5.if f（x′best）＜f（xbest）then用x′best替换种群中间位置的个体，xbest=x′best.

step 6.while终止条件不满足时do

step 7.雇佣蜂阶段：按式（5）对蜜源进行更新、计算函数值和适应值

step 8.按式（4）计算选择概率Pi

step 9.观察蜂阶段：按贪婪选择机制选择蜜源并按式（5）进行更新

step10.侦查蜂阶段：对于要丢弃的蜜源，按式（1）重新产生

step11.保存当前最优个体xbest

step12.if m od（iter，nc）==0 then

step13.计算步长δj，并将xbest作为初始点调用改进RM

step14.if f（x′best）＜f（xbest）then用 x′best替换种群中间位置的个体，xbest=x′best.

step15.iter=iter+1

step16.end while

其中nc为常数，一般设置为nc=k×D［16］.

3　实验

为了验证RDABC算法的有效性，采用函数优化领域中被广泛采用的8个标准测试函数［19］进行了实验.实验在 Pentium（R）Dual-Core CPU: E5400、4 GB内存、2.70 GHz主频的计算机上实现，程序采用Matlab7.10.0语言实现.

3.1实验设置

实验中采用的8个标准测试函数［19］的定义和取值范围如表1所示，8个测试函数的理论最优值都是0，其中函数F1～F3为单峰函数，F4～F5为多峰函数.

表1　标准测试函数表

为了公平地比较各算法的性能，实验公共参数都作如下统一设定：问题的维度为D=40，种群规模为NS=40，最大评价次数为max Cyeld=1000，控制参数limit=NS×D.其中改进的RM部分的参数作如下设置［17］：内部控制参数，nl=15；a=20终止参数ε1= 1.0e-150，ε2=1.0e-4；进行局部搜索的控制参数nc= 5×D.为了分析RDABC的性能，将RDABC与标准ABC、dABC［16］和RABC［17］算法进行比较分析，其中dABC算法在ABC的雇佣蜂和观察蜂阶段引入了方向引导机制，是最近提出的一种改进算法，比很多其他的改进算法表现更优，RABC算法在ABC的基础上针对当前最优个体引入了RM局部搜索策略.

3.2实验结果与分析

Best，Worst，Mean和Std分别为算法独立实验30次的最好值、最差值、平均值和标准差.Best和Worst反映了解的质量；Mean显示了在给定函数评价次数下算法所能达到的精度，反映了算法的收敛速度；Std反映了算法的稳定性.结果如表2所示，每个函数的最优结果标记为黑体.

从表 2中可以看出，RDABC算法在求解Sphere、SumSquare、Zakharov及Griewank函数时，比标准ABC算法的求解质量提高了1.0e-26至1.0e-41，求解精度提高了1.0e-27至1.0e-40；相比于dABC算法，解的质量提高了1.0e-26至1.0e-37，解的精度提高了1.0e-27至1.0e-34.求解复杂的多峰函数Ackley和Bohachevsky时，RDABC相比于标准ABC算法，解的质量提高了1.0e-8至1.0e-10，解的精度提高了1.0e-9至1.0e-10，且在Bohachevsky上获得了理论最优值；相比于dABC算法，解的质量提高了1.0e-6至1.0e-7，精度提高了1.0e-7.RDABC相比于RABC算法，在最好值上针对所有的函数都取得了优于或等于RABC的结果，对于Sphere、SumSquare、Rastrigin、Griewank、Bohachevsky函数，RDABC比RABC在解的精度提高了1.0e-1至1.0e-7，说明相比标准ABC、dABC、RABC，RDABC的收敛速度得到了提高.在反应算法的稳定性的方差指标上，除函数Zakharov和NCRastrigin外 ，RDABC算 法 在 求 解 Sphere、SumSquare、Griewank时，相比标准ABC算法提高了1.0e-32至 1.0e-40；相比dABC算法提高了1.0e-26至1.0e-34，相比RABC提高了1.0e-1至1.0e-7.在求解函数Rastrigin、Ackley、Bohachevsky时，相比标准ABC算法提高了1.0e-1至1.0e-10；相比dABC算法提高了 1.0e-1至1.0e-7，相比RABC提高了1.0e-1至1.0e-3，说明在这些函数上RDABC表现出了优于上述3种算法的稳定性.

实验结果表明，针对这些测试函数，RDABC的性能在多数函数上要优于ABC、dABC、RABC算法，解的质量和精度得到进一步的提高，求解结果也更接近理论最优值.特别是30次独立运行后反应结果的精度的均值普遍要比RABC的结果均值更优，优化最高数量级为1.0e-7，说明RDABC算法在这些优化问题的求解过程中很好的结合了方向引导信息策略和RM局部搜索方法，增强了RDABC算法的寻优能力.

表2　算法最优、最差、均值、方差实验结果表

表3　显著性水平的t检验表

为了从统计学意义上分析RDABC算法的有效性，对其进行显著性水平为p=0.05的t—检验，检验结果如表3所示.

从表3可知，RDABC算法在6个函数上显著优于ABC算法和dABC算法，在5个函数上显著优于RABC算法.从统计意义上表明了，RDABC算法更好的结合了方向指导信息和RM局部搜索策略，使得其在绝大多数测试函数上的求解精度更高，性能更优.

4　结论

针对标准ABC算法在求解复杂多峰问题时容易出现收敛速度慢、开采能力不足、求解精度低的缺点，提出一种改进的RDABC算法用于数值优化问题.由于RDABC算法在雇佣蜂和观察蜂阶段引入方向指导策略，使得个体维度上的数值朝着更优的方向进行搜索.针对当前最优个体进行了转轴法局部搜索，使得当前最优个体能快速而有效的得到优化更新，同时为了避免局部搜索过程可能使算法陷入局部最优，进行了有选择性的调用RM局部搜索，这些改进使得RDABC算法相比ABC、dABC、RABC算法具有更高的求解精度，更快的收敛速度.初始种群的多样性及雇佣蜂和观察蜂阶段的选择策略对算法的性能也有一定的影响，进一步的研究可以从这两个方面开展，从而使得算法性能更优，能更好的用于工程优化问题.

［1］Karaboga D.An idea based on honey bee swarm for numerical optimization［R］.Kayseri:Erciyes University，2005.

［2］Dervis Karaboga，Bahriye Basturk.Apowerful and efficient algorithm for numerical function optimization:artificial bee colony（ABC）algorithm ［J］.Journal of Global Optimization，2007，39（3）: 459-471.

［3］Karaboga D，Basturk B.On the performance of artificial bee colony（ABC）algorithm［J］.Applied Soft Computing，2008，8（1）:687-697.

［4］秦全德，程适，李丽，等.人工蜂群算法研究综述［J］.智能系统学报，2014，9（2）:127-135.

［5］陈阿慧，李艳娟，郭继峰.人工蜂群算法综述［J］.智能计算机与应用，2014（6）:20-24.

［6］Xu C，Duan H，Liu F.Chaotic artificial bee colony approach to Uninhabited Combat Air Vehicle（UCAV）path planning［J］. Aerospace Science&Technology，2010，14（8）:535-541.

［7］Coelho L D S，Alotto P.Gaussian artificial bee colony algorithm approach applied to Loney’s solenoid benchmark problem［J］. Magnetics，IEEE Transactions on，2011，47（5）:1326-1329.

［8］王慧颖，刘建军，王全洲.改进的人工蜂群算法在函数优化问题中的应用［J］.计算机工程与应用，2012，48（19）:36-39.

［9］Akay B.A study on particle swarm optimization and artificial bee colony algorithms for multilevel thresholding［J］.Applied Soft Computing，2013，13（6）:3066-3091.

［10］周文越，吕飞鹏，廖小君.基于人工蜂群算法的环网方向保护配合最小断点集计算［J］.电力系统保护与控制，2013（6）:77-81.

［11］Pan Q K，Wang L，Li JQ，et al.A novel discrete artificial bee colony algorithm for the hybrid flowshop scheduling problem with makespanminimisation［J］.Omega，2014，45（2）:42-56.

［12］阮羚，徐碧川，全江涛，等.用于土壤分层电阻率模型反演的人工蜂群结合混沌搜索算子及混沌算法 ［J］.高电压技术，2015，41（1）:42-48.

［13］Mansouri P，Asady B，Gupta N.The Bisection-Artificial Bee Colony algorithm to solve fixed point problems［J］.AppliedSoft Computing，2015（26）:143-148.

［14］郭肇禄，吴志健，汪靖，等.一种基于精英云变异的差分演化算法［J］.武汉大学学报（理学版），2013，59（2）:117-122.

［15］郭肇禄，吴志健，董晓健，等.一种基于分量热力学迁移策略的并行多种群 GEP［J］.四川大学学报（工程科学版），2012，44（2）: 83-90.

［16］K I ran M S，FIndIk O.A directed artificial bee colony algorithm［J］. Applied Soft Computing，2015，26:454-462.

［17］Kang F，Li J，Ma Z.Rosenbrock artificial bee colony algorithm for accurateglobal optimizationof numerical functions［J］. Information Sciences，2011，181（16）:3508-3531.

［18］陈宝林.最优化理论与算法［M］.2版.北京：清华大学出版社，2005.

［19］Yao X，Liu Y，Lin G.Evolutionary programming made faster［J］. IEEE Transactions on Evolutionary Computation，1999，3（2）:82-102.

Rosenbrock artificial bee colony algorithm with directed information

YIN Yali，XIONG Xiaofeng，GUO Zhaolu

（Faculty of Science，Jiangxi University of Science and Technology，Ganzhou 341000，China）

Artificial bee colony（ABC）algorithm has slow convergence for complexmultimodal problems，and is good at exploration but poor at exploitation.The study proposes animprovedABCalgorithmcalled Rosenbrock-directed ABC（RDABC）by adding the Rosenbrock's rotational direction method for the local search tool and directional information to ABC.The performance of the proposed approach was examined on well-known eight benchmark functions.The experimental results show that the proposed approach is more effective andmore successful in terms of solution quality，and convergence to global optimum.

artificial bee colony algorithm；directional information；Rosenbrockmethod；local search technique

TP391

A

2095-3046（2015）05-0098-06

10.13265/j.cnki.jxlgdxxb.2015.05.017

2015-04-30

国家自然科学基金项目（11401267，11461032）

尹雅丽（1989-），女，硕士研究生，主要从事建模与优化算法应用等方面的研究，E-mail:1071712763@qq.com.

熊小峰（1965-），男，教授，主要从事建模与应用数理统计等方面的研究，E-mail:xxf_gz@163.com.