多目标进化算法总结

MOGA天是第t代种群中个体，其rank值定义为P:为第t代种群中全部支配工的个体数目适应值（fitnessvalue）安排算法:L将全部个体依照rank值大小排序分类；采用插值函数给全部个体安排适应值（从rankl到ranknN），一般采纳线性函数适应值共享rank值相同的个体拥有相同的适应值，保证后期选择时同一rank值的个体概率相同最终采纳共享适应值随机选取的方法选择个体进入下T弋一种改进的排序机制（rankingscheme）:向量H=（）%，、”4）和K=（）%「比较goalvector:”画…以）IfthenumberofexternallystorednondominatedsolutionsexceedsagivenmaximumprunePbymeansofclustering.CalculatethefitnessofeachindividualinPaswellasinP SelectindividualsfromP+户multisetunionuntilthematingpoolisfilled.Inthisstudybinarytournamentselectionwithreplacementisused.Applyproblem-specificcrossoverandmutationoperatorsasusual.IfthemaximumnumberofgenerationsisreachedthenstopelsegotoStep

2.FitnessAssignment:1外部群落eP赋值4«0，l称作strength和小尸的数量成正比3’”ns.=定义N+1适应值工2当前群落，£尸其中沱p适应值加1是为了确保外部群落的个体适应值优于当前群落这里适应值越小/被选中的概率越大smallfitnessvaluescorrespondtohighreproductionprobabilities聚簇缩减:InitializeclustersetC;eachexternalnondominatedpoint‘€尸constitutesadistinctcluster:C=U{{，}}.IfgOpStep5elsegotoStep

3.Calculatethedistanceofallpossiblepairsofclusters.ThedistancedoftwoclustersJandc2eCisgivenastheaveragedistancebetweenpairsofindividualsacrossthetwoclusterswherethemetricreflectsthedistancebetweentwoindividuals*anclinthisstudyanEuclideanmetricontheobjectivespaceisusedDeterminetwoclustersC|an^°2withminimaldistanced;thechosenclustersamalgamateintoalargercluster:C=C\{q，G}D{G°g}qqt0step

2.Computethereducednondominatedsetbyselectingarepresentativeindividualpercluster.Weconsiderthecentroidthepointwithminimalaveragedistancetoallotherpointsintheclusterasrepresentativesolution.优点SPEAIISPEA可改进点FitnessAssignment当P成员只有一个时尸中全部成员的适应值都是相同的会导致选择压力SelectionPressure降低SPEA退化为随机搜寻算法DensityEstimation群落分布太过稀疏，以至于许多成员之间不存在相互支配关系，这些成员所供应的信息非常有限假如能够添加密度信息，那么就能够更加有效地Effectively搜寻非支配成员聚簇Clustering方法只对P有效，而对P没有影响ArchiveTruncation聚簇算法会删减P中部分成员，这其中也极有可能包含了外部解outersolutions造成信息截断truncation不利于非支配解的集中SPEA2MainLoopInput:A/PopulationsizeNArchivesizeTMaximumnumberofgenerationsOutput:ANondominatedsetInitialization:Generateaninitialpopulation〃andcreatetheemptyarchiveexternalset:=

0.Set，=.Fitnessassignment:CalculatefitnessvaluesofindividualsinandEnvironmentalselection:allnondomiantedindividualsin匕and《toC+i.Ifsizeof儿exceedsNthenreduce心bymeansofthetruncationoperatorotherwiseifsizeof匕】islessthanNthenfull匕।withdominatedindividualsin4and£.Termination/If，之7OranotherstoppingcriterionissatisfiedthensetAtothesetofdecisionvectorsrepresentedbythenondominatedindividualsin儿.STOP!Matingselection:Performbinarytournamentselectionwithreplacementon匕।inordertofillthematingpool.Variation/Applyrecombinationandmutationoperatorstothematingpoolandsettotheresultingpopulation.Incrementgenerationcounter=+DandgotoStep

2.FitnessAssignment:IeIdenotesthecardinalityofasetStrengthvalue:=1{J17€+A7•用R（，）=ZS（j）Rawfitnessvalue:梃片+上.”力口入densityinformation采纳k-thnearestneighbormethod计算个体i所处环境的密度这里k的取值k=y[N^No将甘全部其他个体与个体i的距离全部计算出来，并升序排序，取第k个距离值，记作*（）Idensity:吠+2分母加2是为了保证°⑺1适应值*i）=R（i）+O（i）EnvironmentalSelection:Step3）与SPEA中有两点不同:

1、P中的个体数量始终保持不变

2、截断方法可以防止边界值被删除构造分三种状况争论1假如构造的外部群落成员数量正好满意要求，即构造完成；2假如外部群落成员数量偏少即।匕则从中选择NTE/I个支配个体dominatedindividuals进行填充;3假如夕卜部群落成员数量偏多，即N贝采纳archivetruncationmethod对匕”中成员进行剔除，直到

一、课程介绍《计算智能》课程对计算智能领域的主要算法进行介绍，重点争论各种算法的思想来源、流程结构、进展改进、参数设置和相关应用内容包括绪论以及进化计算、群体智能、人工免疫算法、分布估量算法、神经网络、模糊规律和多目标进化算法等并从工程应用及与其他人工智能争论方向相结合的角度争论人工智能的实际问题及其解决方法

二、教学内容

（1）计算智能简介

（2）计算智能典型方法.优化理论（2课时）

（1）优化问题

（2）优化方法分类a）非约束优化b）约束优化c）多解问题d）多目标优化e）动态优化问题.进化计算（9课时）

（1）进化计算导论

（2）遗传算法a）经典遗传算法b）交叉、变异c）掌握参数d）模式定理与积木块假设e）遗传算法的变体f）前沿专题（小生境遗传算法、约束处理、多目标优化、动态环境）g）应用

（3）遗传编程、进化规划、进化策略

（4）差分进化

（5）文化计算

（6）协同进化.人工免疫系统（6课时）1自然免疫系统2人工免疫模型克隆选择模型网络理论模型危急理论3免疫优化计算.群体智能3课时1粒子群优化2蚁群算法.多目标进化算法及应用6课时绪论主要的多目标进化算法多目标进化算法性能评价和问题测试集多目标优化的新进展应用实例经网络6课时1人工神经元2监督学习神经网络3非监督学习神经网络4径向基函数网络5增加学习6监督学习的性能问题

8.深度学习算法DeepLearning3课时

9.分布估量算法3课时

10.计算智能算法在各争论方向的应用6〜9课时争论计算智能算法在每个争论生的争论方向中的结合应用分为以下三种状况:=Ti=l…，攵；

1、可=攵+1…应；（）Lg）A（）:jWgJ

2、3二卜.闯；（%）当支配K时，选择此当此支配此时，选择果优点算法思想简洁，效率优良缺点算法简洁受到小生境的大小影响理论上给出了参数巴海的计算方法NPGA基本思想

1、初始化种群Pop

三、教材与参考书

1、著，谭营译.计算智能导论［M］.清华高校出版社［北京］.

2022.

6.

2、张军詹志辉.计算智能［M］.清华高校出版社［北京］.

2022.

11.

3、吴微，周春光梁艳春.智能计算［M］.高等教育出版社［北京］.

2022.

12.

4、段海滨，张祥银徐春芳.仿生智能计算.科学出版社［北京］.

2022.

1.

2、锦标赛选择机制随机选取两个个体％和工和一个Pop的子集CSComparisonSet做参照系若为被CS中不少于一个个体支配，而占没有被CS中任一个体支配，则选择占

3、其他状况一律称为死结Tie采纳适应度共享机制选择个体适应度工小生境计数NicheCount:-Z梃呼$九[]；d-c.z]，d—bswsShd=ysfuire共享函数〔°d皿共享适应度thesharedfitness:/£选择共享适应度较大的个体进入下一R优点能够快速找到一些好的非支配最优解域能够维持一个较长的种群更新期缺点需要设置共享参数需要选择一个适当的锦标赛机制限制了该算法的实际应用效果NPGAII基本思想

1、初始化种群Pop

2、Pareto排序非支配个体rank=0;其余个体rank二支配该个体的个体数目

3、锦标赛选择机制种群中任选两个个体七和9若“法（与）＜加欣（马），则选择占；若是侬欣⑺“以（毛），称为死结（Tie）采纳适应度共享机制选择小生境计数（NicheCount）:这里的Pop只包含当前一代里的个体，在NPGA中，计算见公式中的Pop包含当前一代以及已经产生的属于下T弋的全部个体最终，选择计数较小的个体进入下T弋在计算NichedCount之前还要对函数值进行标准化NSGA和简洁的遗传算法的不同点在于selectionoperatorworkscrossoverandmutationoperator是一样的不一样的共享函数4・，表示个体i和j之间的距离%皿是共享参数，表示小生境的半径小生境计数NicheCount共享适应值%最终采纳随机余数比例算法选择个体进行重新构造种群的基础优点优化目标个数任选非支配最优解分布匀称允许存在多个不同的等效解缺点计算简单度过高不具有精英保留机制需要预设共享参数5“NSGAU加入精英保留机制快速非支配排序方法FastNondominatedSortingApproach:支配计数〃〃支配解p的解数量支配解集3:解p支配的解集合计算出每一个解的叫和力，第一级非支配解勺二°单独放入一个集合;遍历成员q和逐步递减〃，，假如可以削减为0将p放入单独的集合Q构成其次级非支配解;重复步骤2直到全部成员全部分类完成Crowded-comparisonApproach计算集合I的长度，初始化；对每一个目标，采用目标值进行排序；给予边界点第一个和最终一个最大值，确保它们不会被剔除；循环计算其他点的crowdeddistance.其中J为非支配集合，”山〃表示第m个目标在第i个个体处的目标值/T/./T分别表示第m个目标的最大最小函数值值越小，越拥挤Crowded-ComparisonOperator:Jjfi“mtjrtmkrankJrtmkdivUincirJdixlancrReplacethesharingfunctionapproachinNSGA可以肯定程度上消退一下两点thesharingfunction太过于依靠共享参数，不简洁设定

（2）thesharingfunction时间简单度达到°（M）算法主循环

1、初始种群玲（），并采用binarytournamentselectionrecombinationandmutationoperators构建一个子代种群°（size=N）；

2、合并月和a记凡=A+Q）第t代合并”口0记K=对凡进行非支配分类，结果记作”=（不号…）循环计算crowdeddistanceofF1并入心对当前E进行crowdeddistance排序选择前匕川个成员并入匕।确保1心尸N采用binarytournamentselectionrecombinationandmutationoperators构建a+.进入下一次循环SPEACharacters:StoringnondominatedsolutionsexternallyinasecondcontinuouslyupdatedpopulationEvaluatinganindividualsfitnessdependentonthenumberofexternalnondominatedpointsthatdominateitPreservingpopulationdiversityusingtheParetodominancerelationshipIncorporatingaclusteringprocedureinordertoreducethenondominatedsetwithoutdestroyingitscharacteristicsSteps:GenerateaninitialpopulationPandcreatetheemptyexternalnondominatedsetP.CopynondominatedmemberofPtoP.RemovesolutionswithinPwhicharecoveredbyanyothermemberofP.。