一种双种群协同进化的混合NSGA-II与MOPSO多目标算法

摘 要：多目标非支配排序遗传算法（Non-dominated Sorting Genetic Algorithm II，NSGA-II）是一种经典的多目标进化算法，具有鲁棒性强和搜索性能高的优点，多目标粒子群优化算法（Multi-objective Particle Swarm Optimization，MOPSO）是新型的进化算法，具有收敛速度快、精度高和搜索效率高的优点。为了充分发挥这2种算法的优势，本文提出一种结合NSGA-II和MOPSO的双种群协同进化多目标优化算法。将算法应用于5个标准测试函数优化问题进行对比试验，试验结果表明，本文算法得到的最优解集更接近真实帕累托（Pareto）前沿，收敛性、均匀性和分布性更好，综合性能更强。

关键词：NSGA-II；MOPSO；协同进化；多目标算法

中图分类号：TP 11" " " " 文献标志码：A

在工程实践和科学研究中，许多问题涉及多个相互影响、相互冲突的目标。进化算法在解决多目标优化问题方面具有独特优势，因此受到广泛关注。非支配排序遗传算法（Non-dominated Sorting Genetic Algorithm II，NSGA-II）是经典的多目标进化算法之一[1]，其鲁棒性和搜索性能较强。多目标粒子群优化算法（Multi-objective Particle Swarm Optimization，MOPSO）是一种新兴的进化算法范例[2]，其收敛速度快，精度和搜索效率高。这2种算法在开发和探索过程中各具特色，为了充分利用其各自的优势，本文提出一种双种群协同进化的混合改进NSGA-II和MOPSO的多目标算法。针对多个标准测试函数优化问题进行试验，试验结果表明，与对比方法相比，本文提出的算法在大多数试验中效果更好。

1 多目标粒子群（MOPSO）算法原理

1995年提出的粒子群算法（Particle Swarm Optimization，PSO）是一种模拟鸟类觅食行为的算法，具有操作简单、速度快等特点。但是在实际应用中，许多决策问题都是多目标优化问题，采用粒子群算法来处理多目标优化问题是一种有效方法，COELLO等[3]将粒子群优化算法扩展至多个目标，提出了基于外部存档思想和帕累托（Pareto）支配基本原理的MOSPO。假设D维的搜索域中包括N个粒子，那么第i个粒子的位置和速度如公式（1）、公式（2）所示。

xid=（xi1，xi2，…，xid） （1）

vid=（vi1，vi2，…，vid） （2）

式中：xid为第i个粒子在第d维的位置；vid为第i个粒子在第d维的速度。

在粒子群优化算法中，单个粒子的速度更新过程如公式（3）所示。

vid（t+1）=wvid（t）+c1r1（Pbestid（t）-xid（t））+c2r2（Gbestd（t）-xid（t）） （3）

式中：vid（t+1）为粒子i在维度C中的速度更新后的值；t为当前迭代次数；w为惯性权重，控制上一个时刻速度对当前速度的影响，协调全局/局部搜索能力；vid（t）为粒子i在维度d中的当前速度；c1、c2分别为局部和加速因子，表示个体经验和群体经验的权重；r1、r2为随机数，其作用是增加算法随机性；Pbestid（t）为粒子i在维度d中的个体最优位置；xid（t）为粒子i在维度d中的当前位置；Gbestd（t）为整个粒子群体在维度d中的全局最优位置。

粒子i在维度d中的位置更新过程如公式（4）所示。

xid（t+1）=xid（t）+vid（t+1） （4）

式中：xid（t+1）为在第t+1时刻粒子i在维度d中的位置。

多目标粒子群算法的流程如下。1）初始化多目标粒子群算法参数，包括设置种群规模和最大迭代次数等。2）计算粒子群的适应度，根据Pareto支配原则确定非劣解和局部最优个体Pbest。3）计算非劣解集的密度信息，并在其中选择全局最优解Gbest。4）判断是否满足粒子群的收敛条件。如果满足，那么输出全局最优解Gbest；如果不满足，那么更新粒子的速度和位置，重新计算适应度并更新非劣解集。

这个流程使粒子群不断进行优化，向适应度更高的区域移动，最终获得全局最优解。

2 多目标非支配排序遗传算法（NSGA-II）原理

多目标遗传算法是一种分析和解决多目标优化问题的进化算法，其核心是协调各个目标函数之间的关系，寻找使各个目标函数尽可能达到最优化值的解集。最优解集通常包括多个Pareto最优解，这些最优解的集合称为Pareto前沿。多目标优化问题数学模型的计算过程如公式（5）所示 [4]。

（5）

式中：F（x）min为目标函数向量； fi（x）为第i个目标函数，共有m 个目标函数需要同时优化；g（x）、h（x）分别为不等式约束和等式约束。

3 双种群协同进化的混合改进NSGA-II和MOPSO多目标算法

NSGA-II与MOPSO的信息共享机制不同，NSGA-II利用遗传算子来传递信息，MOPSO利用全局最优粒子来引导其他粒子。2种算法各有优势，NSGA-II搜索能力较强，MOPSO收敛速度较快。因此，本文结合这2种算法，以充分利用其各自的优点，并对其分别进行改进，进一步提升性能。具体的改进策略如下。

3.1 双种群协同进化策略

种群协同进化策略基于NSGA-II的非支配排序。将初始化和非支配排序后的种群分为2个部分。Pareto等级较高的上半部分为精英种群，利用NSGA-II的强大搜索能力在该区域中探索更多Pareto解集，确定非支配解。Pareto等级较低的下半部分使用MOPSO算法，学习精英种群来提升自身质量。为避免MOPSO算法导致早熟收敛，本文采用轮盘赌方法，从精英种群中选择个体作为MOPSO的“社会部分”学习样本。

3.2 改进NSGA-II——基于拥挤度的动态交叉与变异概率

在NSGA-II中，交叉与变异操作是个体探索空间的关键手段，但是传统方法有一定的盲目性。为了合理控制种群的交叉与变异范围，本文提出一种基于种群拥挤度和进化迭代数的动态交叉与变异概率，以增强种群的收敛性。交叉率和变异率的计算过程如公式（6）、公式（7）所示。

（6）

式中：pc为交叉率；pcagv、 pcmax、 pcmin为pc的平均值、最大值和最小值；t为当前迭代次数；maxIt为最大迭代次数；maxt为当前最大迭代次数；d（i）为第i个个体的拥挤度；dagv（i）为第i个个体所在前沿的平均拥挤度。

（7）

式中：pm为变异率；pmagv、pmmax和 pmmin分别为pm的平均值、最大值和最小值。

公式根据个体拥挤度与种群平均拥挤度之间的关系确定交叉和变异概率的进化方向，同时引入迭代因子，完成种群的自适应进化，加快收敛速度。

3.3 改进MOPSO——非线性学习因子

基本的粒子群算法采用固定的学习因子，不利于全局搜索最优解。因此，本文对其进行调整。在算法前期，迭代次数少，那么c1较大，c2较小，利于局部寻优，增加种群多样性；在算法后期，迭代次数多，那么c1较小，c2较大，利于全局搜寻，加快收敛。改进后的迭代过程如公式（8）～公式（11）所示。

vid（t+1）=wvid（t）+c1r1（Pbestid（t）-xid（t））+c2r2（xNSGA-IIrd（t）-xid（t）） （8）

式中：xNSGA-IIrd（t）为NSGA-II种群中随机选择的粒子在维度d中的位置。

c1=c1min+（c1max-c1min）×t/maxt " （9）

c2=c2max+（c2max-c2min）×t/maxt （10）

式中：c1max、c1min、c2max和c2min分别为学习因子c1和c2的最大值和最小值。

xi（t+1）=xi（t）+vi（t+1） （11）

3.4 基于世代距离GD的自适应变异策略

对经过NSGA-II遗传操作以及MOPSO引导寻优后得到的粒子进行非支配排序，其中非支配排序为1的个体包括当前最优的进化信息，无论是NSGA-II还是MOPSO都存在容易陷入局部最优的问题，若干代后可能出现大量相似的个体，算法无法找到最优Pareto前沿。因此，本文对这部分解进行变异操作，提高种群跳出局部最优的能力。同时，本文采用世代距离衡量非支配排序为1的群体变化的动态过程，并根据该变化对变异规模进行动态调整。

在变异方面，本文采用多项式变异[5]，随机选择个体中的一维进行变异，如公式（12）所示。

xd new=xd+（xUd-xLd）δ×k " " " " " " " " " " " " " " " " " " " " " " " "（12）

式中：xd new为变异后的粒子；xd为选择的粒子；xUd和xLd为粒子第d维的上界和下界；δ为扰动项；k为扰动比例系数。

δ的计算过程如公式（13）所示。

（13）

式中：r为（0，1）的随机数；μ为变异分布指数。

世代距离GD可以表示待评价解集中的解与真实Pareto解之间的欧氏距离，但是在本应用中，需要衡量非支配排序为1的群体的动态变化过程，因此取当前代的种群与前一代之间的世代距离，记作GD*，相邻2代解集的GD*差值记作ΔGD*，如公式（14）所示。

ΔGD*（t）=GD*（t）-GD*（t-1），t≥3 （14）

式中：ΔGD*（t）为第t代种群与第t-1代种群的世代距离之差，可表征算法的收敛速度；当ΔGD*（t）gt;0时，算法收敛速度快，应缩小变异规模，提升算法效率；当ΔGD*（t）lt;0时，须增大变异规模，提升算法收敛性与多样性。GD*（t）为第t代的种群的世代距离；GD*（t-1）为第t-1代的种群的世代距离。异规模的调整过程如公式（15）所示。

（15）

式中：Q（t+1）为第t+1代的变异规模；integer（）为取整函数；Q（t）为第t代的变异规模，当t=1，2，3时，Q（t）等于当前非支配排序为1的粒子数量。

4 算法性能分析

为了验证算法的有效性，选择ZDT函数集问题中的函数进行性能测试，双种群协同进化的NSGA-II与MOPSO混合算法（NSGAMOPSO）、NSGA-II和MOPSO 3种算法进行对比。运行程序，对比结果如图1所示，越靠近真实的Pareto前沿线，效果越好。

由图1可知，在ZDT3-6中的测试曲线，NSGAMOPSO算法的最优值基本都靠近ZDT3-6的Pareto真实前沿曲线，在 ZDT4 和 ZDT6 中，MOPSO 算法和 NSGA_II 算法的大部分最优值都偏离了Pareto真实前沿曲线。3种算法的测试性能对比见表1～表5。

由表1～表5可知3个算法在ZDT1-6中的测试结果，使用NSGAMOPSO算法，4项评价指标都比MOPSO算法和NSGA-II算法更好，本文算法得到的最优解集更接近Pareto真实前沿，收敛性、均匀性和分布性更好，综合性能更强。

5 结论

本文提出一种双种群协同进化的混合NSGA-II与MOPSO多目标算法。双种群协同进化策略在NSGA-II的非支配排序基础上进行。首先，利用2种经典算法的优点提出一种基于种群拥挤度和进化迭代数的动态交叉与变异概率方法进行交叉与变异操作，合理控制了种群的交叉与变异范围。其次，在MOPSO算法的基础上使用非线性学习因子，提升算法搜索全局最优解的能力。最后，在非支配排序过程中采用世代距离衡量GD方法和多项式变异方法，使算法更容易跳出局部最优，更靠近Pareto真实前沿。针对多个标准测试函数优化问题进行对比试验，试验结果表明，与 NSGA-II 和 MOPSO算法相比，本文算法效果更好，给多目标优化问题提供新的参考方法。

参考文献

[1]王伟，曲辅凡，杨钫，等.基于NSGA-II算法的分布式驱动电动汽车制动转矩分配控制策略研究[J].汽车技术，2024（5）：22-30.

[2]邢毓华，任甜甜.改进MOPSO在微电网优化调度中的应用研究[J].太阳能学报，2024，45（6）：191-200.

[3]COELLO CA C，PULIDO G T，LECHUGA M S.Handling

multiple objectives with particle swarm optimization[J].IEEE Transactions

on evolutionary computation，2004，8（3）：256-279.

[4]DEB K，PRATAP A，AGARWAL S，et al.A fast and elitist multi-objective genetic algorithm：NSGA-II[J].IEEE Transactions on evolutionary computation，2002，6（2）：182-197.

[5]李汶娟，李广，聂志刚.多项式变异和自适应权重优化的阿奎拉鹰算法[J].计算机技术与发展，2024，34（2）：163-170.

通信作者：冯芝丽（1986-），女，湖南永州人，硕士研究生，湖南环境生物职业技术学院副教授，研究方向为人工智能。

电子邮箱：570561252@qq.com。

基金项目：湖南省教育科学研究工作者协会2024年度高校课题“基于深度学习模型的高职智慧课堂的构建策略与应用研究”（项目编号：XJKX24B241）；2024—2025年度湖南省职业教育与成人教育学会科研规划课题“新质生产力背景下职业教育数字化转型的价值定义与实践路径研究”（项目编号：XH2024198）。