自适应随机优化策略的改进人工蜂群算法

刘 鑫,杨霄鹏,姚 昆,苏子萱,张衡阳

1(空军工程大学 信息与导航学院,西安 710077) 2(中国人民解放军 94042部队，陕西 咸阳 713800)

1 引 言

随着科学技术的进步,最优化问题被广泛运用到数学规划、计算机技术以及工程实践中.通过对生物群体行为进行仿真和建模,并以此解决最优化问题已成为当前一个热门研究领域[1].其中在该领域中较为成熟是Dorgo等人提出的蚁群算法(Ant Colony Optimization,ACO)[2]和Kennedy等人提出的粒子群算法(Particle Swarm Optimization,PSO)[3].

近年来,由Karaboga提出的人工蜂群算法(Artificial Bee Colony,ABC)作为一种新的随机型搜索方法已成功应用于函数的优化问题[4].该算法主要通过模拟蜂群中不同类型的蜜蜂,根据其各自分工不同进行智能采蜜,同时在不同种群之间交换蜜源信息直到找到最优蜜源.文献[5]和[6]通过五个基本函数对ABC算法的性能进行了验证分析,实验结果表明ABC算法与遗传算法(Genetic Algorithm,GA)、粒子群算法(Particle Swarm Optimization,PSO)以及差分进化算法(Differential Evolutionary,DE)一样具有良好的优化能力.但是,实验中也暴露了ABC算法存在收敛速度慢和容易陷入“早熟”的不足.针对这一问题,文献[1]通过将ABC算法与DE算法算法相结合,并在迭代中引入淘汰规则的方法克服了ABC算法的“早熟”现象;文献[7]运用Nelder-Mean法使ABC算法的局部搜索能力得到了改进,并将其应用在混凝土重力坝动力材料参数识别问题,在建立基于不完全模态测试数据动力材料参数识别优化反演模型中取得了较好的效果.文献[8,9]在ABC算法中加入混沌思想,利用混沌运动的随机性、遍历性等特点提高了算法的全局搜索能力.

为提高ABC算法的收敛速度以及解决在算法后期容易陷入局部最优解的问题,本文在重点参考文献[1]及文献[10,11]的基础上,提出了一种基于自适应随机优化策略的改进算法,通过利用自适应思想与双向随机优化机制以期改善算法的局部搜索能力,同时将粒子群算法引入到改进算法的初始阶段以期提高算法的收敛速度.

2 人工蜂群算法原理

人工蜂群算法是基于蜂群迭代来完成寻优过程的一种随机搜索算法[4].在ABC算法中,人工蜂群根据各自分工可分为采蜜蜂、观察蜂和侦查蜂三种类型.通常采蜜蜂和观察蜂各占蜂群总数的一半,每一个采蜜蜂仅对应一个蜜源工作,且蜜源Xi为Q维向量.算法初始化时首先随机生成M个初始解,之后进行对最优解的搜索,其具体搜索过程如下:1)采蜜蜂对蜜源进行搜索并记忆蜜源的花蜜量,即问题解的质量(适应度);2)采蜜蜂将蜜源信息传递给观察蜂,观察蜂根据获得的蜜源信息通过判断收益率对蜜源进行选择,进而改变记忆位置;3)当蜜源因蜂蜜开采完而被放弃时,产生侦查蜂并且由其搜索新的蜜源来替代旧蜜源.

在算法中,为了根据记忆位置Xi产生一个候选位置Vi,采用下式进行更新:

(1)

(2)

其中S为蜜源总数,Xi为第i个蜜源,fit(Xi)表示蜜源Xi的适应度值,i∈P{1,2,…,S}.

假设采蜜蜂和观察蜂经过limit次循环搜索更新之后仍不能改进蜜源Xi的适应度,那么该该位置的采蜜蜂成为侦查蜂,同时蜜源Xi的位置将被改变.limit作为搜索次数,是ABC算法中一个非常重要的控制参数,用来控制侦查蜂的选择.侦查蜂发现新位置并对Xi进行替换的操作如下:

(3)

其中n为Q维向量的某个分量.

由于ABC算法中蜜源Xi的位置无法随着算法的进行而发生改变,而是当解的质量无法得到优化时经过limit次循环搜索之后才能对个别蜜源位置进行更新,存在算法效率低和收敛速度慢的缺陷.此外,算法依靠不同类型蜜蜂之间的交流合作来进行寻优,并且蜜蜂担任的角色只有在特定的条件下才会发生转变.假如其中任意一种类型的蜜蜂的活动受到限制,使其角色发生转变的条件将无法满足,进而造成算法陷入局部最优解.因此,针对人工蜂群算法存在的以上两点缺陷对其进行改进.

3 改进人工蜂群算法

为提高ABC算法的收敛速度以及解决在算法后期容易陷入局部最优解的问题,在上述人工蜂群算法原理的基础上,提出了一种基于自适应随机优化策略的人工蜂群改进算法.该策略将加权粒子群算法与ABC算法进行融合,利用自适应思想及双向随机优化机制对算法的收敛速度和局部搜索能力加以改善,以期提高该算法的寻优性能.

3.1 粒子群算法

Kennedy和Eberhart[10]在1995年提出了基本的粒子群算法后,Yuhui Shi和Eberhart[11]在基本粒子群算法的基础上添加了一个惯性因子w,式(4)和式(5)就是标准PSO算法的更新公式.

(4)

(5)

其中v表示粒子的速度,x表示粒子的位置,i表示第i个粒子,w表示惯性因子,c1和c2都是正的加速因子,而r1,r2都是[0,1]之间均匀分布的随机数,Pi表示单个粒子在历史上已经寻到的最优位置,Pg表示整个种群所已寻到的最优位置,t表示第t次迭代.

文献[11]中提出的粒子群算法的具体寻优过程的基本流程如下:

Step1.对粒子群进行初始化,完成对m个粒子的初始位置和初始速度的随机设定,并计算出所有m个粒子的适应度值;

Step2.对每个粒子,将它的当前位置的适应度值和它经历过的最好位置Pi的适应度值Pibest进行比较,如果当前位置比Pibest好,更新Pi和Pibest,否则保持Pibest不变;

Step3.将每个粒子当前位置的适应度值与群体中所有粒子经历过的最好位置Pg的适应度值Pgbest进行比较,如果当前位置比Pgbest好,更新Pg和Pgbest,否则保持Pgbest不变;

Step4.根据式(4)和式(5)调整粒子的速度和位置;

Step5.如果达到结束条件,则结束;否则转到Step 2.

3.2 自适应随机优化策略

3.2.1 自适应蜂群位置更新公式

在利用公式(1)进行蜜源Xi位置更新时,φij的取值越大越有利于算法跳出局部极小值点,同理,φij的取值越小算法的收敛速度越快[12].在全局搜索过程中,通过在算法的初期取较大的φij值以提高算法的探索能力,进而得到较优的蜜源,使其搜索精度得到提高;而在算法后期取较小的φij值,在提高算法的局部搜索能力的同时使其收敛速度加快.因此将φij设计为迭代次数的函数,且取值随着迭代次数的增加逐渐减小,将φij定义如下:

(6)

其中,k的含义与公式(1)相同,wmax为初始权重、wmin为终止权重,Cmax为最大迭代次数,C为当前迭代次数.则公式(1)重新定义为

(7)

由此可以达到引导蜜源位置的搜索趋势的目的,并针对算法本身随机性强、收敛速度慢的缺陷进行了改进.

3.2.2 双向随机优化机制

在ABC算法计算蜜源的适应度值时,观察蜂在对Xi周围的蜜源进行比较之后后选择其中一个蜜源,选择的临近蜜源位置的计算公式如下:

Xi(C+1)=Xi(C)+Δi(C)

(8)

其中Δi(C)是Xi附近随机产生的递进步长,C表示当前的迭代次数,若经过适应度值计算后得到fit(Xi(C+1))>fit(Xi(C)),则观察蜂选择Xi(C+1);否则维持不变.若在限定循环次数后蜜源质量仍没有提高,则放弃该位置,采蜜蜂根据式(3)变成侦查蜂.

采用上述方法存在一定的缺陷,即每次循环仅对单一方向的蜜源进行搜索,观察蜂的活动仅在邻域内的一个方向上进行,同时也使其他类型蜜蜂的活动受到了限制,无法达到使角色发生转变的条件,因此容易陷入局部最优解的情况.文献[13]在研究动态网络环境下搜索命中率及搜索成功率的过程中提出了一种双向随机漫步搜索机制,有效的提高了网络的搜索特性.受到这一思想的启发,本文将该机制改进后引入到本文对搜索蜜源的方向加以改进:设l为搜索步长,若

fit(Xi+l)

(9)

则

Xi=Xi+l

(10)

若

fit(Xi-l)

(11)

则

Xi=Xi-l

(12)

否则Xi保持不变.

改进后的蜜源搜索机制下,观察蜂可对当前蜜源Xi临近位置的其他蜜源进行双向搜索,通过比较Xi与Xi+l、Xi与Xi-l的适应度值的大小关系对蜜源进行重新选择.该种搜索机制不仅大大提高了算法的搜索效率,同时去除了对蜜蜂活动方向和范围的限制,使不同类型蜜蜂间的交流合作更加密切,克服了传统算法后期容易陷入局部最优解的问题.

3.2.3 粒子群算法实现算法初始化

在传统蜂群算法中存在收敛速度较慢的缺点,而粒子群算法则具有较收敛速度快的特点,利用这一特性,本文将粒子群算法引入到改进算法的初始化阶段,即首先利用粒子群算法通过较少次数的迭代产生出全局最优解,而后根据这一全局最优解在该解附近随机产生初始蜜源位置,之后再进行人工蜂群算法蜜源位置的寻优过程.不论粒子群产生的是全局最优解还是局部最优解,都通过改进的ABC算法进行双向邻域搜索,当蜜源Xi的位置不发生改变时改进的人工蜂群算法切换为粒子群进行二次初始化.

改进后ABC算法的初始化蜜源位置如下:

(13)

因粒子群算法和传统人工蜂群算法均存在易收敛于局部最优解的缺陷,故将两种算法进行融合,有效地平衡了全局搜索和局部搜索.

人工蜂群算法通过位置信息进行搜索,并最终得到最优蜜源,因此蜜源的初始位置、领域搜索的范围和搜索机制就显得格外关键.利用粒子群算法收敛速度快的特性对算法进行初始化,通过较少的迭代得到全局最优解作为初始蜜源位置.

StartStep1．人工蜂群算法与粒子群算法的相关初始参数进行设置，根据式(4)和式(5)随机生成M个粒子的初始速度和初始位置；Step2．通过计算每个粒子的适应度值并比较，在循环次数c内确定最优解Pg，best；Step3．采蜜蜂按式(6)和(7)搜索一个新的蜜源，并对该蜜源位置的适应度进行计算，如果新位置的适应度值优于原来的位置，则用新位置替换原位置；Step4．观察蜂根据蜜源的花蜜量依概率公式(2)选择一个蜜源位置，并根据双向随机优化机制随机产生一个新的位置，并对该位置进行评价；Step5．若存在放弃的蜜源，该处的采蜜蜂根据式(3)变成侦查蜂；Step6．记录当前的最优位置及适应度值．End

若粒子群算法在迭代过程中产生局部最优解,则将该最优解作为新增邻域点,从而加速了侦查蜂的搜索,在该邻域内采用双向随机优化机制以l为步长进行搜索,若蜜源Xi保持保持不变,则跳出该邻域,再对人工蜂群算法进行初始化,进而最终使得蜂群以最快速度找到最优蜜源.

4 仿真实验

本文合理选择三个基准函数作为样本,通过实验分别验证了算法的有效性、普遍适用性以及相应的性能指标,并且将实验结果同传统ABC算法进行比较,文献[1]提出的混合人工蜂群算法(HABC)性能进行比较.

1)Rastrigin函数

2)Griewank函数

3)Sphere函数

本文算法的参数设置如下:对本文改进算法SRABC算法,种群规模S=60,limit=60,粒子群数为60,粒子群算法循环次数c=100;将传统人工蜂群算法的种群规模S和循环搜索次数limit设置为60,规定算法做多完成2500此迭代,且每个算法都独立且完整实现30次.表1至表3分别表示Rastrigin函数、Griewank函数和Sphere函数在维数等于30和60的情况下,且依据以上参数设定在30次运行后所得到的平均值、方差.最大值和最小值,并在表中对结果进行了对比.

对表1和表2数据进行对比可知,改进后的SRABC算法在不同维数下仿真精度都要明显优于ABC算法及HABC算法对这两个函数的仿真精度.尤其在维数等于60时,针对Rastrigin函数算法可以快速收敛到0.根据表3数据可知,对于单峰函数Sphere,SRABC算法在不同维数下对此函数的优化结果虽然没有很大程度的提高,但仍优于标准ABC算法及HABC算法的优化结果.因此,改进算法不仅保持了原有算法的特性,在计算精度和稳定性方面较传统算法以及HABC算法都有明显提高.

表1 Rastrigin函数的测试结果
Table 1 Test results of Rastrigin function

算法维数平均值方差最大值最小值ABCHABCSRABC302．58239E⁃0091．03788E⁃0085．65922E⁃0081．13687E⁃0121．13687E⁃0121．64169E⁃0128．15703E⁃0121．12578E⁃0151．32635E⁃0141．78719E⁃145．68434E⁃0140ABCHABCSRABC600．1678950．4582411．990331．72463E⁃0104．56788E⁃0081．53871E⁃0078．25186E⁃0071．3074E⁃0111．21393E⁃0102．62695E⁃0101．2559E⁃0091．7053E⁃013

表2 Griewank函数的测试结果
Table 2 Test results of Griewank function

算法维数平均值方差最大值最小值ABCHABCSRABC 302．18149E⁃0129．27583E⁃0124．90501E⁃0119．99201E⁃0164．08007E⁃0149．89653E⁃0144．99267E⁃0134．44089E⁃0166，25426E0161．41953E⁃0157．54952E⁃0150ABCHABCSRABC602．79554E⁃0138．89572E⁃0134．85578E⁃0122．77556E⁃0151．4011E⁃0132．87342E⁃0131．20581E⁃0122．33147E⁃0151．72825E⁃0151．94662E⁃0158．54872E⁃0151．11022E⁃016

表3 Sphere函数的测试结果
Table 3 Test results of Sphere function

算法维数平均值方差最大值最小值ABCHABCSRABC301．13714E⁃0152．97144E⁃0161．79207E⁃0155．46909E⁃0165．55572E⁃0169．00306E0177．23074E⁃0164．09377E⁃0162．95155E⁃0165．79213E⁃174．61564E⁃0161．80046E⁃016ABCHABCSRABC602．34037E⁃0141．82907E⁃0147．64184E⁃0144．13668E⁃0153．6088E⁃0151．45665E⁃0158．65843E⁃0151．87149E⁃0158．15309E⁃0161．32347E⁃0169．89696E⁃0164．72298E⁃016

图1 Rastrigin函数不同维数对比Fig.1 Comparison of different dimensions for Rastrigin function

图1至图3则分别给出了每个函数的维数为30和60时对ABC算法、HABC算法以及SRABC算法寻优迭代过程曲线图,为了更清晰地显示结果,x轴表示迭代次数,y轴采用对数坐标表示最优值.

图2 Griewank函数不同维数对比Fig.2 Comparison of different dimensions for Griewank function

由图1～图3可知,在迭代次数不发生变化时,在不同维数下,三个基准函数对于传统人工蜂群算法的最优解在迭代次数较大是表现出趋向于不发生变化,HABC算法相比较ABC算法有一定的改善,而SRABC算法在寻优过程中性能改善较为明显.根据图1、图2可知,改进后的算法通过自适应随机优化策略可以在迭代次数不发生改变的情况下,能够使Rastrigin函数和Griewank函数在算法的初始阶段近似地依线性快速收敛至最优解,且收敛速度明显由于其他两种算法.由图3可看出Sphere函数作为基准函数时SRABC算法能够快速递减收敛到最优解,由于在算法初期采用了粒子群算法初步寻优的结果作为SRABC算法的初始值,而使搜索空间大大缩小,进而提高了算法的收敛速度.

图3 Sphere函数不同维数对比Fig.3 Comparison of different dimensions for Sphere function

由此可知,改进后的人工蜂群算法能够依据自适应随机优化策略和双向搜索机制使算法实现快速收敛,提高全过程的寻优能力,极大地改善了算法的结果精度,使算法能够有效地避免“早熟”现象的产生.

6 结 语

经过改进之后的人工蜂群算法是一种先进的群体智能优化算法,算法易于实现且具有操作简单的特点,同时减少了控制参数.本文针对ABC算法局部搜索能力较弱、搜索精度不高及收敛速度较慢的缺点,在算法开始阶段引入粒子群算法对蜂群进行初始化,同时在自适应思想及双向随机优化机制的基础上,提出了基于双向随机优化策略的改进算法,有效的改善了寻优过程中随机性过强及搜索方向单一的缺陷,在一定程度上避免了算法陷入局部最优的问题.通过对比传统算法、文献[1]提出的HABC算法及本文改进算法,并通过三个不同基准函数对算法性能进行验证,结果表明本文算法具有普遍有效性,同时在提高算法收敛速度的基础上,有效的改善了算法的寻优能力.

[1] Gao Wei-feng,Liu San-yang,Jiang Fei,et al.Hybrid artificial bee colony algorithm[J].Systems Engineering and Electronics,2011,33(5):1167-1171.

[2] Dorgo M,Maniezzo V,Golorni A.The ants system:optimization by a colony of cooperating agants [J].IEEE Transactions on System,Man and Cybernetics PartB:Cybernetics,1996,26(1):29-41.

[3] Kennedy J,Ebethart R.Particle swarm optimization [C].Proceeding of IEEE International Conference on Neural Networks,Piscataway,NJ:IEEE Computer Scoiety,1995:1942-1948.

[4] Karaboga D.An idea based on honey bee swarm for numerical optimization,technical report-TR06 [R].Computer Engineering Department,Engineering Faculty,Erciyes University,2005.

[5] Karaboga D,Basturk B.A powerful and efficient algorithm for numerical function optimization:artificial bee colony(ABC)algorithm [J].Journal of Global Optimization,2007,39(3):459-471.

[6] Karaboga D,Basturk B.On the performance of artificial bee colony(ABC)algorithm [J].Applied Soft Computing,2008,8(1):687-697.

[7] Kang Fei,Li Jun-jie,Xu Qing.Hybrid simplex artificial bee colony algorithm and its application in material dynamic parameter back analysis of concrete dams [J].Journal of Hydraulic Engineer,2009,40(6):736-742.

[8] Alatas B.Chaotic Bee colony algorithms for global numerical optimization [J].Expert Systems with Applications,2010,37(8):535-541.

[9] Xu C F,Dun H B,Liu F.Chaotic artificial bee colony approach to uninhabited combat air vehicle path planning [J].Aerospace Science and Technology,2010,14(8):535-541.

[10] Kennedy J,Eberhart R C.Particle swarm optimization [C].Proc.of IEEE International Conference on Neural Networks,Perth,Australia,1995:1942-1948.

[11] Shi Y,Eberhart R C.A modified particle swarm optimizer [C].Proc.of IEEE World Congress on Evolutionary Computation,Anchorage,Alaska,USA,May,1998:69-73.

[12] Lei Xiu-juan,Huang Xu,Zhang Ai-dong.Improved artificial bee colony algorithm and its application in data clustering [C].Proc.of 2010 IEEE Fifth International Conference on Bio-Inspired Computing:Theories and Applications,2010:514-521.

[13] Ma Wen-ming,Meng Xiang-wu,Zhang Yu-jie.Bidirectional random walk search mechanism for unseructured P2P network[J].Journal of Software,2012,23(4):894-911.

[14] Yang Sheng-pei,Li Zhong-yang,Cheng Zhong-yang.Particle swarm optimization algorithm based on chaotic searching and people crossover operator[J].Computer Simulation,2016,33(6):218-222.

[15] Ma Can,Liu Jian,Yu Fang-ping.Research on cuckoo algorithm with simulated annealing[J].Journal of Chinese Computer Systems,2016,37(9):2029-2034.

[16] Li Yan-cang,Peng Yang.Improved artificial bee colony algorithm based on information entropy[J].Control and Decision,2015,30(6):1121-1125.

[17] Zhu Bing-lian,Zhu Fang-fang,Duan Qing-yan,et al.An improved spectrum allocation algorithm using multi-strategy discrete artificial bee colony technology[J].Journal of Xi′an Jiaotong University,2016,50(2):20-25.

[18] Naeem M,Anpalagan A,Jaseeemuddin M,et al.Resource allocation techniques in cooperative cognitive radio networks[J].IEEE Communications Surveys & Tutorials,2014,16(3):729-744.

[19] Ren Kai-jun,Deng Ke-feng,Liu Shao-wei,et al.Adaptive artificial bee colony optimization for parameter estimation of chaotic systems[J].Journal of National Univ-ersity of Defense Technology,2015,37(5):135-140.

[20] Ouyang A,Tang Z,Li L,et al.Estimating parameters of muskingum model using an adaptive hybrid P-SO algorithm[J].International Journal of Pattern Recogniti-on and Artificial Intelligence,2014,28(1):1-29.

附中文参考文献：

[1] 高卫峰,刘三阳,姜 飞,等.混合人工蜂群算法[J].系统工程与电子技术,2011,33(5):1167-1171.

[7] 康 飞,李俊杰,许 青.混合蜂群算法及其在混凝土坝动力材料参数反演中的应用[J].水利学报,2009,40(6):736-742.

[13] 马文明,孟祥武,张玉洁.面向非结构化P2P网络的双向随机漫步搜索机制[J].软件学报,2012,23(4):894-911.

[14] 杨胜培,李仲阳,陈中样.基于混沌搜索与种群交叉的粒子群优化算法[J].计算机仿真,2016,33(6):218-222.

[15] 马 灿,刘 坚,余方平,等.混合模拟退火的布谷鸟算法研究[J].小型微型计算机系统,2016,37(9):2029-2034.

[16] 李彦苍,彭 阳.基于信息熵的改进人工蜂群算法[J].控制与决策,2015,30(6):1121-1125.

[17] 朱冰莲,朱方方,段青言,等.采用多策略离散人工蜂群的改进频谱分配算法[J].西安交通大学学报,2016,50(2):20-25.

[19] 任开军,邓科峰,刘少伟,等.自适应人工蜂群优化的混沌系统参数估计[J].国防科技大学学报,2015,37(5):135-140.