多目标进化算法总结

《多目标进化算法总结》由会员分享，可在线阅读，更多相关《多目标进化算法总结（13页珍藏版）》请在装配图网上搜索。

1、MOGAx 是第 t 代种群中个体，其 rank 值定义为：irank (x, t) = 1 + p( t)iiP(t)为第t代种群中所有支配x的个体数目ii适应值(fitness value)分配算法：1、将所有个体依照 rank 值大小排序分类；2、利用插值函数给所有个体分配适应值(从 rank1 到 rank n* a,i当 y 支配 y 时，选择 y a b a3、Vj = 1,q; (y ),i g优点：算法思想容易，效率优良 缺点：算法容易受到小生境的大小影响 理论上给出了参数b的计算方法shareNPGA基本思想：1、初始化种群 Pop2、锦标赛选择机制：随机选取两个个体 x 和

2、 x 和一个 Pop 的12子集CS(Comparison Set)做参照系。若x被CS中不少于一个个体支配，而x没有被CS中任一个体支配，则选择x 。 223、其他情况一律称为死结(Tie)，采用适应度共享机制选择。个体适应度： fc)i小生境计数(Niche Count): m = hdij1pP1 d 一1-, d c共享函数：Sh(d) = bshare共享适应度(the shared fitness):选择共享适应度较大的个体进入下一代 优点：能够快速找到一些好的非支配最优解域 能够维持一个较长的种群更新期 缺点：需要设臵共享参数需要选择一个适当的锦标赛机制限制了该算法的实际应用效果

3、NPGA II基本思想：1、初始化种群 Pop2、Pareto排序：非支配个体rank=0;其余个体 rank=支配该个体的个体数目3、锦标赛选择机制：种群中任选两个个体 x 和 x ， 若 rank (x) rank (x)，贝选择 x ； 若是rank(x)= rank(x)，称为死结(Tie),12 采用适应度共享机制选择。小生境计数( Niche Count)：工 1 -= jePop (d、j 亍丿shareif d cijshare这里的 Pop 只包含当前一代里的个体，在 NPGA 中， 计算m公式中的Pop包含当前一代以及已经产生的 属于下一代的所有个体最后，选择计数较小的个体

4、进入下一代 在计算 Niched Count 之前还要对函数值进行标准化：O - O0 = ii ,min i 0 0i,max i ,minNSGA和简单的遗传算法的不同点在于 selection operator works， crossover and mutation operator 是一样的不一样的共享函数：i , j(dij匕 share0,if d ci, jshareotherwised 表示个体 i 和 j 之间的距离b是共享参数，表示小生境的半径share小生境计数(Niche Count): m =ltnorf tnerrucSdi jC)共享适应值：最后采用随机余数比

5、例算法选择个体进行重新构造种群的基础 优点：优化目标个数任选非支配最优解分布均匀 允许存在多个不同的等效解 缺点：计算复杂度过高（O（MN 3） 不具有精英保留机制 需要预设共享参数bNSGA II加入精英保留机制快速非支配排序方法(Fast NondominaedSorting Aproach):支配计数n :支配解p的解数量 支配解集 S ：解 p 支配的解集合1、计算出每一个解的n和S，第一级非支配解n二0,单独放入一个集合；2、遍历成员q和S，逐步递减n，如果可以减少为0，将p放入单独的集合Q,qq构成第二级非支配解；4、循环计算其他点的 crowded distance.3、重复步骤

6、2，直到所有成员全部分类完成。Crowded-comparison ApproachrQwdiig；dis tcuLGQas:? innent(T)Tiber of sDlutiais in Jfiw 翎ch l 曲斷也op = 0 fbr ch bbjcxtive tainitialize diFtaiKUZ m 淋lf(工 TH jusing each obj&cdveluefor 三 2 边(l - 1)so lhat boundaiy points irc alw-ays selcclcdfiM HI 4lKrTBlhaUjjMe =工4_12皿回+ 1刑-邛-WMU严-办严)1、计算

7、集合I的长度，初始化；2、对每一个目标，利用目标值进行排序；3、赋予边界点(第一个和最后一个:最大值，确保它们不会被剔除；I 口 = IMdis tancedis tance其中，I为非支配集合,+(Z b +1 .m -1 i - 1.m )/f max f minmml丄m表示第m个目标在第i个个体处的目标值,f max / f min 分别表示第m个目标的最大最小函数值 mm值越小，越拥挤Crowded-Comparison Operator: yi y j 讦(i j )dis tancedis tanceReplace the sharing function approach in

8、 NSGA 可以一定程度上消除一下两点：( 1: the sharing function 太过于依赖共享参数，不容易设定(2)the sharing function 时间复杂度达到 O2丿Non-dominatedsortingCrowding distance sortingF3QtR t算法主循环：1、初始种群 P ( size = N )，并利 用 binary tournament selection, recombination and0mutation operators 构建一个子代种群 Q ( si2、合并P和Q，记R = P + Q0size = N);000严 fast

9、uiated-sort (Jiji)= 0 and i 二 1until |JUi|+11J =耳+1i = i + lQi41 = nwike-Mw -pop/4i)carbine parent and offspring populatiDn F = (Zi?于*“、* 直Unaidfiminated florta of Jiruntil the parent population ie filled calculate crowding-distance in ” jnclucle ith iKrndotkhnarted (WiH iib paitnt pq clietk the nex

10、t frivt fbr iiKlu$iori sort in descending order using 叫口 chmee Ih亡 first (jV |；+山 dements of 片iwe sekrtioti. crcswver atfed umltian to treate a ikw popiibtiud Qg】increment the gcnerMim counter第 t 代：合并P和Q，记R二P+Qt t t t t对R进行非支配分类，结果记作F =（F,F ,）t 1 2循环计算 crowded distance of F ，并入 Pit+1（、对当前F进行crowded

11、distance排序，选择前（N-丨P I）个成员并入P，确保it+1t+1IP I二 Nt+1利用 binary tournament selection, recombination and mutation operators 构建 Qt+1进入下一次循环SPEACharacters:a) Storing nondominated solutions externally in a second, continuously updated populationb) Evaluating an individuals fitness dependent on the number of e

12、xternal nondominated points that dominate itc) Preserving population diversity using the Pareto dominance relationshipd) Incorporating a clustering procedure in order to reduce the nondominated set without destroying its characteristicsSteps:1) Generate an initial population P and create the empty e

13、xternal nondominated set P.2) Copy nondominated member of P to P .3) Remove solutions within P which are covered by any other member of P .4) If the number of externally stored nondominated solutions exceeds a given maximum N , prune P by means of clustering.5) Calculate the fitness of each individu

14、al in P as well as in P .6) Select individuals from P + P (multiset union), until the mating pool is filled. In this study, binary tournament selection with replacement is used.7) Apply problem-specific crossover and mutation operators as usual.8) If the maximum number of generations is reached, the

15、n stop, else go to Step 2.Fitness Assignment:1)外部群落i e P赋值S ，称作strength, 和j e P的数量成正比，i二j定义：s =i N +1适应值 f = s2)当前群落 j ePf = 1 +s , where f e1,N).jii其中i e P，适应值加1是为了确保外部群落的个体适应值优于当前群落这里适应值越小，被选中的概率越大( small fitness values correspond to high reproduction probabilities)聚簇缩减：1) Initialize cluster set C

16、; each external nondominated point i e P constitutes adistinct cluster: C = U1/.2) If 1 C V N, go to Step 5, else go to Step 3.3) Calculate the distance of all possible pairs of clusters. The distance d of two clusters c and c e C is given as the average distance between pairs of individuals acrosst

17、he two clusters1d =工 II i i III c 口 c I121 2 i1ec1,i2ec2. .where the metric II II reflects the distance between two individuals i and i (in12 this study an Euclidean metric on the objective space is used)4) Determine two clusters c and c with minimal distance d; the chosen clusters amalgamate into a

18、 larger cluster: C = C c,c oc Oc . Go to Step 2.1 2 1 25) Compute the reduced nondominated set by selecting a representative individual per cluster. We consider the centroid (the point with minimal average distance to all other points in the cluster) as representative solution.优点：02) Fitness assignm

19、ent：Calculate fitnessvalues of individuals inP and Ptt3) Environmental selection: Copy all nondomianted individuals in P and P tott4)Termination： If t、Tpool and set 丿 and go tot+1Step 2.SPEA IISPEA 可改进点：1) Fitness Assignment当 P 成员只有一个时， P 中所有成员的适应值都是相同的。会导致选择压力(Selection Pressure)降低，SPEA退化为随机搜索算法。2)

20、 Density Estimation 群落分布太过稀疏，以至于很多成员之间不存在互相支配关系，这些成员所提供 的信息十分有限。如果能够添加密度信息，那么就能够更加有效地( Effectively) 搜索非支配成员。聚簇(Clustering)方法只对P有效，而对P没有影响。3) Archive Truncation聚簇算法会删减P中部分成员，这其中也极有可能包含了外部解(outer solutions) 造成信息截断(truncation)，不利于非支配解的扩散。SPEA 2 Main LoopInput:N (Population size)N (Archive size)fT (Maxi

21、mum number of generations)Output:A (Nondominated set)1) Initialization：Generate an initial population P and create the empty archive (external set) P 0 . Set t = 0.ttP .If size of P exceeds N then reduce P by means of the truncation t+1t+1t+1operator, otherwise if size of P is less than N then full

22、P with dominatedt+1t+1individuals in P and P .or another stopping criterion is satisfied then set A to the setof decision vectors represented by the nondominated individuals in P . STOP!t+15) Mating selection： Perform binary tournament selection with replacement on Pt+1 in order to fill the mating p

23、ool.6) Variation ： Apply recombination and mutation operators to the mating P to the resulting population. Increment generation counter t +1Fitness Assignment:i e P o P1 口 1 denotes the cardinality of a setStrength value:Raw fitness value:S (i)=l j I j e P + P A iA jl R (i)=工S (j)jePt + Pt, jYi加入 de

24、nsity information,采用 k-th nearest neighbor method 计算个体 i 所处环境的 密度。这里k的取值：k = QN + N。将PUP所有其他个体与个体i的距离全部计算出来，并升序排序，取第k个距t离值，记作：b k。i1density: D (i)=分母加 2 是为 了保证 0 D(i) 1b k + 2适应值：F(i)= R(i)+ D(i)Environmental Selection:Step 3)与 SPEA 中有两点不同：1、P中的个体数量始终保持不变2、截断方法可以防止边界值被删除构造 PP = i i e P + P a F(i) 1t

25、 +1tt分三种情况讨论：(1) 如果构造的外部群落成员数量正好满足要求，即IP I = N，构造完成；(2) 如果外部群落成员数量偏少，即I P l N，则采用archive truncation methodt+1对P中成员进行剔除，直到I P I = N o一、课程介绍计算智能课程对计算智能领域的主要算法进行介绍，重点讨 论各种算法的思想来源、流程结构、发展改进、参数设置和相关应用。 内容包括绪论以及进化计算、群体智能、人工免疫算法、分布估计算 法、神经网络、模糊逻辑和多目标进化算法等。并从工程应用及与其 他人工智能研究方向相结合的角度讨论人工智能的实际问题及其解 决方法。1. 导论(1

26、 课时)(1) 计算智能简介(2) 计算智能典型方法2. 优化理论 (2 课时)(1) 优化问题(2) 优化方法分类a) 非约束优化b) 约束优化c) 多解问题d) 多目标优化e) 动态优化问题3. 进化计算(9 课时)(1) 进化计算导论(2) 遗传算法a) 经典遗传算法b) 交叉、变异c) 控制参数d) 模式定理与积木块假设e) 遗传算法的变体f) 前沿专题(小生境遗传算法、约束处理、多目标优化、动态环 境)g) 应用(3) 遗传编程、进化规划、进化策略(4) 差分进化(5) 文化计算(6) 协同进化4. 人工免疫系统(6 课时)(1)自然免疫系统（2）人工免疫模型a） 克隆选择模型b）

27、网络理论模型c） 危险理论（3）免疫优化计算5. 群体智能（3 课时）（1）粒子群优化（2）蚁群算法6. 多目标进化算法及应用（6 课时）5.1 绪论5.2 主要的多目标进化算法5.3 多目标进化算法性能评价和问题测试集5.4 多目标优化的新进展5.5 应用实例7. 神经网络（6 课时）（1）人工神经元（2）监督学习神经网络（3）非监督学习神经网络（4）径向基函数网络（5）增强学习（6）监督学习的性能问题8. 深度学习算法（Deep Learning） （3课时）9. 分布估计算法（3 课时）10. 计算智能算法在各研究方向的应用（69 课时）（讨论计算智能算法在每个研究生的研究方向中的结合应用）1、著，谭营译.计算智能导论M.清华大学出版 社北京.2010.6.2、张军,詹志辉.计算智能M.清华大学出版社北京.2009.11.3、吴微，周春光,梁艳春.智能计算M.高等教育出版社北京.2009.12.4、段海滨,张祥银,徐春芳.仿生智能计算.科学出版社北京.2011.1.