改进人工蜂群算法在路径优化上的应用*

张平华，贾万祥，徐 静，胡 俊

(1.安徽新华学院；2.万博科技职业学院)

0 引言

旅行商问题是一个典型的NP-Hard问题.由于经典算法在解决较大规模的组合或高度非线性优化问题的效率低下.近年来，许多解决旅行商的元启发式的算法被提出来，主要有神经网络 (Neural Network)、模拟退火 (Simulated Annealing，SA)、遗传算法 (Genetic Algorithms，GA)、蚁群优化算法 (Ant Colony Optimization，ACO)、粒子群优化算法(Particle Swarm Optimization，PSO)，人工蜂群算法[1](ABC，Artificial Bee Colony Algorithm)算法等一系列群体智能算法.蜂群算法是一种相对较新的群智能算法，模拟自然界蜜蜂的采蜜行为.蜜蜂使用摇摆舞定位最佳食物来源，并寻找新的食物源.基于觅食的蜂群算法利用蜜蜂寻找最优解的正反馈机理具有收敛性强、鲁棒性强等优点，将蜂群算法建立应用模型运用在路径优化问题上，提供了一种新的思路，具有一定的研究意义.

1 基本人工蜂群算法

土耳其Erciyes大学的karaboga教授于2005年在文献[1]中提出了一种新型的群智能优化算法——人工蜂群算法.算法包括雇佣蜂、非雇佣蜂和食物源三个基本要素[2].

雇佣蜂：也被称为引领蜂，储存着食物源的相关信息，并在采蜜后回到蜂巢中通过摇摆舞的形式蜜源的信息，其数量与食物源的数量相等.

非雇佣蜂：有跟随蜂与侦察蜂两种.跟随蜂在观察引领蜂的舞蹈后按轮盘赌法选择是否跟随.

食物源：蜜蜂的搜索目标，在算法中，蜜源的质量与收益度成正比；侦察蜂主要是发掘新的蜜源，使算法跳出局部最优.

算法流程描述:

初始化阶段：算法按(1)式随机初始化SN/2个D维的可行解xi(xi1,xi2,…,xiD)T，(i=1,2,……，SN)，SN代表了蜜蜂数量.

(1)

引领蜂阶段：引领蜂根据(4)式在邻域中搜索食物源，并进行位置更新寻找新的食物源，记录食物源信息.引领蜂采用贪婪算法或轮盘赌算法确定食物源，并依据(2)式计算初始适应度值,选择适应度较优的解，并按(3)式计算跟随概率(Pj).

(2)

(3)

其中，f(x)为待优化的函数，fitness(xi)为函数的适应度值，Pi选择概率，适应度越高的食物源被选择的概率越大.

跟随蜂阶段：跟随蜂根据引领蜂传达的食物源信息，依照轮盘赌方式选择食物源，利用(4)式在邻域范围内搜索蜜源，并计算适应度值，依据(3)式的贪婪选择机制计算跟随概率，选择最优蜜源.

vij=xij+Rij(xij-xkj)

(4)

其中，k∈{1,2,…,SN}，j∈{1,2,…,SN} 都是随机选择的，并且k≠j，Rij∈[0,1]随机数.

侦察蜂阶段：若食物源经过limit次搜索后，没有得到改善，并且非当前最优，表明此时可能陷入局部最优，则该食物源将被引领蜂放弃，相应采蜜蜂并转变为侦查蜂.侦察蜂在其领域范围内依据(1)式随机地产生一个新的蜜源，从而防止算法陷入局部最优，加快算法的收敛速度和求解精度[3].

2 改进的人工蜂群算法在路径优化上的应用

2.1 TSP问题的描述

2.2 改进的蜂群算法求解TSP 问题

2.2.1 算法改进

由于蜂群的位置更新采用的事随机函数，基本的人工蜂群算法易陷入局部最优，收敛速度也受限.故文中在算法的位置更新阶段引入了高斯分布和柯西分布，其函数图像如图1所示.

图1 高斯和柯西概率分布图

高斯分布，又叫正态分布，由德国的数学家和天文学家Moivre于1733年首次提出，由德国数学家Gauss率先将其应用于天文学研究，其概率密度函数如(5)式所示.

(5)

其中，μ为期望值决定分布的位置，σ为标准差决定了分布的幅度.当μ=0,σ=1时，称标准正态分布.

由文献[4]可知，高斯变异的局部搜索能力很强，而柯西变异算子全局搜索能力很强，也能保持种群的多样性.雇佣蜜蜂在搜索食物源时，食物源的质量越好，跟随概率越高，故在雇佣蜂阶段引入高斯变异算子，以加算法的收敛速度；为了增加可行解的多样性，在侦察蜂引入柯西变算子，避免算法陷入局部最优解.

将高斯变异算法子(Gaussian mutation operator)引入到雇佣蜂阶段的位置更新式中后，(4)式改进为(6)式，可以加快算法的收敛速度.

vij=xij+xij×Nij(0,1)+Rij(xij-xkj)

(6)

由图1可知柯西分布较高斯分布窄，采用服从柯西分布的随机数进行变异会产生较大的变异步长，有利于算法跳出局部最优解，增强全局搜索能力.故将柯西变异算子(Cauchy mutation operator，如(7)(8)式所示)引入到侦察蜂阶段，侦察蜂按(9)式进行随机选择一个新的食物源，这既可以增强算法的全局搜索能力，也可以保持种群的多样性.

(7)

其中，x0是分布峰值的位置，γ是最大值一半处的一半宽度的尺度参数.当x0=0,γ=1时，称为标准柯西分布，(7)式即变为柯西变异算子，如(8)式所示.

(8)

(9)

2.2.2 算法流程描述

step1:初始化算法参数:蜂群规模SN、最大代数次数MCN、放弃参数Limit；

step2:按(1)式随机生成种群的初始解，计算每个解的适应度值，置t=1(当前迭代次数)；

step3:采蜜蜂进行目标搜索，根据 (6) 式产生新的食物源，并计算其适应度fitness(xi)，按照贪婪机制进行选择；

step4:根据 (2) 式和 (3) 式计算蜜源的选择概率P；

step5:跟随蜂按照贪婪机制选择食物源(解)，并根据式(6)产生新的食物源，并计算其适应度;

step6:判断Limit次数，若食物源经Limit次后仍没有改进，则放弃，并由侦察蜂依(9)式产生一个新解代替当前解；

step7:记录当前最优解，算法迭代次数t=t+1；

step8:若t

2.3 TSP求解仿真分析

TSP问题和可行解优化问题对应的关系见表1.

表1 人工蜂群算法与 TSP 问题对应的关系

该次实验首先选用Burma14的14个城市[5](坐标见表2)进行算法的可行性验证，14个城市的优化前和优化后的路径如图2和图3所示，其最优路径为1 2 14 3 4 5 6 12 7 13 8 11 9 10 1,此条路径的长度是:30.8785.然后，再采用文献[6]提供7个标准的TSPLIB库中的地图数据进行优化仿真，并与基本人工蜂群算法进行比较，以验证改进后算法的鲁棒性和可靠性.仿真实验的算法参数：初始化蜜蜂总数(NP=20)，采蜜蜂数量(FoodNumber=NP/2)，最大搜索次数(Limit=100)，最大迭代次数(maxCycle=2500).对上述参数采取独立运行10次，取其平均值作为最优结果.

表2 Burma14的14个城市的坐标

图2 初始(优化前)路径 图3 优化后路径

表3 7个标准地图优化结果比较

注：上表中的误差采用(10)式计算，所用时间比采用(11)式计算.

(10)

(11)

由表3可以明显地看出，改进后的算法在求解精度和误差以及在运算时间上都比基本的人工蜂群算法要优.当地图上的城市规模扩大时，基本人工蜂群算法的各方面的性能都下降很大，改进后算法的下降程度比基本算法要平缓很多.

经过大量的实现证实，改进后的人工蜂群算法提高了算法的全局搜索能力，可以有效地防止算法陷入局部最优，在相同样的参数设置下可以在更短的时间内得到更优解，因此，改进的人工蜂群算法优于基本人工蜂群算法.

3 结束语

随着问题的计算复杂程度和规模不断地扩大，基本人工蜂群算法全局搜索能力不强，不能有效地保持种群的多样性，易陷入局部最优解，影响求解效果.该文采用了高斯变异和柯西变异分别在雇佣蜂阶段和侦察蜂阶段加入了扰动因子，通过TSP问题证实改进后的算法各方面性能更佳.由于时间和篇幅原因算法的收敛性[7]和复杂度有待进一步证明.