基于最优网格距离的改进多目标粒子群算法研究

冷 蕊，袁 恋，刘衍民

（1.五邑大学数学与计算科学学院，广东江门529020；2.贵州民族大学数据科学与信息工程学院贵州贵阳550025；3.遵义师范学院数学学院，贵州遵义563006）

粒子群算法（Particle Swarm Optimization,PSO）[1]是一种源于对鸟类觅食行为的模拟的随机搜索算法，它是在1995年由Eberhart和Kennedy等人提出，算法具有操作简单、求解速度快等优点，在求解单目标优化问题中得到了广泛的应用。但现实遇到的优化问题中，很多优化问题都是多目标优化，因此，如何设计将单目标 PSO用于优化问题成为了研究热点，多目标粒子群算法（MOPSO）[2]为处理和解决这类问题提供了思路和方法，并广泛地应用到了相关优化问题中。在将单目标扩展到多目标的过程中遇到如下挑战：在单目标优化过程中，因目标单一的特点能够简单的通过比较来选取学习样本 pbest和gbest，而在多目标粒子群算法迭代过程中，存在多个相互制约的目标，粒子不能简单的通过单个目标的比较来确定学习样本。因此，如何在外部存档中判断个体的优劣是多目标粒子群算法的关键步骤；另外，由于多目标优化问题往往存在一组非劣解，如何从这些非劣解中选取信息多样化的解来供决策者选择是一个巨大的挑战。针对这些关键问题，学者们纷纷提出了相应的策略使得单目标粒子群算法能有效处理多目标优化问题。

Coello等人[3]第一次将粒子群算法扩展到多目标,利用外部存档思想和pareto占优的基本原理，提出了MOPSO算法。但该算法遇到非凸、多峰以及解空间中出现许多弱支配关系个体时，则容易陷入局部最优和多样性差的缺点。为防止MOPSO在迭代过程中容易导致早熟收敛，陷入局部最优解，一些学者也提出了一些解决方法，如Deb等人提出了最近邻密度估计法[4]和核心密度估计法[5]，该方法主要从粒子间的距离来研究学习样本的选取；Mostaghim和Teich提出了Sigma法[6]，它主要利用当前外部档案中目标函数的Sigma值来确定学习样本的选取；也有学者为保持解的多样性方面提出了小生境法、聚集密度法[7]以及信息熵[8]等；这些改进策略对于粒子跳出局部最优都有一定的效果，但在求解精度和实现上仍有很大的改进空间。

根据单目标粒子群算法处理多目标优化问题的关键，在MOPSO的基础上，本文提出了一种新的改进算法HMOPSO，算法利用最优网格技术对每个个进行改进，实验结果表明，体的全局学习样本相比多目标粒子群算法MOPSO具有较好的性能，是对标准多目标粒子群算法的一种有效改进。

1 基本概念

1.1 粒子群算法

粒子群算法因其结构简单、操作方便等特点，在许多工程应用等领域得到了广泛的应用。它是一种通过个体之间自我认知和相互协助来寻找最优解的随机优化的智能技术。假设每个粒子的搜索空间是维，粒子 在维空间由时刻 到1时刻的位置与速度更新公式如下：

1.2 基本定义

定义1.1假设一个有n个决策变量，m个目标的最小化多目标优化问题表示如下：

xu）当且仅当

定义1.3 pareto最优解集：对于多目标优化问题，最优解集可定义为

1.3 粒子群算法流程

在算法迭代过程中，每个粒子存在一个潜在的解，粒子在解空间中根据个体最优粒子与全局最优粒子飞行方向更新迭代逐渐靠近最优解。

第一步：初始化种群中所有粒子的速度和位置，并对每个粒子位置进行变异操作。设置加速常数c1和c2，并计算其适应值。

第二步：对于每个粒子，将当前迭代的适应值与该粒子所经历的最好适应值进行排序比较，如果优于后者，则被替代，反之不然；若相等，则随机选取一个。

第三步：建立外部存档，利用网格技术对粒子进行外部存档控制并予以更新。

第四步：对每个粒子选择全局学习样本。利用轮盘赌方法对每个粒子所在网格随机选择其学习样本进行飞行。

第五步：根据公式（1）和（2）更新每个粒子的位置和速度。

第六步：判断是否满足终止条件，若满足，输出结果，算法结束；若不满足，返回第二步。

2 基于最优网格距离的改进算法

2.1 学习样本的选取

多目标优化问题不同于单目标优化问题，每个目标之间存在相互制约的情况，在迭代的过程中会产生一组非劣解，而如何在这些非劣解中选取学习样本成为该算法的关键。本文提出了一种新的选取社会学习样本的策略，其定义如下：

定义2.1网格的边界坐标.设在决策空间中，第m个目标对应函数的最小值、最大值分别为则在第m个目标上网格上下边界：这里是网格划分数，根据种群规模来取决定值。

定义2.2网格坐标（Gm）.设fm(X)为粒子X在第m维目标上的函数值，则对应的网格坐标为：

定义2.3最优网格距离（HGD）．定义个体到所在网格的最小边界点的欧氏距离作为最优网格距离来判断同一网格内个体的优劣：

其中，fm(xi)为个体xi的实际函数值，Gm(xi)为个体xi的网格坐标．个体的最优网格距离越小，说明离实际最优边界越近，在排序值相同的情况下应当被优先选取．在图2中，个体p2，p3在同一网格内，其排序值相同（即网格坐标相同），但是从图1中可以明显看出，p2的最优网格距离小于p3，说明p2个体离真实最优边界近，在这种情况下p3应该被排除。

图1 最优网格距离实例

问题：一个多目标最小化问题，在某次迭代中，假设有n个粒子所占p个网格，某个网格中有k个粒子，m个目标，建立了一个c×c个网格。在排序值相同的情况下，同一网格内的粒子最优网格距离越小，该粒子越优。

又因为HGD1(x1)＜HGD（2x2），

所以f1(x1)＜ f1(x2)∧ f2(x1)≤f2(x2)或 f1(x1)≤f1(x2)∧f2(x1)＜ f2(x2)

由定义1.2可知x1x2；同理，粒子i可推广到n个，故定义2.3成立。

若存在b（b(1,k)）个最优粒子的最优网格距离相等，则随机选择一个粒子作为全局学习样本进行飞行。

2.2 算法流程

由于多目标优化问题各目标之间相互制约，所以在选取全局学习样本时具有一定的盲目性，采用随机法选取学习样本来引导其它粒子飞行会导致算法收敛性较差。因此，本文提出了一种新的学习样本选取策略，利用最优网格技术代替随机法，图2给出HMOPSO算法流程图。

图2 HMOPSO算法主要流程图

3 实验结果与讨论

3.1 测试函数的选取

为测试算法的性能，选取国际公认的五个基准函数来测试算法的运行效果，检测函数表达式如下：

1)ZDT1函数：

2)ZDT2函数：

3)ZDT3函数：

4)ZDT4函数：

5)ZDT6函数：

3.2 实验结果与讨论：

实验参数设置如下：算法种群规模为200，检测函数为30维，最大迭代次数为200，网格划分数为50，外部存档规模200，其它参数设置与算法提出时一致。选取国际上公认的五个测试函数 ZDT1、ZDT2、ZDT3、ZDT4、ZDT6函数进行测试，并与之相应的MOPSO算法进行对比仿真。

图3分别给出了5个MOPSO和HMOPSO检测函数的对比图，可以看出不管是对于求解凸函数的pareto前沿能力而言，还是遇到pareto前沿面是凹型、不连续的以及包含多个局部极值，相比MOPSO算法，HMOPSO算法表现出了更好的收敛性与分布性。

图3 检测函数的收敛特征图

表1 MOPSO和HMOPSO在检测函数上的GD指标

表2 MOPSO和HMOPSO在检测函数上的Spacing指标

表1和表2分别给出了两种算法在检测函数上运行5次的收敛性（GD）指标和多样性（Spacing）指标，分别从最大值、最小值以及平均值分析。从表1中可以看出，HMOPSO算法在收敛性能上基本上比MOPSO算法的收敛性要好；表2中HMOPSO算法在多样性指标基本上也比MOPSO算法的多样性指

标要好，与图1中的结果一致。

图4 不同算法的GD指标的盒状统计图（0-MOPSO;1-HMOPSO）

图4和图5分别给出不同算法独立运行5次的GD评价指标和Spacing评价指标盒状统计图。从图2中可以看出，HMOPSO算法在ZDT1-ZDT6上都获得了最小值；在图3中，HMOPSO算法在ZDT1、ZDT4、ZDT6上也明显的比MOPSO获得了较好的非劣解，虽然在ZDT2、ZDT3函数上没有获得更好的非劣解，但相比MOPSO算法差别并不明显，这与表1和表2中的定性分析一致。

图5 不同算法的Spacing指标的盒状统计图（0-MOPSO;1-HMOPSO）

4 结论

为了更好的提高解的收敛性和多样性，本文提出了基于最优网格距离的改进多目标粒子群算法研究。该算法借鉴了pareto占优排序原理，融合了最优网格距离的网格技术，利用轮盘赌策略对网格中每个粒子选择局部最优粒子作为学习样本进行飞行，增加了种群的多样性，使优化效果更佳，进而提升了算法的寻优能力。仿真实验结果表明，通过对比实验与MOPSO算法在同一实验环境下，验证了HMOPSO算法在大多数测试函数中均表现出了更好的收敛性和分布性，使获得的最优解集更加靠近真实的pareto前沿。