MOGA
xi是第t代种群中个体，其rank值定义为： rank(xi,t)?1?pi(t)
pi(t)为第t代种群中所有支配xi的个体数目
适应值（fitness value）分配算法：
1、 将所有个体依照rank值大小排序分类；
2、 利用插值函数给所有个体分配适应值（从rank1到 rank n?N），一般采用线性函数
3、 适应值共享：rank值相同的个体拥有相同的适应值，
保证后期选择时同一rank值的个体概率相同
最后采用共享适应值随机选取的方法选择个体进入下一代
一种改进的排序机制（ranking scheme）： 向量ya?(ya,1,???,ya,q)和yb?(yb,1,???,yb,q)比较 goal vector：g?g1,???,gq 分为以下三种情况： 1、
*???k?1,???,q?1; ?i?1,???,k;?j?k?1,???,q; ?ya,i?gi???ya,j?gj?
2、?i?1,???,q; ya,i?gi 当ya支配yb时，选择ya 3、?j?1,???,q; ya,j?gj
当yb支配ya时，选择yb
优点：算法思想容易，效率优良
缺点：算法容易受到小生境的大小影响 理论上给出了参数?share的计算方法
????
NPGA
基本思想： 1、初始化种群Pop
2、锦标赛选择机制：随机选取两个个体x1和x2和一个Pop的 子集CS(Comparison Set)做参照系。若x1被CS中不少于一 个个体支配，而x2没有被CS中任一个体支配，则选择x2。 3、其他情况一律称为死结（Tie），采用适应度共享机制选择。
个体适应度：fi
小生境计数（Niche Count）：mi??pojP?Shdij???,???
d?,d??share?1-共享函数：Sh(d)???share
?0,d??share?共享适应度（the shared fitness）：
fimi
选择共享适应度较大的个体进入下一代 优点：能够快速找到一些好的非支配最优解域 能够维持一个较长的种群更新期 缺点：需要设臵共享参数
需要选择一个适当的锦标赛机制 限制了该算法的实际应用效果
NPGA II
基本思想：
1、初始化种群Pop
2、Pareto排序：非支配个体rank=0；其余个体 rank=支配该个体的个体数目
3、锦标赛选择机制：种群中任选两个个体x1和x2， 若rank?x1??rank?x2?，则选择x1； 采用适应度共享机制选择。
小生境计数（Niche Count）：
若是rank?x1??rank?x2?，称为死结（Tie），
?dij?????1?? if dij??share mi??j?Pop??share?? 0 if d??ijshare?这里的Pop只包含当前一代里的个体，在NPGA中， 计算mi公式中的Pop包含当前一代以及已经产生的 属于下一代的所有个体
最后，选择计数较小的个体进入下一代
在计算Niched Count之前还要对函数值进行标准化：
Oi?Oi,minO?
Oi,max?Oi,min'i
NSGA
和简单的遗传算法的不同点在于selection operator works， crossover and mutation operator是一样的
不一样的共享函数：
??di,j?2?1-?, if di,j??share Sh?di,j??????share??? 0, otherwisedi,j表示个体i和j之间的距离
?share是共享参数，表示小生境的半径
小生境计数（Niche Count）：mitn?orftnerrujc??Shdi?j??,???
共享适应值：dfmi
最后采用随机余数比例算法选择个体进行重新构造种群的基础 优点：优化目标个数任选 非支配最优解分布均匀 允许存在多个不同的等效解 不具有精英保留机制 需要预设共享参数?share
缺点：计算复杂度过高（O?MN3?）
NSGA II
加入精英保留机制
快速非支配排序方法（Fast Nondominated Sorting Approach）： 支配计数 np：支配解p的解数量 支配解集 Sp：解p支配的解集合
1、计算出每一个解的np和Sp，第一级非支配解np?0，单独放入一个集合； 2、遍历成员q和Sq，逐步递减nq，如果可以减少为0，将p放入单独的集合Q，构成第二级非支配解；
3、重复步骤2，直到所有成员全部分类完成。
Crowded-comparison Approach
1、计算集合I的长度，初始化；
2、对每一个目标，利用目标值进行排序；
3、赋予边界点（第一个和最后一个）最大值，确保它们不会被剔除； 4、循环计算其他点的crowded distance.
I?i?distance?I?i?distance??I?i?1?.m?I?i?1?.m?其中，I为非支配集合，I?i?.m表示第m个目标在第i个个体处的目标值，
maxmin分别表示第m个目标的最大最小函数值 fm/fmmaxminfm?fm
值越小，越拥挤
Crowded-Comparison Operator：?n
i?nj if ?irank?jrank? or ??irank?jrank? and ?idistance?jdistance??
Replace the sharing function approach in NSGA 可以一定程度上消除一下两点：
（1）the sharing function 太过于依赖共享参数，不容易设定 （2）the sharing function 时间复杂度达到ON??
2
多目标进化算法总结
