《基于反向学习的自适应α约束病毒种群搜索算法-李牧东.pdf》由会员分享，可在线阅读，更多相关《基于反向学习的自适应α约束病毒种群搜索算法-李牧东.pdf（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第49卷第3期2017年5月工程科学与技术ADVANCED ENGINEERING SCIENCESV0149No3May2017信息工程 DOI：1015961jjsuese201600292基于反向学习的自适应倪约束病毒种群搜索算法李牧东12，赵 辉1，吴利荣2，陈超2，李建勋2，韩 博3(1空军工程大学航空航天工程学院，陕西西安710038；2复杂航空系统仿真重点实验室，jE京100076；395994部队，甘肃酒泉735006)摘要：为了提高该算法求解约束优化问题的能力，提出一种新的约束病毒种群搜索算法。首先，提出自适应6c1evelEL较策略，以在算法的不同阶段充分利用可行个体与不可
2、行个体的有效信息；其次，为了进一步提高算法求解约束优化问题的收敛速度和搜索精度，针对算法的病毒扩散行为，提出了结合反向学习机制的搜索方程，以提高种群多样性并加速全局收敛。对CEC2006中13个约束优化函数的对比仿真结果表明，本文算法在搜索精度、收敛速度以及稳定性方面，相比于aSimplex算法、粒子群遗传算法算法、交叉人工蜂群算法算法以及约束改进差分进化算法算法具有明显优势。同时将该算法应用于无人机协同实时航迹规划约束优化问题中，通过仿真实验并与利用约束改进差分进化算法对这一问题进行求解的方法进行对比，验证了本文算法在规划效率、规避威胁等方面的优越性。关键词：病毒种群搜索算法；约束优化；自适
3、应6c1evelEL较策略；反向学习；无人机协同航迹规划中图分类号：TPl83 文献标志码：A 文章编号：20963246(2017)03014409Self-adaptive a-constrained Virus Colony Search Algorithm Using oppositio一based LearningLIMudon91，一，ZHA0 Huil，WULiron92，CHEN Cha02，LIJianxun2，HANB03f1School ofAeronautics and Astronautics，Air Force EngUniv，Xian 710038，China；2
4、Sciand Teehn01on Complex AviationSystems Simulation Lab，Beijing 100076，China；3PLA of95994，Jiuquan 735006，China)Abstract：In order to improve the performance for solving constrained optimization problems，a novel constrained virus colony search(vcs)algorithm was proposedFirstlyself-adaptive“一level comp
5、arison strategy was proposed to make full use ofthe feasible and infeasible solution atthe different stages ofthe algorithmThen，in order to improve the convergence rate and search ing precision for solving constrained optimizationproblems，the search equations based on opposition-based learning mecha
6、nism were designed for the process ofvirus diffusion in VCSIt wasmainly used to improve the population diversity and convergence of the algorithmFinally，the comparative experiments on thirteen CEC2006benchmark functions showed that the proposed algorithm possessed more distinct advantages on searchi
7、ng accuracy，convergence rate and stability compared with aSimplex algorithm，particle swarm-assisted genetic algorithm(PSGA)，crossover-based artificial bee colony(CBABC)andconstrained optimization based on modified differential evolution(COMDE)algorithmMeanwhile，compared with COMDE algorithm，the SUCc
8、essful application in unmanned aerial vehicles(UAVs)cooperative path planning constrained problem verified the superiority ofthe proposed algorithm in the aspects ofplanning efficiency and threats avoidingKey words：virus colony search algorithm(VCS)；constrained optimization；self-adaptive nlevel comp
9、arison strategy；oppositionbasedlearning；UAVs cooperative path planning随着实际科学与工程问题的不断复杂化，约束优化问题(constrained optimization problem，c0P)逐渐成为人工智能领域研究的热点11。如何在较好地处理约束条件的同时收敛至全局最优解是提高约束优化效果的关键21。目前针对约束优化算法的研究主要集中于智能优化算法和约束处理技术2个方面【31。在约束处理技术方面，常用的方法有罚函数法4、多目标优化法51、随机排序法61以及仅约束法【71等，其中，a约束法采用定义约束满意水平“的方法来确定
10、个体的满足约束收稿日期：20160328基金项目：国家杰出青年科学基金资助项目(71501184)作者简介：李牧东(1987一)，男，博士，工程师研究方向：智能优化理论与方法、无人飞行器总体技术E-mail：modern_lee163tomhttp：jsueseijournalscn http：jsueseSCUeducn万方数据第3期 李牧东，等：基于反向学习的自适应a约束病毒种群搜索算法 145的程度，同时通过定义a1evelEL较策略评价个体的优劣，以筛选出较优的个体，在允许的约束满意水平下有效地放大了约束区域，然而水平参数a的选取并没有考虑在算法不同阶段对可行个体与不可行个体的有效信息
11、的充分利用，且约束满意水平参数的设置存在一定的盲目性。而在智能优化算法方面，主要围绕如何提高现有算法的优化性能或设计出新型算法展开，如文献8】在研究遗传算法的基础上，通过提出的顺序选择策略、基于方向的交叉策略以及动态随机变异策略对其进行改进，提高了算法的收敛速度。Mirjalili箸j99】在设计并提出的灰狼优化算法(grey wolf optimizer，GWO)基础上，通过引入多目标优化处理技术，提出了多目标灰狼优化算法以处理约束优化问题。课题组通过研究病毒在细胞环境内感染寄主细胞过程中所表现出的扩散与感染现象于2016年提出了病毒种群搜索算法(virus colony search al
12、gorithm，VCS)【J。VCS算法是一种新型群智能算法，该算法在综合平衡算法的探索性能和开发性能的基础上，通过病毒扩散、寄主细胞感染以及免疫反应3个行为的相互作用，促使种群个体朝着全局最优解收敛。通过对40个不同类型的测试函数并与目前较为流行的8种算法比较，验证了其在收敛速度、搜索精度以及稳定性方面的优越性。虽然，文献10】中讨论了利用罚函数法处理3个工程约束优化问题的有效性，但算法并没有对多种复杂约束优化问题进行讨论。作者在前期研究的基础上，针对所提出的病毒种群搜索算法，结合机器学习中的反向学习机制和a1evel比较策略约束处理方法，提出了基于反向学习的自适应a约束病毒种群搜索算法(s
13、elf-adaptive aconstrained virus colony search based on oppositionbased learning，SaVCSOBL)，以拓宽病毒种群搜索算法的应用领域。首先通过自适应a水平参数，提高了算法在不同阶段对可行个体与不可行个体有效信息的利用程度；其次，针对VCS算法的病毒扩散行为，利用反向学习机制以进一步提高算法的搜索能力和收敛速度。1病毒种群搜索算法VCS算法主要包含3个策略：病毒扩散阶段中的高斯游走策略、寄主细胞感染阶段中的自适应协方差进化策略(evolutionary strategies with covariancematrix
14、 adaptation，CMAES)【llJ以及免疫反应过程中的筛选进化策略。从理论角度分析，第1个策略的设计主要是为了提高算法的探索能力，第2个策略则是主要加强算法的开发能力，第3个策略则是充分利用生存能力较差的个体以提高整体的搜索效率。1)病毒扩散。病毒种群印op在初始化后，根据高斯游走策略在种群个体位置附近随机扩散：Vpopi=Gaussian(G毛。l，T)+(rlG是。trEVpopi)(1)式中，gpopi为更新后种群的第i个(i=1，2，)个体，为种群规模，G&。为当前迭代次数g下的最优个体，Gaussian(G毛sl丁)为以ug嘲为均值，r=lg(g)g(Vpop，一G毛。)为
15、方差的高斯随机游走分布，1、r2为0，1间的随机数。2)寄主细胞感染。更新后的种群首先根据VCS算法的边界控制策略对个体进行边界控制，即对于超出搜索区间的个体进行重新初始化，其次利用贪婪选择策略选择较优的个体并替换种群场叩中相应较差的个体，而后结合CMAES策略，对寄主细胞进行感染交叉并产生新的种群Hpop。Hpop；=群。+鲜伊Gi (2)式中，G为个体元素服从均值为0方差为1的标准正太分布矩阵，曰为协方差矩阵C的特征向量，D为相应特征值，瑶。为五个较优个体的平均位置，盯为全局步长，参数的具体过程可参见文献1011，在这里不再赘述。3)免疫反应。在对上述过程中产生的种群进行边界控制和个体更新
16、后，由于寄主细胞免疫系统的作用，因此根据筛选进化策略，对病毒细胞中的较差个体和较好的个体分别采取不同的操作以提高病毒的免疫能力，如式(3)所示：f Vpopi”=VpOpk厂rand(Vpoph，厂Vpopi，J)，Prra。秭I Vpopi，“=Vpopi，J，else(3)式中，i、k、为种群个体下标，且互不相等，j(j-1，2，D)为个体第价元素，D为问题维数，rand和Jr为o，1之间的随机数，P。t(f)为第i个个体的选择概率，计算式为： Prra删)_掣(4)删)=二 ()V式中，rank(i)为第i个个体适应度值从小到大的顺序。最后通过边界控制和贪婪选择策略更新个体并选出适应度值
17、较好的个体，直到满足终止条件，输出优化结果。其中，边界控制策略如下：1 1 ifxi,|印，then Xf=瑚门办(Up-Low)+Low。万方数据146 工程科学与技术 第49卷其中，吻和Dw分别为搜索区间的上、下界，Xi,J为第价个体的第，维元素。图l给出了VCS算法的基本流程。l初始化、D、并在搜索区间内随机生成初始种群场甲l叫对于每个病毒个体，利用式(1)产生新的个体gpop 7 f病毒 扩散l边界控制，评价种群F乡甲并根据贪婪选择更新种群F锄，I阶段l对用式(2)产生新的个体坳叩? 茹高J边界控制，评价种群砀缈弃衰据贪婪选择更新种群堙坤J感染l根据式(1)计算算则概率脚I+对于更新后
18、种群中的病霉个体的元素，利 免疫用式(3)产生新的个体元素场嚼。” 反应I边烈空制，评价种群脚7，并根据贪婪选择更新种群懒lt否乏0图1 VCS算法的基本流程Fig1 Flow chat of VCS algorithm2口约束处理技术21约束优化问题约束优化问题一般由目标函数、等式约束、不等式约束以及变量边界等组成，如下：min f(x)stgj(x)0，-=1，2，p； ，“庇女(工)=0，足=1，2，留； 、。7lowf置upf，i=1，2，D式中，他)为目标函数，gO)为不等式约束，Jlz)为等式约束，萨l，X2，瑚为一个D维向量，low和印分别为x的下界和上界。一般情况下，式(5)等
19、式约束需要转换为不等式约束，即lh女(z)I一60 (6)式中，d为容忍因子，一般为正数。22满意水平，l满意水平函数肛一般可以定义为：p(x)=1，if gj(x)o且(劝o对所有f，； (7)Io s肛(工)1，otherwise从式(7)中可以看出，当解的满意水平小于1时，即为不可行解。式(5)中每个约束可以转换为1个分段线性方程：f 1，if gj(x)0；19，(x)=1一gj(x)bj，if0占，(曲bj； (8)I o，otherwisex)：1一I玩(力f仇，2f l玩(力lbk；Izh,( (9)叫2 1O,otherwiseLy J式中，6，和6七为2个正整数。因此，结合各
20、个约束条件的满意水平，解的满意水平可表示为：u(x)=蝉n以。肛)，Ph。(z) (10)23 a-level匕较策略伉约束处理技术主要采用0【一level比较策略来衡量个体的优劣，勘、厶和1、22分别为个体印叩1和场叩2的目标函数值和满意度，则当满足下式时，则认为个体场印1优于个体场叩2：f卢2式中，位0，1，当a=O时，式(1 1)中小于号心，(Vpopf)b严旦1广一 (12)，I-th,(Vpopi)bk=三I_万一 (13)式中，为种群场印规模。32自适应水平参数口在标准仅约束中，水平参数仅一般设置为1，虽然在多数情况下可以满足约束问题的求解。但是当可行域较小时，比如存在多个强等式约
21、束时，就必须通过调整a值而获得较好的解12。为了提高解的质量，万方数据第3期 李牧东，等：基于反向学习的自适应a约束病毒种群搜索算法 147必须在算法初期充分利用不可行解的个体信息，而在算法后期则需要加强利用可行解的个体信息，对此，文献12对0【的计算提出了如下公式：f p0,t=0；a=(1一卢)口“1+3，t(叫 ) ()，=1图4航路点严生过程Fig4 Generation process of flight point其中：=arccos(而ej,iP习si+l两Pji+碉lPr) (18)DisJ=Lj+lj-Lsr，=Ief+1斥HBref+l|_|，PrI(19)不等式约束和等式
22、约束条件主要采用文献20提出的关于威胁、机身性能等处理方法，即：gl-J器(一一机一栩一础)o(20)=i=l IIxj92m警(H(xj，Yj)+ZjHm。)0 (21)93=ma。，x(Sc厂o,j)0 (22)94=m哆q3jScj)0 (23)95 2嘴Aaj,i一。m“Io (24)grm拒a置x(d“n一慨一划l：)o，Vj,k (25)h-一m帐a置xI(L妒r+Fi，P)V，一(Lj,Pr+)V小f力(26)其中，o,i=-1537 7x 10。10毒一2699 7x 10。zJ+o421 1(27)岛=2506 310。9弓-6301 4x 10一zj-0325 7(28)S
23、c产_垒兰垒兰一 (29)(屯f+l-Xj,f)2+魄f+1-y川)2f arctan(AxAyj)，Ayjo；口l-arctan(AxffAyj)+瓦Ayo； (30)l arctan(AxjAy，)+7【，yf0，Axj0式中，91为威胁约束，(，y：，z：)为第i个半球形威胁的球心坐标，碰为威胁半径，为威胁个数；92为地形约束，H(xj,yj)荚j第，架uAV航路点0，)所对应的地面高度，风。为最大高度；93和94分别为爬升坡度和下降坡度约束；g，为最大转弯角约束，其中；Aaif-。，f+1一f为转弯角，amax为最大转弯角，且血i fi，+l屯i，叻，f可，I+1-yj。i；96为防碰
24、撞约束，drain为无人机间的最小间隔；h，为速度约束，通过优化速度变量v，以达到多架无人机同时到达目标点的目的；Lj,pr=慨一Pr|12；=圳P加，一酬：。其中，c为第，架uAV已经规划出的航路点个数；另外，飞行高度约束可通过SaVCSOBL算法的边界控制策略将坐标变量Z控制在安全飞行高度区间凰。feL，凰。feu内。则无人机协同航迹规划问题模型可概括为式(31)：min f(x，Y，Z，1，)=fit，J，z，-， 、stgj(x，Y，z，1，)0，-=1，2，6； L31 Jhk(x，Y，Z，1，)=0，k=1基于上述模型，通过与COMDE算法相比较，以验证SctVCSOBL算法求解多
25、UAVs协同实时航迹规划问题的有效性。设任务空间0，100】kmO，100kmx0，16】km内存在不同类型的12个威胁，探测半径R=10 km，UAV性能参数为amax=x2，夙afeL=001 km、皿afeu=5 km，Vmi。=50 ms，Vmax=300 ms，3架UAV起始点坐标分别为(90，95)、(2，20)和(5，92)，目标点为(46，49)，且起始飞行方向指向目标点，其中，有一个威胁覆盖UAV3的起始点。维度D=34=12，种群规模N=60，迭代次数25，靠。jn-1 km，m。=8 km。图5和6分别给出了在相同条件下两种方法3维和平面的规划结果。从图5和6中可以看出，
26、UAV3虽然在起始点探测到威胁，但两种方法均能快速跳出威胁，说明了本文所设计的问题模型的有效性，同时万方数据第3期 李牧东等：基于反向学习的自适应口约束病毒种群搜索算法 15lUAVl-UAV2一一UAV3口 Q(a)COMDE算法的3D飞行航迹一UAVl一一UAV2一一UAV3O Q(b)ScxVCS-OBL算法的3D飞行航迹图5两种算法3维规划结果Fig5 Planning results of two algorithms in 3D view1008060要402001。8。墓6。4。2。OO 20 40 60 80 100xkm(b)SaVCS-OBL算法的平面飞行航迹图6两种算法的
27、平面规划结果Fig6 Planning results of two algorithms in 2D view可以发现，相比于COMDE算法，SctVCSOBt39法在跳出威胁时能以较为平滑的航迹绕过地形障碍并逐渐搜索下一航迹点。另一方面，在图5和6中可以看出COMDE算法所规划出的航迹会出现无法及时规避威胁的情况，而SaVCSOBL算法所规划出的协同航迹均能有效规避威胁，且相比于C舡蝉法更为平滑。图7为两种算法的平均收敛曲线，从图7中可以看出，相比于COMDE算法，SaVCSOBL算法明显收敛较快，另外，COMDE算法在最大评价次数为1 500次时(迭代次数为1500+60=25次)，尚无
28、法收敛至较优解，而采用改进的ScWCSOBL算法则在较少评价次数时已收敛至较为理想的解。奇邑lOi璺鼎粤盖lOo 500 l 000 l 500评价次数图7收敛曲线Fig7 Convergence curves表5列出了两种方法的仿真结果，从表5中可以看出，COMDE算法在规划过程中由于产生了不必要的航路点而导致了3架UAVs总飞行距离及飞行时间大于利用SaVCsOBL算法所规划的结果，另外，COMDE算法虽然到达时间误差较小，但相比于ScWCSOBL算法明显较差，特别需要指出的是COMDE算法在上述实验设置的条件下无法有效规避威胁，也说明了利用S c【VCSOBL算法能有效处理所多UAVs协
29、同实时航迹规划问题。表5仿真结果Tab5 Simulation results5结论本文在前期提出的病毒种群搜索算法的基础上，O迹0航行E砸盎阢M加0万方数据152 工程科学与技术 第49卷针对约束优化问题，提出了基于反向学习的自适应a约束病毒种群搜索算法。通过对13个标准约束测试函数的仿真并与PSGA、CBABC、COMDE以及aSimplex约束算法相比较，说明了所提出的算法在有效提高种群多样性的基础上，能够以较快的速度收敛至全局最优解，且具有较好的搜索精度和稳定性。另一方面，通过将该算法应用与无人机协同航迹规划问题中，并与COMDE约束算法进行比较，从而进一步验证了本文所提出的算法对于求
30、解多机协同航迹规划这一实际约束优化问题的有效性。然而，在求解高维、窄可行域约束优化问题方面，仍需进一步的研究。参考文献：【l】Mezura-Montes E，Coello C AConstraint handling innatureinspired numerical optimization：Past，present and fu-tureJSwarm and Evolutionary Computation，201 1，1(4)：173-194【2】Bi Xiaojun，Zhang LeiDual population constrained optimization algorithm
31、 with hybird strategyJControl and Decision，2015，30(4)：7 1 5720毕晓君，张磊基于混合策略的双种群约束优化算法J】控制与决策，201 5，30(4)：7157203】Guo S M，Hsu P H，Yang C C，Tsai J S HConstrained minmax optimization via the improved constraint-activated dif-ferential evolution with escape vectorsJExpert Systemswith Applications，20 1 6，
32、46：336-3454Mellal M A，Williams E JCuckoo optimization algorithmwith penalty function for combined heat and power economic dispatch problemJEnergy，2015，93(2)：1 171 1-1 17185】Cai Z X，Wang YA multiobjective optimization based evol-utionary algorithm for constrained optimizationJIEEETransactions on Evol
33、utionary Computation，2006，1 0(6)：658_6756Rodrigues M D C，Lima B S L P，Solange GBalanced ranking method for constrained optimization problems usingevolutionary algorithmsJInformation Sciences，2016，327：71-90【7】Takahama T，Sakai SConstrained optimization by applyingthe n constrained method to the nonlin
34、ear simplex methodwitll mutationsJIEEE Transactions on Evolutionary Com-putation，2005，9(5)：437-45 18】Chuang Y C，Chen C T，Hwang CA simple and efficientreal-coded genetic algorithm for constrained optimizationJApplied Soft Computing，2016，38：87105【9】Mirjalili S,Saremi S,Mirjalili S M，et a1Multiobjectiv
35、e greywolf optimizer：A novel algorithm for multi-criterion optimizationJExpert Systems with Applications，2016,47：106-11910】Li M D，Zhao H，Weng X W，Han TA novel natureinspiredalgorithm for optimization：virus colony searchJAdvancesin Engineering Software，2016，92：65881 11 Hansen N，Miiller S D，Koumoutsak
36、os PReducing the timecomplexity of the derandomized evolution strategy with covariance matrix adaptation(CMAES)J】EvolutionaryComputation，2003，11(1)：1-1 812Wang L，Li L PFixedstructure H。controller synthesisbased on differential evolution with level comparisonJIEEE Transactions on Evolutionary Computa
37、tion，201 1，9(1)：120-12913Xu Q Z，Wang L，Wang N，et a1A review ofopposition-basedlearning from 2005 to 2012JEngineering Applications ofArtificial Intelligence，2014，29(1)：112141 Wei Wenhang，Zhou Jianlong，Tao Ming，et a1Constraineddifferential evolution using oppositionbased learningJACTA Electronica Sini
38、ca，201 6，44(2)：426-436魏文红，周建龙，陶铭，等一种基于反向学习的约束差分进化算法J电子学报，2016，44(2)：426-43615Yu K J，Wang X，Wang Z LConstrained optimization basedon improved teaching learning based optimization algorithmJInformation Sciences，2016，352：61-78【16】Dhadwal M K，Jung S N，Kim C JAdvanced particle swarnlassisted genetic algo
39、rithm for constrained optimizationproblemsJComputational Optimization and Applications，2014，58(3)：78180617Brajevic ICrossover-based artificial bee colony algorithmfor constrained optimization problemsJNeural Computing and Applications，2015，26(7)：1587-160118Mohamed A WConstrained optimization based o
40、n modi-fled differential evolution algorithmJInformation Sciences，2012，194：17120819Corder G W，Foreman D INonparametric statistics for non-statisticians：A step-by-step approachMNew Jersey：JohnWiley&Sons2009【20Fu Y，Ding M，Zhou C，et a1Route planning for unmannedaerial vehicle(UAV)on the sea using hybrid differentialevolution and quantumbehaved particle swarm optimiza-tionJIEEE Transactions on Systems，Man and Cybernetics：Part A：Systems，2013，43(6)：1451-1465(编辑黄b11)：蓍蛐警孟啦警L莉荆*罴一一叩唧吁淼蒜一二黧一啷胁擞一磊紫M外种il蕊一虹一黪爱燃万方数据