关于NSGA—II算法的研究

高小艳

摘 要 遗传算法通过模拟生物自适应选择过程和自适应进化过程，通过不断迭代逼近最优解，可以将其用于求解高度复杂的非线性最优值问题，多目标遗传算法在优化多目标问题时具有良好的效果。本文在简单遗传算法的理论基础上，主要着重的介绍了NSGA与NSGA-II算法，得出，改进后的算法时间开销有所降低，既保证了种群的多样性，同时引入拥挤距离排序机制使算法避免了预先设定参数的困难。

关键词 多目标优化 遗传算法 最优解 生物进化算法

中图分类号：TP181 文献标识码：A

0前言

19世纪70年代初期，由于受到达尔文进化理论的启发，Rosenberg提出了采用达尔文进化理论的思想解决多目标优化问题。1993 年，Deb和 Srinivas 首先提出基于非劣分级排序的遗传算法（NSGA）。Hom 提出 Pareto 遗传算法。NSGA-II是针对原NSGA算法存在的不足的改进，2002 年 Deb提出带有精英策略的非劣分级排序的遗传算法（NSGA-II），该算法通过采用快速分级排序以及精英策略，能够提高算法收敛速度及保持结果多样性。目前，NSGA-II算法已经成为解决多目标优化问题的优秀算法，被广泛应用到科学工程领域等。

1 Pareto占优

对于多目标优化问题，通常存在一个解集，这些解之间就全体目标函数而言是无法比较优劣的，其特点是：无法在改进任何目标函数的同时不削弱至少一个其他目标函数。这种解称作非支配解或Pareto最优解。对于组成Pareto最优解集的所有Pareto最优解，其对应目标空间中的目标矢量所构成的曲面称作Pareto最优前沿。

NSGA与简单的遗传算法的主要区别在于：该算法在选择算子执行之前根据个体之间的支配关系进行了分层。其选择算子、交叉算子和变异算子与简单遗传算法没有区别。

2 NSGA算法

NSGA-II拥挤度比较算子：经过前面的快速非支配排序和拥挤度计算之后，种群中的每个个体i都拥有俩个属性：非支配排序决定的配置配序irank和拥挤度id。只要下面任意一个条件成立，则个体i获胜。胜出的个体进入下一个操作。

（1）如果个体i所处的非支配层优于个体j所处的非支配层，即irank

（2）如果他们具有相同的等级，且个体i比个体j有一个更大的拥挤距离，即：。

4结语

NSGA-II与NSGA比较而言，采用了快速非劣排序，新的多样性保持策略，使得其计算复杂度由原来的为O（MN3）降低到O（MN2）（其中M为目标数量，N为种群大小）。

采用了拥挤度和拥挤度比较算子，不但克服了NSGA中需要人为指定共享参数的缺陷，而且将其将其作为种群中个体的比较标准，使得准Pareto域中的个体能均匀地扩展到整个Pareto域，保证了种群的多样性。

参考文献

[1] 郭修豪. 改进遗传算法在多目标问题上的应用研究[D].重庆师范大学，2016.

[2] 徐磊. 基于遺传算法的多目标优化问题的研究与应用[D].中南大学，2007.

[3] 魏静. 基于改进NSGA2算法的给水管网多目标优化设计[D].北京工业大学，2016.