多目标优化算法标准测试函数寻优研究

栗方

摘要：多目标优化问题在各种领域中日益展现出举足轻重的地位。该文对6种多目标优化算法进行了测试，选择了四种不同性质的测试函数，安排了12组实验，从实验数据可以得出，NSGA-III算法在多目标优化问题中具有很好的寻优效果，IBEA算法在单目标优化问题或者是多目标问题中需要观测单个变量时能起到很好的寻优效果，CMAES算法在高值域多目标优化中能起到很好的优化作用。

关键词：多目标优化算法;多目标标准测试函数;智能优化算法;多目标优化评价指标;多目标优化性能测试

中图分类号：TP301.6      文献标识码：A

文章编号：1009-3044（2020）23-0203-04

Abstract： Multi-objective optimization problems play an increasingly important role in various fields. In this paper， six kinds of multi-objective optimization algorithms are tested， four kinds of test functions with different properties are selected， and 12 groups of experiments are arranged. From the experimental data， it can be concluded that NSGA-III algorithm has a good optimization effect in multi-objective optimization problems， and IBEA algorithm can play a good optimization effect when single-objective optimization problems or multi-objective problems need to observe a single variable. CMAES algorithm can play a good role in high-range multi-objective optimization.

Key words： multi-objective optimization algorithm; multi-objective standard test function; intelligent optimization algorithm; multi-objective optimization evaluation index; multi-objective optimization performance test

1 背景

多目標计算问题在日常生活中很常见，不管是在科学探索还是实际的工程应用当中，多目标优化算法都是很重要的。不仅因为多目标优化算法需要同时对多个目标进行优化，多目标优化的最优解还是一组解集，如何选出符合决策者偏好的解也是需要注意的问题[1]。常用的多目标算法有NSGA-II、NSGA-III、CMAES、IBEA、MOEAD等，每种算法都有各自的适应条件，本文会通过设计的实验优化对比出6种算法的优劣性及适应空间。在多目标优化算法的发展过程中，形成了多种标准测试函数，这些测试问题由于其容易将优化问题上升为多维而被广泛采用。常用的标准测试函数有SCH、DEB、ZDT1、ZDT2、DTLZ2、DTLZ3、WFG3、WFG7等，这些测试函数各有其特点。在优化性能的评比中，通常采用以下3种方法，只考虑收敛性指标、只考虑多样性指标、综合考虑收敛性和多样性指标。本文围绕多目标优化问题，基于Platypus实验平台，设计了6种多目标优化算法在3种不同适应度值下的标准测试问题中优化效果分析实验[2]，通过实验数据分析出6种算法的优劣性，以便在处理优化问题时选择适合问题的优化算法。

2 多目标优化算法

2.1 NSGA-II和NSGA-III算法

带精英策略的非支配排序遗传算法（NSGA-II）是迄今为止最优秀的多目标进化遗传算法之一，该算法解决了第一代优化算法中如何将进化算法与多目标优化问题有机结合起来的问题，采用了基于聚类、精英保留机制、空间超格、拥挤距离等机制。该算法面临的主要问题是如何处理高维多目标优化以及效率问题[3]。该算法的逻辑图如图1所示。

是否满足终止条件取决于人为设定或迭代次数限定，但最优值不会变化，迭代次数要尽可能多次，因为在迭代次数太少的情况下，不能确定出现的解为最优解。在NSGA-II遗传算法中，拥挤度计算是确保种群多样性的一个重要部分[4]，伪代码表示为：

NSGA-III算法在原有的NSGA-II算法框架基础上，增添了下面结构：① 假设有一个规模为N的种群A，用选择、重组、变异遗传算子对种群A进行操作，得到一个规模为N的种群B，再将种群A和种群B混合，得到一个规模为2N的种群C;②对种群C进行非支配排序;③对目标函数进行标量化操作，方便下一步关联参考点，见公式（1）;④寻找极值点，此时需要用到ASF函数，见公式（2）;⑤遍历每个函数，找到ASF数值最小的个体，根据这些点的具体函数值，计算出相对应坐标轴上的截距[ai]，得到[ai]和[zi]后，按照公式（3）进行归一化运算。

之后对计算出的参考点进行递归处理，筛选子代并删除参考点寻优。

2.2 MOEAD算法

MOEAD（基于分解的多目标优化算法）将一个多目标优化问题分解为若干个标量优化子问题，并同时对其进行优化，每个子问题都通过使用来自它的几个相邻子问题的信息来优化的，能够大大提高处理处理高纬度目标函数时的效率[5]，算法流程如下：

1）初始化设置，包括目标函数、终止条件、邻居个数等;

2）分解目标问题，明确子问题及邻居;

3）依次对每个子问题进行优化;

4）更新端点和邻居;

5）判断停止条件。

通过算法流程可以看出，MOEAD是一种将多目标问题分解为一系列的单目标问题的方法，在处理高纬度问题时降低了问题维度。

2.3 IBEA算法

IBEA（基于指标的多目标选择）采用对指标的优劣性判断来优化目标问题，算法流程如下：

1）产生初始种群P，种群大小为α，当前迭代此时m=0;

2） 适应度计算，根据如下公式计算P里个体的使用度，例如[x1]（k为比例缩放因子）;

3） 对每一代P，进行迭代筛选，直到种群大小为a;

4） 终止条件判断;

5） [p']为[p]的复制;

6） 用交叉变异作用在[p']上，[p]=[p']+[p]，m=m+1，转2）。

3多目标优化标准测试函数及评价指标

3.1多目标优化标准测试函数

3.1.1 DTLZ2测试函数

DTLZ2可以扩展到任意多个目标，从而很好地扩展到高维多目标优化问题，是目前采用的最多的测试算法之一[6]，公式如下：

3.1.2 WFG测试函数

WFG为变量关联测试函数，WFG1具有平偏好的特征，WFG2具有多模非连续特征，WFG3为欺骗问题，WFG7为参数独立测试函数，WFG9为参数独立多模欺骗问题。本文选取WFG3和WFG7作为测试函数。

3.2多目标优化性能评价指标

评价一个算法效率的方法，就是设置算法性能评价指标，目前主流的多目标算法性能评价指标主要有两种。

3.2.1收敛性指标

设A和B为两组PF近似解集，C（A，B）的定义如下面公式（6），表示B中个体至少被A中一个个体支配的占比[7]：

若[CA，B=1]，则表示B中所有个体都被A支配，证明B的收敛性比A差。

3.2.2多样性指标

空间评价法可衡量PF近似解集中个体在目标空间中的分布情况，表达式如公式（7）所示：

其中，[PF] 代表已知的真实[PF]，[di]为解集中非支配边界上两个连续向量的欧氏距离，[d]是平均距离。该目标方法比较适用于二维目标空间，在超多目标情况下不理想。

4多目标优化性能测试实验设计

4.1实验平台搭建

本文基于Platypus实验平台，使用Pycharm2019编译器设置了12组不同参数配置的实验。对NSGAII、NSGAIII、IBEA、MOEAD、SPEA2、CMAES六种优化算法在适应度值分别为500、5000、50000时分别对DTLZ2、WFG3、WFG7、WFG2四种测试问题进行优化分析。

4.2实验具体内容设置

详细的12組实验设置及安排如下。

E-1：适应度值选取500时，六种算法对DTLZ2进行优化计算。

E-2：适应度值选取5000时，六种算法对DTLZ2进行优化计算。

E-3：适应度值选取50000时，六种算法对DTLZ2进行优化计算。

E-4：适应度值选取500时，六种算法对WFG3进行优化计算。

E-5：适应度值选取5000时，六种算法对WFG3进行优化计算。

E-6：适应度值选取50000时，六种算法对WFG3进行优化计算。

E-7：适应度值选取500时，六种算法对WFG7进行优化计算。

E-8：适应度值选取5000时，六种算法对WFG7进行优化计算。

E-9：适应度值选取50000时，六种算法对WFG7进行优化计算。

E-10：适应度值选取500时，六种算法对WFG2进行优化计算。

E-11：适应度值选取5000时，六种算法对WFG2进行优化计算。

E-12：适应度值选取50000时，六种算法对WFG2进行优化计算。

5多目标优化性能测试实验结果分析

5.1进行12组实验结果展示

对DTLZ2测试问题在不同适应度值下的结果展示如图2、图3、图4所示;对WFG3测试问题在不同适应度值下的结果展示如图5、图6、图7所示;对WFG7测试问题在不同适应度值下的结果展示如图8、图9、图10所示。对WFG2测试问题如图11、图12、图13所示。

5.2 对DTLZ2测试函数结果的分析

从图2中的数据可以看出，当适应度值为500时，6种算法都不能很好地优化出帕累托前沿面，也就是无法得出最优值。此时NSGA-II和NSGA-III算法能得出大量的非支配解，而MODEA得到的解空间差较大，效果在6种算法中最差。 在图3中，适应度值设置为了5000，此时NSGA-II和NSGA-III可以优化出帕累托前沿，但相比较来说NSGA-III优化效果最好，CMAES算法优化出了大量非支配解，是六种算法中最好的，但是帕累托前沿面没有NSGA-III算法体现的好[8]。IBEA算法在三个坐标平面上找到了帕累托前沿线，但是解空间中非支配解稀少，这证明了IBEA算法在单目标寻优上具有很高的效率。图4中适应度值设置为了50000，此时NSGA-III算法表现最优，该算法优化出了完美的帕累托前沿面，并且优化得到的解在解空间中分布均匀，优化效果远远高于NSGA-II算法。此时CMAES虽然优化得解最多，但仍然无法表现出良好的回归曲线。SPEA2算法优化效果仅次于NSGA-III并优于NSGA-II算法。IBEA算法仍是对单目标结果表现出优越性。

5.3对WFG3测试函数结果的分析

如图5所示，在适应度值为500时，CMAES算法表现最优，得到了大量最优解，解空间基本收敛，MOEAD算法表现最差，体现不出收敛性。图6中适应度值为5000时，IBEA开始表现出对目标函数的适应性，已经形成完整的收敛直线，此时另外5种算法效果基本相同。图7中适应度值为50000时，IBEA算法求出了无偏差的最优解，这是由于IBEA算法的特性决定的，而CMAES在低值区域表现较差，在高值区域优化效果良好，证明CMAES对高值域多目标函数具有很好的适应性。此时NSGA-II和NSGA-III算法无法得到最优收敛曲线，证明NSGA算法对WFG3这种类型的测试问题不能起到良好的优化效果。

5.4对WFG7测试函数结果的分析

图8中，在适应度值较小时，依然是CMAES算法表现最好，求得的最优解最多，MOEAD算法表现最差。当适应度值增加到5000时，依然是CMAES算法最优，SPEA2和NSGA-III优化效果次之。在图10中适应度值设置为50000时，NSGA-III算法最优，IBEA算法仍然是能在单坐标平面上优化出最优解，此次实验进一步证明IBEA算法在单目标优化上能表现出很高的效果，NSGA-III在多目标优化问题中优于其他几种算法。

5.5对WFG2测试函数结果的分析

图11中，在适应度值为500时，无一种算法表现出良好的寻优曲线，在图12所示的结果中，适应度值被设置为了5000，此时NSGA-II、NSGA-III、CMAES、SPEA2四种优化算法寻优效果较好，由于IBEA算法本身特性，其优化效果仍然是稀疏边界，无法形成帕累托曲面，MOEAD算法依然无法表现出好的解。在图13中，对应的是实验E-12结果图，实验数据显示，当适应度值设置为50000时，IBEA算法在优化结果上表现得稀疏，无法形成帕累托曲面，进一步证明IBEA算法在高纬度优化问题上优化效果不佳，MOEAD算法优化效果最差，得到的解杂乱无章，CMAES算法优化效果最好，NSGA-III算法次之。此三次实验进一步证明在对高纬度多目标优化问题的求解中，NSGA-III算法和CMAES算法能起到很好的优化作用，对单目标问题或者低维度问题采用IBEA算法能获得更优的帕累托最优解。

6 结论

本文通过搭建Python平台，进行了12组不同设置的实验安排，通过对12组实验结果的分析，对比出所选取6种算法的优缺点，NSGA-III算法在整体上優于NSGA-II算法，在处理多目标优化问题上，NSGA-III算法表现优越，另外5种算法都次之。通过设置的WFG3测试函数得出，在对多目标优化问题分解方面，IBEA效果最好，证明在处理单目标问题或者需要研究多目标函数中某个单独变量时采用IBEA算法最好。CMAES算法在三种测试问题上求解最多，但并不能形成良好的帕累托回归曲面，在WFG3测试问题中，CMAES算法在低值区域表现较差，证明CMAES算法在高值域多目标优化中能起到很好的优化作用。在所有实验中，MOEAD优化效果没有其他的五种算法好，SPEA2算法表现良好，但优化效果适中。通过本次实验得出结论，在多目标优化算法中，NSGA-III表现最优，在对单目标测试问题或者观测多目标函数中的单个量时采用IBEA算法最好，在对大型高值多目标问题的研究上采用CMAES算法能得到较多的最优解。

参考文献：

[1] 胡涵，李振宇.多目标进化算法性能评价指标综述[J].软件导刊，2019，18（9）：1-4.

[2] 李子轩，杨国来，孙全兆，等.强冲击载荷下永磁式电涡流阻尼器阻力特性及优化研究[J].兵工学报，2018，39（4）：664-671.

[3] 李朝芳，苟英.基于改进NSGA-Ⅱ算法测试资源优化配置的研究[J].科学咨询，2017（11）：38.

[4] 戴喜妹，张军峰，赵鹏力，等.离场航班多目标优化排序研究[J].哈尔滨商业大学学报，2019，35（2）：241-245， 252.

[5] 徐一红，陈青华. 基于GEP算法的煤矿瓦斯涌出量预测模型研究[J].山东师范大学学报，2015，30（2）：27-30.

[6] 吴伟丽.基于NSGA-Ⅲ的复杂成因变压器直流偏磁控制优化算法[J].电测与仪表，2018，55（11）：89-93.

[7] 朱永胜，王杰，瞿博阳，等.含风电场的多目标动态环境经济调度[J].电网技术，2015，39（5）：1315-1322.

[8] 王经卓，樊纪山.空间数据关联的多目标粒子群优化算法[J].控制与决策，2015，30（7）：1291-1297.

【通联编辑：谢媛媛】