《多目标进化算法总结》由会员分享，可在线阅读，更多相关《多目标进化算法总结（24页珍藏版）》请在金锄头文库上搜索。
1、MOGAx 是第 t 代种群中个体，其 rank 值定义为： irank (x, t) = 1 + p( t)iiP(t)为第t代种群中所有支配x的个体数目 ii适应值(fitness value)分配算法：1、将所有个体依照rank值大小排序分类；2、利用插值函数给所有个体分配适应值(从rankl到rank n* g )A(y g )a ,ii当 y 支配 y 时，选择 y a b a3、Vj = 1,q； (y g )a, jj当 y 支配 y 时，选择 yb a b优点：算法思想容易，效率优良缺点：算法容易受到小生境的大小影响理论上给出了参数&的计算方法shareNPGA基本思想：1、初
2、始化种群 Pop2、锦标赛选择机制：随机选取两个个体x和x和一个Pop的 12子集CS(Comparison Set)做参照系。若x被CS中不少于一1个个体支配，而x没有被CS中任一个体支配，则选择x。 223、其他情况一律称为死结(Tie)，采用适应度共享机制选择。个体适应度： fi小生境计数(Niche Count)： m =丫ShdC,j)_1jwPop1-,d a共享函数：Sh(d) = bshareshare0,dbshare共享适应度( the shared fitness)：选择共享适应度较大的个体进入下一代 优点：能够快速找到一些好的非支配最优解域能够维持一个较长的种群更新期
3、缺点：需要设置共享参数需要选择一个适当的锦标赛机制限制了该算法的实际应用效果NPGA II基本思想：1、初始化种群 Pop2、Pareto排序：非支配个体rank=0；其余个体2“山=支配该个体的个体数目3、锦标赛选择机制：种群中任选两个个体x和x ,12则选择 x ；1若 rank (x ) rank (x ),12若是rank(x )= rank(x ),12称为死结(Tie),采用适应度共享机制选择。小生境计数( Niche Count)：工 1 -= jePop (shareif d oijshare这里的Pop只包含当前一代里的个体，在NPGA中，计算m公式中的Pop包含当前一代以及
4、已经产生的 i属于下一代的所有个体最后，选择计数较小的个体进入下一代在计算 Niched Count 之前还要对函数值进行标准化O - O:ii ,minO - Oi ,maxi,minNSGA和简单的遗传算法的不同点在于 selection operator works， crossover and mutation operator 是一 样的不一样的共享函数：Sh C )=i, j1-r d )2 share 丿0,if d Gi, jshareotherwised 表示个体 i 和 j 之间的距离 i , ja 是共享参数，表示小生境的半径share小生境计数（Niche Count）
5、： m =工ShdC,j）_ij ecurrentfront共享适应值：df/mi最后采用随机余数比例算法选择个体进行重新构造种群的基础 优点：优化目标个数任选非支配最优解分布均匀允许存在多个不同的等效解缺点：计算复杂度过高（0（MN3）不具有精英保留机制需要预设共享参数shareNSGA II加入精英保留机制快速非支配排序方法（Fast Nondominated Sorting Approach支配计数 n ：支配解 p 的解数量p支配解集 S ：解 p 支配的解集合p1、 计算出每一个解的n和S，第一级非支配解n 0，单独放入一个p p p集合；2、 遍历成员q和S，逐步递减n，如果可以减
6、少为0，将p放入单独qq的集合Q，构成第二级非支配解；3、重复步骤 2，直到所有成员全部分类完成。Crowded-comparison ApproachTor each t.狛t刀习日制财 =0for each otij:trvr tn2 =ffe）刃 ldiitUKe = wftr 心 2 施（l 一 1）邛応皿亡=加4血UUMCr + CT卩+ Ipn 一邛number nf 5elutions in T initialfee difilanoe:Wil ii如唱 aclk obidivt value sd that boundary poinls arc -alwirrs selecte
7、d for dl other p&inte一 M 加计算集合I的长度，初始化； 对每一个目标，利用目标值进行排序； 赋予边界点（第一个和最后一个）最大值，确保它们不会被剔除 w4、 循环计算其他点的 crowded distance.i L-dis tan ce_ i a+(!L + l.m-1i-1dis tan cem- f minm其中，I为非支配集合，I Alm表示第m个目标在第i个个体处的目标值,f max / f min 分别表示第 m 个目标的最大最小函数值 mm值越小，越拥挤Crowded-Comparison Operator：ni j f (/ j)nrank rankra
8、nk rankdis tan cedis tan ceYReplace the sharing function approach in NSGA 可以一定程度上消除一下两点：(1)the sharing function 太过于依赖共享参数，不容易设定(2)the sharing function 时间复杂度达到 O(N2)F2關Qtptf3Non-dominated sortingCrowding distancepsorting珥+i算法主循环：1、初始种群 P ( size 二 N ),并利用 binary tournament selection,0recombination and
9、 mutation operators 构建一个子代种群 Q ( size 二 N );02、合并po和Qo，记叮Po + Qo第t代：ft = UQF7 = fast-jn.QnicfiinatBdCrtA+l w 盟 atM i = 1until 1+L + |；| eheck die tKl Ikotri Ibr irKluicn sol in descendng order using 叫忖 choose lhe first (N 亡lemerts ofu$e elediibh crcsscAer and帕 male即 new 卩qwhticn QiincrtfiKfiA the ge
10、ncriitian couAer合并P和Q，记R二P + Qt t t t t对R进行非支配分类，结果记作F =（F, F ,）t 1 2循环计算 crowded distance of F ，并入 Pit+1对当前F进行crowded distance排序，选择前（N-1P l）个成员并入P ,it+1t+1确保l P l二Nt +1利用 binary tournament selection, recombination and mutation operators构建Qt+1进入下一次循环SPEACharacters:a) Storing nondominated solutions e
11、xternally in a second, continuously updated populationb) Evaluating an individuals fitness dependent on the number of external nondominated points that dominate itc) Preserving population diversity using the Pareto dominance relationshipd) Incorporating a clustering procedure in order to reduce the
12、nondominated set without destroying its characteristicsSteps:1) Generate an initial population P and create the empty external 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 individual in P as
