基于三支决策的多目标优化自然计算策略研究

张心茹， 季伟东， 岳玉麒， 殷曾祥

(哈尔滨师范大学 计算机科学与信息工程学院， 哈尔滨 150025)

0 引 言

多目标优化问题(MOP)在工程实践与理论研究等领域广泛存在并持续发展，多目标优化问题具体是指各目标之间相互冲突与协同，传统的自然计算方法难以找到最优解。国内外诸多学者对传统自然计算方法进行改进，提出以多目标进化算法(MOEA)、非支配排序遗传算法(NSGA)等经典算法为首的诸多衍生算法，从而适应多目标优化问题的求解。Deb等[1]提出一种带精英策略的快速非支配排序算法NSGA-II，依据快速非支配排序，对种群分层，降低算法的计算复杂度；Zhang等[2]将数学规划和进化算法相结合，提出基于分解的多目标优化算法(MOEA/D)，提高算法的计算速度；2002年，Coello等[3]提出多目标粒子群算法(MOPSO)，首次将标准粒子群优化算法应用于多目标领域；2016年，Mirjalili等[4]提出多目标灰狼算法(MOGWO)，具有参数少、实现简单、鲁棒性强等优点；Yen等[5]提出一种基于动态多子群的多目标粒子群优化算法(DSMOPSO)，充分平衡探索开发能力；Martinez等[6]提出重新初始化策略，提高种群多样性；魏文红[7]等人通过泛化反向学习机制，引导种群个体向最优帕累托前沿逼近；2018年，谢承旺[8]等提出混合型多目标萤火虫算法，融入档案精英个体引导策略及三点最短路径技术，提高算法的整体性能；2020年，张伟等[9]提出基于种群分区的多策略粒子选取，平衡算法的收敛性和多样性；徐航等[10]利用小孔成像反向学习策略增加寻优的多样性，提高跳脱局部最优的能力；2022年，季伟东等[11]利用局部线性嵌入(LLE)降维思想解决大规模多目标优化领域问题；王旭等[12]利用多指标的精英个体博弈机制，融合K-means 聚类，平衡算法性能。

国内外学者虽以不同视角和背景针对收敛精度、速度、分布性等多方面进行改进和创新，但大多针对于某一单独算法，其策略不具有通用性和普适性。对于多目标优化领域，寻找一种通用的优化策略具有重要的意义。针对上述问题，本文基于三支决策理论思想，结合三支分域及异域分治策略，提出应用于自然计算领域的三支决策多目标优化策略(Natural computing strategy for multi-objective optimization based on three-way decision, 3WD-MNC)，通过分段Tent映射改变种群初始化，提高算法的多样性；结合三支决策思想，提出三支分域策略，对子域种群进行异域分治策略寻优，从而指导种群进化。

将该方法分别应用于两种不同的自然计算方法中，从整体和局部两方面提升算法收敛性、分布性、高效性，综合提升算法平均性能，并与这两个代表性算法在6个经典测试函数上进行对比，验证其有效性和普适性。

1 多目标优化问题

设在目标空间Rm中，多目标优化问题的数学描述可表示为式(1)：

minF(x)=(f1(x),f2(x), …,fm(x))

(1)

满足条件：

其中，x=(x1,x2,…,xn)为决策空间Ω中的一个决策变量，gi(x)和hj(x)为约束函数，分别表示MOP的p个不等式约束和q个等式约束条件，共同确定满足所有条件的可行域。

2 基于三支决策的多目标优化自然计算策略(3WD-MNC)

2.1 Tent混沌种群初始化

初始种群的优劣在一定程度上会影响算法的收敛速度和解的精度[13]。随机产生的数据初始化种群信息难以保留种群的多样性。因此本文采用迭代速度快，且遍历均匀性较好的Tent混沌映射，设初始化种群的种群规模为n，在[0,1]内随机产生初始值X0，利用公式(2)进行迭代并生成n-1个新个体，最后将全部个体映射到变量的取值范围内，生成Tent混沌初始化种群。在保证种群多样性的前提下，提高收敛速度，缩短寻优时间。

(2)

2.2 基于三支思想的种群分域策略

三支决策是将不确定事物放入“待定区”的决策模式，将整体分为正域、负域、边界域。正域代表接受，负域代表拒绝，边界域代表无法做出接受或拒绝的判断。三支决策可以很好划分样本间属性的差异，将相似样本划分到同一区域，采用不同策略。受此思想影响，将初始化种群分为正域、负域、边界域，对于可行解空间Ω，设定阈值因子r，构造基于三支决策的自适应种群分域，式(3)：

(3)

其中，POS、NEG、BND分别为正域、负域、边界域，Favg为平均适应度值，设定阈值因子r划分域并区分优劣个体。

2.3 异域分治策略

通过三支分域策略将初始种群分为三域后，对三域进行不同的寻优更新操作。

在BND域，将候选解间的欧式距离，作为个体的分布性指标，d(x,y)为n维空间中任意两个体之间的真实距离，式(4)：

(4)

利用式(5)将BND中最优个体的d值与平均值相比较，若其大于平均欧氏距离，则对最优个体进行高斯变异，反之反向学习变异，增强全局搜索，增加种群多样性。

(5)

NEG域中，获取随机数rand，根据当前个体迭代次数t、最大迭代次数Tmax以及突变率mu，计算扰乱算子p，式(6)：

(6)

若rand>p，采用小孔成像变异策略，随机向附近寻优更新，变异计算公式(7)：

(7)

在POS域，同样通过获取随机数rand，根据式(6)计算扰乱算子p。若rand

2.4 3WD-MNC在自然计算方法中的实现策略

本文将3WD思想以及异域分治策略结合，构建3WD-MNC算法，并将其应用于自然计算领域的MOPSO和MOGWO中，其中，算法流程图如图1所示。

图1 3WD-MNC算法流程图

3 实验结果与分析

为验证所提策略有效性，选取ZDT1-ZDT4、ZDT6、DTLZ2作为测试函数，参数设置：双目标种群规模N=100，迭代次数为100次；三目标种群规模N=300，迭代次数100次，测试30次；3WD策略中阈值因子r=0.1。

将所提策略应用于MOPSO和MOGWO中，得到3WD-MOPSO和3WD-MOGWO，与MOPSO、MOGWO经典算法进行对比实验，各对比算法在测试函数上的超体积指标(HV)、反世代距离指标(IGD)的结果见表1和表2，其中最优结果加粗显示。

表1 HV指标对比

表2 IGD指标对比

由表1可知，3WD-MOGWO和3WD-MOPSO均优于MOPSO算法，说明本文所提3WD策略应用于MOPSO算法和MOGWO算法后的综合性能相对较好。

由表2可知，在ZDT系列5个测试问题上，3WD-MOGWO算法和3WD-MOPSO算法的表现均优于其他经典算法，且相对于其他算法，平均值以及标准差也取得了较低的数值，表示本文所提算法在各测试函数上均有不错的表现。ZDT1、ZDT4中，3WD-MOGWO算法普遍优于MOPSO等算法，相对较好地收敛于真实帕累托前沿的附近，且分布较为均匀。

仿真结果表明，在6个测试函数中，与其他经典优化算法相比，本文所提出的3WD策略大多都能找到更好的解，说明本文所提策略在解决多目标问题能很大程度上提升算法的综合性能，有效平衡算法的收敛性与多样性。

4 结束语

本文提出基于三支决策的多目标优化自然计算策略，充分利用三支决策三分而治的基本思想，将整体分为3个独立域，分别对每个域进行异域分治策略，有效解决收敛速度过快导致陷入局部最优的问题，保证前期多样性，维持后期收敛速度的稳定性，最终找到均匀分布且准确的前沿。综合实验结果表明，本文策略具有较好收敛性和多样性，能够有效提高解的精度。