改进的人工蜂群算法及其收敛性分析与应用
张鑫,陈国初,公维翔
(上海电机学院电气学院,上海 200240)
摘 要:针对人工蜂群算法容易陷入局部最优的缺陷,本文提出一种自适应柯西变异人工蜂群算法。该算法引入自适应因子来扩大蜂群的搜索范围,并利用柯西分布的特点对全局进行搜索,提高了蜂群搜索的普遍性。然后利用随机过程理论,对自适应柯西变异人工蜂群算法进行了理论分析,论证了该算法的收敛性。最后将改进的人工蜂群算法应用到风电功率短期预测模型参数的优化中,与常规方法比较,表明该方法拟合精度更高。
关键词:人工蜂群算法;自适应;柯西变异;收敛性分析;风功率预测;
Artificial bee colony algorithm Based on Adaptive Cauchy Mutation and Its convergence
analysis and its application
Zhang Xin, Chen Guochu,Gong Weixiang
(School of Electric Engineering, Shanghai DianJi University, Shanghai 200240,China)
Abstract: As to the problem of falling into the local optimum in standard artificial bee colony , it is proposed to introduce an adaptive factor which can expand the search of the swarm and uses the Cauchy distribution to improve the universality of colony search. This improved algorithm named adaptive Cauchy mutation artificial bee colony (ACMABC). Then the ACMABC is analyzed in theory by using the theory of random process to prove the convergence of the algorithm. Finally, this modified method is applied to the optimization of the parameters of wind power short-term prediction model, compared with standard statistic strategy, an illustration with higher precision is given.
Key words: artificial bee colony algorithm; adaptive; Cauchy mutation; convergence analysis; Wind power short-term prediction
1 引言
人工蜂群算法( Artificial Bee Colony, ABC)是由D.Karaboga于2005年提出的一种群体智能寻优搜索方法,相对于其他优化算法,其具有原理简单、参数少、易实现、全局搜索能力强的优点,被广泛应用到各种问题优化中
[2-3]
[1]
。
尽管ABC具有简单、高效的特点,但在接近全局最优势,易陷入极值点,降低了优化效果,在高维多峰优化函数中尤为突出。为此,近年来出现了不少对其改进的文章。比如,邻域搜索中引入惯性递减权重,性能参数分段搜索,邻域搜索方程中增加调节扰动,邻域搜索采用量子位 Bloch 坐标编码变换等。虽然这些方法一定程度上提高了算法的精度和收敛速度,但是没有从根本上增加种群的多样性,邻域搜索虽引入衰减权重,但同一代种群采用统一权重,这样无法有效开发不同蜜蜂邻域搜索的能力。基于此,本文引入自适应调节函数确定邻域搜索权重,增加了种群的多样性,有效开发了种群邻域搜索能力,理论上避免种群陷入局部最优。在搜索后期,种群最优值若连续几代没有变化,则引入柯西变异算子,及时使种群跳出局部极值,把该方法称为自适应柯西变异人工蜂群算法(Adaptive Cauchy
mutation artificial bee colony, ACMABC);对其进行收敛性分析并将其应用到支持向量机的短期
[7]
[5]
[6]
[4]
风电功率预测模型参数优化中,对实测风电功率数据进行建模仿真,通过与常规SVR预测模型进行性能对比,验证该方法的有效性。
2 人工蜂群算法
2.1 标准人工蜂群算法
在ABC算法中,人工蜂群有引领蜂(leaders)、跟随蜂(followers)和侦察蜂(scouts)三种角色。引领蜂在搜索空间开采花蜜,即寻找最优解,同时引领蜂会记录食物源的相关信息。跟随蜂按轮盘赌选择策略选择引领蜂进行跟随,并在其附近进行采蜜;当引领蜂放弃食物源时,便会变成侦察蜂重新寻找食物。
实际优化问题中,蜜源的位置代表优化问题的可行解,蜜源的丰富程度代表解的质量。在蜂群搜索的过程中,首先在搜索空间会生产初始解Xi(i=1,2, ,SN) SN为蜜源个数,每个初始解Xi是一个d维的向量。然后,引领蜂根据下式进行搜索:
[8]
Vij=xij+Rij(xij-xkj) (1)
1,2, ,SN},并且Vij是新的食物源的位置,Rij是一个[-1,1]范围内的随机数,k∈{
k≠i;j∈{1,2, ,d}。搜索之后,比较最优解和搜索解,当搜索解比最优解更优时则替换掉
最优解。反之,则保持最优解不变。
跟随蜂根据轮盘赌选择策略来选择食物源采蜜,选择概率由下式确定:
[9]
Pi=
fiti
∑fit
i=1
SN
(2)
i
其中,fiti是第i个解的适应度函数值,SN是解的个数。选择引领蜂之后并在其附近进行领域搜索。
当引领蜂Xi连续limit次迭代都没有改变,则此引领蜂转变成侦察蜂,由侦察蜂通过下式随机生成一个新解来代替Xi。
jjj
xij=xmin+rand(0,1)(xmax-xmin) (3)
jj
1,2, ,d},xmax其中,j∈{和xmin表示所有蜂群中第j维的最大值和最小值。
2,2 自适应柯西变异人工蜂群算法 2.2.1 搜索步长的自适应调整
ABC算法在初始搜索阶段不一定可以保证蜂群的全局性,且在随后的搜索中也可能陷入局部搜索,不能保证算法的整体性能。因此本文引入一种自适应因子w,使其在初始阶段搜索范围扩大,在最优解附近区域缩小搜索范围。
在蜂群迭代寻优过程中,初始阶段搜索进程快,步长较大可以扩大蜂群搜索范围,此时
要求自适应因子w较大,同时各引领蜂平均适应值和最小适应值之差比较小;当引领蜂接近最优解区域时,引领蜂要精细搜索,此时要求自适应因子w较小,同时平均适应值和蜂群最小值之差较大。鉴于此,自适应因子w可以随搜索的进行自身进行调整,本文约定自适应因子w的调整公式如下:
w=wmin+(fv(j)-fmin)⋅(wmax-wmin)/(fvag-fmin) (4)
式中:wmax,wmin分别为最大,最小惯性权值;fv(j),fvag,fmin分别为引领蜂当前适应度值、平均适应度值、群体最小适应度值。引入自适应因子w后,引领蜂和跟随蜂进行位置更新的公式如式(5)所示:
Vij=xij+w⋅Rij(xij-xkj) (5)
由公式(4)可以看出,在初始阶段,平均适应值和群体最小适应值之差较小,而
(fv(j)-fmin)/(fvag-fmin)的值较大,所以自适应因子较大,算法容易从局部极值跳出,
从而扩大搜索范围。同理,在后期蜂群搜索阶段,平均值和群体最小适应值较大,
(fv(j)-fmin)/(fvag-fmin)的值较小,所以自适应因子较小,加强引领蜂局部搜索。这样
能够提高引领蜂动态搜索性能。
2.2.2 侦察蜂根据柯西分布搜索新解
当引领蜂Xi连续迭代Limit次后适应值仍不变,则该引领蜂变成侦察蜂。本文在侦察蜂搜索公式中引入柯西分布,以便提高算法的扰动能力,使人工蜂群更容易跳出局部极值,充分利用当前搜索到的信息,提高搜索效率。
柯西分布是概率论与数理统计中的一类常见分布,一维柯西分布概率密度函数为
[9]
f(x)=
t
,-∞
πt+x2
⋅
1
当t=1时,称为标准柯西分布。图1是标准柯西和标准高斯分布概率密度函数曲线。由图1可见柯西分布原点处的峰值比高斯分布小以便提高扰动能力,并且两端长扁形状趋于零的速度比高斯分布慢,这样可以使算法更易避免早熟现象。本文中采用的柯西分布随机变量
ξ-0.5)π],其中ξ是[0,1]上的随机变量。鉴于此,侦察蜂搜索的公生成函数为η=tan[(
式改进为:
jjj
xij=xmin+Cauchy(0,1)⋅(xmax-xmin) (6)
式中,Cauchy(0.1)为标准柯西分布。
图1 标准柯西、高斯分布概率密度函数曲线
Fig.1 Probability density function curve of standard Cauchy and Gaussian
2.2.3 自适应柯西变异人工蜂群算法
自适应柯西变异人工蜂群算法(adaptive Cauchy mutation artificial bee colony, ACMABC)的基本思想是在人工蜂群搜索初期运用式(5)进行搜索,增加蜂群的多样性,有利于跳出局部极值进行全局搜索。在算法迭代过程中,蜂群迭代后见种群中最优解与历史最优值进行比较,如果优于历史最优值,则将其取代。当历史最优值在连续两次迭代过程中都没有改变,则利用式(6)产生新解。算法步骤如下所示:
①算法初始化。包括初始化种群规模,控制参数“limit”,最大迭代次数;随机产生初始解xi,i 1,2, ,SN,并计算每个解的适应度函数值。
②引领蜂根据公式(5)在搜索空间搜索蜜源Vi并计算其适应值;如果Vi的适应值优于初始解xi,则替代xi。否则,保持初始解不变。
③计算所有xi的适应度值,运用公式(2)计算与xi相关的概率值Pi。
④跟随蜂采用轮盘赌选择策略选择引领蜂进行跟随,并根据公式(5)在其附近搜索新解
Vi,然后计算其适应值并将其与历史最优值比较,更新历史最优值。
⑤若蜜源开采到一定程度后适应度仍没有得到改善,则该引领蜂变成侦察蜂,侦察蜂运用柯西分布特点根据式(6)搜索新解xi
⑥一次迭代完成之后,记录到目前为止最好的解。
⑦若迭代次数满足终止条件,则输出最优解,否则返回②。
2.3 测试函数优化与结果讨论 2.3.1 测试函数
(1)Sphere函数
minf(x)=∑xi2,-10≤xi≤10
i=1
n
该函数只有一个全局最小点:(0,„,0),最小值为0。 (2)Ackley 函数
-0.2
1
⋅x2jnj=1
minf(x)=-20⋅e
∑
n
-e
1
⋅cos(2⋅π⋅xj)nj=1
∑
n
+22.71282,-5≤xj≤5
此函数有一个(0,0)为全局最小,最小值为0。这个函数的搜索十分困难。求解Ackley函数的最小值是优化算法应用的一个有力的例证。(可取n=2)。(函数最后的常数最好为:22.[**************])。 (3)Rastrigin 函数
f(x)=∑(xi2-10⋅cos(2πxi)+10),-5.12≤xi≤5.12
i=1
n
当n=2时,该函数有4个全局最大值点,全局最大值为80.7066。
2.3.2 优化结果与讨论
在ACMABC算法的测试实验过程中,为了实验结果更具有说服力,将它与标准的ABC算法进行比较。其参数设置如下:两种优化算法的蜜蜂种群数目为50,迭代次数为2000,误差极限为1E-20,开采次数为50,ACMABC最小权重系数为0.08,最大权重系数为1.8。对每一个测试函数都进行2维,10维和20维的测试,每组实验都独立进行20次,并比较运行结果中的最优值、平均值及20次独立实验中接近最优值的概率,本文中接近最优值的概率是以最优值的±5%为标准进行计算的。优化的结果如表1所示,曲线收敛图如图2,3,4。
表1 函数测试结果对比 Table 1. Function test results
由表1可以看出,在设定条件相同的情况下,ACMABC在对上面4个函数寻优达优概率
和收敛速度明显优于ABC;从最优适应值和平均适应值来看,MABC的寻优效果较ABC有了质的提高,这是因为其在局部搜索时引入了根据适应值大小自动调整的权重系数,增强了局部搜索的目标性;利用柯西变异算子使种群及时跳出局部最优,在保证种群结构的情况下,增加了种群的多样性。下面给出ACMABC算法和ABC算法搜索最优解过程的收敛曲线图。从仿真的收敛图可以看出,ACMABC算法比ABC算法优化连续函数的收敛速度更快,对于这三个测试函数,ACMABC算法均有比较好的收敛速度。
全局收敛曲线
全局最优适应值
200
400
600
800
100030
维
[***********]00
图2 Sphere函数优化曲线
Fig2. The convergence curve of Sphere function
全局收敛曲线
全局最优适应值
200
400
600
800
[***********]00200030维
图3 Ackley函数优化曲线
Fig3. The convergence curve of Ackley function
全局收敛曲线
[1**********]00
全局最优适应值
10002维
[***********]00
10维
200
400
600
800
1000
30维
1200
1400
1600
1800
2000
图4 Rastrigin函数优化曲线
Fig3. The convergence curve of Rastrigin function
4 结论
为了开发蜜蜂搜索能力,蜜蜂搜索时引入自适应权重,其权重大小的确定根据蜜蜂收益进行动态调整,增强搜索目标性;同时引入不同于常规的边界设定方法,更好的保存群体的结构,增加种群的多样性;另外当蜜蜂收益连续几代不变时,采用柯西变异算子的方法变异更新当前最优位置,使蜜蜂及时跳出局部极值。对几个测试函数的优化结果表明,改进的人工蜂群算法精度明显提高,而且收敛速度加快。然后将改进的人工蜂群算法用于风电功率短期预测模型的参数优化,与常规交叉法相比,结果表明MABC的优化性能更好,拟合精度更高。
参考文献
[1] D. Karaboga, An idea based on honey bee swarm for numerical optimization, Technical Report-TR06, Erciyes University, Engineering Faculty, Computer Engineering Department, Turkey, 2005.
[2] Fahad S. Abu-Mouti, M. E. El-Hawary. Optimal Distributed Generation Allocation and Sizing in Distribution Systems via Artificial Bee Colony Algorithm[J]. IEEE TRANSACTIONS ON POWER DELIVERY,2011,26(4):2090—2101.
[3] Bahriye Akay, Dervis Karaboga. A modified Artificial Bee Colony algorithm for real-parameter optimization[J], Information Sciences. 2012,192:120—142.
[4]Dervis Karaboga, Bahriye Akay. A comparative study of Artificial Bee Colony algorithm[J], Applied Mathematics and Computation,2009, 214 :108—132.
[5]Leandro dos Santos Coelho ,Piergiorgio Alotto. Gaussian Artificial Bee Colony Algorithm Approach Applied to Loney’s Solenoid Benchmark Problem [J], IEEE TRANSACTIONS ON MAGNETICS,2011,47(5):1326—1329.
[6]Guopu Zhu, Sam Kwong. Gbest-guided artificial bee colony algorithm for numerical function optimization [J], Applied Mathematics and Computation.2010, 217 : 3166—3173.
[7]易正俊,何荣花,侯 坤 . 量子位 Bloch 坐标的量子人工蜂群优化算法[J], 计算机应用,2012,32(7) : 1935—1938.
[8]张长胜.多目标人工蜂群算法及遗传算法的研究与应用.东北大学出版社,2013 [9]杨淑莹,张桦.群体智能与仿生计算.电子工业出版社,2012.
[10]Szeto W Y, Wu Yongzhong, Sin C Ho. An artificial bee colony algorithm for the capacitated vehicle routing problem[J]. European J of Operational Research, 2011, 215(1):126-135.
[11]任子晖,王坚,高岳林. 马尔科夫链的粒子群优化全局收敛性分析.控制理论与应用,2011,28(4):462-466.
[12]曾建潮,介婧,崔志华.微粒群算法[M].北京:科学出版社,2004.
[13]朱晓荣,刘艳萍. 基于稳健估计时间序列法的风功率预测[J]. 电力系统及其自动化学报,2012,24(3):107—110.
[14]常 鹏,高亚静,张 琳,等. 基于EMD与时间序列法的短期风电场功率预测[J]. 电力科学与工程,2012,28(3):33—39.
[15][李俊芳,张步涵,谢光龙,等. 基于灰色模型的风速-风电功率预测研究[J]. 电力系统保护与控制,2010,38(19):151—158.
[16]师洪涛,杨静玲,丁茂生,等. 基于小波—BP神经网络的短期风电功率预测方法[J]. 电力系统自动化,2011,35(16):44—48.
[17]陈 宁,沙 倩,汤 奕,等. 基于交叉熵理论的风电功率组合预测方法[J]. 中国电机工程学报,2012,32(4):29—34.
[18]孔 强,姚建刚,汪梦健,等. 基于多重核学习支持向量机短期负荷预测研究[J]. 计算机工程与应用,2012,48(33):207—211.
[19]滕卫平,胡 波,滕 舟,等. SVM回归法在西太平洋热带气旋路径预报中的应用研究[J]. 科技通报,2012,28(11):49—53.
[20]杨 洪,古世甫,崔明东等.基于遗传优化的最小二乘支持向量机风电场风速短期预测[J]. 电力系统保护与控制,2011,39(11):44—48.