几种多目标进化算法简介

多目标进化算法多目标进化算法1.绪论2.主要的多目标进化算法3.多目标进化算法性能评价和问题测试集4.多目标进化的新进展5.应用实例绪论-背景•进化算法(EvolutionaryAlgorithm，EA)已经广泛运用，发展较为成熟。•现实问题中，一般需要对多个目标同时进行优化，而这些目标往往是相互冲突的。•例如，企业生产中，产品质量，生产成本，生产效率之间的关系。•为达到总目标的最优化，对各个子目标进行折衷，于是就提出了多目标进化算法(Multi-ObjectiveEA，MOEA).绪论–进展•1967年，Rosenberg建议采用基于进化的搜索来处理多目标优化问题。•1984年，DavidSchaffer首次在机器学习中实现了向量评估遗传算法(VEGA)。•1989年，DavidGoldberg在其著作《GeneticAlgorithmsforSearch,OptimizationandMachineLearning》中，提出了用进化算法实现多目标的优化技术。•1997年，国际期刊《IEEETransitionsonEvolutionaryComputation》创建。•2001年以来，每两年召开一次有关多目标进化的国际会议EMP:EvolutionaryMulti-CriterionOptimization。绪论–问题描述假设有r个优化目标，则目标函数表示为：约束条件：任务：寻求目标集合，使得在满足约束条件的同时获得最优解12()((),(),,())rfXfXfXfX()01,2,,()01,2,,iigXikhXil()fX****12(,,,)nXxxx多目标优化算法1、MOGA(Multi-ObjectiveGeneticAlgorithm)2、NPGA(TheNichedParetoGeneticAlgorithm)/NPGA-II3、NSGA(Non-dominatedSortingGeneticAlgorithm)/NSGA-II4、SPEA(TheStrengthParetoEvolutionaryAlgorithm)/SPEA-II5、PESA(TheParetoEnvelope-baseSelectionAlgorithm)/PESA-II6、PAES(TheParetoArchivedEvolutionStrategy)帕累托（Pareto）最优解多目标优化的解称为Pareto最优解（1896年，VilfredoPareto）给定一个多目标优化问题，最优解定义为：其中，这里为满足约束条件的可行解集，称为决策变量空间（简称决策空间），向量函数将映射到，称作目标函数空间（ObjectiveFunction-Space,简称目标空间）。()fX*()()XfXfXopt:rf{|()0,()0;(1,2,,;1,2,,)}nijXgXhXikjlfnrVilfredoPareto意大利经济学家个体支配关系假设x和y是群体P中不同的两个个体，我们定义x支配（dominate）y，如果满足下列条件：（1）对所有子目标，都有x不差于y,（2）至少存在一项子目标，x优于y，即，使得此时，我们称x为非支配的（non-dominated）,而y为被支配的（dominated），记作()(),(1,2,,)kkfxfykr{1,2,,}lr()()llfxfyxy基于Pareto的基本流程1.初始化：种群P2.进化：利用进化算法EA，得到新种群R3.构造的非支配集Nset4.调整Nset（调整N的大小，Nset满足分布性要求）5.判断是否满足条件，是则输出结果，否则继续循环进化PR基本流程图产生初始种群P用EA进化P得新群体R构造P∪R的非支配集Nset调整Nset的规模并使之满足分布性要求满足终止条件P=Nset开始是否输出结果，结束小生境（niche）小生境是来自于生物学的一个概念，是指特定环境下的一种生存环境。生物在其进化过程中，一般总是与自己相同的物种生活在一起，共同繁衍后代。小生境技术的基本思想是将生物学中的小生境概念应用于进化计算中，将进化计算中的每一代个体划分为若干类，每个类中选出若干适应度较大的个体作为一个类的优秀代表组成一个群，再在种群中，以及不同种群之间，杂交、变异产生新一代的个体种群。小生境（niche）小生境计数（NicheCount）用来估计个体i所有邻居（小生境内）的拥挤程度其中，表示个体i和个体j的距离共享函数Sh,ijPopmShdij,dij1,()0,shareshareshareddShddMOGAFonsecaCM,FlemingPJ,GeneticAlgorithmsforMulti-ObjectiveOptimization,Formulation,DiscussionandGeneralizing.InForrestS,ed.OceedingsoftheFifthInternationalConferenceonGeneticAlgorithms,pagesSanMateo,California,1993.416~423MOGA-RankingMOGA-MainLoopDM:DecisionMaker.Todecidewhichofallofthenon-dominatedpointstochooseasthesolutiontotheproblem.MOGA–总结评价1.排序，分配rank值2.分配适应值fitnessvalue3.适应值共享sharing4.随机选择个体进入下一代优点：算法思想简单，效率高缺点：算法过于依赖共享函数的选择容易导致未成熟收敛理论上给出了参数的计算方法shareNPGAHornJ,NafpliotisN,GoldbergDE.ANichedParetoGeneticAlgorithmforMultiobjectiveOp-timization.In:ProceedingsoftheFirstIEEEConferenceonEvolutionaryComputation,IEEEWorldCongressonComputationalIntelligence,vol1.Piscataway,NewJersey,June1994.82~87NPGA-共享机制NPGA-SelectionNPGA–总结评价1.选择一定数目的个体之后2.利用交叉变异等方法产生一个新的种群3.并循环，直至达到一定条件结束优点：能够快速找到一些好的非支配最优解域能够维持一个较长的种群更新期缺点：需要设臵共享参数，比较困难需要选择一个适当的锦标赛机制NPGAIIErichsonM,MayerA,HornJ.TheNichedParetoGeneticAlgorithm2AppliedtotheDesighofGroundwaterRemediationSystems.In:FirstInternationalConferenceonEvolutionaryMulti-CriterionOptimization,2001.681~695NPGAII-RankingNPGAII-NicheCountNPGAII–总结评价1.Pareto排序，分配rank值2.采用锦标赛机制选择个体进入下一代，出现tie则使用共享机制3.计算个体的NicheCount，选择NC值较小的进入下一代1.相对而言，效率不错（SGA和ERS），但也不算很好2.不使用外部种群，精英保护机制类似于NSGAIINSGA和普通遗传算法的比较：1）采用相同的交叉、变异算子（crossoverandmutationoperators）2）不同的个体选择方式（thewaytheselectionoperatorworks）Beforetheselectionisperformed,thepopulationisrankedonthebasisofanindividual’snondomination.SrinivasN,DebK.MultiobjectiveOptimizationUsingNondominatedSortinginGeneticAlgorithms.EvolutionaryComputation,1994,2(3):221~248NSGAFlowChartNSGA-共享机制NSGA-性能评价优点：优化目标个数任选非支配最优解分布均匀允许存在多个不同的等效解缺点：计算复杂度过高不具有精英保留机制需要预设共享参数3OMN第一代多目标进化算法包括：MOGA、NPGA、NSGA1.基于非支配排序；2.基于共享函数，保持多样性；3.相对而言，思想较为简单；4.缺乏验证方法，没有标准测试函数。NSGAII1.对NSGA的改进版本。2.对于每一个解成员，都需要确定多少解支配它以及它支配的解集。3.估计围绕着种群中一个特定解的密度(density）。4.密集比较算子（Crowded-ComparisonOperator）既会考虑种群中的非支配解的rank值，也会考虑Crowdeddistance。5.其精英保留策略包含了最好的父代和子代。DebK,PratapA,AgarwalS,etal.AFastandElitistMultibojectiveGeneticAlgorithm:NSGA-II.IEEETransactionsonEvolutionaryComputation,2002,6(2):182~197NSGAII-SortingNSGAII-SortingCrowdedComparisonCrowdedComparisonNSGAII-MainLoopNSGAII-MainLoopNSGAII-MainLoopNSGAII-性能评价a.最优秀的多目标进化算法之一。b.新的快速非支配排序方法将计算复杂度降低到c.采用拥挤距离（CrowdedDistance）算法取代NSGA中的适应值共享方法，能够使当前Pareto前沿面中的个体能够扩展到整个Pareto前沿面，并尽可能的均匀分布。d.引入精英保护机制，选择后参加繁殖的个体所产生的后代与其父代共同竞争产生下一代种群，让更多更优的个体进入下一代，提高种群的整体进化水平。2OMNSPEACharacters:1.Storingnondominatedsolutionsexternallyinasecond,continuouslyupdatedpopulation2.Evaluatinganindividual'sfitnessdependentonthenumberofexternalnondominatedpointsthatdominateit3.PreservingpopulationdiversityusingtheParetodominancerelationship4.IncorporatingaclusteringprocedureinordertoreducethenondominatedsetwithoutdestroyingitscharacteristicsZitzlerE,ThieleI.MultiobjectiveOptimizationUsingEvolutionaryAlgorithms-AComparativeStudy.In:EibenAE,ed.ParallelProblemSolvingfromNatureV,Amsterdam,September1998.292~301SPEA-StepsSPEA-FitnessSPEA-ClusteringSPEA-总结1.Fitnessassignmentbasedonprinciplesofcoevolution（外部种群共同进化）2.ThenichingtechniquefoundedontheconceptofPareto