论文部分内容阅读
摘要：解集的分布性是解集的重要性能之一。结合“可变影响空间”和“边界集”，提出了一种新的基于可变影响空间的解集分布性保持机制。该方法通过可变影响空间保持解集的均匀性，并加入边界集来保持解集的分布广度。以经典算法NSGA-II为算法框架，将基于可变影响空间的解集分布性保持机制替代NSGA-II中的分布性保持机制--聚集距离。实验结果证明了该方法的可行性和有效性。
关键词：分布性保持机制;NSGA-II;边界集;可变影响空间
随着各种多目标进化算法的提出，如何评价算法的性能变得越来越重要，学者们往往通过评价解集的性能来评价解集的优劣。解集的性能包含收敛性和分布性两个方面，本文针对解集的分布性进行研究。
1. NSGA-II[1]的分布性保持机制
NSGA-II采用的分布性保持机制是聚集距离，对于要筛选的个体，通过计算每个个体与其他个体间的欧式距离，依次将欧式距离最小的个体淘汰，最终留下与初始种群数目相等的个体。
2. 基于可变影响空间[2]的解集分布性保持机制
随着目标维数的增加，在欧氏距离相等的情况下，两两个体的分布情况有多种，无法仅仅根据距离关系准确得出解集的分布性情况。因而容易出现淘汰分布性好的个体而留下差个体的现象，从而使解集的整体分布性变差。为此，本文提出了基于可变影响空间的解集分布性保持机制，不仅在低维情况下能很好的保持解集的分布性，而且较好的适应于高维问题。
2.1 个体可变影响空间值的计算
个体的可变影响空间值的计算分三步进行：
第一步：计算种群中两两个体间的欧式距离，并在此基础上结合邻近个体数确定个体的可变影响空间半径，其中邻近个体数为，为目标维数，个体的可变影响空间半径的计算公式是，为个体与个体的距离。
第二步：根据个体的可变影响空间半径确定个体可变影响空间，如以个体为圆心，为长度阈值确定个体的可变影响空间，记为，即为个体的可变影响空间。
第三步：统计可变影响空间内的个体数（除圆心，包含影响空间界限上个体），计算可变影响空间内的个体在内的分布关系，其中，为区域半径，所得的值即为个体的可变影响空间值。
2.2 基于可变影响空间的解集分布性保持机制
对于要筛选的M个非支配解，M>N，N为种群大小。对每一个个体，先判断是否为边界解。若是边界解，则将个体保留下来并为其设置一个非常大的可变影响空间值;若不是，再计算其可变影响空间值。根据可变影响空间值由小到大对个体进行删除，若出现几个可变影响空间值最小的个体，则任选一个进行删除，直到满足。
3. 对比实验
本文以基于非支配的多目标进化算法—NSGA-II为主要算法框架，将基于可变影响空间的解集分布性保持机制替代该算法中的聚集距离，我们将嵌入了可变影响空间的解集分布性保持机制的算法称为V-NSGA-II。
为了证明算法中的可信性和有效性，本节选取了NSGA-II，SPEA2[3]两种算法在3，4，6，8维情况下对问题DTLZ1[4]、DTLZ2[4]进行对比测试，实验结果由IGD[5]进行评判，实验独立运行30次取平均值。表1为由IGD对三种算法所得解集的评价结果。IGD进行测试时，值越小越好。表中深色阴影表示最优秀的数值，浅色阴影表示最差的数值。
由表可知，除了4维DTLZ1时V-NSGA-II最差，其余情况下都优于NSGA-II，且随着目标维数的增加，由V-NSGA-II得到的解集越来越优秀。
表1 IGD评价结果
目标维数 函数名称 IGD
SPEA2 NSGA-II V-NSGA-II
3 DTLZ1 0.02091 0.02601 0.02352
DTLZ2 0.05433 0.06868 0.06302
4 DTLZ1 0.04166 0.04653 0.04808
DTLZ2 0.10098 0.13118 0.10461
6 DTLZ1 0.15079 0.25406 0.15242
DTLZ2 0.67403 0.74832 0.72033
8 DTLZ1 0.21587 0.26689 0.21416
DTLZ2 1.53708 1.90278 1.10937
4. 結论
本文提出了一种新的基于可变影响空间的解集分布性保持机制。以经典算法NSGA-II为算法框架，将新的分布性保持机制替代NSGA-II中的聚集距离，并设计了几组实验进行验证。实验结果表明本文方法在分布性保持方面的可行性与有效性。但是该算法还需要进一步提升运行速度，这也将是接下来的研究工作。
参考文献：
[1] Deb K，Pratap A，Agarwal S，Meyarivan T. A Fast and Elitist Multi-objective Genetic Algorithm：NSGA-II. IEEE Transactions on Evolutionary Computation，2002，6（2）：182-197
[2] 郑金华，黄端，王康，张作峰. 基于可变影响空间的多目标进化算法解集均匀性评价方法. 模式识别与人工智能
[3] Zitzler E，Thiele L. Multiobjective Evolutionary Algorithm：A Comparative Case Study and the Strength Pareto Approach. IEEE Transactions on Evolutionary Computation，1999，3（4）：257-271
[4] 郑金华. 多目标遗传算法及其应用. 北京：科学出版社，2007
关键词：分布性保持机制;NSGA-II;边界集;可变影响空间
随着各种多目标进化算法的提出，如何评价算法的性能变得越来越重要，学者们往往通过评价解集的性能来评价解集的优劣。解集的性能包含收敛性和分布性两个方面，本文针对解集的分布性进行研究。
1. NSGA-II[1]的分布性保持机制
NSGA-II采用的分布性保持机制是聚集距离，对于要筛选的个体，通过计算每个个体与其他个体间的欧式距离，依次将欧式距离最小的个体淘汰，最终留下与初始种群数目相等的个体。
2. 基于可变影响空间[2]的解集分布性保持机制
随着目标维数的增加，在欧氏距离相等的情况下，两两个体的分布情况有多种，无法仅仅根据距离关系准确得出解集的分布性情况。因而容易出现淘汰分布性好的个体而留下差个体的现象，从而使解集的整体分布性变差。为此，本文提出了基于可变影响空间的解集分布性保持机制，不仅在低维情况下能很好的保持解集的分布性，而且较好的适应于高维问题。
2.1 个体可变影响空间值的计算
个体的可变影响空间值的计算分三步进行：
第一步：计算种群中两两个体间的欧式距离，并在此基础上结合邻近个体数确定个体的可变影响空间半径，其中邻近个体数为，为目标维数，个体的可变影响空间半径的计算公式是，为个体与个体的距离。
第二步：根据个体的可变影响空间半径确定个体可变影响空间，如以个体为圆心，为长度阈值确定个体的可变影响空间，记为，即为个体的可变影响空间。
第三步：统计可变影响空间内的个体数（除圆心，包含影响空间界限上个体），计算可变影响空间内的个体在内的分布关系，其中，为区域半径，所得的值即为个体的可变影响空间值。
2.2 基于可变影响空间的解集分布性保持机制
对于要筛选的M个非支配解，M>N，N为种群大小。对每一个个体，先判断是否为边界解。若是边界解，则将个体保留下来并为其设置一个非常大的可变影响空间值;若不是，再计算其可变影响空间值。根据可变影响空间值由小到大对个体进行删除，若出现几个可变影响空间值最小的个体，则任选一个进行删除，直到满足。
3. 对比实验
本文以基于非支配的多目标进化算法—NSGA-II为主要算法框架，将基于可变影响空间的解集分布性保持机制替代该算法中的聚集距离，我们将嵌入了可变影响空间的解集分布性保持机制的算法称为V-NSGA-II。
为了证明算法中的可信性和有效性，本节选取了NSGA-II，SPEA2[3]两种算法在3，4，6，8维情况下对问题DTLZ1[4]、DTLZ2[4]进行对比测试，实验结果由IGD[5]进行评判，实验独立运行30次取平均值。表1为由IGD对三种算法所得解集的评价结果。IGD进行测试时，值越小越好。表中深色阴影表示最优秀的数值，浅色阴影表示最差的数值。
由表可知，除了4维DTLZ1时V-NSGA-II最差，其余情况下都优于NSGA-II，且随着目标维数的增加，由V-NSGA-II得到的解集越来越优秀。
表1 IGD评价结果
目标维数 函数名称 IGD
SPEA2 NSGA-II V-NSGA-II
3 DTLZ1 0.02091 0.02601 0.02352
DTLZ2 0.05433 0.06868 0.06302
4 DTLZ1 0.04166 0.04653 0.04808
DTLZ2 0.10098 0.13118 0.10461
6 DTLZ1 0.15079 0.25406 0.15242
DTLZ2 0.67403 0.74832 0.72033
8 DTLZ1 0.21587 0.26689 0.21416
DTLZ2 1.53708 1.90278 1.10937
4. 結论
本文提出了一种新的基于可变影响空间的解集分布性保持机制。以经典算法NSGA-II为算法框架，将新的分布性保持机制替代NSGA-II中的聚集距离，并设计了几组实验进行验证。实验结果表明本文方法在分布性保持方面的可行性与有效性。但是该算法还需要进一步提升运行速度，这也将是接下来的研究工作。
参考文献：
[1] Deb K，Pratap A，Agarwal S，Meyarivan T. A Fast and Elitist Multi-objective Genetic Algorithm：NSGA-II. IEEE Transactions on Evolutionary Computation，2002，6（2）：182-197
[2] 郑金华，黄端，王康，张作峰. 基于可变影响空间的多目标进化算法解集均匀性评价方法. 模式识别与人工智能
[3] Zitzler E，Thiele L. Multiobjective Evolutionary Algorithm：A Comparative Case Study and the Strength Pareto Approach. IEEE Transactions on Evolutionary Computation，1999，3（4）：257-271
[4] 郑金华. 多目标遗传算法及其应用. 北京：科学出版社，2007