动态优化算法研究综述

动态优化算法研究综述

0动态优化问题的描述许多复杂现实世界的优化问题是动态的。例如，当新任务完成时，必须立即添加到当前的议程中。机器可能会崩溃并降低加工速度。原材料的质量正在变化。所谓的动态优化问题（dops）是指适应值函数、问题示例或限制条件变化的优化问题。动态优化问题可以包括如下。DOP={max(ormin)f(x,t)s.t.x∈X(t)⊆S,t∈TDΟΡ={max(ormin)f(x,t)s.t.x∈X(t)⊆S,t∈ΤS∈Rn,S是搜索空间;t:时间;f:S×T→R是目标函数;x是可行解;X(t)是在t时间可行解集合.动态优化问题的目标就是寻找一系列随时间变化的最优个体的集合X*={x*t},t∈T,满足f(x*t,t)≤f(x,t),∀x∈X(t)(对于最小化问题).尽管EA(evolutionaryalgorithm)解决静态优化问题取得了很好的效果,但传统EA并不能很好地解决动态优化问题,因为EA运行一段时间后会收敛到一个固定的解或者搜索空间的一个有限区域.正常而不是过早的收敛对于传统EA处理静态优化问题是必需的,但是,对于动态优化问题而言,一旦收敛,当新的环境到来时,EA就失去了探索新的区域所必需的多样性,从而不能跟踪到在新的环境下已经变化了的问题的最优解.在动态优化问题中,对不断变化的最优解的快速跟踪甚至比找到最优解本身更有意义.如果环境完全随机改变,就没有任何可以利用的信息,从零开始进行进化,将每一次变化的发生都作为一个新优化问题的开始无疑是最好的选择.但是这种简单的方法通常是不切实际的,其主要原因是:没有利用过去任何信息,每次小变化后都重新对问题进行求解;变化后的新问题同老问题一般是有关联的,新问题的解和老问题的解离得并不是很远;现实世界里,有些变化是循环变化的,因此重新使用过去获得的信息来指导现在的进化是有益的.近年来,动态优化算法的研究引起了越来越多研究者的兴趣,动态优化算法主要可以分为环境变化后增加多样性的方法、运行过程中始终保持多样性的方法、基于记忆机制的方法、多种群方法和基于预测机制方法5类.1可变局部搜索环境变化后增加多样性的方法是指一旦检测到了环境的变化,就使用外部方法来增加种群的多样性,从而使EA重新适应变化了的环境.这类方法典型的代表有超级变异方法(hypermutation),这是由Cobb提出的,当探测到环境的变化后立刻猛烈增大变异率,使得趋于收敛的种群发散.但是这种算法并不是对所有的环境都是有效的,因为,首先环境的变化并不能实时被察觉到,其次环境很小的变化可能很容易被跟踪到,不需要使用破坏性较高的高变异率来实现;另外,由于变异率在整个过程中是不可控的,会导致EA性能的降低.因此,Vavak等提出可变局部搜索(variablelocalsearch,VLS)方法,采用一种称为可变局部搜索的变异算子,当检测到环境变化后,变异率不是突然增大,而是逐步增大.对于分布估计算法(estimationofdistributionalgorithm,EDA),Yang提出了PBIL(population-basedincrementallearningalgorithm)算法的超级学习模式,用当环境发生变化时暂时的提高学习率来增加多样性.对于粒子群优化算法(PSO),文献使用了环境发生变化后能够增加种群多样性的方法.以上的这些方法有以下缺点:第一,环境变化的检测通常是不容易察觉的.在动态优化问题中,经常需要检测环境变化,如果能够假设环境的变化或多或少会引起当前解质量的下降,那么将监测整个种群性能或者累积平均最优解的退化作为环境变化的探测器.Branke采用了另一种略有不同的探测环境变化的方法,在算法运行的每一代,若干个个体都要被重新估值.如果其中至少有一个个体的适应值发生了变化,那么就可以认为环境也发生了变化.但如果在没有种群个体的地方出现变化,将无法检测到环境的变化.第二,不同程度地带有检测滞后性的问题,这样就使得一旦检测到了环境的变化,就使用外部方法来增加种群的多样性的方法并不能及时地对变化了的环境做出反应,从而不能有效地跟踪变化了的最优解.第三,用这类方法增加种群的多样性带有一定程度的盲目性.多样性的增加是以破坏前面的好解为代价的.因此,很难找到一种适当的多样性,而太多的多样性会导致种群类似于重新开始的策略,太少的多样性又不能有效地解决收敛问题.2保持多样性的方法2.1自组织随机移民为了避免种群收敛,必须保持多样性,使得算法能够随时适应变化了的环境,并尽快地跟踪到变化的最优解.Grefenstette提出一种随机移民的方法(randomimmigrantsGA,RIGA),即在每一代,种群中的部分个体都会被随机产生的个体所替代.这保证了每一代都有新的基因物质被引入到种群中,有效地避免了整个种群向一个小的搜索空间的区域收敛.RIGA不像超级变异的方法作用于整个种群,而是作用于一部分种群,不至于破坏整个进行的进程.RIGA已经成为一种动态优化算法的标准算法,经常用于和其他动态优化算法的比较.但RIGA也有一些缺点,新插入的随机个体可能会因为自身的适应度值比较低而在选择阶段就被淘汰了,导致不能使更多的基因物质引入.Tinós和Yang在RIGA的基础上提出了一种自组织随机移民算法(self-organizingrandomimmigrantsGA,SORIGA),在每一代中,SORIGA用一定数量的随机产生的若干个体,替换种群中最差的个体以及与其相邻(序号相邻)的个体.试验证明SORIGA呈现了自组织行为.当多样性较低时,一个个体被替换能引起许多其他个体的连锁反应,从而以一种自适应的方式增加种群的多样性,使EA不至于因为种群收敛到一个区域而难以适应环境的变化.Fernandes等使用了沙堆(Sandpile)变异算子,沙堆是一个运行在混沌和有序之间的自组织临界状态的复杂系统.沙堆变异算子不需要外在的机制对最优值的移动做出反应,它本身就增加了新的基因物质.变异率是以自我调节的方式增加的,而不需要了解环境本身的信息.自组织自适应方法对多样性的变化根据需要进行自动控制,势必会增强算法的性能,但是这类方法的设计相对困难.有导向的移民策略在处理一些动态优化问题时,表现得更加有效.比起RIGA,这些策略减少了基因物质引入的盲目性和对当前搜索进程的破坏性.这方面主要代表有:Yang提出混合移民模式(AHybridImmigrantsScheme)、基于记忆的移民模式(Memory-BasedImmigrants)以及基于精英的移民模式(Elitism-basedImmigrants).具有导向的移民策略对于解决某一类问题,比如剧烈变化的,变化后的最优值在原来最优值附近的,周期变化的问题等是有效的,但由于算法对动态环境是未知的,因此在缺乏动态问题先验知识的情况下,限制了算法在多种动态环境中的使用.2.2增加多样性方法Andersen提出了一种共享机制的动态优化算法,Cedeno等引入了共享和排挤机制能有效地控制相似个体的个数,使个体尽量地分散到搜索空间中,但排挤距离难以确定.Mori等提出的热动力GA(ThermodynamicalGeneticAlgorithm,TDGA)的核心思想是通过“自由能量”的变量F来直接控制种群的多样性.还有一些算法从改变个体配对模式出发,提出了有助于保持种群多样性的方法.这些方法改变了原有算法随机配对的模式,采用了非随机配对的模式来增加多样性.Fernandes等提出了适应性非同型配对GA(theAdaptiveDissortativeMatingGA,ADMGA),通过检测两个父体之间的海明距离是否满足一个能够自我调节的门槛值来决定是否配对产生下一代.试验证明在解决动态欺骗函数的问题上有很好的效果.非随机配对模式虽然在很大程度上保持了多样性,但是也存在计算量的增加影响算法性能的问题.Wang和Wineberg认为多样性增加(diversityenhancement)不是处理动态优化问题的根本原则,随之提出了进化性(evolvability)的概念,即进化性是个体适应环境变化的能力,并给出了进化性的度量方法,将进化性和适应值一起用于选择操作并基于此提出了进化性估计GA(Estimationofevolvabilitygeneticalgorithm,EEGA),通过试验证明了在动态环境中,EEGA比GA有较低的多样性却比GA有更好的性能.2.3多步算法保持种群多样性对于PSO,解决动态优化问题,多样性保持的方法也经常使用.Esquivel提出的一种混合PSO(hybridPSO,HPSO)方法中,采用了大变异操作,用以保证系统的多样性.Blackwell和Bentley提出了一种“带电粒子”PSO(chargedPSO,CPSO),它通过模拟带电粒子之间的排斥作用,防止种群收敛从而达到保持系统多样性的目的.文献将模拟退火算法中的基于概率的选择机制引入到PSO中,作为PSO算法的选择函数,以一定概率接收劣解,有助于多样性的保持.Hashemi等把细胞自动机嵌入到搜索空间中,利用各个细胞中包含粒子的多少来控制种群的多样性.Janson和Middendorf提出了分层邻域结构以保持多样性.Simões等受到免疫系统的启发,使用transformation算子,该算子操作是从基因库中随机选择一个基因段,移植到一个随机抗体中.对于EDA算法,Fernandes等使用了一种新的UMDA(univariatemarginaldistributionalgorithm)概率模型更新策略,旨在修正UMDA在采样生成种群过程中的多样性的丢失,从而延迟或避免了种群的完全收敛,提高了UMDA适应动态环境的能力.Wang等改进了原对偶遗传算法的原对偶映射模式,提出了一种基于统计机制的适应性原对偶映射模式,通过种群中所有个体各个基因位的统计信息决定各个基因位的映射概率,由映射概率决定该基因位是否参与映射.该映射模式保持了种群的多样性,文献,进一步提出了适应性基于概率的原对偶映射算子,该算子引入了Lamarckian学习机制,适应度值高的映射算子有更高的选择机会.Park等提出了一种对偶种群遗传算法(dualpopulationgeneticalgorithm,DPGA)用于解决静态优化问题,在文献中,他们对DPGA做了改进,提出了DPGA2算法,该算法使用两个储备种群,与主种群有不同的距离,通过生存选择控制来自两个储备种群的基因物质的流入,使得主种群保持足够的多样性来适应环境的变化.本节所提及的方法都从不同的角度上使得算法在运行过程中,始终保持多样性,这样一旦环境发生变化,算法能及时跟踪到变化的最优值.这类方法一般不需要检测环境的变化,因此避免了环境变化后增加多样性的方法中不能及时检测到环境变化的缺点,但是由于持续地关注多样性可能会减慢或阻碍优化进程.3保持稳定性作用于优化算法设计中.主要有20个自在EA中增加记忆的机制,能够很好地保存过去的信息,一旦环境发生变化,这些信息能够被重新使用,从而提高算法的性能.尤其是对于周期变化的环境很有效,当环境重新回到原来的环境时,存储的原来环境的最优解信息使EA很快回到最优值附近.另外记忆体中的解也可以起到保持多样性的作用.记忆机制大多和多样性保持机制一起使用,通常有两种记忆模式:隐式记忆模式和显式记忆模式.3.1多倍体法制备适合不同环境的算法隐式记忆模式利用了染色体的冗余表达,大多使用二倍体形式,Goldberg等提出了基于二倍体和基因显性机制的遗传算法,在动态背包问题的应用中,该方法比简单GA表现出更好的性能.Hadad等提出了多倍体的方法,多倍体的方法更适用于变化频率较高的环境.隐式记忆模式使得算法隐式的存储一些在运行过程中有用的信息,但是不清楚算法是否真的以一种有效的方式使用这些信息,隐式记忆模式可能更多的是利用冗余的表达降低收敛速度,使得种群的多样性增加,从而能较好的处理变化的环境.染色体的冗余表达的方法对于处理数目较小的几个环境状态之间振荡变换的情况下是有效的,但是对于大量环境状态出现的情况效果不是很好,因为在这种情况下需要的冗余代码会变长,算法性能降低,此外,由于对问题先验知识的缺乏(即到底有多少环境状态),染色体冗余代码的设计会变得困难.3.2基因概率向量的实验与研究显式记忆模式是引入额外的存储空间(记忆体)存储特定的信息并在后面的运行中重新引入到种群使用.Branke提出了显式记忆的一种直接记忆模式,经过几代后,最优解存储在记忆体中,当检测到环境发生变化时,再从记忆体中取回这些解到当前种群中,经过某种替换策略替换掉同等数量的个体.当最优个体重新回到原来的位置的时候,使用这种模式是有效的.但是当环境变化时,取出的记忆体中的信息可能是冗余的,从而影响算法的性能.Yang等在直接记忆模式上做了扩展,提出了一种联想记忆模式(associativememoryscheme).每隔几代,存储在记忆体中的不仅仅是当前种群最优解本身,还有与最优解所在的相关的环境信息,借鉴了EDA的思想.与最优解相关的环境信息用当时种群中所有个体基因座上基因所决定的等位基因概率向量来描述.这样,当环境发生变化时,将当前环境下的记忆体中的最好解对应的等位基因概率向量取出,利用该向量以类似于EDA中生成种群的方式生成一定数量的个体,用这些个体随机替换掉同等数量的当前种群中的个体.通过一系列动态问题的试验证明通常情况下在动态环境中,联想记忆模式优于传统的直接记忆模式.与直接记忆好解本身的方法不同,Richter和Yang最近提出了一种基于抽象的记忆模式(abstractionmemoryscheme),算法运行过程中,存储的不是好解本身,而是在搜索空间中好解的大概位置,构建了好解空间分布的概率模型,当环境发生变化时,根据这个概率模型产生出一定数量的随机个体插入到当前种群中,文中还探讨了动态优化中记忆和学习之间的关系.直接记忆模式中,并不清楚记忆体中存放的曾经出现的最优个体是与哪一种具体的动态环境相对应,一旦环境发生变化,就把记忆体中所有的个体引入到种群中的方法,带有一定的盲目性.Ramsey和Grefenstette较早提出的基于案例推理(case-basedreasoning)的记忆来处理动态优化问题的方法就减少了这种盲目性.作者提出一种能表征不同变化环境特征的方法,用基于案例推理的方法来映射这些变化的环境和找到的最优个体之间的关系.当环境变化后,这些映射信息再用来确定变化后的环境并把和这个环境相关的最优个体引入到当前种群中.和以上方法的思想相类似的,Karaman提出了记忆索引EA(thememoryindexingevolutionaryalgorithm,MIEA)来解决0-1动态背包问题.利用问题的特定信息来定义不同的环境,为每个环境进行编号.记住新的环境出现之前的前一个环境的信息,这个信息是由当时种群的等位基因概率向量来描述,每当环境发生变化时,若检测到新环境与过去某个编号的环境一致,则使用和该编号环境对应的等位基因概率向量来初始化种群,产生的个体替换掉老种群中部分个体再进行演化.当新出现的环境与过去所有的环境都不一致时,再使用超级变异的方法.基于案例推理的记忆方法和使用记忆索引的类似的记忆方法的关键是如何表征环境信息.当环境变化是可以度量的情况下,这些方法才是可用的.Bendtsen和Krink提出了一种动态记忆模型(dynamicmemorymodel,DMM),和传统的基于记忆机制的方法不同,这种模型的记忆体自身能够跟踪动态环境的变化,并能够进行自我调整.通过对移动峰问题和温室效应问题的试验,证明了DMM优于传统的静态记忆模式.但是当问题域很大的时候,使用记忆体中存储随机候选解的方式就不适合了,因为可能只有记忆体中的少数候选解有更新调整的机会.对于EDA,Yang在文献中分别把记忆机制引入了UMDA和PBIL中,Yang和Yao把联想记忆模式引入了PBIL中.Wang等在PSO中使用了记忆的机制.4标准动态测试方法多种群方法主要应用在一类多峰函数动态优化问题上,动态性体现在峰的位置.高度和宽度会随着时间发生变化.标准动态测试问题有移动峰问题(movingpeaksproblem,MPB).4.1最优值的搜索多种群方法中,一般把种群分为搜索种群和跟踪种群,搜索种群用于寻找最优值,跟踪种群用于跟踪可能的变化.Branke等提出的自组织侦察群SOS(self-organizingscouts)方法中,主种群用来搜索最优值,一旦主种群发现了一个新的峰,就会产生一个新的子种群跟踪这个峰值的变化.Ursem提出了多种族GA(multi-nationalGA),每个子种群兼有搜索和跟踪的功能,当一个子种群发现一个新的最优值,就会分成两个子种群用来保证每个子种群在同一时间仅仅跟踪一个最优值.Oppacher等提出一种漂移平衡算法(shiftingbalanceGA,SBGA),一个大种群称为核心种群,同时有多个小种群称为小殖民地种群.核心种群用于跟踪最优值的变化,小殖民地种群用于探索不同的区域,小殖民地种群保证在核心种群之外,核心种群接收来自小殖民地种群搜索到的最优个体.4.2多种群方法的使用近年来多种群方法更多地出现在了PSO解决动态优化问题上,Parrott和Li在文献中使用了物种(species)的概念,定义为使用欧式距离或是海明距离度量的相似粒子所形成的群组.物种种子(speciesseeds)是物种的中心.通过算法确定种群中的哪些个体是物种中心,并以一定距离rs为半径形成对应的物种,由算法得到的物种中心,不仅是物种距离的中心,而且还是该物种中的最优粒子.这样使用PSO的lbest模型更新每个粒子的速度和位置.算法能自适应调整多个物种在搜索空间的分布,跟踪变化了的多个全局或局部最优解.Blackwell和Branke把种群分成一系列相互作用的子种群,使用了排斥(exclusion)算子实现局部交互,当两个子群离得太近时,具有较低适应值的种群重新初始化,还使用反收敛(anti-convergence)算子实现全局交互,当所有的子群都收敛时,初始化其中最差的种群,以期持续寻找更好的新的峰.Li和Yang也是使用多种群PSO用来跟踪多峰问题,一个父群用具有较好的全局搜索能力的快速EP(evolutionaryprogramming)保持多样性,在整个搜索空间中探测有希望的区域,另外,多个子群用快速PSO算法搜索局部最优解.Yang使用了分层聚类的方法(hiterarchicalclustering)把种群分成多个子种群,该方法的好处是子种群初始粒子依据在适应值曲面(fitnesslandscape)的分布自动产生,而不是依赖于像k-means聚类方法中的参数k.Mender等在差分演化(differentialevolution)上使用了多种群方法.武燕等把多种群的思想引入了UMDA.多种群方法中各个子种群能有效地分开和避免多个种群寻找相同峰的情况出现是两个关键的问题.多个子种群独立地处理搜索空间不同的区域,因此能够在新的最优值出现时及时跟踪,并且由于多种群的存在还保留了大量过去搜索到的最优值,即保留了搜索空间中若干个有希望的区域的信息,使得算法能有效处理重新出现的动态环境.因此多种群方法也被认为是一种多样性保持和自适应的记忆策略.多种群方法是解决动态优化问题的一种非常有效的方法,尤其适合适应值函数多峰或者有竞争峰(competingpeaks)的情况,但是太多的种群会减低搜索的效率,为了有效分离各个子种群而进行的大量计算也会影响算法的效率,另外,分离各个子种群经常用到的拥挤半径的参数的选取比较困难.5消除不确定性的预测近年来,基于预测机制的动态演化算法引起了越来越多的关注,预测未来时刻环境状态,根据预测做出外部决策,使得EA提前为变化的环境做准备,从而提高EA在动态环境下的适应性,不至于在环境突然变化时候,EA性能突然减低.目前,用于动态优化问题的基于预测机制的算法如下.Branke等在动态工作调度问题上,通过外在地搜索更能灵活地适应新工作到达后的环境变化的解而达到预测的目的.灵活性可以通过避免较早的机器空闲时间来获得,因此EA中加入了惩罚较早空余时间的措施.这种方法是面向特定问题的,不能推广到一般的问题中.为了研究在更一般意义上预测用于动态优化问题,Bosman从理论上讨论了对于时间相关的问题,在某一时间做出的决定可能会影响到未来能获得的最优值.他得出了一种结合机器学习、统计学习和进化计算的算法框架.通过机器学习和统计学习技术进行未来情况的预测.随后还在随机动态问题上做了讨论.受到Bosman的启发,Simões等使用具体的统计学习方法进行预测,线性回归用于预测下次环境发生变化的时刻,马尔可夫链用于预测下次环境变化可能的状态.两个预测模型都使用了过去的信息来构建相应的预测模型.算法引入了记忆机制来存储过去的信息.在预测的环境变化时刻之前,种群就引入更能适合未来环境状态的信息,从而适应变化的环境,提高算法的性能.该算法主要的局限性在于使用线性回归来预测何时发生环境变化,仅适用于某种模式的变化,对于更加复杂的变化模式,线性回归预测就会有较大的误差,而导致算法性能的降低.随后,Simões等在文献中进一步讨论了非线性回归预测模型的情况.如果最优个体在搜索空间中的移动是遵循一定的运动模型的,那么使用预测技术预测下一刻最优个体的位置,把搜索过程导向新的最优个体最有可能存在的区域,有助于及时跟踪变化了的最优个体.Rossi定义了最优值的状态包括最优值的位置和速度,使用卡尔曼滤波技术估计系统未来的状态并计算估计误差,两者分别称为预测和准确度.EA可以通过测量获得过去最优值状态,并结合相应的运动模型,使用卡尔曼滤波技术得到未来最优值的估计值,文中提出了EA可以通过3种技术使用这个估计值作为外在的信息加入到EA中,从而提高EA跟踪移动最优值的能力.第一种是修改遗传算子,第二种是使用修正的适应度值函数,第三种是使用优异个体方式.3种不同的技术其实都是使得搜索向未来最有可能出现最优值的区域移动,从而提高了在动态环境下算法的适应能力.但该算法仅适用最优个体在搜索空间运动模型是线性具有高斯噪声的情况.Stroud从个体的适应值在动态环境下存在不确定性的角度提出了一种新的算法,扩展卡尔曼GA(Kalman-extendedgeneticalgorithm,KGA),动态环境中个体的适应值有两种不确定性,一种是环境的变化造成的不确定性,一种是评价个体适应度值时造成的不确定性.第一种不确定性可以类似于卡尔曼滤波中的过程噪声,第二种类似于观测噪声.这两种不确定性可以通过重新评价已存在的个体(观测)而减低.针对两种不同的情况,KGA包含了两种不同的卡尔曼协方差和适应值估计的更新方式.通过卡尔曼技术对动态环境下个体适应度的两种不确定性的预测来达到使算法适应不断变化了的环境的目的.vanHemert等提出了使用元学习来预测环境的下个状态.使用两个种群,当前种群和未来种群,用两个具有同样参数的GA演化,未来种群中的个体评价使用由元学习预测的适应度值函数.每经过固定的代数,未来种群中一定数目的个体拷贝到当前种群中,去掉超过种群大小的多余的最差的个体.通过这种方法,当前种群为未来环境变化做好了准备.通过挖掘过去每一代最优值信息,回归一个函数来预测未来的状况.如果预测准确,使用预测方法会大大增加算法的性能.然而,使用统计学习的方法进行预测需要大量的训练数据.一方面,大量训练数据的获得需要通过长时间运行得到,降低了算法的效率;另一方面,可能会得到错误的训练数据,从而引导种群在一个没有希望的区域演化导致更为恶劣的结果.另外,学习模型的选择也是关系预测准确与否的重要因素,而遗憾的是,EA由于本身的算法特点,对外界环境信息是未知的.对于选择何种学习模型对算法而言存在一定的盲目性,从而使得算法不能适应多种多样的环境变化.如果能获得更多的关于问题本身的先验信息,对于不同的问题选择不同的学习模型将会使基于预测的方法更加有效.6其他优化算法传统的演化算法一般都是针对静态问题的,然而现实世界很多问题都是动态的.静态环境下的演化算法由于自身在运行过程中不断收敛到最优值附近,多样性丧失,一旦环境发生变化就很难跟踪到变化的最优解.因此,多样性的增加