多目标优化中的非支配排序算法
多目标优化中的非支配排序算法 以NSGA-II为例 多目标优化指的是针对多个目标函数，去寻找一组最优解，形式如下： 其中*fi(x)*是各单一的目标函数 但是多目标优化问题通常面临多个目标函数无法同时达到最优，为了解决这一问题，提出了pareto-Optimality的概念， 针对pareto-Optimality，有几个概念： 1.非支配解：假设任何二解S1 及S2 对所有目标而言，S1均优于S2，则我们称S1 支配S2，若S1 的解没有被其他解所支配，则S1 称为非支配解（不受支配解），也称Pareto解 支配解：若解S2的所有目标均劣于S1，则称S1优于S2，也称S1支配S2，S2为受支配解。 因此现在的首要任务是寻找解空间里面所有的Pareto解，找到所有Pareto解之后，这些解组成的平面叫做Pareto前沿面（Non-dominated front）。在目标函数较多时，前沿面通常为超曲面。 非支配解排序（Non-dominated Sorting）
- 设所有解的集合为S，现从中找出非支配解集合，记为F1
- 令S=S-F1，从S中再找出非支配解集合，记为F2
- 重复第二步，直到S为空集
将每次找出的非支配解进行排序如下：
{F1,F2,…,Fn} 例如：有两个目标函数Time(f1(x)),Cost(f2(x)),通过求解，我们获得了一组pareto解集，如下图所示： 对这个解集进行排序： 第一轮：我们发现A,B,D,F不能被其他解所支配，则这是第一组非支配解集； 然后我们针对剩余解集，C,E,G,H,I进行排序，C,E,G不能被其他解所支配，组成第二组非支配解集； 剩余的H,I,不能彼此支配，所以组成第三组非支配解集。 通过这个过程我们发现，非支配排序实际上就是“不断的剔除非支配解集，将目标值大的保留下来，然后进一步处理”。 matlab代码实现过程：
clear all
close all
functionvalue=[2 7.5;3 6;3 7.5;4 5;4 6.5;5 4.5;5 6;5 7;6 6.5];%当前的非支配解集
fnum=0; %当前分配的前沿面编号，就是上述的第一轮，第二轮，第三轮
cz=false(1,size(functionvalue,1)); %记录个体是否已被分配编号
frontvalue=zeros(size(cz)); %每个个体的前沿面编号
[functionvalue_sorted,newsite]=sortrows(functionvalue); %对种群按第一维目标值大小进行排序，第一位目标值相同，
%就对第二维目标进行排序
while ~all(cz)
fnum=fnum+1;
d=cz;
for i = 1:size(functionvalue,1)
if ~d(i)
for j=i+1:size(functionvalue,1)
if ~d(j)
k=1;
for m=2:size(functionvalue,2)
if functionvalue_sorted(i,m)>functionvalue_sorted(j,m)%将目标值大的解保留下来，来进行下一次排序，
%该过程通过d(j)=true实现
k=0;
break
end
end
if k
k
d(j)=true;
end
end
end
frontvalue(newsite(i))=fnum;
cz(i)=true;
end
end
endhon
```python
