风驱动优化算法

第29卷第2期江苏科技大学学报(自然科学版)Vol. 29 No. 22015年4月Journal of Jiangsu University of Science and Technology ( Natural Science Edition )Apr.2015doi :10.3969/j. issn. 1673 - 4807.2015. 02.010风驱动优化算法任作琳'，张儒剑”，田雨波'(1.江苏科技大学电子信息学院,江苏镇江212003)(2.南京邮电大学海外教育学院,江苏南京210046)摘要:风驱动优化( wind driven optimization, WDO)算法是一种新兴的基于群体的迭代启发式全局优化算法.该算法是对物理学中大气运动的简单模拟,其概念清晰,高效易实现，且可调参数较少,鲁棒性强,寻优效率高,全局搜索能力较强,适用于解决多维和多模态问题,可以处理连续和离散优化问题.文中首先介绍了该算法的物理学基础,以及基本原理,并给出--些应用实例,最后对内容做出总结,并对该算法未来的研究提出了-.些建议.关键词:风驱动优化算法;群体智能;全局优化中图分类号:TP301. 6文献标志码: A文章编号: 1673 - 4807(2015 )02 -0153 -06Wind driven optimization algorithmRen Zuolin'，Zhang Rujian^ ，Tian Yubo'(1. School of Electronics and Information, Jiangsu University of Science and Technology ，Zhenjiang Jiangsu 212003 , China)(2. School of Oversea Education , Nanjing University of Posts and Telecommunications , Nanjing Jiangsu 210046 , China)Abstract : The wind driven optimization ( WDO) algorithm is a population -based iterative heuristic global optimi -zation algorithm. It is a simple copy of atmospheric motion in physics. WDO algorithm is easily understood withless parameters and better robustness，for multi- dimensional and multi +modal problems , which is also well -suitedfor problems with both discrete and continuous valued parameters. It is easy to execute and highly effective withfaster convergence speed and stronger ability for the global optimum . This paper presents the physical knowl -edge, and then a detailed introduction of WDO 's basic principle and its applications are covered. Finally, a briefconclusion and some suggestions for future research are given .Key words: wind driven optimization algorithm ; swarm itelligent ; global optimization智能优化算法具有全局的、并行高效的优化性rithm and its application to electromagnetic ”的论能、鲁棒性、通用性强、无需问题特殊信息等优点,文[2] ,标志着风驱动优化( WDO)算法的诞生.已经被广泛应用于计算机科学、优化调度、运输问风驱动优化算法是一种基 于群体的迭代启发题组合优化、工程优化设计等众多领域,并引起了式全局优化算法,该算法是基于对简化的空气质点国内外学者的广泛关注".美国宾夕法尼亚州立受力运动模型的模拟.其核心是研究空气质点在大大学电气工程系的Bayraktar Z和WernerDH博士气中的受力运动情况,应用牛顿第二定律并结合理以及气象学系的Komurcu M博士在2010年IEEE想气体状态方程,推导出空气质点在每一次迭代中Antennas and Propagation Society International Sym-的速度和位置的更新方程.该算法简单,易于实现,posium.上发表了名为“Wind Driven Optimization :可调中国煤化工局部极值寻找到最优( WDO): A novel nature Hinspired optimization algo-YHCN M H C问题，也可以处理连续收稿日期: 2014-10-15基金项目:国家自然科学基金资助项目(61401179)作者简介:任作琳(1991- -) ,女,硕士研究生,研究方向为智能算法及其应用. E-mail: lebaishi.2014@ 163. com通讯作者:田雨波(1971-),男 ,博士,教授,研究方向为优化算法在电子学和电磁学中的应用. E-mail :tianyubo@ just. edu. cn154江苏科技大学学报(自然科学版)2015年优化问题和离散优化问题.下述表达式对所有矢量普遍成立:相比于其他智能优化算法(如粒子群优化算d.A dA+QxA(5)法)该算法更新方程具有实际的物理意义,其全局dtd搜索能力较强,收敛速度较快,寻优效率高，鲁棒性式中A为某- -矢量.将式(2)代人式(5):强，且可以通过微调系数达到不同的优化拓扑结d.V._l.，+Qx}V。=构,应用前景十分广泛.目前国内刚刚开始关注.dt'WDO算法的研究,文中介绍了WD0算法的原理lt \(V+Qxr)+Qx(V+nxr)=和目前的研究情况,进而给致力于研究WD0算法dV的研究者们提供一- 些借鉴.+2(IxV)+nx(Q2xr)1风驱动优化算法式(6)中最后一个等号右边第- -项为相对于地球表面的加速度;第二项为科氏( Coriolis)加速1.1算法物理基础大气动力学是经典力学中牛顿定律在地球大度,只有当气块相对地表运动时(V≠0)才出现;气中的应用，大气运动和经典流体力学的一一个主要第三项为气块随地球旋转而具有的向心加速度,只区别是:大气运动是处于一个旋转的地球表面与气块位置(矢量r)有关,与其是否相对运动无.关.上31.众所周知,牛顿定律是在一个无加速度的坐标下面再分析式(1)右端项.在地球表面上,气系(即惯性坐标系)中处理质点加速度与质点所受块受到的力有:①气块与地球之间的牛顿万有引.作用力之间的关系.若将这些定律应用于非惯性旋力,可表示为g° ;②由于气压空间分布差异引起转坐标系中,就必须做一些相应的变化与调整.的气压梯度力- Vp/ρ,p为空气密度,p为空气压在一个无加速度的惯性坐标系(或称绝对坐强;③由于空气分子粘性引起的内摩擦力vV'V,v标系)中,一个单位质量气块运动的速度矢量以V.为运动分子的粘性系数,V”为拉普拉斯算子表示.按牛顿定律,它的加速度与所受到的力之间+ )。于是式(1)成为:0:的关系可以表达为:d.V。._= 2F(1)=g°-⊥Vp+vV°V式中:下标a表示绝对坐标系,F,为作用在气块上将式(6)代人上式,只在左端保留dV项,得'd的力.到:首先分析式(1)左端项.由于大气运动处于一=g°→_Vp+vV°V-2QxV个旋转的地球表面上,其运动的速度和加速度,从绝对坐标系(例如在恒星上)观察与从地球表面上Qx (Q xr)(8)观察是不同的,前者称为绝对速度和绝对加速度,这是在旋转地球上的坐标系即非惯性坐标系后者称为相对速度和相对加速度.中,气块加速度与作用在其上作用力之间的关系,设地球的旋转角速度为0,- -个物体或空气块即非惯性坐标系中的牛顿第二二定律.其右端前3项的绝对速度为V.,地球表面上观察的相对速度为仍保持原来的含义;第4项称为科氏力,在惯性坐V,则它们之间的关系为:标系中它本是物体的加速度,在非惯性坐标系中把V。=V+nxr(2)它看成为力,所以称其为虚拟力.科氏力与地球自式中r为气块的位置矢量,其大小为地心至气块重转轴垂直,并在北半球指向风矢量的右方.第5项心的距离,方向由地心指向气块.式(2)可以表示中国煤化工由于这个力只与位置为:有一看待,而是将其与引力TYHCNMHGd.r_ drQ xr(3)项，川，你一里力,所dt=dtg =g°-∩x(Q xr)(9)d.RdI+ QxR(4)Vp +g-20xV+vV°V (10)Htdt、式中R为气块相对地球转动轴的位置矢量.式(10)即是单位质量气块加速度与作用在其上作第2期任作琳,等:风驱动优化算法155用力之间的关系,亦即非惯性坐标系中的牛顿第二的科氏力F, 它代表在每一 -次迭代中,空气质点当定律.前所在维度中的速度和位置受其他任-.维度的影1.2算法基 本原理响.4个力具体简化方程如下:地球大气的成分和结构是很复杂的,大气的任Fpc =- V P8V(13)一-微小部分(空气微团)可以作为“点"来处理,称Fr =- pou(14)为空气质点4.根据以上得出非惯性坐标系中的Fc = pδVg(15)牛顿第二定律并结合理想气体状态方程,可以简化F。=-20 xu(16)模型得出风驱动优化算法.式中: - VP为气压梯度,负号说明沿梯度下降方1.2.1速度更新方程.向;δV为空气粒子的有限体积;a为摩擦系数,u为世界气象组织( WMO)对于标准大气的定义中风速度矢量,g为重力加速度矢量,02为地球旋转有这样的描述21 :假定空气服从使温度、压力和密角速度矢量.度与位势发生关系的理想气体定律和流体静力学将这4个力代人方程式(11)的右边,同时将方程.其中,大气处于流体静力平衡状态是指大气加速度公式a =代人式(11) 左边,得到:△在垂直方向上受到重力和垂直气压梯度力的作用并达到平衡.在建模过程中，研究者并没有完全模Au.ρ= (pδVg) + (- VP8V) + (- pou) +拟大气运动,忽略了平流层离心力等微小影响的作(-20 xu)(17)用力,简化了建模,主要考虑4个力作用,并且假设由于研究对象为无限小的空气质点,为了简化空气质点处于流体静力平衡状态,且满足理想气体模型令δV = 1,同时为了便于公式的推导,假定Ot定律(即理想气体状态方程).又由于地球自转以.= 1,得到式(18):及不同高度大气对太阳辐射吸收程度的差异,使得ρOu=(pg)+(-VP)+(-pou)+大气在水平方向比较均匀,而在垂直方向呈现明显(-20xu)(18)的层状分布.所以,大气运动中水平运动对空气质将式(12)代人式(18)得到:点的影响强于垂直运动,在研究WD0算法中,仅.P。|P。需关注风的水平运动.由于研究对象是无限小的空,Ou =|g- VP- pau +(-20xu)气质点,可以假设空气质点为单位体积.虽然研究(19)大气运动是在三维的世界里,但是算法应用可以映式中P2w为当前位置空气质点的压力数值,将式射到解决多维的问题中.简化的牛顿第二定律及理想气体定律方程式(19)左右两边同时除以，得到: .RT'如下:△u=g+-VPPeur'2T-xu+-20 x uRTρa= EF(11) .Peur(20)P=pRT(12)式中:a为加速度,p为空气质点的密度,F:为作用在风驱动优化算法中,空气质点速度和位置的在空气质点上的力,P为压强,R为理想气体常数,每一-次迭代都会发生改变,来探索新的搜索空间.因此,速度变量可以表示为Au = unew -uur,其中T为温度.由大气动力学知识可知,影响风吹动的主要力uw为当前迭代中空气质点的速度,uww为下一次有4个,分别是:①启动空气质点运动的气压梯度迭代中空气质点的速度.式(14)中,摩擦力的计算力Frc，其方向由高压区指向低压区;②与Frc作用应用的是当前迭代速度值uwr ,那么式(20)可以改相反的摩擦力F;需要指出的是,由于摩擦力的方写为:中国煤化工+ - VP, RT+程式较复杂,故在推导速度更新方程时应用另-种简化的表达方式;③垂直指向地心的重力Fc,在MYHCNM HG(21)物理学三维坐标系中假设地球的中心为直角坐标Pewr系的中心,那么可以认为重力是使空气质点移向坐根据重力定义,在一维坐标系[- 1,1]范围中标系原点的力,相似的将三维问题映射到N维中，(图1a))表示空气质点的重力Fc,则矢量g可以.重力代表指向坐标系中心的力;④地球旋转产生表示为g =| g| (0-xun).156江苏科技大学学报(自然科学版)2015年相似的由图1b) ,Frc方向为空气质点从高压程,第一项表示在没有其它力作用在空气质点上时,区指向低压区,即从当前位置指向最优压力点，那摩擦力会使其速度在原路径上减小.可以使用固定么-VP可以表示为-VP=|Pop-PI(xp-的摩擦系数a,也可根据具体问题选择自适应的摩xur),Peur为空气质点当前位置的压力值,Pu为种擦系数x, 实验证明a一般取[0.8,0.9].第二项表示群中目前为止找到的最优压力值,x为当前位置，空气质点从 当前位置按常数g成比例向坐标系中心xopm为最优位置.式(21)中g和- VP可以认为是靠近 ,实验证明其取值范围为[0.6,0.7].由于重力由矢量图(图1a)和b))表示的两个矢量,并非物的存在,一 定程度上避免了空气质点困在或跳出搜理定义的表达式,这样做的目的是为了简化方程，索边界 ,提高了全局搜索能力,加快了收敛速度.第将式(21)中g和一VP写成标量与方向乘积形式，三项促使空气质点移向最大压力点即全局最优位那么可以改写为:置,一般系数RT在[1.0,2.0]范围内.第四项模拟了Unew = (1 - a)uewr - gxeur +科氏力,提供了其它维对当前维内空气质点速度的RTp.._P1 (xx..)|+=2Q2x uRT影响,增强了算法的鲁棒性,一般认为c取[0.05,Peur3.6].(22)1.2.2 位置更新方程"GWDO算法是基于大气中空气质点运动的优化十方法,每-次迭代过程中都要更新空气质点的速度1cur和位置.已知速度更新方程式(24) ,不难得出位置更新方程如下:a)重力_FPoXnew = xeur+(UnewN)(25)0假设时间间隔为△t = 1.-1 XxomXeur对于每一维中的空气质点,其搜索位置范围可b)气压梯度力以根据具体问题进行设定,其更新速度也具有一定图1-维坐标系中重力和气压梯度力的范围,可以简单将速度值大小作如下判断:Fig. 1 Ilustration of the gravitational force and the pressureUmaxUnew > IUmaxUnew =(26 )gradient force in a one dimensional coordinate systemUnew < - LUumax由科氏力F。定义可知,它代表在每一一次迭代式中uma为速度边界值.中,空气质点当前所在维度中的速度受其他任- -维1.3 算法流程度的影响，这个速度用uauerdin来表示.文献[2]为为了描述方便清晰,表1列出了风驱动优化算了简化方程定义设置了常数c=-21 21 RT",使得法中用到的各个术语.式(22)可以表示为:表1风驱动优化算法相关术语及 其描述Unew = (1 - a)ucwr - gxcewr +Table 1 Terminologies used in the wind drivenRTucrerdim'1 Popr-Pew1 (xou -xr)|+optimization algorithm and its descriptions。PerPe术语描述(23)空气质点一个独立的个体,其坐标值代表当前优化文献[2]中用式(23)作为速度更新方程,会因问题的候选解群体-群预定数量的空气质点为引人压力值(Pour和Pn)而使更新后的速度变得非常大，从而降低WDO算法的可操作性.相对于式位置空气质点的坐标,其可被映射到当前优化问题的维度上(23)中使用的真实压力值,可以用i表示在所有空速度每次迭代中位置移动的变化量气质点中的一个降序排列,用来替换式子中的压力-个值，代表空气质点中国煤化工匹配程度司与其它优值(Pow和Po) ,而在xCon最优位置时压力值最小,可设为1 ,那么式(23)可以改写为:MHCNMHG数、成本函数以及罚函Unew = (1 -a)uur -gxeur +排列根据压力值在每次迭代中对空气质点的排cutenimRT'I-11 (xom -xw)+Clou(24)风驱动优化算法的流程如下:综上所述,式(24)为最后改进的速度更新方1)初始化群体规模,设置最大迭代次数,相关参第2期任作琳,等:风驱动优化算法157数(x,g ,RT,c) ,搜索边界以及定义压力函数(即适题,并将WD0算法与粒子群算法(particleswarm值函数);optimization ,PSO)、综合学习粒子群算法( compre-2)随机初始化空气质点，随机分配起始速度和hensive learming P0S , CLPSO)作了比较,实验证明位置;WDO算法的优化效果优于PSO算法和较复杂的3)计算当前迭代中空气质点的压力值(适值)，CLPS0算法,更加证实了WDO算法的简单易行且.并按照压力值将种群重新排列;高效的特性.文献[6]中应用WD0算法设计了两4):通过式(24)更新空气质点的速度;种微带天线,分别是E形微带贴片天线和加载短5)通过式(25)更新空气质点的位置;截线的倒F天线”.两个应用都证明了WD0算法6)若未达到终止条件，则转3).针对设计和解决复杂的电磁学问题是一种高效的最后一次迭代过程中的压力值被记为最优结优化工具.在吸波材料设计问题上,文献[2,5,8]果. - -般将终止条件设定为一一个 足够好的压力值(适应用WDO算法设计了用于WiFi使用的复杂的双应值)或达到一一个预设的最大迭代代数.图2为风驱面人工磁导体表面材料( double sided artificial mag-动优化算法流程.netic conducting , DSAMC),并与应用遗传算法( ge-开始netic algorthm , GA)算法设计的DSAMC作了比较,实验结果突出了WDO算法在电磁优化问题上的初始化:优越性,证明了WDO算法可以很好的解决离散优群体规模，最大迭代次数，相关参数，边界以及定义压力函数化问题.2.2 WDO 算法在图像处理问题中的应用随机分配起始位置和速度在图像处理方面,WD0算法也表现出了其强大的计算能力以及高效寻优的特性.图像分割技术评估每一个空气质点的压力值一是将图像分割成具有相似特性区域的过程,它是图像分析应用于模式识别和目标检测的领域中的一更新速度个重要步骤9.在卫星图像分割问题中，由于卫星图像的数据量大、特征信息丰富背景复杂,使得精更新位置确分割i卫星遥感图像是- -项极具有挑战的任务.若想高效准确的找出图像分割合适的阈值就不得不是否达到最大进行大量的计算,而传统的优化方法表现出了局限迭代次数?性.文献[ 10]应用WD0算法基于卡普尔熵寻找卫TY星图像分割中的多层次阈值，实验证明WD0算法结束对于解决多层次阈值优化问题是十分合适且高效图2风驱动优化算法流程准确的,为WD0算法在图像处理领域的应用提出Fig. 2 Flowchart of the wind driven optimization algorithm了一些方向,比如卫星图像增强,卫星图像分类以及其他卫星图像应用等.2算法应用2.3WDO算法在其他问题中的应用.风驱动优化算法是- -种新 型的全局优化算法,云计算是并行计算、分布式计算和虚拟技术相具有较强的鲁棒性,寻优效率高,既可以解决离散结合的产物,是当前计算机行业的技术热点，任务优化问题又可以解决连续优化问题.调度是云计算的核心技术之- - ,对云计算系统整体2. 1WDO算法在电磁学问题中的应用性能影响很大"。文献[12]基于微观经济学和电磁优化问题大多都是非线性、多极值和不可WDO算法对云资源调度分配方案进行了设计，其微的复杂问题,一-般的优化方法难以达到全局最应MH中国煤化工古合法对云资源分配进优+. WDO算法因具有较强的全局搜索能力,并且行C NM H G择出最优个体,其余候可以处理离散优化问题,故可用于优化设计电磁学选解依据Metropolis准则进行交叉、高斯变异操.中的问题,目前主要解决三大类问题:天线阵综合作,最后将进行过GA操作的候选解与最优个体整问题,微带天线设计问题以及吸波材料设计问题.合得到当前迭代结果.实验结果表明, WD0算法的文献[5]中WDO算法研究了线性天线阵综合问全局搜索能力较强.158江苏科技大学学报(自然科学版)2015年1689.3总结与展望Gao Qiang, Y an Dunbao , Yuan Naichang. A genetic -al-风驱动优化算法是一种新近提出的全局群智gorithm: Hbased AMC structure [J]. Acta Electronica Sin-ica ,2006 ,34 (9) :1686 - 1689. (in Chinese)能优化算法,该算法具有简单易实现、搜索效率高、收敛速度快等优点,文中对算法物理原理以及算法[ 5 ] Bayraktar Z，Komurcu M, Bossard J A, et al. Thewind driven optimization technique and its application基本原理做出了详尽的介绍，并将近几年来国内外in electromagnetics [J]. IEEE Transactions on Antennas对该算法的应用研究进行了细致阐述.and Propagation, 2013, 61(5): 2745 -2757.目前该算法研究正处于起步和发展阶段,随着[6] 刘式适,刘式达.大气动力学(上)[M].北京:北研究的深入, WDO算法必将在理论和实践应用上京大学出版社, 2011:1-10.取得新的突破,现对其未来研究提出几点展望:[ 7 ] Bayraktar Z, Komureu M, Jjiang Z H, et al. Stub -在算法理论研究方面:①算法的收敛性研究.loaded inverted - F antenna synthesis via wind driven对于任何优化算法,收敛性都是一一个基本的研究问opimization [ C] // Antennas and Propagation ( AP-题,目前风驱动算法还缺少收敛性的理论研究.②SURS. I. )，2011 IEEE International Symposium on ,IEEE. [S. l.]:IEEE ,2011: 2920 - 2923.算法关键参数的研究.目前算法参数的选择大多依[ 8 ] Bayraktar Z, Turpin J P, Werner D H. Nature- inspired据经验值选取,一- 些论文中给出了参数的选取范optimization of high -impedance metasurfaces with ul -围,但针对不同问题,参数选取的不合适，则会大大trasmall interwoven unit cells [ J]. Antennas and Wire-影响寻优结果.如何根据具体问题,自适应地选取less Propagation Letters, EEE, 2011, 10: 1563这些关键参数将是--个值得深人研究的内容.③1566.算法与其他算法或技术的结合.为了不断完善风驱[9]丁知平.基于混合智能算法的卫星图像分割技术研动优化算法的性能,增强其对不同问题研究的针对究[J].计算机测量与控制, 2012, 20(5):1420 -性,可以将其与成熟的智能优化算法或技术相结.1422.合,增强算法的寻优效率,同时也推进了对风驱动Ding Zhiping. Satellite image segmentation based on .优化算法的研究.hybrid itelligent algorithms [ J ]. Computer Measure-ment & Control ,2012, 20(5):1420- 1422. (in Chi-在算法实践应用研究方面:开辟风驱动优化算nese )法新的应用领域.与其他算法一样,应用是检验算[10] Bhandari A K, Singh V K, Kumar A, et al. Cuckoo法优劣的标准,是算法研究的价值体现.虽然WDOsearch algorithm and wind driven optimization based算法在电磁学领域应用广泛,但其在更丰富的工程.study of satellite image segmentation for multilevel应用中还未取得和其他智能算法一样的地位 ,研究thresholding using Kapur's entropy [ J]. Expert Systems该方法更广泛的实际应用将有着十分重要的意义.with Applications ,2014, 41(7): 3538 -3560.[11] 陈海燕.基于多群智能算法的云计算任务调度策略参考文献( References)[J]. 计算机科学, 2014, 41(6A) :83 - 86.[ 1 ]刘琼.智能优化算法及其应用研究[D].江苏无锡:Chen Haiyan. Task scheduling in cloud computing江南大学, 2011. .based on swarm intelligent algorithms [ J ]. Computer[ 2] Bayraktar Z, Komurcu M, Werner D H. Wind drivenScience ,2014, 41(6A) :83 - 86. ( in Chinese)optimization ( WD0): a novel nature -inspired optimi-[12] SunJ, Wang X, Huang M, et al. A cloud resource al-location scheme based on microeconomics and windzation algorithm and its application to electromagnetics[C] // Antennas and Propagation Society Internationaldriven optimization [ C] // ChinaGrid Annual ConferenceSymposium ( APSURSI), 2010 IEEE ,2010: 1 -4.(ChinaGrid) ,2013 8th IEEE. [S.1. ] :IEEE,2013: 34[3] 盛裴轩,毛节泰,李建国,等.大气物理学[M].北.京:北京大学出版社, 2003:30 -48, 168 - 169.[4] 高强，闫敦豹，袁乃昌.一种基于遗传算法的AMC中国煤化工(责任编辑:曹 莉)结构设计[J].电子学报, 2006,34 (9):1686 -YHCNM HG