文档介绍:该【结合正交补空间反向学习策略的自然计算方法 】是由【科技星球】上传分享,文档一共【12】页,该文档可以免费在线阅读,需要了解更多关于【结合正交补空间反向学习策略的自然计算方法 】的内容,可以使用淘豆网的站内搜索功能,选择自己适合的文档,以下文字是截取该文章内的部分文字,如需要获得完整电子版,请下载此文档到您的设备,方便您编辑和打印。结合正交补空间反向学习策略的自然计算方法??黄亮,张军,季伟东(哈尔滨师范大学计算机科学与信息工程学院,哈尔滨150025)1引言自然计算(putation)通常代指从自然中获取灵感而发展起来的算法,主要研究领域包括人工神经网络,群体智能,进化计算,人工免疫系统等[1].自然计算方法具有自学习、自组织和自适应的特点,(ParticleSwarmOptimization,PSO)用于电力系统经济调度问题以优化燃料成本[2],将差分进化算法用于光电精跟踪系统以提高收敛速度与辨识准确度[3],将遗传算法用于求解标签印刷车间的排产问题以提高加工效率[4],将蚁群算法用于求解带时间窗的车辆路径规划问题以优化物流配送效率[5],并通过模拟不同的自然行为来设计候选解的迭代方式,,种群可能会陷入局部最优区域,,,如将种群分组[6]或对种群数据增加变异偏置[7,8]来增加多样性,将易陷入局部极值的算法与全局搜索能力强的算法结合来增强搜索能力[9],[10]等人将反向学习策略及柯西变异算子应用于粒子群算法,提出了基于反向学习的粒子群算法(Opposition-basedParticleSwarmOptimization,OPSO),算法在8个测试函数上相较原始PSO有所提升;在随后的研究中,Wang[11]等人改进反向位置的计算公式,扩大反向粒子搜索范围,,[12]等人将反向学习策略应用于竞争粒子群算法,在竞争过程中部分粒子利用反向学习更新位置;钱晓宇[13]等人由此启发,提出一种基于Solis&-YounPark[14]等人将反向学习策略与Beta分布结合应用于差分进化以提高算法收敛速度与搜索能力;Yu[15]等人将反向学习策略应用于差分进化以解决多任务优化问题;AzamAsilianBidgoli[16]等人基于反向学习差分进化提出一种二进制差分进化算法,[17]等人利用反向学习策略为萤火虫算法获得更好的初始种群并提高算法收敛速度;Yu[18]等人将反向学习策略应用于萤火虫算法以帮助个体跳出局部极值范围;周凌云[19]等人将正交实验设计与反向学习结合应用于萤火虫算法,[20][21]等人用混沌反向学习策略初始化种群解,,缺少探索粒子当前位置正交空间的能力,,提出一种新颖的反向学W⊥为一切与W中向量都正交的向量所成的集合,称为W在V中的正交补空间[22].,则V有直和分解V=W⊕W⊥[22].依据定理1,任何欧式空间V都可以分解为1个属于此空间的子空间W及其正交补空间W⊥.设线性方程组对应矩阵记为Am×n,此矩阵的行向量生成的向量空间记为R(A),此线性方程组的解所组成的空间记为N(A),则R(A)与N(A),设有线性方程组:(1)其对应矩阵:R(A)=c1a1+…+cmam,c1…cm∈R(2)R(A)共有r个线性无关向量.(3)其中c′1,c′2,…,c′m为a在式(2)(3)可得R(A)中的向量均正交于N(A)中的向量,特别的有r个R(A)中线性无关向量与n-r个N(A)中线性无关向量正交,则可得到n个线性无关的n维向量,并以此生成整个Rn空间,因此证得R(A)与N(A),根据种群当前最优解,计算其正交补空间的基(basis),,将问题解空间记为RD,种群最优解记为gbest=(g1,g2,…,gD),对应正交补空间记为gbest⊥.建立方程组:g1x1+g2x2+…+gDxD=0(4)可求得D-1个线性无关的解向量x1,x2…xD-1,应用Gram-Schmidt将解向量组正交单位化,得到gbest⊥内的正交单位化的解向量组u1,u2,…,uD-1,根据这组解能生成gbest⊥内的任意向量,且由u1,u2,…,uD-1,gbest可以生成RD内的任意向量,,一部分为gbest所在直线空间的信息,另一部分为gbest⊥空间信息,当群体陷入局部最优时,:s=g/G(5)(6)(7)(8)x⊥=(1-s)×g⊥+b×g,b~N(s,1)(9)其中g表示当前迭代次数,G表示总迭代次数,rand(-1,1)表示在[-1,1]上服从均匀分布的随机数,norm表示向量求模长运算,Mnorm表示gbest⊥空间内向量的最大模长,xmax、xmin分别表示解空间的取值上下限,g表示当前种群的最优解,由式(7)可知g⊥位于gbest⊥中,(9)式来计算反向解,迭代初期,生成的反向解接近gbest⊥空间,随着迭代进行,反向解散布在整个空间中,充分探索潜在最优解,,设问题维数D=2,gbest=[2,2],解空间取值范围为[-5,5].、,根据gbest计算其正交补空间的正交单位化的解向量组u1=[-,],根据公式(8)计算Mnorm=5,根据公式(6)、公式(7)生成gbest补空间内的随机个体,最后根据公式(9)(Opposition-BasedSolution,OPS),反向解多数分布在gbest⊥内,且模长较长,离gbest位置较远;当s值适中时,反向解分布在整个解空间,模长适中,充分探索空间中潜在的最优解;当s较大时,反向解多数分布在gbest所在直线空间,模长与gbest相似,,种群多样性强,后期侧重开发gbest区域,-,:,群体位置矩阵X等参数,计算个体对应适应度值f(X);=1toG;<Pc;(4)计算gbest⊥的正交单位化解向量组;(5)、(8)分别计算s、Mnorm;(6)、(7)、(9)计算N个当前gbest反向解,记为X⊥;⊥中的N个反向解进行越界处理;=1toN;;;;;;;算法1中G表示种群总迭代次数,rand表示在[0,1]上服从均匀分布的随机数,Pc表示使用反向策略的概率,依据文献[10]的实验结果,~,避免因超参数值的不同而导致的实验结果差异,采用原始反向策略的Pc值,即Pc=,对越界个体采用吸收墙的处理方式,,以matlab环境为例,,将其分别应用到标准PSO与标准遗传算法(icAlgorithm,GA)中,记为正交补空间反向学习粒子群算法(plementarySpaceOpposition-BasedLearningParticleSwarmOptimization,OCOPSO)及正交补空间反向学习遗传算法(plementarySpaceOpposition-icAlgorithm,OCOGA).仿真平台为Windows10,[10]进行对比实验,:学习因子c1=c2=,惯性权重线性减小,ωmax=,ωmin=,参数设置:,:种群数N=20,算法迭代次数G=1000,维数D=,其中f2~f6为多模函数,剩余函数为单模函数,因f13在30维上的最小值缺乏精准数据,暂定为-100作为衡量不同算法表现的标准,,取运行结果平均值与全局最小值的误差(mean)作为评价标准,计算20次运行结果的标准差(std),进行Friedman检验,,选取算法在多模函数f2、f4、f5及单模函数f1、f8、f11上的收敛图比较算法性能,,OCOPSO相较PSO、OPSO而言,在f1-f5、f7-f13、、f8、f14,、f13以外的函数上寻得解的精度均高于标准GA,但精度提升相较PSO并不明显,这是因为GA本身并不易于陷入局部极值,-f5多模函数,应用反向策略的算法寻得解的精度普遍高于原始算法,f6的全局极值点靠近解空间边界,且边界上存在许多局部极值点,OCOPSO前期大范围探索解空间,易陷入远离全局极值点的局部极值点,随着迭代进行探索范围减小,算法偏向开发当前群体最优点周边区域,,反向策略能帮助算法跳出局部极值区域继续搜寻全局最优解,而本文策略所生成的反向解相比OPSO生成的反向解更加多样化,能探索更大解空间范围,“没有免费午餐”定理,反向策略算法没能在所有类型函数上都寻得最高精度的解,但在大部分函数上其解的精度高于对比算法,且剩余函数上解的精度相近,,在相同的迭代次数时,OCOPSO不论在单模函数还是多模函数上均寻得精度高于PSO与OPSO的解,、f4、f8而言,对比算法收敛曲线在后期趋于平缓,而OCOPSO收敛曲线在后期仍有明显的下降趋势,说明正交补空间反向学习策略相比OPSO的反向学习策略改善种群多样性能力更强,,其收敛曲线在f2上呈阶梯状下降,在f2、f4、f8上末端仍有下降趋势,表明本文策略具有较强的探索能力,能加快算法收敛速度,,分别设置问题维数D=100、200,对PSO、OPSO、OCOPSO、GA、,因此选用剩余的14个函数作为测试函数,,,在D=100、200时,OCOPSO与PSO、OPSO相比在除f6、f13、f15的测试函数上均取得精度最高的解,OCOGA与GA相比在除f6、f13、,OCOPSO在f1-f4、f8、f10、f11、f14上均寻得精度相似的最优解,说明本文策略能应用于高维问题求解,,,在D=100、200条件下,将结合本文策略的算法运行时间绘制成图,,两种维度下OCOPSO相较原始PSO算法运行时间增加约5%~10%;OPSO相较PSO运行时间增加越200%~250%;OCOGA相比GA运行时间增加约20%~70%,特别的当D=200时,在f9~f11上运行时间增加近100%.OPSO运行时间高的原因在于其柯西变异算子计算复杂,,本策略更适用于PSO算法,并且能在略微增加运行时间的代价下寻得精度更高的解,,选用CEC13函数集作为测试函数[23],其中f1~f5为单模函数,f6~f20为多模函数,f21~,分别为OPSO[10]、GOPSO[11]、NCOPSO[24]、HCOPSO[25],其中OPSO及GOPSO为经典的基于反向学习策略的PSO算法,,为了弥补其缺点,将其与重心反向学习策略[26]及随机拓扑结构粒子群[27],将反向解限制在重心一定范围内,,随机拓扑粒子群往往优于固定拓扑粒子群[24],[24]计算如下:(10)(11)本文将结合两种反向学习策略的随机拓扑结构粒子群算法称为混合正交反向学习粒子群优化算法(HybridOrthogonalOpposition-BasedParticleSwarmOptimization,HOOPSO),为了验证本文策略的有效性,将结合重心反向学习策略的随机拓扑结构粒子群算法作为对比算法,称为重心反向学习随机拓扑粒子群算法(CentroidOpposition-BasedLearningStochasticTopologicalParticleSwarmOptimization,COSPSO).(12)(13)(14)其中l表示当前粒子的最优邻居粒子,:vid(t+1)=ωvid(t)+c1r1(pbestid-xid(t))+c2r2(lbestd-xid(t))(15)xid(t+1)=xid(t)+vid(t+1)(16)其中vid(t)、xid(t+1)分别表示第i个粒子在第t、t+1次迭代时d维方向上的速度与位置大小,pbestid表示第i个粒子的历史最优位置在d维方向上的大小,r1、r2为服从[0,1]均匀分布的随机数,ω、c1、,若当前最优解没有提升,则使用重心反向策略,,,种群邻居矩阵L,位置矩阵X,速度矩阵V,计算个体对应适应度值f(X),flag=0;=1toG;<Pc;==0;=1toN;;⊥粒子进行越界处理;=1toN;;;;,则flag=1;;(10)、式(11)计算X*;*的粒子进行越界处理;(X*);=1toN;;;;,则flag=0;;;(15)、式(16)式更新粒子的速度与位置;;,更新相应的pbest;