MOGA ix是第t代种群中个体，其rank值定义为：

()(,)1tiirankxtp

()tip

为第t代种群中所有支配ix的个体数目

适应值（fitness value）分配算法： 1、 将所有个体依照rank值大小排序分类； 2、 利用插值函数给所有个体分配适应值（从rank1到 rank *nN），一般采用线性函数 3、 适应值共享：rank值相同的个体拥有相同的适应值， 保证后期选择时同一rank值的个体概率相同

最后采用共享适应值随机选取的方法选择个体进入下一代 一种改进的排序机制（ranking scheme）： 向量,1,(,,)aaaqyyy和,1,(,,)bbbqyyy

比较

goal vector：1,,qggg 分为以下三种情况：

1、,,1,,1; 1,,;1,,; aiiajjkqikjkqygyg 2、,1,,; aiiiqyg 当ay支配by时，选择ay

3、,1,,; ajjjqyg 当by支配ay时，选择by

优点：算法思想容易，效率优良 缺点：算法容易受到小生境的大小影响 理论上给出了参数share

的计算方法 NPGA 基本思想： 1、初始化种群Pop 2、锦标赛选择机制：随机选取两个个体1x和2x和一个Pop的 子集CS(Comparison Set)做参照系。若1x

被CS中不少于一

个个体支配，而2x没有被CS中任一个体支配，则选择2x。 3、其他情况一律称为死结（Tie），采用适应度共享机制选择。

个体适应度：if

小生境计数（Niche Count）：,

ijPopmShdij







共享函数：1-,()0,shareshareshareddShdd





共享适应度（the shared fitness）：i

i

f

m

选择共享适应度较大的个体进入下一代 优点：能够快速找到一些好的非支配最优解域 能够维持一个较长的种群更新期 缺点：需要设臵共享参数 需要选择一个适当的锦标赛机制 限制了该算法的实际应用效果 NPGA II 基本思想： 1、初始化种群Pop 2、Pareto排序：非支配个体rank=0；其余个体 rank=支配该个体的个体数目 3、锦标赛选择机制：种群中任选两个个体1x和2x， 若12rankxrankx，则选择1x；

若是12rankxrankx，称为死结（Tie），

采用适应度共享机制选择。

小生境计数（Niche Count）： 1 0 ijijsharejPopshareiijsharedifdmifd







这里的Pop只包含当前一代里的个体，在NPGA中， 计算im

公式中的Pop包含当前一代以及已经产生的

属于下一代的所有个体 最后，选择计数较小的个体进入下一代

在计算Niched Count之前还要对函数值进行标准化： ',min,max,minii

iii

OOOOO NSGA 和简单的遗传算法的不同点在于selection operator works， crossover and mutation operator是一样的

不一样的共享函数： 2,,,1-, 0, ijijshareijshare

difdShdotherwise







,ijd表示个体i和j之间的距离

share是共享参数，表示小生境的半径

小生境计数（Niche Count）：,

ijcurrentfrontmShdij







共享适应值：i

df

m

最后采用随机余数比例算法选择个体进行重新构造种群的基础 优点：优化目标个数任选 非支配最优解分布均匀 允许存在多个不同的等效解 缺点：计算复杂度过高（3OMN）

不具有精英保留机制 需要预设共享参数share NSGA II 加入精英保留机制 快速非支配排序方法（Fast Nondominated Sorting Approach）： 支配计数 pn：支配解p的解数量

支配解集 pS：解p支配的解集合

1、计算出每一个解的pn和pS，第一级非支配解0pn，单独放入一个集合； 2、遍历成员q和qS，逐步递减qn，如果可以减少为0，将p放入单独的集合Q，构成第二级非支配解； 3、重复步骤2，直到所有成员全部分类完成。

Crowded-comparison Approach

1、计算集合I的长度，初始化； 2、对每一个目标，利用目标值进行排序； 3、赋予边界点（第一个和最后一个）最大值，确保它们不会被剔除； 4、循环计算其他点的crowded distance.



maxmintantan1.1.discedisce

mm

IimIimIiIiff

其中，I为非支配集合，.Iim表示第m个目标在第i个个体处的目标值，

maxmin/mmff分别表示第m个目标的最大最小函数值

值越小，越拥挤 Crowded-Comparison Operator：n

nij if rankrankij or tantan rankrankdiscedisceijandij

Replace the sharing function approach in NSGA 可以一定程度上消除一下两点：

（1）the sharing function 太过于依赖共享参数，不容易设定 （2）the sharing function 时间复杂度达到2ON 算法主循环： 1、初始种群0P（sizeN），并利用binary tournament selection, recombination and mutation operators构建一个子代种群0Q（sizeN）; 2、合并0P和0Q，记000RPQ 第t代：

合并tP和tQ，记tttRPQ

对tR进行非支配分类，结果记作12,,FFF

循环计算crowded distance of iF，并入1tP

对当前iF进行crowded distance 排序，选择前1||tNP个成员并入1tP，确保

1||tPN 利用binary tournament selection, recombination and mutation operators构建1tQ 进入下一次循环 SPEA Characters: a) Storing nondominated solutions externally in a second, continuously updated population b) Evaluating an individual's fitness dependent on the number of external nondominated points that dominate it c) Preserving population diversity using the Pareto dominance relationship d) Incorporating a clustering procedure in order to reduce the nondominated set without destroying its characteristics

Steps: 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 well as in 'P. 6) Select individuals from 'PP(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, then stop, else go to Step 2.

Fitness Assignment: 1) 外部群落 'iP 赋值

0,1

is，称作strength， 和jP的数量成正比， ij

定义：1insN

适应值if=is

2）当前群落 jP 

,1, 1,.jiiiijfswherefN

 其中'iP，适应值加1是为了确保外部群落的个体适应值优于当前群落

这里适应值越小，被选中的概率越大（small fitness values correspond to high reproduction probabilities）

聚簇缩减： 1）Initialize cluster set C; each external nondominated point 'iP constitutes a distinct cluster: iCi. 2) If ||'CN, 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

12 candcC is given as the average distance between pairs of individuals across