多目标优化算法,非支配的精英策略遗传算法:NSGA-II
1.算法简介
-
排序算法的时间复杂度 O(MN2)
-
精英保留策略
-
无需要共享的参数
2.算法相关概念
2.1 Pareto optimum
Pareto解又称非支配解或不受支配解(nondominated solutions):在有多个目标时,由于存在目标之间的冲突和无法比较的现象,一个解在某个目标上是最好的,在其他的目标上可能是最差的。这些在改进任何目标函数的同时,必然会削弱至少一个其他目标函数的解称为非支配解或Pareto解。一组目标函数最优解的集合称为Pareto最优集。最优集在空间上形成的曲面称为Pareto前沿面。一组目标函数最优解的集合称为Pareto最优集。
2.2 非支配的快速排序
整个种群的大小为P,首先需要计算出种群中的每个个体的p和被支配个数np和该个体支配解的集合Sp。
- 生成np和Sp的算法过程
for each p∈P (遍历种群中的每个个体)
Sp=∅
np=0
for each q∈P
if( p<q )then (如果p能支配q)
Sp =Sp ⋃ {p}(将q加入到被p支配的解集中)
else if(q<p) then
np=np+1 (增加p的支配数)
if np=0 then
prank=1
F1=F1⋃{p}
i=1
while Fi̸=∅
Q=∅ (用来存储下一个的集合)
for each p∈Fi
for each q∈Sp (遍历支配解)
nq=nq−1
if nq=0 then (q属于下一个集合)
qrank=i+1
Q=Q⋃{q}
i=i+1
Fi=Q
2.3 拥挤度分配
我们引入了拥挤距离KaTeX parse error: Expected '}', got 'EOF' at end of input: I[i]_{distance}$来代替用户定义的共享参数,为了使解在目标空间更加均匀,并且提高了计算复杂度。算法步骤如下:
crowding-distance-assignment(I)
-
num=∣I∣.n,记录I的数量
-
for each i, 设I[i]distance=0
-
for each objective m(对每个目标函数fm):
- 根据目标函数对该种群进行个体排序,其中fmmax为目标函数fm的最大值,fmmin为最小值
- 排序后的前边界I[1]distance和后便捷I[num]distance拥挤距离设为∞
- for i=2 to (num−1),计算除边界外所有点 I[i]distance=I[i]distance+(fm(i+1)−fm(i−1))/(fmmax−fmmin)
该拥挤距离度,就是使目标能生成最大的矩阵,且不干扰到其他点。
![屏幕快照 2018-12-22 下午4.54.20](/Users/IngeTeng/Desktop/屏幕快照 2018-12-22 下午4.54.20.png)
2.4 精英保留策略
算法步骤如下:
-
将父代种群Pi和子代种群Ci合并成Ri,此时种群数量为2N
-
Ri根据Pareto进行排序,根据Pareto的等级,将等级最低的优先放入新的父代种群Pi,直到此代放满既定种群数量N
-
在第二步放入排序中,按照拥挤距离从大到小放入到Pi
2.5 锦标赛选择
算法步骤如下:
-
确定每次选择的个体数量k,种群总数为N,k<N
-
从种群中随机选择k个个体(每个个体被选中的概率相同),根据每个个体的适应度,选择适应度值最好的个体进入下一代种群
-
重复步骤(2),直到新的种群规模达到原来的总数N为止
3.算法实现流程图
主体循环部分:
1.随机初始化一个种群P0,对P0进行非支配排序,初始化每个个体的rank值,i=0。
2.通过锦标赛法从Pi选择个体,进行交叉和变异,产生新一代种群Qi。
3.将Pi和Qi合并,产生一个结合后的种群Ri。
4.对Ri进行非支配排序,并使用拥挤距离和精英保留策略选出每代的N个个体,组成新一代种群Pi+1。
5.跳转至2,直至达到预期代数。
4.仿真结果及说明
以下是对ZDT1,ZDT2,ZDT3,ZDT4,ZDT6测试问题的仿真
f1(X)=x1
f2(X)=g(X)[1−x1/g(X)]
g(X)=1+9(i=2∑nxi)/(n−1)
n=30,
x1∈[0,1],xi=0
设置初始种群大小为500,迭代次数为500代,pc=0.9,pm=1/30,ηc=20,ηm=20。结果如图(1)所示。
![多目标优化算法,非支配的精英策略遗传算法:NSGA-II 多目标优化算法,非支配的精英策略遗传算法:NSGA-II](/default/index/img?u=aHR0cHM6Ly9waWFuc2hlbi5jb20vaW1hZ2VzLzI3MC80MTBmMTc2NDcwNDVkYWEwZjJmOTAzYzZiYjQ1ZjA2ZS5KUEVH)
图(1)
设置初始种群大小为100,迭代次数为2000代,$p_c = 0.9,p_m=1/30,\eta_c =20,\eta_m=20$。结果如图(2)所示。
![多目标优化算法,非支配的精英策略遗传算法:NSGA-II 多目标优化算法,非支配的精英策略遗传算法:NSGA-II](/default/index/img?u=aHR0cHM6Ly9waWFuc2hlbi5jb20vaW1hZ2VzLzQzMS84ZDNjYWVmOGQ0YTQ5ZDgyMDhjZGQxYzM0OTI3YTJlZi5KUEVH)
图(2)
其中蓝色为Pareto最优解,红色为NSGA-II的值
f1(X)=x1
f2(X)=g(X)[1−(x1/g(X))2]
g(X)=1+9(i=2∑nxi)/(n−1)
n=30,
x1∈[0,1],xi=0
设置初始种群大小为500,迭代次数为500代,pc=0.9,pm=1/30,ηc=20,ηm=20。结果如图(3)所示。
![多目标优化算法,非支配的精英策略遗传算法:NSGA-II 多目标优化算法,非支配的精英策略遗传算法:NSGA-II](/default/index/img?u=aHR0cHM6Ly9waWFuc2hlbi5jb20vaW1hZ2VzLzk0Ny9lZDg5NmU5YTZjNmQ0ZTI4ZDhkMmViZjA5M2NiMTY1Yi5KUEVH)
图(3)
设置初始种群大小为100,迭代次数为2000代,$p_c = 0.9,p_m=1/30,\eta_c =20,\eta_m=20$。结果如图(4)所示。
![多目标优化算法,非支配的精英策略遗传算法:NSGA-II 多目标优化算法,非支配的精英策略遗传算法:NSGA-II](/default/index/img?u=aHR0cHM6Ly9waWFuc2hlbi5jb20vaW1hZ2VzLzE2MC9hNmQ3NDNjZDUwNTFhMTE1ZmQ5ZjMyNzZkZTkzNDEwMC5KUEVH)
图(4)
其中蓝色为Pareto最优解,红色为NSGA-II的值
* ZDT3
f1(X)=x1
f2(X)=g(X)[1−x1/g(X)−g(X)x1sin(10πx1)]
g(X)=1+9(i=2∑nxi)/(n−1)
n=30,
x1∈[0,1],xi=0
设置初始种群大小为250,迭代次数为500代,pc=0.9,pm=1/30,ηc=20,ηm=20。结果如图(5)所示。
![多目标优化算法,非支配的精英策略遗传算法:NSGA-II 多目标优化算法,非支配的精英策略遗传算法:NSGA-II](/default/index/img?u=aHR0cHM6Ly9waWFuc2hlbi5jb20vaW1hZ2VzLzk4Ni82NjAzMjY1ZTI1ZGMzYmZhNDA3Zjc1MWVkYmMxYzgzYS5KUEVH)
图(5)
设置初始种群大小为250,迭代次数为2000代,$p_c = 0.9,p_m=1/30,\eta_c =20,\eta_m=20$。结果如图(6)所示。
![多目标优化算法,非支配的精英策略遗传算法:NSGA-II 多目标优化算法,非支配的精英策略遗传算法:NSGA-II](/default/index/img?u=aHR0cHM6Ly9waWFuc2hlbi5jb20vaW1hZ2VzLzc4My9iNDU2ZWVlNDcxN2I3ZDljMzJlZDhmZWVhOGFmNzc3Ny5KUEVH)
图(6)
其中蓝色为Pareto最优解,红色为NSGA-II的值
* ZDT4
f1(X)=x1
f2(X)=g(X)[1−x1/g(X)]
g(X)=1+10(n−1)+n∑i=2[xi2−10cos(4πxi)]
n=10,
x1∈[0,1],xi=0
设置初始种群大小为250,迭代次数为500代,pc=0.9,pm=1/10,ηc=20,ηm=20。结果如图(7)所示。
![多目标优化算法,非支配的精英策略遗传算法:NSGA-II 多目标优化算法,非支配的精英策略遗传算法:NSGA-II](/default/index/img?u=aHR0cHM6Ly9waWFuc2hlbi5jb20vaW1hZ2VzLzk5OS9jN2VjYWViNjk1NDlhM2I3YzRkMTIxMmQyODQ1MjQ1Ny5KUEVH)
图(7)
设置初始种群大小为250,迭代次数为2000代,$p_c = 0.9,p_m=1/10,\eta_c =20,\eta_m=20$。结果如图(8)所示。
![多目标优化算法,非支配的精英策略遗传算法:NSGA-II 多目标优化算法,非支配的精英策略遗传算法:NSGA-II](/default/index/img?u=aHR0cHM6Ly9waWFuc2hlbi5jb20vaW1hZ2VzLzE5MC82YTFjM2IyN2U3NTlmYmM0Yzk4NzEwZjM5NGUwYWQwNi5KUEVH)
图(8)
其中蓝色为Pareto最优解,红色为NSGA-II的值
* ZDT6
f1(X)=1−exp(−4πx1)sin6(6πxi)
f2(X)=g(X)[1−(f1(X)/g(X))2]
g(X)=1+9[(n∑i=2xi)/(n−1)]0.25
n=10,
x1∈[0,1],xi=0
设置初始种群大小为100,迭代次数为500代,pc=0.9,pm=1/10,ηc=20,ηm=20。结果如图(9)所示。
![多目标优化算法,非支配的精英策略遗传算法:NSGA-II 多目标优化算法,非支配的精英策略遗传算法:NSGA-II](/default/index/img?u=aHR0cHM6Ly9waWFuc2hlbi5jb20vaW1hZ2VzLzU2MC8yMzBjNDcxZjRmN2Y2MWQ2ODE2MzE4YmM2YmRiODkzOC5KUEVH)
设置初始种群大小为100,迭代次数为500代,pc=0.9,pm=1/10,ηc=20,ηm=20。结果如图(10)所示。
![多目标优化算法,非支配的精英策略遗传算法:NSGA-II 多目标优化算法,非支配的精英策略遗传算法:NSGA-II](/default/index/img?u=aHR0cHM6Ly9waWFuc2hlbi5jb20vaW1hZ2VzLzMxNS85YmVjYjY0MzUyZDQ0YjYwY2EwNjgxOWUyNmE1MTgyYi5KUEVH)
图(10)
其中蓝色为Pareto最优解,红色为NSGA-II的值
从仿真结果可以得到NSGA-II在测试问题ZDT1、ZDT2、ZDT3甚至是ZDT6都呈现出了不错的结果,非常接近Pareto-front值,只有在ZDT4问题上表现较差。
Δ的Mean和Vairance
Problem |
ZDT1 |
ZDT2 |
ZDT3 |
ZDT4 |
ZDT6 |
Mean(500) |
0.4569 |
0.4583 |
0.6731 |
0.4972 |
0.6956 |
Vairance(500) |
0.0010 |
0.0317 |
0.0052 |
0.0083 |
0.0041 |
Mean(2000) |
0.4954 |
0.4890 |
0.6925 |
0.4977 |
0.4544 |
Vairance(2000) |
0.0056 |
0.0013 |
0.0013 |
0.0057 |
0.0031 |
γ的Mean和Vairance
Problem |
ZDT1 |
ZDT2 |
ZDT3 |
ZDT4 |
ZDT6 |
Mean(500) |
0.0118 |
0.1000 |
0.9240 |
22.4199 |
0.5100 |
Vairance(500) |
0.0082 |
0.0033 |
0.0042 |
0.5061 |
0.0380 |
Mean(2000) |
0.0013 |
0.0011 |
0.0900 |
16.7371 |
0.4400 |
Vairance(2000) |
0.0001 |
0.0005 |
0.0003 |
0.4937 |
0.0032 |
根据图(1)和图(2),图(3)与图(4),图(5)与图(6)的对比可以发现,迭代的代数是对最优解结果有一定的影响的,能得到更好的接近Pareto最优值。由图(7)与图(8)可以的看出迭代次数对ZDT6的影响不大。在数据表中γ数据可以得出,在ZDT4问题上效果较差,从Δ数据可以看出,以上5个问题的传播多样性较好。