NSGA-II

1.1 背景和概念

• 多个目标函数同时优化

• 在两个或多个相互冲突的目标之间进行权衡的情况下作出最优决策

（若优化方向一致，可以加权转化为单目标）

优化的结果是一组解（曲线或者曲面）：

决策边界——帕累托前沿，即帕累托最优

2.1 基本原理

智能优化基本流程

多目标优化真正的核心难点：如何评价解的好坏，即怎么排序。

非支配排序

e.g.有两个解A和B

1. 支配（Dominate）

支配是为了决定，A是否严格好于B

如果两个解都不互相支配，即为非支配解，需要根据下一指标判断。

2. 拥挤距离（Crowding - Distance）

想要获得的解均匀地分散在帕累托前沿，因此，选择拥挤距离更大的点。

计算公式：

逐个目标计算，而不是针对逐个点计算。

例如，先计算目标函数F，对所有点（e.g.0,1,...,i-1,i,i+1,...,n）在F维度上进行排序。

对于第i个点，拥挤度为F(i+1)-F(i-1)，可以计算出点i在目标F上，距离周围两个点的距离。

分母的Fmax-Fmin是为了进行归一化的操作。

然后再计算，目标函数H、目标函数G...

对于边界上的两个点0和点n，拥挤度设置为无穷大，为了保证边上的两个点一定被选中。

总结：排序方法

STEP1（支配）：根据多个优化目标，判断所有解之间的支配关系，选择非支配解（支配解数量为0的解）；

STEP2（拥挤距离）：针对非支配解，计算每个解的拥挤距离，以获得拥挤距离较大的解，从而获得均匀的帕累托前沿。

3. 非支配排序（Non-dominated Sortiing）

NSGA-I，复杂度较高

一层一层地剥离，获得一层后，去掉该层的解，对剩下的所有解进行排序。

NSGA-II，快速非支配排序

多了Sp和np，记录当前解支配的，以及能支配当前解的。

选取出第一层，再对第一层的解遍历，查找被其支配的解，将第一层的该解删除，重新计算支配解；然后逐层计算。

4.总结多目标优化基本流程：

（适应度更高=解更优，“优”取决于优化方向）

3.1 算法分析

4.1 算法拓展

算法的优化建议

不同算法适用场景不同，例如GA天然适应离散变量的优化（交叉，变异等）；PSO适合连续值。

可以结合应用场景着手改进，例如，针对自己的场景，提出新的初始化、计算拥挤距离的方式。

5.1 代码分析

yarpiz.com（代码很清晰，还有机器学习、多目标优化的代码）

python版本直接搜索NSGA-II python

在写两层循环的时候，第一层for i in (1:n)，

第二层只要for j in (i+1,n)。

因为第一次已经对比过一些解。

疑问：如何进化？