基于维度扰动的快速非支配排序遗传算法II

张茂清，李东洋，胡 博，汪 镭，崔志华，郭为安

(1.同济大学 电子与信息工程学院，上海 201804；2.太原科技大学 计算机科学与技术学院，山西 太原 030024；3.同济大学 中德工程学院，上海 201804)

0 引言

多目标优化问题是指目标函数数量为2～3个的优化问题[1-3]。一般情况下，多目标优化问题不同目标之间具有相互冲突的特点，即一个目标性能增加会导致另外一个目标性能降低。为求解此类优化问题，许多学者提出了有效的求解算法，如NSGA-II[4]、SPEA2[5]、PEASII[6]以及最近提出的MOEAIGDNS[7]等。NSGA-II[4]是Deb等于2002年提出的算法。由于其在多目标优化问题上较优的求解性能引起了广大研究者关注，并被应用到许多实际工程优化问题中。根据不同研究角度，可将近些年对NSGA-II的研究做如下分类。

优化NSGA-II中支配关系，进一步拓展算法求解问题范围。针对实际工程领域中复杂非线性多目标优化问题，赖文星等[8]发现NSGA-II无法有效识别伪非支配解。为解决此类问题，赖文星等[8]采用快速支配强度排序法构造非支配集,引入基于方差的拥挤距离公式,并通过自适应精英保留策略动态调整精英保留规模。为在理论上解决NSGA-II中Pareto支配在高维多目标优化问题上无法区分有效解的问题，Yang等[9]提出利用基于网格的支配方法来区分不同个体，并利用网格产生待交叉父代个体。同样为解决此类问题，Zhang等[10]则提出基于分解的进化算法，即将多目标优化问题分解为多个单目标优化问题，有效避免了多目标优化问题中支配关系，提升了算法的收敛性能。

针对实际工程应用问题特点，改善算法适用性，郝志宽等[11]针对车辆悬架系统中多目标优化问题特点，提出引入精英保持策略,去除重复个体,减少变量重复性,有效提高了算法的效率。面向特定区域部署的临近空间通信网络需要兼顾考虑资源分配、覆盖率及载荷功率等多个因素，为了针对性优化此类复杂问题，唐树祝等[12]将动态反向学习机制和差分局部变异算子引入NSGA-II，为网络实际部署提供了参考。为应对跨区域突发事件过程中受灾点服务差异化需求问题,宋艳等[13]通过设计分段染色体编码方式改进NSGA-Ⅱ算法，提升运算效率，并且有效地解决了多目标选址决策问题。

虽然NSGA-II在理论以及应用方面[14]已有广泛研究，但其采用的锦标赛选择策略(tournament selection)会产生大量重复个体，从而导致后代种群多样性受到影响。针对此类问题，笔者设计具有维度扰动策略的NSGA-II(non-dominated sorting genetic algorithm II based on dimensionality perturbation, DPNSGA-II)，该算法通过采用对部分维度进行扰动的方法消除重复个体，从而有效地提高了算法的整体性能。

1 基本概念以及锦标赛选择策略

1.1 基本概念

笔者考虑如下多目标优化问题[15]：

(1)

定义2：决策空间上所有pareto最优解构成的集合称为pareto最优解集(paretoset)。

定义3：pareto最优解集在目标空间上对应点集称pareto前沿面(paretofront)。

1.2 锦标赛选择策略以及分析

NSGA-II[4]是多目标优化算法中经典的算法,其涉及快速非支配排序、锦标赛选择策略(tournament selection)、交叉算子、变异算子以及拥挤度距离等多种策略。NSGA-II中种群个体间进化压力以及多样性保持策略主要依赖快速非支配排序以及拥挤度距离的方法。锦标赛选择策略是NSGA-II算法中用于选择待交叉父代个体的主要方法，如图1所示。首先从种群中以等概率选择个体，然后从所选个体中选择最优个体作为父代个体，按照上述方法多次选择即可产生多个交叉父代。从上述过程可看出，若个体Ii为种群中第一层非支配个体，则其有很大概率在多次选择较优个体时被再次选中，从而导致出现多个重复个体现象。

图1 锦标赛选择策略说明

图2为运行NSGA-II 算法时，运用锦标赛选择策略单个个体每代最大重复次数统计，图3为算法运行到70代时运用锦标赛选择策略所产生重复个体数量统计，其中运行条件为种群个体数量为100，算法运行80代，测试函数为ZDT1(请见实验部分)。从图2可以看出，算法NSGA-II计算过程中每代都会出现每个个体5次的重复次数，最大出现10次重复。从图3可看出，就某一代重复个体而言，较优个体出现4次，甚至最高出现10次重复次数。若每个个体均按照上述数量重复，则可导致后代个体多样性变差以及算法整体性能降低。

图2 每代重复个体统计

图3 第70代重复个体数量统计

2 维度扰动策略

(2)

(3)

(4)

图4 维度扰动示意图

3 实验结果及分析

为验证笔者所提算法性能，本部分实验为两小部分：

(1)第一部分验证笔者所提算法参数λ取1.0E-02、1.0E-03、1.0E-04、1.0E-05对算法性能的影响；

(2)第二部分将笔者所提基于维度扰动的NSGA-II与传统算法SPEA2[5]、PEASII[6]以及最近提出的算法MOEAIGDNS[7]做对比。表1列出了上述不同算法运行所需参数。其中pc为交叉概率；pm表示变异概率；D为测试函数变量维度。div为每个目标分量个数。注意，所有参数设置均按照原始参考文献设置，有兴趣读者请参阅文献[5-7]。

表1 算法参数说明

(3)展示种群多样性指标与个体进化代数之间的关系图，并进一步分析验证本文前述维度扰动策略所起作用。

为了综合测试算法性能，笔者采用ZDT测试函数集[16]，如表2所示。ZDT测试函数集由Zitzler和Deb在2000年提出，这些函数具有凸、凹、连续、非连续和具有多重局部最优等特点，评价指标采用IGD[17]。

实验所用计算机为Inter Core i 5-2400 3.10 GHz CPU, 6.00 GB内存，Windows7操作系统，运行环境为Matlab7.9。每个算法独立运行20次，算法最大迭代100次，种群个体为50。

3.1 参数.对算法影响

表2所示为不同λ取值对本文算法的影响，其中每个取值为算法独立运行20次IGD均值。最后一行为Friedman检验结果ranking值(排序值)，值越小表示算法性能越优，Friedman检验是对每个算法运行20次的IGD均值计算得出的，最优值用黑体显示。对比算法的方式为首先通过比较不同算法在各个测试函数集上的IGD均值以及在整个测试函数上占优的总数，然后进一步比较Friedman检验结果，综合以上方法得出最优算法。

表2 实验算法所求平均IGD对比

从表2可看出，λ=1.0E-04时分别在ZDT1、ZDT2、ZDT4表现较优，在ZDT2和ZDT6表现略差。从Friedman检验结果来看，λ=1.0E-04时具有最小检验值。因此，综合而言，当λ=1.0E-04时本文算法具有较优性能。下面实验将采用λ=1.0E-04作为算法DPNSGA-II参数。

3.2 与现有算法对比

表3列出了笔者所提算法与NSGA-II、PEASII、SPEA2、MOEAIGDNS对比结果，其中“均值”表示算法运行20次的IGD平均值，“方差”表示算法20次求解IGD结果“方差”。最后一行为Friedman检验结果ranking值，其由在每个测试函数上对每个算法运行20次的IGD均值计算得出。

从表3可以看出，与NSGA-II相比，笔者所提算法在ZDT1、ZDT2、ZDT3、ZDT4上均表现较优，说明笔者所提基于维度扰动的策略有效地改善了算法性能。与其他算法相比，笔者所提算法在ZDT3上超过SPEA2性能。就Friedman测试结果而言，笔者所提算法具有较小ranking值，说明本文算法整体性能较优。

图5展示算法DPNSGA-II、NSGA-II以及真实前沿面在不同测试函数上的对比效果。从图5可以看出，在收敛性方面，算法DPNSGA-II与NSGA-II在ZDT1测试函数上有明显差距；在ZDT2上，算法NSGA-II所求结果均匀性稍差于DPNSGA-II。在ZDT3和ZDT6测试函数上可明显看出，NSGA-II算法在某些点上存在明显偏离真实pareto前沿面(true pareto front)的个体。在ZDT4上的两个算法性能表现可以充分说明改进算法DPNSGA-II有效地改善了NSGA-II 收敛性，提高了算法的整体性能。

表3 不同算法获得的IGD值

图5 不同算法pareto前沿面对比

3.3 种群多样性指标分析

图6展示了DPNSGA-II和NSGA-II算法在运行过程中种群多样性变化趋势，其中横坐标表示算法评价次数(即种群个体与算法运行代数的乘积，此方式相比于以代数更加精细反应种群多样性的变化)，纵坐标表示多样性指标，所用测试函数为ZDT1。

图6 种群多样性随代数变化趋势说明

根据第二部分介绍的扰动策略，该方法可以有效减少重复个体数量。从图6种群多样性变化趋势对比可以看出，笔者提出的DPNSGA-II 算法在运行初期相对于NSGA-II多样性较差，其原因是在初始化种群时，种群个体间本身具有较大距离，且分布相对均匀，此时笔者所提维度扰动策略只能在个体附近产生扰动，并未产生明显效果。随着种群个体不断进化，在算法运行到1 000次评价时，DPNSGA-II对应种群多样性明显优于NSGA-II对应种群性能，并一直保持到算法运行结束。在1 000次评价之后，个体不断逼近真实pareto前沿面，同时，个体间距离不断缩小，此时维度扰动策略产生作用，使得种群多样性保持在一定程度，有利于种群向更优的方向进化。

基于以上讨论，综合比较而言，笔者所提算法DPNSGA-II通过降低算法重复个体的方式，有效改进了算法整体性能，证明笔者所提改进策略的有效性。

4 结论

锦标赛选择策略是NSGA-II用于选择产生后代的策略，由于其固有缺陷导致产生大量重复个体。为了解决此问题，笔者提出了基于维度扰动的策略，即通过以当前父代位置为期望，融入方差参数的正态分布函数进行扰动，以此消除重复个体现象。通过实验数据可以说明，提出的基于维度扰动的策略可以有效地提升算法性能，达到了预期的效果。后期研究工作将专注于NSGA-II算法性能的进一步提升。