NSGA-II

Abstract:

NSGA(采用Non-dominated sorting and sharing算法的MOEA)存在以下三个问题：

a、非劣排序遗传算法的复杂度为O（MN3）

b、没有引进精英策略；

c、必须人为指定一个共享参数；

Introduction:

传统的优化方法（Multi-criterion decision-making methods）提出将多目标优化问题转换为单目标优化问题，强调一次仿真运行只获得一个最优解，然后通过多次仿真希望获得多个不同的最优解；

NSGA-II改进主要是针对如上所述的三个方面：

a、提出了快速非支配排序算法，一方面降低了计算的复杂度，另一方面它将父代种群跟子代种群进行合并，使得下一代的种群从双倍的空间中进行选取，从而保留了最为优秀的所有个体；

b、引进精英策略，保证某些优良的种群个体在进化过程中不会被丢弃，从而提高了优化结果的精度；

c、采用拥挤度和拥挤度比较算子，不但克服了NSGA中需要人为指定共享参数的缺陷，而且将其作为种群中个体间的比较标准，使得准Pareto域中的个体能均匀地扩展到整个Pareto域，保证了种群的多样性。

NSGA-II提出了一个简单的解决约束优化问题的方法；

Part II:

强度Pareto进化算法，SPEA(suggested an elitist multi-criterion EA with the concept of non-domination)具体步骤如下：

a、 产生初始种群P和空的外部非劣解集NP；

b、 将种群P中的非劣个体拷贝到非劣解集NP；

c、 剔除集合NP中受种群P中个体支配的解；

d、 如果保留在集合NP中的非劣解的个数超过事先给定的最大值，则通过聚类分析对集合NP进行修剪，剔除多余的解；

e、 计算种群P和集合NP中每个个体的适应度值；

f、 利用二元锦标赛方法从P +NP中选择个体进入下一代；

g、 对个体实施交叉和变异操作；

h、 如果最大代数达到，停止搜索；否则转到b。

适应度赋值：首先对非劣解集NP中的个体进行赋值，然后对种群中的个体赋值，具体描述如下：

a、 对于每个解xi ∈ NP, 赋予一个强度值Si ∈[0,1)，Si = hi /(N+1)，其中hi 表示种群中受个体xi 支配的个体数，N为种群规模。Si 即为xi 的适应度值；

b、 每个个体xj ∈ P 的适应度值为1+ ∑Si ，即所有支配解xj 的解xi ∈ NP的强度之和再加1。

聚类分析：通常情况下，非劣解集大小必须受限，必须为其规定最大规模，即保留在其中的解的最大个数，主要原因有四个方面：

a、 MOP的非劣解集大小可能非常大，甚至无穷大

b、 实现算法的计算资源是有限的；

c、 档案维护的复杂性会随档案规模的变大而显著增加；

d、 遗传漂移可能出现，因为均匀采样过程中搜索空间中过度代表的区域总是优先被选择。

前面三点意味着必须限制档案大小，而第四点表示对档案进行修剪可能对算法性能有利。

SPEA采用如下聚类分析对非劣解集进行修剪：

a、 初始化聚类集C，该集合由非劣解NP的解构成，每个解对应一个聚类；

b、 如果∣C∣≤ N’，转到e，否则转到c；N’为非劣解集的最大大小。

c、 计算所有聚类之间的距离（采用欧式距离）；

d、 确定具有最小距离的两个聚类，然后调整聚类集C，转到b；

e、 确定每个聚类的代表个体，通常选择和同一聚类的其他个体之间的平均聚类最小的个体作为该聚类的代表；

SPEA存在如下劣势：

a、 根据SPEA的适应度赋值的过程，被相同档案成员支配的种群个体适应度相同，这意味着当外部档案只包含一个成员时，无论种群个体之间是否存在支配关系，所有种群个体都具有相同的适应度值，这样，SPEA与随机搜索类似；

b、 聚类分析能够减少非劣解集的大小，但它可能错误的删掉了一些必须保存在非劣解集中的个体，影响算法的多样性；

PAES：采用自适应网格法对外部档案进行维护。由1+1策略和档案组成；

自适应网格的基本思想：利用外部档案保存所有非劣解，然后将目标空间分割成多网格，当插入到档案中的个体位于网格的现有边界之外，则重新分割网格个计算每个网格中

个体数。自适应网格不需要附加参数，可以维持种群的多样性；

1+1策略的具体步骤：

1、 随机产生一个初始解c并将它加入到档案A中.

2、 对当前解c执行变异操作，产生新解d，并对d作如下评价：

If c 支配 d then 舍弃d;

else if d 支配c then 用d代替c并将d加入到档案中；

else if d被档案中的一个成员支配 then 舍弃d；

else 执行 test(c, d, A)以决定d和c中之一为当前解，以及是否将d加入到档案中；

3、若终止条件满足，则结束；否则，转到（2）；

当当前解 c和新解d互相不受支配，且d不受档案中任意个体支配时，利用test（c, d, A）选择密度最小的个体。

test（c, d, A）具体过程如下：

if 档案A未满，将d加入到A中

if d在A中的密度值小于c then d 作为新的当前解

else 仍将c作为当前解

else

if d在档案中的密度值小于某个个体x属于A

将d加入到档案中，同时将x从档案中剔除；

if d在档案中的密度值小于c then d 作为新的当前解；

else 仍将c作为当前解

else

if d 在档案中的密度值小于c then d 作为新的当前解；

else 仍将c 作为当前解；

end if

NSGA-II：

a、 Fast Non-dominated Sorting Approach:

对每一个解，计算两个数据：Np表示种群中所有解中支配p的解的总数，Sp表示种群中被解p所支配的解的解集。

b、 拥挤距离（先对非劣解集中的解根据目标函数值的大小进行排序）然后如下图所示计算由解i+1和i-1构成的立方体的平均边长作为i的拥挤度距离：

NSGA-II:具体的过程如下图所示

Performance Measuresmetric1:收敛程度值：Y 、Y的方差

meitric2:多样性的衡量值det (spread)

SPEA2(强度Pareto进化算法2)：

针对SPEA的缺陷，SPEA2在适应度赋值、个体密度值计算方法和外部档案维护三个方面进行了改进。

1、a fine-grained fitness assignment strategy，which takes for each individual

into account how many individuals it dominates and it is dominated by。

2、a density estimation technique，which allows a more precise guidance of the search process

3、an enhanced archive truncation method，guarantees the preservation of

boundary solutions

本周细读论文：Improving the non-dominated sorting genetic algorithm using agene-therapy method for multi-objective optimization

论文创新点：1、在交叉操作中引进了基因疗法，这样就不需要再采用传统的搜索方法去精确分析解空间；

2、修改了原来的替换策略，这样来保持多样性以及产生连贯的解集

The illustration of the gene-therapy method.

This study applies the following two performance measures:

1、

the convergence metric (Y ),

2、

the diversity metric (det),

The performance of the evaluative crossover is affected by three parameters:

(1) crossover percentage; (100%)

(2) crossover rate; (10%)

(3) therapeutic coefficient(0.5-1)

Test problem can be characterized by four characteristics:

(1) unimodal/multimodal;

(2) convex/non-convex;

(3) bias/non-bias;

(4) con-nected/disconnected.