目录
预备知识多目标优化问题的求解NSGA-II综述快速非支配排序拥挤度精英战略部分代码展示1.预备知识
多目标优化知识： https://blog.csdn.net/haha 0332/article/details/88634378
统治：假设自觉的玉米9岁、50斤，qrdlz岁、45斤。 自觉的玉米无论年龄还是体重都大于qrdlz，所以自觉的玉米支配着qrdlz。
不相容：假设自觉的玉米7岁、50斤，qrdlz岁、45斤。 自觉的玉米年龄比qrdlz小，但体重比qrdlz大，自觉的玉米和qrdlz不支配。
fkdxlz集：在这个集合中，任意两个解互不支配。
非支配排序：将一组解分为n个集合，即rank1、rank2…rankn。 各集合中的所有解互不支配，但ranki中的任意解支配rankj中的任意解(ij )。
2.多目标优化问题的解
在单目标优化问题中，通常只有一个最优解，可以用比较简单和常用的数学方法求出其最优解。 另一方面，在多目标优化问题中，由于各目标之间的相互约束，一个目标的性能的改进往往不存在以损害其它目标的性能为代价来优化所有目标的性能的解。 也就是说，这两个目标可能有很大的负相关关系。 因此，在多目标优化问题中，其解通常是非劣化解的集合-fkdxlz解集合。
在存在多个fkdxlz最优解的情况下，所有的fkdxlz最优解被认为同等重要，因为如果没有更多的关于问题的信息，就很难选择哪个解更优选。 由此可见，对于多目标优化问题，最重要的任务是尽可能多地找到该优化问题的fkdxlz优化解。 因此，多目标优化主要执行以下两项任务：
)1)找到尽可能接近fkdxlz最佳域的解
)2)尽可能找到一组不同的解
优选的是，第一个任务不收敛于接近真正的fkdxlz最优解集的解，这必须在每个优化操作中执行。 只有当收敛到接近真实fkdxlz最优解的解集时，才能确保该解集接近最优的特性。
不仅要求优化问题的解收敛到近似fkdxlz最优域，而且要求的解也必须均匀分布在fkdxlz最优域中。 多个目标间的良好共识解的组基于各种解的组。 简而言之，一组解中的差异越大，这一组解越被认为是好的。
3.NSGA2算法的简介
多目标遗传算法是分析和解决多目标优化问题的进化算法，其核心是协调各目标函数之间的关系，找到使各目标函数成为尽可能大(或小)函数值的最优解集。 在众多目标优化的遗传算法中，NSGA2算法是影响最大、应用范围最广的多目标遗传算法。 自出现以来，由于它具有简单有效、比较明显的优势，该算法已经成为多目标优化问题中的基本算法之一。
介绍NSGA2。 首先介绍以下NSGA算法。
NSGA采用基于非支配序列的方法保持种群中的优良个体，利用适应度共享函数保持群体多样性，取得了非常好的效果。 但在实际工程领域NSGA算法存在明显的不足，这主要表现在以下三个方面。
(1)非支配地位高的计算复杂性。 非支配排序算法一般进行mN^3次搜索(m可视为目标函数数，体重和年龄为两个目标函数，n为一组解的大小)，搜索次数随目标函数数和种群大小的增加而增加。
)2)精英战略缺失。 研究结果表明，引用精英策略也有助于加快遗传算法的运行，防止优秀个体的丢失。
)3)需要指定共享参数share，NSGA算法中保持种群和解多样性的方法都依赖于共享概念，共享的主要问题之一是需要人为指定共享参数share。
为了克服非支配排序遗传算法(NSGA )的上述不足，印度科学家数据库于2002年在NSGA算法的基础上进行了改进，开发出了具有精英策略的非支配排序遗传算法(elitist non-dominatedsoson )
提出一种快速非支配排序算法，降低计算非支配顺序的复杂度，优化算法的复杂度由原来降低到(目标函数的个数、种群大小)。 引入精英战略，扩大了采样空间。 将母种群和出生子种群结合起来，共同通过竞争形成下一代种群，有利于保证母体内优良个体得以维持，保证这些优良个体在进化过程中不会被舍弃，提高优化结果的精度。 另外，将种群的所有个体分层保存，可以避免失去最佳个体，迅速提高种群水平。 引入拥挤度和拥挤度比较算子，不仅克服了NSGA算法需要人为指定共享参数的缺点，而且以拥挤度作为种群间的比较标准，准Pareto域种群均匀扩展到整个Pareto域，保证种群多样性。4.快速非支配排序
NSGA算法采用非支配排序方法，该方法的计算复杂度为O(mN^3，而NSGA-II算法采用快速非支配排序方法，计算复杂度仅为O(mN2 )。 以下，简单说明两者计算复杂度的由来：
)1)非支配排序算法的计算复杂度：
为了优化
对象的个数为m，种群规模大小为N的种群进行非支配排序，每一个个体都必须和种群中其它的个体进行比较，从而得出该个体是否被支配，这样每个个体就总共需要 次的比较，需要O（mN ）的计算复杂度。当这一步骤完成之后，继续找出第一个非支配层上的所有个体，这需要遍历整个种群，其总的计算复杂度就是O（ mN^2）。在这一步中，所有在第一个非支配层中的个体都被寻找到，为了找到随后各个等级中的个体，重复前面的操作。可以看到，在最坏的情况下(每一层级上只有一个个体)，完成对整个种群所有个体的分级，这种算法的计算复杂度为O（ mN3）。
（2） 快速非支配排序算法的计算复杂度：
对于种群中每一个个体 i，都设有两个参数ni和Si,ni是种群中支配个体i的解的个体数量,Si是被个体i 支配的解的个体的
集合。 找出种群中所有ni=0的个体，将它们存入当前非支配集合rank1中；对于当前非支配集合rank1中的每一个个体 j，遍历它所支配的个体集合Sj，将集合Sj中每一个个体 t的 nt都减去1，即支配个体t的解的个体数量减1(因为支配个体 的个体j已经存入当前非支配集 中)，如果 nt-1=0，则将个体t存入另一个集H；把rank1作为第一级非支配个体的集合，所以在rank1中的解个体是最优的。它只支配个体，而不受其他任何个体所支配，对该集合内所有个体都赋予相同的非支配序 ，然后继续对集合H作上述分级操作，并也赋予相应的非支配序，直到所有的个体都被分级，即都被赋予赋予相应的非支配序。
每一次迭代操作，即上述快速非支配排序算法步骤的1)和2)需要N次计算。于是，整个迭代过程的计算复杂度最大是N^2。这样，整个快速非支配排序算法的计算复杂度就是： mN2
5.拥挤度
手打好痛苦，还有各种公式不让我打，直接用word打了复制上来吧。
6.精英策略
NSGA-II算法引入了精英策略，以防止在种群的进化过程中优秀个体的流失，通过将父代种群与其产生的子代种群混合后进行非支配排序的方法，能够有较好地避免父代种群中优秀个体的流失。精英策略的执行步骤如图3-2所示：
**7.部分代码展示**```java/* * nsga2的选择部分 */public static Population nsga2(Population father, Population child) { // 两代种群的所有个体都参与筛选HashMap<Integer, Individual> fatherAndChild = new HashMap<Integer, Individual>();//father.map放入的是父代的所有个体fatherAndChild.putAll(father.map);Population.MAXSIZE是该种群的最大大小for (int i = 0; i < Population.MAXSIZE; i++) { //父代和子代一起进行筛选fatherAndChild.put(i + father.map.size(), child.map.get(i));} // 对每个个体进行处理，找出被它支配和支配它的个体 fatherAndChild.forEach((key,in)->{ //n是该个体被多少个体支配 in.n=0; //dominate是该个体支配多少个体 in.dominate.clear(); }); fatherAndChild.forEach((key1,in)->{fatherAndChild.forEach((key, o) -> {if (((in.fitness1 < o.fitness1) && (in.fitness2 <o.fitness2))||((in.fitness1 <=o.fitness1) && (in.fitness2 < o.fitness2))||((in.fitness1 < o.fitness1) && (in.fitness2 <= o.fitness2)))// 找出in支配的个体放入dominate中{in.dominate.add(o); }elseif (((in.fitness1 > o.fitness1) && (in.fitness2 > o.fitness2))||((in.fitness1 >= o.fitness1) && (in.fitness2 > o.fitness2))||((in.fitness1 > o.fitness1) && (in.fitness2 >= o.fitness2)))// 碰上一个支配in的个体就++n{in.n++;}}); });ArrayList<ArrayList<Individual>> rank = new ArrayList<ArrayList<Individual>>();// 对种群进行分级别// 外层的ArrayList是存放每一个rank，内层的ArrayList是存放该rank对应的个体while (!fatherAndChild.isEmpty())// 本函数将所有个体进行分级，分级后放入rank数组中{ArrayList<Individual> po = new ArrayList<Individual>();// 用来存放第x rank的个体，这里的x是while的第x个循环for (int i = 0; i < Population.MAXSIZE * 2; i++)// 对哈希表中的每个个体进行遍历{Individual indi = fatherAndChild.get(i);if (indi == null)continue;if (indi.n == 0)// 如果发现该个体的n为0，即没有支配该个体的其他个体{po.add(indi);// 将该个体放入第n rank的集合中fatherAndChild.remove(i);// 把该个体从哈希表中去除//for (Individual in : indi.dominate) {//--in.n;//}}}for(Individual indi:po)for(Individual in:indi.dominate){in.n--;}rank.add(po);// 该rank的所有个体都放入ArrayList后将该ArrayList放入对应rank的位置} //int t=0;//for(ArrayList<Individual> arr:rank)//{//System.out.println(++t);//for(Individual indi:arr)//{//System.out.println(indi.fitness1+" "+indi.fitness2);//}//}// 查找哪个rank放入qjdm一代之后会超出MAXSIZEint num = Population.MAXSIZE;int index = 0;// 这是用来指示第几rank的while (true) {if (num - rank.get(index).size() > 0) {num = num - rank.get(index).size();++index;} else {break;}}// 找出该rankArrayList<Individual> po = rank.get(index);//System.out.println("最后一层有"+po.size()+"个");// 对该rank根据fitness1的大小进行排序，根据fitness2也可以po.sort((Individual o1, Individual o2) -> { // TODO Auto-generated method stub//int i = o1.fitness1 > o2.fitness1 ? 1 : -1;//return i;if(o1.fitness1>o2.fitness1) return 1;else if(o1.fitness1<o2.fitness1)return -1;return 0;});//归一化double fitness1sum=0,fitness2sum=0;int numSum=0;for(Individual o:po){fitness1sum+=o.fitness1;fitness2sum+=o.fitness2;numSum+=o.uav.size();} // 对该rank的每一个个体计算其distancefor (int i = 0; i < po.size(); i++) {if (i == 0 || i == po.size() - 1) {po.get(i).distance = (float) Double.MAX_VALUE;} else {po.get(i).distance = (float) (Math.abs((po.get(i - 1).fitness1 - po.get(i + 1).fitness1)/fitness1sum)+ Math.abs(po.get(i - 1).fitness2 - po.get(i + 1).fitness2)/fitness2sum);}} // 对该rank根据distance大小进行排序po.sort((Individual o1, Individual o2) -> {// TODO Auto-generated method stub//int i = o1.distance > o2.distance ? -1 : 1;//return i;if(o1.distance>o2.distance)return -1;else if(o1.distance<o2.distance)return 1;return 0;});// 将所有选中的个体放入新的ArrayList中ArrayList<Individual> newpo = new ArrayList<Individual>();for (int i = 0; i < index; i++) {newpo.addAll(rank.get(i));}// 同上for (int i = 0; i < num; i++) {newpo.add(po.get(i));} //System.out.println("放入"+num+"个");// 创建一个种群，将刚才筛选出的所有个体作为该种群的组成部分Population pp = new Population();for (int i = 0; i < Population.MAXSIZE; i++) {pp.map.put(i, newpo.get(i));}return pp;// 返回该种群}