基于多策略融合的混合多目标蝗虫优化算法

王 博，刘连生，韩绍程，祝世兴

（1.中国民航大学基础实验中心，天津 300300；2.中国民航大学航空工程学院，天津 300300）

0 引言

工程实践和科学研究中很多决策及设计问题同时涉及两个或以上的目标，这些问题称为多目标优化（Multi-Objective Optimization，MOO）［1］。由于MOO 问题中各目标函数之间一般存在内在冲突，很难得到使所有目标同时达到最佳状态的解决方案，求解过程中通常需要经过权衡得到一组相互折中的解集［2］。

近几十年来，国内外学者针对MOO 问题开展了大量研究工作，涌现了众多优化算法，主要可以分为两类：基于偏好信息的方法和Pareto 最优解法［3］。第一类优化方法根据每个目标函数的重要性设定权重系数并计算它们的加权和，从而将MOO 问题转化为单目标优化问题。此类方法较为简单，但权重系数的选择直接影响最终优化结果，实际应用中权重系数的设定带有一定主观性、随机性，很难得到客观准确的优化结果。第二类优化方法同时对多个子目标优化，通过搜索得到一组不存在优劣关系的非支配最优解（即Pareto 最优解）。该方法能够获得一组较高质量的最优解集，供决策者从中选择最合适的解，相较第一类方法应用更广泛［4］。

蝗虫优化算法（Grasshopper Optimization Algorithm，GOA）是Saremi 等［5］受蝗虫捕食过程中种群行为的启发，在2016 年提出的一种新型启发式智能优化算法。GOA 简单，计算复杂度较低，具有较高的收敛速度。近年来，为提高GOA的性能众多学者做了大量研究工作。Mafarja 等［6］利用动态种群进化（Evolutionary Population Dynamics，EPD）策略改进了GOA 的种群选择机制，有效避免了算法过早收敛，提高算法的准确性。Luo 等［7］提出将高斯变异引入GOA 以增强局部搜索能力，利用Levy 飞行策略和反向学习机制（Levy flight and Opposition-Based Learning，LOBL）提高了算法的全局搜索能力和搜索效率。Taher 等［8］改进了GOA 的变异机制和种群更新策略，避免了局部最优。Mirjalili等［9］于2017年首次将GOA应用于多目标问题，提出了多目标蝗虫优化算法（Multi-Objective Grasshopper Optimization Algorithm，MOGOA）。黄超等［10］利用曲线自适应策略调整控制参数，提高算法收敛速度，提出一种求解移动机器人路径规划问题的MOGOA。目前，多目标蝗虫优化算法由于采用了标准GOA 的基本框架，继承了蝗虫优化算法在复杂度和收敛速度上的优势，具有较好的应用前景；但由于GOA 的天然缺陷，限制了其优化性能。首先，由于种群采用优势个体引导的更新机制，易造成群体进化聚集，算法容易陷入局部最优；其次，调整算法搜索能力的重要参数c只随迭代次数被动变化，导致算法全局搜索和局部开发的不平衡，降低了收敛效率和解集质量。

针对上述问题，本文提出一种混合多目标蝗虫优化算法（Hybrid Multi-Objective Grasshopper Optimization Algorithm，HMOGOA）。HMOGOA 利用Halton 序列进行种群初始化，增强了初始种群的多样性以及分布均匀性；由差分变异算子引导种群更新，提高了算法全局搜索能力避免陷入局部最优，改善了解集分布特性；加入自适应权重因子，根据种群优化情况动态调整算法的全局搜索和局部开发能力，提高了算法优化效率和解集质量。采用ZDT、CEC09 系列函数对算法进行仿真实验，通过与多目标蝗虫优化、多目标粒子群（Multi-Objective Particle Swarm Optimization，MOPSO）、基于分解的多目标进化（Multi-Objective Evolutionary Algorithm based on Decomposition，MOEA/D）、非支配排序遗传（Non-dominated Sorting Genetic Algorithm Ⅱ，NSGA Ⅱ）等算法对比，表明HMOGOA具有更好的优化性能和稳定性。

1 标准多目标蝗虫优化算法

多目标蝗虫优化算法是一种求解多目标优化问题的GOA。它模拟了蝗虫的捕食行为，算法中每个搜索个体（即蝗虫个体）的位置代表了问题的一种解决方案。算法通过判断不同解之间的支配关系寻找Pareto解，并借助外部档案集存储优化过程中的临时解。其优化过程分为探索和开发两部分。在探索阶段，搜索个体在整个解空间内进行快速随机移动寻找所有可能的解；而在开发阶段，搜索个体根据已有信息对部分区域进行精细搜索寻找最优解［11］。这恰好与蝗虫在成虫和幼虫时期的运动特点相吻合。蝗虫种群运动的数学模型［12］为：

其中：Xi是第i只蝗虫在种群中的位置，Si、Gi、Ai分别代表第i只蝗虫受到的种群间社交作用、重力以及风力的影响。种群间的社交作用是影响蝗虫运动的最主要因素，可通过下述公式描述：

其中：dij为第i只与第j只蝗虫之间的距离,为第i只与第j只蝗虫之间的单位向量，函数s（r）为蝗虫间的社会作用力。由于重力对蝗虫种群的影响较小可以忽略不计，同时假设风向始终指向最佳个体所处的位置，蝗虫位置的更新模型可表示为：

其中：ubd、lbd分别表示蝗虫在d维度上的位置上界和下界表示当前种群中优势引导个体的位置；参数c为线性缩减系数，它随着迭代次数增加减小算法全局搜索能力的同时提高局部寻优能力，计算公式如下所示：

标准MOGOA流程如图1所示。

图1 标准MOGOA流程Fig.1 Flow chart of standard MOGOA

2 混合多目标蝗虫优化算法

为提高MOGOA 的性能，需解决两方面问题：1）种群更新过程中，缺少个体间信息的交换，进化容易集中在优势个体的邻域范围内进行，导致算法全局搜索能力下降，算法过早收敛陷入局部最优。2）衰减系数c是GOA 求解MOO 问题过程中的一个重要参数，它与迭代次数呈线性反比关系，主要限制算法的搜索区域，平衡全局搜索能力和局部寻优能力。优化前期，c数值较大，促进个体在整个解空间内搜索所有可能的优势解；优化后期，其数值减小，有利于种群在当前解的局部区域寻优，使最优解能够收敛到理想Pareto 解集。通常MOO 的优化过程并不随迭代次数线性变化，应当根据种群进化过程合理控制算法的搜索能力。

因此，本文从提高初始种群质量降低种群进化聚集的概率，加强进化过程中个体信息交换、提高种群多样性，根据种群进化状态平衡算法全局搜索和局部开发能力3个方面，提高MOGOA的优化性能，提出一种混合多目标蝗虫优化算法。

2.1 基于Halton序列初始化

算法初始阶段蝗虫种群的位置随机产生，极易出现种群分布不均的情况，造成搜索个体的初始位置集中于局部极值点附近，导致算法陷入局部最优。Halton 序列是一种低差异化序列，能够生成在搜索空间内均匀分布的点集［13］。由随机法和Halton 序列生成的一组二维个体分布情况如图2 所示。图2（a）、（b）分别为使用两种方法生成个体的散点分布图，图2（c）、（d）为个体数量的分布直方图。通过对比可见，相较于随机方法Halton序列产生的个体在二维空间上分布更均匀，没有聚集情况，同时处于不同数值区间的个体数量更平均，表明Halton序列能够生成分布均匀性更好的个体。为此，本文采用Halton 序列初始化种群，提高初始种群质量有效避免局部最优。

图2 随机法与Halton序列生成个体的分布情况Fig.2 Distribution of individuals generated by random method and Halton sequence

2.2 基于差分变异算子的种群更新策略

MOO 需要在优化过程中不断寻找所有非支配解，组成非支配解集。由于多目标问题的解空间由多个分段连续区域组成，为使解集能够逼近真实Pareto 最优前沿且分布更均匀，优化过程中搜索个体在决策空间中的搜索方向应指向真实Pareto 前沿，且可以在平行于真实Pareto 前沿的流行区域移动［15-16］。图3 反映了MOGOA 优化过程中种群进化趋势。图中以ZDT1为目标函数，由10个初始父代解利用MOGOA 产生1 000 个新的子代解。可以明显看出搜索个体由优势个体引导沿不同轨迹向着目标位置移动，最终聚集到真实Pareto 前沿的部分区域，表明MOGOA 的种群更新策略易使算法陷入局部最优。针对该问题，在单目标蝗虫优化算法中，文献［6］中采取了动态种群进化策略，文献［7］中利用了Levy 飞行和反向学习策略改进个体的更新机制［2］。分别将EPD 和LOBL策略应用于多目标蝗虫优化算法，以ZDT1 为测试函数，由图3 中的10 个父代解出发，产生1 000 个子代解，得到的种群进化情况如图4、5 所示。图4 中EPD 策略一定程度扩大了搜索个体在进化过程中的寻优范围，但依然无法避免解聚集；而图5 中LOBL 策略虽然增强了算法的全局搜索能力，但种群搜索范围过大影响了算法的收敛性能。由此说明，EPD 和LOBL策略对MOGOA性能的改善有限。

图3 MOGOA进化示意图Fig.3 Schematic diagram of MOGOA evolution

图4 基于EPD的MOGOA进化示意图Fig.4 Schematic diagram of MOGOA evolution based on EPD

图5 基于LOBL的MOGOA进化示意图Fig.5 Schematic diagram of MOGOA evolution based on LOBL

由于差分算子有利于种群间信息交换，促进全局探索，改善种群分布和收敛精度，因此本文提出一种基于差分变异算子的种群更新策略。差分变异算子及个体更新公式如下：

式（9）中，α0、α1为缩放系数（α0，α1∈(0，2]），r为（0，1）内的随机数，Xsi(t)表示以较大概率在解集稀疏区域选取的个体，Xc1i(t)、Xc2i(t)表示以较大概率在解集密集区域选取的个体，Xsi(t)表示由当前解集随机选取的个体，上述4个种群个体互不相同。Xsi(t)、Xc1i(t)、Xc2i(t)组成的差分算子实现了种群个体间优势信息的交换，能够提高算法的全局寻优能力，有助于算法跳出局部最优，改善收敛精度。而随机个体Xri(t)可以增加变异的随机性，避免过早收敛。为验证差分变异算子对MOGOA的改善作用，同样选取图3中的父代解作为初始解，以ZDT1为目标函数，利用基于差分变异算子的MOGOA生成1000个子代解，进化结果如图6所示。由图中可见，差分变异算子能够引导种群在父代解构成的带状区域变异，可以改善解空间的整体分布性能。

图6 基于差分变异算子的MOGOA进化示意图Fig.6 Schematic diagram of MOGOA evolution based on differential evolution operators

2.3 自适应权重因子

多目标问题的优化是一个复杂的过程具有随机性，MOGOA 求解过程中c是一个开环参数，单纯通过它无法有效平衡全局搜索和局部寻优能力［18］。根据种群进化状态调节参数c的衰减速度，实现闭环控制，有助于提高种群的搜索效率和收敛精度。通常种群进化过程中个体的分布特性是影响算法性能的一个重要因素［19］。本文以群体分布均匀性和分散广度作为进化过程反馈信息，提出种群进化状态动态评价指标（Evolution State Metric，ESM）。ESM定义如下：

其中：Ns为当前解的数量，M为目标函数的数量，表示当前Pareto 解集中相邻解的欧氏距离表示的平均值表示理想Pareto 解集中使第m个目标函数取得最大值的解（即理想解空间第m维上的极值解）,表示当前解集与理想解空间第m维上极值解的最短距离。式（13）中第一项表示当前解集相邻解之间距离的标准差，体现了解集分布的均匀度，数值越小解集分布越均匀；第二项表示当前解集与理想解空间各维度上极值点的最短距离之和，体现了解集分布的广度，其值越小说明解集分布范围越广。图7所示为MOGOA针对目标函数ZDT4 运行三次得到的ESM 数值随迭代次数变化曲线。可以看出ESM 是波动变化的，算法每次运行过程中其变化幅度与趋势不同，说明种群进化状态具有非线性和不确定性，根据进化过程调节算法搜索能力有助于提高算法性能。因此，本文建立基于ESM 的自适应权重因子wa，在种群更新公式中加入自适应权重因子，通过权重因子调整参数c的衰减速度平衡算法的全局搜索和局部寻优能力。

自适权重因子wa和种群个体更新公式如下：

其中，wa数值根据种群进化状态变化。种群进化状态不佳时ESM 数值较大，说明解分布较集中、均匀性不好，此时wa数值增加大可减缓c的衰减速度，促进搜索个体在更大区域寻找新解；反之ESM 数值较小，说明搜索个体在目标空间内分布均匀且分布范围广，wa数值减小，可以促进算法局部寻优，提高收敛精度和收敛速度。实现了根据算法寻优过程动态调整全局搜索和局部开发能力，提高了算法的优化效率，有效改善了Pareto最优解集的质量。

图7 ESM变化曲线Fig.7 Variation curve of ESM

2.4 混合多目标蝗虫优化算法的流程

混合多目标蝗虫优化算法的伪代码流程如下：

3 实验及分析

3.1 测试问题及实验设置

本文为验证HMOGOA的性能，以MOGOA、MOPSO、MOEA/D及NSGA Ⅱ作为对比算法，选取ZDT、CEC2009系列测试函数集中的两目标函数（ZDT1、ZDT2、ZDT3、ZDT4）和三目标函数（UF8、UF9、UF10），使用软件Matlab2016a进行仿真实验测试。

实验过程中，所有算法的相关参数均设置一致以保证公平性：种群规模N=100，外部档案集规模NA=100，迭代次数Tmax=100。HMOGOA、MOGOA 参数c的取值范围均设置为：cmax=1，cmin=0.000 5。其他算法参数设置如下：MOPSO算法惯性权重因子w=0.5，个体学习因子c1=2，社会学习因子c2=2，变异率pm=0.1；MOEA/D算法邻域大小T=15，交叉概率pc=0.5；NSGA Ⅱ算法交叉概率pc=0.7，变异概率pm=0.02。为避免随机误差对测试结果的影响，针对每个测试函数所有算法均运行30次。

3.2 性能指标

为分析比较不同优化算法的性能，选取两种评价指标来量化分析算法的性能。具体性能指标［20］如下：

1）反世代距离（Inverted Generational Distance，IGD）。IGD 反映了算法求得的Pareto 解集P与真实Pareto 前沿之间的距离，它是评价算法收敛性的指标。其值越小说明所求解越逼近真实Pareto 前沿，表明算法的收敛性越好，解的精度越高。IGD定义如下：

其中，NPt为真实Pareto前沿中解的数量为真实Pareto前沿中的第i个解与解集P间的最短欧氏距离。

2）分布度量指标（Δ）。Δ体现了所求Pareto 最优前沿相对真实前沿的分布广度及均匀度，它是评价Pareto 解分布特性的指标。Δ数值越小说明解的多样性越高、分布范围越广、分布均匀度越好，非支配解能够更好地覆盖整个真实Pareto解集。Δ的定义如下：

其中：Np为所求解的个数，di为Pareto前沿中相邻点间的距离，为di的平均值，df、dl为Pareto 最优前沿与真实前沿边界点之间的最短距离。

3.3 实验结果及分析

五种算法针对多目标问题测试所得各项性能指标的均值（Mean）和方差（Var）如表1、2所示，同一测试问题中的最优数值加粗显示。

表1 IGD实验结果Tab.1 Results of IGD

表2 Δ实验结果Tab.2 Results of Δ

由表1 可见，相较于MOPSO、MOEA/D、NSGA Ⅱ算法，HMOGOA 的IGD 数值在大部分测试函数上明显优于此三种算法，只是在函数UF9 上稍差于MOPSO，但数值相近且明显优于其他两种算法，表明HMOGOA 的收敛性优于此三种算法。而对于MOGOA，HMOGOA 的收敛性能和收敛稳定性在全部测试问题上都体现出了明显优势。由此说明HMOGOA采取的基于差分变异算子的更新策略有助于引导种群向理想解空间中目标个体位置移动。

通过表2 对比分析五种算法的分布性能指标可以看出，由于HMOGOA 在进化初期提高了初始种群分布性，避免了算法前期陷入局部最优；差分变异算子能够提高全局搜索能力，改善解集分布特性；同时采用自适应权重因子平衡全局和局部寻优能力，提高了最优解集的质量。因此，HMOGOA 在所有测试问题上的分布性能均明显优于其他算法。

图8 所 示 为HMOGOA、MOGOA、MOPSO、MOEA/D 的Pareto 最优前沿分布图。通过图8 可以看出，对于函数ZDT3，HMOGOA 求得的解相较其他三种算法能均匀分布在函数的4个波谷上，收敛精度更好。对于函数ZDT1、ZDT2，HMOGOA与其他算法相比能更均匀分布在整个真实Pareto 前沿面上。而对于三目标问题，HMOGOA 求得解的数量更多，能够较好逼近真实Pareto前沿，且分布更均匀。

图8 各算法对部分函数的Pareto前沿对比Fig.8 Comparison of Pareto optimal front for some benchmark functions obtained by various algorithms

为进一步比较HMOGOA 与其他算法性能之间的显著优势，本文利用Wilcoxon 秩和检验按照显著性水平α=0.05，将HMOGOA 分别与其他四种算法进行对比分析。分析结果如表3 所示，“+”“-”“≈”分别表示HMOGOA 的性能指标明显优于、劣于或近似于对比算法。由表3 可以看出，HMOGOA 的IGD、Δ指标在大部分测试函数上，相较于MOGOA、MOPSO、MOEA/D、NSGA Ⅱ具有明显优势，只是在个别测试函数上近似于MOPSO、MOEA/D。通过上述实验分析可知，本文提出的HMOGOA 性能明显优于MOGOA，算法具有较高的收敛精度和较好的分布性能，且稳定性较高。

表3 Wilcoxon秩和检验结果Tab.3 Results of Wilcoxon rank-sum test

4 结语

本文为提高MOGOA 的优化性能，提出一种混合多目标蝗虫优化算法。该算法利用Halton 序列初始化种群，使初始种群具有较好的多样性和分布特性，减小了算法过早收敛的概率；设计基于差分变异算子的种群更新机制，促进种群向优势个体移动的同时进行更大范围寻优，实现种群间优势个体的信息交换，提高了算法的全局寻优能力，有效避免算法陷入局部最优，提升了解集的分布特性，改善了收敛精度；引入自适应权重因子，根据种群进化状态反馈信息动态调整算法的全局搜索和局部开发能力，实现算法寻优能力的闭环精细控制，提高了算法的优化效率和最优解集质量。通过与四种多目标优化算法的对比实验表明，HMOGOA 的性能相较于MOGOA有明显提升，算法具有较好的收敛精度、分布广度、分布均匀性和稳定性。下一步研究的主要内容是算法对于求解高维多目标优化问题的性能。