曹萌萌,皇甫大恩,刘晓斐
(1.开封大学 信息工程学院,河南 开封475004;2.中国矿业大学 安全工程学院,江苏 徐州221116)
人工蜂群算法[1-4]由于在进化过程和选择策略中具有更强的随机性,在很多问题中的全局搜索能力优于其它一些群体智能算法,但也减慢了算法收敛速度。许多国内外学者从各个角度出发,提出了多种改进人工蜂群算法。例如:Alatas利用混沌映射系统来自适应调整参数,提出了CABC算法[5];暴励等结合差分进化算法,提出了BDABC算法[6];Kang等结合的Rosenbrock旋转方向法,提出了RABC算法[7];罗钧等采用 “分段搜索”方式对食物源进行贪婪更新,提出了SABC算法[8];付丽等提出了一种引入跟踪搜索和免疫选择的人工蜂群算法[9];冀俊忠等引入了 “引导素”的概念,提出引导素更新和扩散机制的人工蜂群算法[10];刘三阳等利用随机动态局部搜索算子和采用基于排序的选择概率的方法,提出了LRABC算法[11]。从改良人工蜂群算法中收益度分配的角度出发,同时在观察蜂的更新公式中增加了全局最优个体的信息反馈,提出了一种具有较快收敛速度的改进人工蜂群算法。
人工蜂群算法主要由3部分组成:采蜜蜂、观察蜂和侦查蜂。其中,采蜜蜂和观察蜂数量相等,用m表示。侦查蜂是当采蜜蜂放弃一个蜜源后转变而成的。算法首先在初始化时,随机产成m个初始解,然后按照蜜蜂采蜜原理进行搜索。搜索过程为:①采蜜蜂选择记忆中邻近的一个蜜源;②观察蜂根据信息选择跟随其中一个采蜜蜂;③观察蜂在邻近的蜜源内选中最好的蜜源;④采蜜蜂放弃原来的蜜源,变成侦查蜂,随机搜索新的蜜源。
通过上述过程蜜蜂进行搜索,每个蜜源表示一个可能解,蜜源的质量对应着解的质量,用收益度值表示。观察蜂选择蜜源的概率公式为
式中:θi——第i个蜜源,i∈{1,2,…,S},S——蜜源的个数,F(θi)——第θi处蜜源的收益度值。在比较θi周围的蜜源后,观察蜂选择其中一个蜜源。新的蜜源位置计算公式如下
式中:φi(c)——θi附近随机产生的更新步长,如果新蜜源适应值大于原来蜜源适应值即F(θi(c+1))> F(θi(c)),则观察蜂选择新蜜源θi(c+1);否则维持不变。如果达到限定循环次数后,蜜源质量仍然没有得到提高,则采蜜蜂放弃该蜜源,变成侦查蜂,位置xi更新如下
其中,φ′为 [0,1]内服从均匀分布的随机数。
改进人工蜂群算法与标准人工蜂群算法相比主要在以下两个方面做了改进:①改进了蜂群算法中关于个体收益度的计算方法;②在观察蜂的更新公式中增加了全局最优个体的信息反馈,以加快算法的收敛速度。
人工蜂群算法中,收益度值时衡量蜜源位置好坏的一个度量值,因此受益度的计算是否合理对算法的性能有着直接而且非常重要的影响。在标准人工蜂群算法中收益度F(θi)计算公式为
式中:θi——第i个蜜源,i∈ {1,2,…,S},S表示蜜源的个数,fitness为函数适应值。在式 (4)中,当fitness>1时,fitness值越大,蜜源位置就越差,收益度越小,这也与蜂群理论基本一致,但当fitness<1,且fitness趋近于0时,F(θi)趋近于常数1,这样所有蜜源位置的受益度都基本相等,因此无法找出最优蜜源位置,算法出现早熟现象。
为此,针对标准人工蜂群算法中在受益度分配上存在的不足的问题,提出了一种新的收益度计算方法。具体计算公式如下
对比标准蜂群算法收益度计算式 (4),在式 (5)中当fitness>1时,对fitness值进行平方处理,有助于加大蜜源位置的区分度;当0<fitness<1,由于fitness为double数据类型,因此1≤F(θi)<309,且fitness相差一个数量级,F(θi)差值为1;fitness趋近于0时,F(θi)趋近于309,因此fitness=0时,F(θi)=309。由于目前的基准测试函数最优值多为0,因此式 (5)只是针对最优值大于等于0的情况进行讨论,如fitness小于0需进行转换。
标准人工蜂群算法在更新策略中,没有采用最优蜜源位置进行更新位置,而是采用根据蜜源位置的收益度大小,随机选择蜜源位置进行更新的方法。这种方法使选择策略具有更强随机性,增加了算法的全局搜索能力,但是在很大程度上降低了算法的收敛速度,为此本文在蜜源位置更新公式中保留了随机选择蜜源位置进行更新的方式,同时也增加最优蜜源位置来更新蜜源位置。使算法性能更加均衡
改进算法流程如图1所示。
图1 算法流程
改进算法具体流程为:
(1)初始化种群,计算每个个体的适应值;
(2)引领蜂根据式 (6)在蜜源附近进行搜索产生新蜜源位置Vi,然后计算其适应值;
(3)如果新蜜源Vi的适应值好于原来蜜源Xi,则用新蜜源Vi替换原来蜜源Xi,将Vi作为当前最蜜源,否则保持原来蜜源Xi不变;
(4)计算蜜源Xi的适应值,根据式 (1)计算蜜源Xi的选择概率值Pi;
(5)跟随蜂根据概率Pi选择蜜源,然后根据式 (6)再蜜源附近进行搜索产生新蜜源Vi,计算新蜜源适应值;
(6)同步骤 (3);
(7)判断是否满足放弃蜜源条件,若满足,则侦查蜂根据式 (3)产生一个新蜜源Xi代替原蜜源;
(8)记录迄今为止最好的蜜源;
(9)判断是否符合算法结束条件,不满足继续迭代,否则输出结果。
本文选择8个经典基准函数进行测试,具体形式如下:
(5)Schwefel函数:f(x)=418.98288727243369·n+范 围 [-500,500],在(420.9687,420.9687,…,420.9687)处取得最小值0。
(7) Ackley 函 数: f(x) =- 20exp(- 0.2范围[-32,32],在 (0,0,…,0)处取得最小值0。
为更好地测试本文算法的性能,选择标准ABC算法和改进算法IABC算法[12]进行对比测试实验。算法参数设置为,蜜蜂个数为40,函数维数为30,评估次数为12万次。本文算法简称DABC算法,表1为3种算法在30维函数上的测试结果,表中结果均为算法独立运行30次的平均值。
表1 3种算法在30维函数上的测试结果
从表1的测试结果可知:DABC算法在8个测试函数中,有7个测试函数测试结果是最好的,其中有5个测试函数比其它两种算法结果都好。特别是在Sphere函数,Schwefel 2.22函数,Rosenbrock函数和Schwefel 2.21函数上。DABC算法结果与其它两种算法相比结果有大幅度的提高,例如,Sphere函数结果比其它算法高了23个数量级,Schwefel 2.22函数比其它算法高了12个数量级。
为了方便在统计意义上比较多个算法的性能,采用T检验对结果进行分析,以此判断本文算法与其它两种算法的性能是否存在显著性差异。t检验的分位数为单侧0.05,样本容量为30,T检验的临界值通过查表为1.697。当t>1.697时说明DABC算法优于该算法,标记为 “+”;当t<-1.697时说明DABC算法差于该算法,标记为 “-”;否则,说明DABC算法与该算法无明显差异,标记为 “=”。“w/t/l”表示DABC算法与所选算法相比在w个函数上优于该算法,t个函数上无明显差异,一个函数上差于该算法。表2为T检验的测试结果。
表2 T检验结果
从表2可以明显看出,在8个测试函数中,本文算法与标准ABC算法在全部8个函数上结果都有显著提高,与IABC算法在5个函数上结果都有显著提高,其它3个函数测试结果无明显差异。
为进一步检测算法处理更高维数函数问题的能力。仍然选择标准ABC算法和改进算法IABC算法[12]进行对比测试实验。函数维数为40,评估次数为24万次,其它参数设置保持一致。3种算法的测试结果见表3,表中结果均为算法独立运行30次的平均值。
表3 3种算法在60维函数上的测试结果
由表3测试结果可知:DABC算法在8个测试函数中,有7个测试函数测试结果是最好的,其中有6个测试函数比其它两种算法结果都好。并且对比表1和表3数据可知:ABC算法和IABC算法在维数增加后,有些函数的结果有明显的下降趋势,比如,Schwefel函数,而DABC算法结果则下降趋势较慢,因此在60维函数测试中,DABC算法优于其它算法的结果增加了一个。
为了进一步验证DABC算法的鲁棒性,选择其中的4个测试函数继续增加函数的维数进行测试,其中评估次数为4000*n,n为函数维数,算法的其它参数保持不变。
图2为Sphere函数的测试结果,由图可知,随着函数维数的增长,测试结果基本上保持在10-58数量级左右,图3为Schwefel 2.22函数的测试结果,与图2一致,测试结果基本上保持在10-28数量级左右,相差一两个数量级左右。图4为Rastrigin函数的测试结果,所有维数结果都为0,没有任何变化,图5为Ackley函数的测试结果,虽然30维和40维之间,结果出现一定下降,但是总体上差异不大。综上可知,随着函数维数的增长,DABC算法的测试结果基本上保持在同一个数量之间,并没有出现,明显下降的趋势。由此可见DABC算法具有很强鲁棒性,且具有较强的处理高维复杂函数的能力。
图2 Sphere函数的测试结果
图3 Schwefel 2.22函数的测试结果
图4 Rastrigin函数的测试结果
图5 Ackley函数的测试结果
针对标准人工蜂群算法中在受益度分配上存在的不足,提出了一种新的收益度计算方法,同时在更新策略中增加最优蜜源位置来更新蜜源位置。在8个测试函数的仿真结果中,与对比算法相比,DABC算法在30维和60维上测试结果都优于其它两种,T测试表明DABC算法在大多数函数上测试结果都有显著性提高;此外,进一步加大函数维数测试结果表明DABC算法具有很强鲁棒性,且具有较强的处理高维复杂函数的能力。
[1]GAO Xiangming,LIU Fubin,YANG Shifeng.Intelligent fault diagnosis of water supply network based on ELM [J].Computer Engineering and Design,2013,34 (8):2887-2891(in Chinese).[高相铭,刘付斌,杨世凤.基于极限学习机的供水管网故障智能诊断方法 [J].计算机工程与设计,2013,34 (8):2887-2891.]
[2]YU Ming,AI Yueqiao.SVM parameter optimization and application based on artificial bee colony algorithm [J].Journal of Optoelectronics Laser,2012,23 (2):241-243 (in Chinese).[于明,艾月乔.基于人工蜂群算法的支持向量机参数优化及应用 [J].光电子激光,2012,23 (2):241-243.]
[3]Singh A.An artificial bee colony algorithm for the leaf-constrained minimum spanning tree problem [J].Applied Soft Computing,2009,9 (2):625-631.
[4]KANG Fei,LI Junjie,XU Qing.Hybrid simplex artificial bee colony algorithm and its application in material dynamic parameter back analysis of concrete dams [J].Journal of Hydraulic Enginessring,2009,40 (6):736-742 (in Chinese). [康飞,李俊杰,许青.混合蜂群算法及其在混凝土坝动力材料参数反演中的应用 [J].水利学报,2009,40 (6):736-742.]
[5]Alatas B.Chaotic bee colony algorithms for global numerical optimization [J].Expert Systems with Applications,2010,37 (8):5682-5687.
[6]BAO Li,ZENG Jianchao.A bi-group differential artificial bee colony algorithm [J].Control Theory and Applications,2011,28 (2):266-272 (in Chinese). [暴励,曾建潮.一种双种群差分 蜂 群 算 法 [J].控 制 理 论 与 应 用,2011,28 (2):266-272.]
[7]Kang F,Li J,Ma Z.Rosenbrock artificial bee colony algorithm for accurate global optimization of numerical functions[J].Information Sciences,2011,181 (16):3508-3531.
[8]LUO Jun,XIAO Xianghai,FU Li,et al.Modified artificial bee colony algorithm based on segmental search strategy [J].Control and Decision,2012,27 (9):1402-1405 (in Chinese).[罗钧,肖向海,付丽,等.基于分段搜索策略的改进蜂群算法 [J].控制与决策,2012,27 (9):1402-1405.]
[9]FU Li,LUO Jun.Artificial bee colony algorithm with tracking search and immune selection [J].Pattem Recognition and Aitificial Intelligence,2013,26 (7):688-694 (in Chinese). [付丽,罗钧.引入跟踪搜索和免疫选择的人工蜂群算法 [J].模式识别与人工智能,2013,26 (7):688-694.]
[10]JI Junzhong,WEI Hongkai,LIU Chunnian,et al.Artificial bee colony algorithm based on inductive pheromone updating and diffusion [J].Journal of Computer Research and Development,2013,50 (9):2005-2014 (in Chinese).[冀俊忠,魏红凯,刘椿年,等.基于引导素更新和扩散机制的人工蜂群算法 [J].计算机研究与发展,2013,50 (9):2005-2014.]
[11]LIU Sanyang,ZHANG Ping,ZHU Mingmin.Artificial bee colony algorithm based on local search [J].Control and Decision,2014,29 (1):123-128 (in Chinese). [刘三阳,张平,朱明敏.基于局部搜索的人工蜂群算法 [J].控制与决策,2014,29 (1):123-128.]
[12]GAO Weifeng,LIU Sanyang,HUANG Lingling.Inspired artificial bee colony algorithm for global optimization problems[J].Acta Electronic Sinica,2012,40 (12):2396-2403 (in Chinese).[高卫峰,刘三阳,黄玲玲.受启发的人工蜂群算法在全局优化问题中的应用 [J].电子学报,2012,40(12):2396-2403.]