注释：是学习之余整理的资料，如有不足的地方还请指教，十分感谢！
目录
1、多目标进化算法
进化算法是一类模拟生物自然选择与自然进化的随机搜索算法，因其适用于求解高度复杂的非线性问题而得到了广泛的应用，同时他又具有较好的通用性。在解决只有单个目标的复杂系统优化问题时，进化算法的优势得到了充分展现。然而，现实世界中的优化问题通常是多属性的，一般是对多个目标的同时优化。由此，针对多个目标的优化问题，出现了多目标进化算法MOEA。
1.1MOEA概述
1967年，Rosenberg建议采用基于进化的搜索来处理多目标优化问题，但他没有具体实现。1985年，David Schaffer首次在机器学习中实现了向量评估遗传算法。1989年，David Goldberg提出来用进化算法实现多目标的优化技术，在对多目标进化算法的研究具有重要的方向性指导意义。
1994-2001年的8年，国际上所出版的论文是过去10年的3倍多。最近15年的发展速度比过去8年又有很大提高，一方面，在IEEE Transacrions on Evolutionary Computation、Evolutionary Computation和Genetic Programming and Evolvable Machines等国际重要学术期刊，以及各类国际进化计算学术会议上发表的有关多目标进化的论文比过去八年增长的幅度大很多，另一方面有关进化算法的期刊或会议的影响力越来越大，如IEEE Transacrions on Evolutionary Computation、Evolutionary Computation按JCR期刊影响因子均已进入SCI一区。第三方面，应用成果越来越多，涉及的应用范围越来越广。
1.2 MOEA的分类
MOEA种类较多，在此我们只讨论按不同的进化机制和不同的决策方式对MOEA进行分类:
①基于分解的MOEA
②基于支配关系的MOEA
③基于指标的MOEA
而本次要讲解的NSGA-Ⅱ属于②基于支配关系的MOEA
2、NSGA-Ⅱ算法介绍
2.1 NSGA算法
NSGA通过基于非支配排序的方法保留了种群中的优良个体,并且利用适应度共享函数保持了群体的多样性，取得了非常良好的效果。但实际工程领域中发现NSGA算法存在明显不足，这主要体现在如下3个方面：
(1)非支配排序的高计算复杂性。非支配排序算法一般要进行mN^3次搜索，搜索的次数随着目标函数数量和种群大小的增加而增多。（m为目标数，N为群体大小）
(2)缺少精英策略。研究结果表明，引用精英策略可以加快遗传算法的执行，并且还助于防止优秀的个体丢失。
(3)需要指定共享参数share，在NSGA算法中保持种群和解的多样性方法都是依赖于共享的概念，共享的主要问题之一就是需要人为指定一个共享参数share。
2.2 NSGA-Ⅱ算法
为了克服非支配排序遗传算法(NSGA)的上述不足，印度科学家Deb于2002年在NSGA算法的基础上进行了改进，提出了带精英策略的非支配排序遗传算法(Elitist Non-Dominated Sorting Genetic Algorithm，NSGA-II)，NSGA-II算法针对NSGA的缺陷通过以下三个方面进行了改进：
①提出了快速非支配的排序算法，降低了计算非支配序的复杂度。
②引入了精英策略，扩大了采样空间，提高优化结果的准确度。
③引入拥挤度和拥挤度比较算子，这不但克服了NSGA算法中需要人为指定共享参数的缺陷，而且将拥挤度作为种群中个体之间的比较准则，使得准Pareto域中的种群个体能均匀扩展到整个Pareto域，从而保证了种群的多样性。
①支配：假设小明9岁，50斤，小红8岁，45斤，小明无论是岁数还是体重都比小红大，所以小明支配小红。
②互不支配：假设小明7岁，50斤，小红8岁，45斤，小明岁数比小红小，但体重比小红大，所以小明和小红互不支配。
③非支配排序：将一组解分成n个集合：rank1,rank2…rankn,每个集合中所有的解都互不支配，但ranki中的任意解支配rankj中的任意解（i<j）。
④精英策略即保留父代（上代），然后让父代和经过选择、交叉、变异后产生的子代共同组成一个群体，其目的就是为了防止父代中可能存在的最优解被遗落，最后经过再次选择操作，获得与初始种群同样规模的群落。
3、NSGA-Ⅱ算法的步骤
3.1 NSGA-Ⅱ算法流程图
首先,随机产生规模为N的初始种群,非支配排序后通过遗传算法的选择、交叉、变异三个基本操作得到第一代子代种群;
其次,从第二代开始,将父代种群与子代种群合并,进行快速非支配排序,同时对每个非支配层中的个体进行拥挤度计算,根据非支配关系以及个体的拥挤度选取合适的个体组成新的父代种群;
最后,通过遗传算法的基本操作产生新的子代种群:依此类推,直到满足程序结束的条件。
二进制锦标赛法（二元锦标赛法）
锦标赛方法选择策略每次从种群中取出一定数量个体，然后选择其中最好的一个进入子代种群。重复该操作，直到新的种群规模达到原来的种群规模。具体的操作步骤如下：
(1)确定每次选择的个体数量。一般选择2个。
(2)从种群中随机选择个个体(每个个体入选概率相同)构成组，根据每个个体的适应度值，选择其中适应度值最好的个体进入子代种群。
(3)重复步骤(2)，得到的个体构成新一代种群。
下面举一个简单的例子演示NSGA-Ⅱ算法的流程。设种群大小为5，目标函数2个。
①初始化：初始化5个个体为初代
②选择、交叉、变异
原先的5个个体变异，再任选两个进行交叉，交叉又产生5个个体，现在总共有10个个体了。
④选择
我们自然是选择rank高的个体，rank=1和rank=2的个体，总共3个被保留。我们要再次凑成5个个体的种群。我们就在rank=3的个体中选，但是也不能全要，因为会超过5个，这就用到拥挤度了，选择拥挤度大的，那么就是最左边和最右边的两个，因为我们定义了这两个的拥挤度是无限大。
⑤迭代
选择完了又回到第②步，直到进化到了一定的次数，结束算法。
3.2 NSGA-Ⅱ关键子程序算法
3.2.2保持解群体分布性和多样性的方法
为了保持解群体分布性和多样性，首先通过计算进化群体中每个个体的聚集距离，然后依据个体所处的层次及其聚集距离，定义一个偏序集，构造新群体时依次在偏序集中选择个体。
在产生新群体时，通常将优秀且聚集密度比较小的个体保留并参与下一代进化。聚集密度小的个体其聚集距离反而大。
（1）聚集距离：通过计算与其相邻的两个个体在每个子目标上的距离差之和来求取。
4、NSGA-Ⅱ算法的优、缺点
NSGA-II的提出，为多目标进化算法的一大进步，特别是其基于Pareto支配关系的框架被后来许多算法采用，如NSGA-III，VaEA等。同时，NSGA-II对于低维多目标优化问题效果是不错的，但是对于高维多目标优化问题，其首先面对的便是由于其基于Pareto支配关系所导致的选择压力过小的问题，其次，便是拥挤距离在高维空间不适用，计算复杂度也比较高。
5、NSGA-Ⅱ算法的应用
NSGA-Ⅱ算法是Deb等学者于2000年在NSGA算法的基础之上提出来的，该算法能够得到一系列分布均匀、多样性较好的最优解集，适用于多个目标的优化问题，且相对成熟，广泛应用于桥 梁、核电等领域的维修策略优化中。
5.1公交调度优化问题
公交运营成本与乘客出行时间成本是一对矛盾的组合体，单方面最优无法满足公交体系建设的需要。不科学的发车频率不仅会延长乘客的候车时间，降低乘客乘车舒适度，也会造成运营成本的增加。所以在优化调度体系时，应同时考虑车辆运营成本与乘客的出行时间成本进行多目标优化，找到使双方相对最优的策略。利用NSGA-Ⅱ算法求解最优发车间隔。
5.2轨道电路维修策略问题
针对轨道电路传统维修的低可靠性和高维修费用问题，提出轨道电路维修策略多目标优化模型，通过NSGA-Ⅱ算法对其维修策略进行优化。