一种用于MOPSO的全局极值确定和种群更新的新策略

刘少伟+朱永利

摘要：多目标粒子群优化过程中，收敛速度和粒子的多样性之间往往不能兼顾，且常易于陷入局部最优。为了更好地解决此问题，该文结合Pareto支配的思想，提出了一种改进的多目标粒子群优化算法。此方法使用带有规模限制的外部档案，并采用在线归档技术，改进了粒子群和外部档案的更新方式。当外部档案达到最大规模时，剔除密集距离最小的非劣解；在全局极值的确定中，除考虑概率外，选取稀疏距离最大的非劣解作为当前代的全局极值；另外采取多次迭代的方法更新种群。对几个典型函数的仿真结果表明，算法在寻优效率和Pareto前沿的性能指标方面达到了满意的效果。该算法为其他更加复杂的多目标优化问题提供了新思路。

关键词：多目标优化；外部档案；密集距离；稀疏距离

中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2017）27-0217-04

Abstract：In the MOPSO， it may be difficult to take into consideration both the convergence rate and diversity. Usually， locally optimal solution can be gained. In order to settle these questions much better， a modified MOPSO which combined with the conception of Pareto domination is proposed in this paper. External archive with size limitation is adopted，and online elite archive， which is benefit to the modification of updating method is referred to. While the size of external archive exceeds the edge， the Pareto optimal solution with minimal crowding distance will be deleted. Besides the probability， one of the solutions whose sparse distance value are biggest will be chosen as the global best value. In addition， several times of iteration are applied to update the swarm. The simulation results of typical functions show that the new approach has good effect on search efficiency and performance metrics of Pareto fronts. It will contribute to more complicate multi-objective problems.

Key words：multi-objective optimization； external archive； crowding distance； sparse distance

工程實践中的很多实际问题在进行数学建模以后，都可以抽象为一个多目标的优化问题。多目标优化问题（Multi-objective Optimization Problem， MOP）通常不存在某个绝对的最优解，使得各目标均同时达到令人满意的结果[1]。随着优化问题的复杂程度越来越高，特别是带有约束条件的MOP问题，现有的算法往往难以兼顾优化过程中算法的收敛性和解集的多样性。

传统的多目标算法往往将多目标优化问题转换成单目标问题进行求解，其最大的缺点在于一次只能求出一个解。目前，基于Pareto支配机制的粒子群优化算法常用于求解MOP，这些算法主要的区别在于全局极值的选取方式和最优解集的保存形式上。文献[2]提出一种基于免疫网络的改进多目标粒子群优化（Multi-objective Particle Swarm Optimization， MOPSO）算法，改进的多目标粒子群算法和改进的聚类免疫网络算法保证了算法的有效性。文献[3]利用外部精英存储策略，利用余弦距离排挤机制来选取最分散的粒子，从而增强算法的全局寻优能力。文献[4]依据Pareto支配关系对个体极值进行选择，并计算外部存储中粒子与其他粒子的海明距离之和作为适应值，采用轮盘赌方式选取粒子的全局最优位置。文献[5]提出一种ε占优的自适应多目标粒子群算法，粒子动态组建邻居，粒子速度由所有邻居调整。文献[6]提出用自适应网格法来维护外部集，以网格中的粒子数作为网格密度定义网格适应度值，从而求取全局极值。

本文提出一种改进的多目标粒子群优化算法，使用带有规模限制的外部档案和在线归档技术，并改进了全局极值的选取策略，同时加入粒子越界处理保证种群的可行性。对几个典型函数的仿真结果表明，该算法能有效地提高Pareto最优前沿的收敛性和均匀分布。

1 多目标优化问题

MOP是指多个目标同时需要优化的问题，这些目标包含两个或者两个以上，同时多个目标之间相互制约。这些目标之间存在约束条件。MOP解集不唯一，可能存在多个解。

上式中，x为向量，维数为D，m为待优化的目标函数的数目，[fi（x）]是第i个目标函数，[gj（x）]和[hk（x）]分别是第j个不等式约束和第k个等式约束条件。A和B分别代表其约束的总数。[xmind]和[xmaxd]为第d维向量搜索的上下限。endprint

公式（1）是m个目标对应的目标函数，公式（2）和（3）为其约束条件。本文假设每个目标都要求其最小值。理想情况下，可求得使每个目标函数均能取到最小值的x值。实际情况下，求取这样的x值，使某个或某些目标更优但同时牺牲其他一些目标值。这些x值为Pareto最优解。所有Pareto最优解组成的集合为Pareto前沿。

2 粒子群优化算法

在粒子群优化算法中，每个粒子附带一个速度使粒子可以在可行解区域内飞行，粒子根据自己和其他粒子的经验来调整飞行方向。在算法的迭代过程中，粒子始终追踪个体极值（pbest）和全局极值（gbest）来调整速度和位置，以此来实现群体的进化。

式中：i为粒子编号，j为粒子的某个维度；t为迭代次数；[pbesti，j（t）]为第i个粒子第j维在第t次迭代中的个体极值；[gbesti，j][gdbest]为第t次迭代中所有粒子第j维的最好位置；[vi，j（t）]、[xi，j（t）]分別为第i个粒子第j维在第t次迭代中的速度和位置；w、c1和c2为速度更新时的权重系数；[fr1]和[fr2]产生0到1之间的随机数。

3 基于密度距离的多目标粒子群算法

在确定多目标问题的Pareto最优解的过程中，主要的评价标准体现在两个方面，最终求得的非劣解集越接近真实的Pareto前沿、沿着Pareto前沿分布地越均匀，则效果越优。

3.1 非劣解集的存储与更新

为了求出初始非劣解集BP，首先要构造出一个数据结构形成两个N行（种群规模）D列（问题维度）的二维矩阵，其中一个矩阵表示各粒子的位置，另一个表示各粒子趋向于各个维度的速度，并对其进行随机初始化。为了防止速度和位置值过大或过小而导致解集分布不均匀，设定它们的上下限。将第一个粒子的位置直接赋给BP，然后开始初始化，通过粒子间的相互支配关系确定非劣解集的个数即根据各粒子之间的相互支配关系的比较，剔除被支配的粒子的位置，得出最优或互不支配的解集即为非劣解集BP。

算法1：空间分布距离

//x，y分别为两个D维的向量

gx=变量x在特定测试函数下的适应度值

gy=变量y在特定测试函数下的适应度值

gxy=（gx-gy）.^2；

空间划分距离=sqrt（gxy个分量求和）

为了保持解集的均匀性，防止其陷入局部最优，我们引入空间分布距离SD。空间分布距离即表示向量间的距离关系的矩阵，它是随非劣解的增加而逐渐增加的，例如：当非劣解只有两个时，它的空间分布距离矩阵为两行两列，这时由于对角线上元素表示各粒子内部自身即空间分布距离为零，并且其关于对角线对称的各元素相等。当非劣解每增加一个时，空间分布距离矩阵就会增加一行一列，以保持其始终和非劣解相联系。

算法2：密集距离求取

r=空间分布距离SD的行数

c=空间分布距离SD的列数

Initialize d（密集距离）=一行r列的零向量

d（i）=SD中第i行的最小值

综上，对求得的空间分布距离进行密集距离的计算即依次求出非劣解中空间分布距离最小解元素，将其组成一行多列的向量。

定义1：最优种群极限T

定义T为非劣解集的种群极限，它限定了非劣解集的最大数量，限制了种群粒子的活动范围同时保持适应度值的均匀性并且节省了一定的存储空间。一旦非劣解的个数超过了最优种群极限，需要对其进行约束管理即剔除其中密度距离最小的元素，使其始终处于最优状态。

3.2 速度和位置的更新方式

在更新速度和位置时，在原有更新公式基础之上，可采取更好的方法使粒子下一次飞行中趋向更好的位置，以便于求解更优的个体极值和全局极值。假设此时粒子有n个趋向即可以有n个方向来更新速度，当粒子在每一个方向更新速度后，再通过位置公式更新位置，故此时粒子共有n个趋向位置，再通过支配关系比较，即把n个位置中被支配的位置剔除，其余为互不支配的较优的位置，再从中随机选择一个当作粒子将要达到的位置，通过速度位置关系求出速度。综上，此方法可以从多个趋向中选择最优的速度和位置，比单一的更新公式具有更好的收敛性和准确性，是一个值得推广的算法。

3.3 外部档案的更新方式

使用外部档案（External Archive，EA）来存储算法每一次迭代产生的一组非劣解。外部档案初始化为空，随着迭代的进行，每一代所产生的非劣解用来更新外部档案。外部存档的规模逐渐增加，其计算复杂度呈指数级别增长，传统的PSO粒子优化算法采用拥挤距离来限制外部档案的规模[8]。为了防止粒子群的退化，使用一种在线归档技术来更新外部档案[9]，即把外部档案中的精英粒子引入下一代的进化种群中，使得外部档案中的精英粒子和新一代种群中的粒子一起竞争，从而更新非劣解集。这样做的好处是若粒子群在迭代过程中出现了退化的粒子，则直接淘汰，保证了种群一直向目标方向进化，提高了寻优效率。

3.4 全局极值的选取方式

目前确定全局最优位置的常用方法为从外部档案中保存的已经找到的最优解中随机选取最优位置[10]。有的文献里介绍全局极值的确定不但使用外部档案选取，还应用轮盘赌方法根据各最优解的拥挤距离来确定[11]。但该方法随着迭代次数的增加，该外部集合中的最优解数量也会迅速增加，从而会影响程序的运行速度。本文为了更为准确的求得全局极值，引入了稀疏距离的概念。

定义2：稀疏距离

通常来说，根据密集距离移除超出非劣解集规模限制情况下的某些粒子是一种维持外部档案规模的有效方法。为了更广泛地考察某粒子周围其他粒子的分布情况，提出了稀疏距离的概念。稀疏距离更能反映出当前非劣解集中某粒子为核心的周围群体的密度大小。在特定概率下，判定了每个非劣解的稀疏距离后，从而选取当前稀疏距离较大的粒子作为全局最优解，在保证均匀分布的前提下保证了非劣解的多样性。endprint

算法3：稀疏矩阵算法

r=空间分布距离SD的行数；

c=空间分布距离SD的列数；

Initialize s（稀疏距离）=zeros（1，r）；

s（i）=SD中第i行的两个次小值求均值

3.5 粒子的越界处理

在粒子的不断运动和更新中，有一定的几率会飞出事先设定好的上下界，所以有必要在算法中进行越界处理。我们考虑到了三种处理方法，其中一种是使越界的粒子停留在边界处，速度方向与之前相反，大小不变；另一种是通过相关的越界公式对粒子的位移和速度进行随机初始化；第三种是返回粒子越界前的位置，然后对其速度进行随机初始化，然后重新更新粒子的位移。

3.6 算法流程

1） 随机初始化粒子种群，设置参数。

2） 求解各目标的函数值，按照适应度确定支配关系。如果新粒子支配原种群中的粒子，则剔除原粒子加入新粒子，如果互不支配，则加入新粒子。

3） 从非劣解集中选取全局极值。同时确定个体极值。并且更新外部档案。

4） 根据速度和位置更新公式，更新種群位置。若是超出边界，则按粒子的越界处理方式拉回边界。

5） 满足迭代次数算法结束，否则回到步骤2）。

4 仿真结果及分析

在这里我们选用文献[12]中的三个测试函数进行测试，在相同的配置环境下，通过多次测试，对结果进行分析。

在仿真计算过程中，公式（5）中的相关参数设置如下：惯性权重[ω]从1.0惯性下降到0.4，[fr1]和[fr2]为[0，1]的随机数，种群规模分别设置为50和100两种不同的情况，以便对比仿真结果。总迭代次数为200次，外部档案的大小为100。算法采用Matlab编程，重复运行30次。

仿真结果如图1至图6所示。

算法的局部时间复杂度分析如下。对于每个多目标优化的标准测试函数来说，假设迭代过程中设定种群规模为N，问题维度为D，非劣解集的容量为T，目标数为m。在确定一个新的粒子x是否应进入非劣解集时，需要判断此粒子与所有非劣解的支配关系，而支配关系的值取决于x与此解各目标函数值的关系，因此这个比较过程的时间复杂度为[Ο（Tm）]，则种群中所有粒子的判定过程时间复杂度为[Ο（NTm）]。

从仿真结果可以看出，对粒子群的迭代达到一定次数，Pareto解集趋向稳定，解集呈现均匀性。从算法的角度来看，大约经过50次左右迭代基本可以找到Pareto前沿。通过对同一个测试函数在不同的种群规模下迭代的结果进行比较可以看出，随着种群规模的不断增大，其曲线的平滑度更好，非劣解的密度更大，从而在具体问题上给决策者提供更多选择。

采用文献[13]提出的算法评价标准对本文算法测试的三个经典问题进行评价，包括两个方面：

1） 收敛度。从目标空间中真实Pareto前沿均一地寻找一个空间解的集合H=500。对于算法获得的每一个解，我们计算它与Pareto最优前沿上H个选定解的最小欧氏距离。这些距离的平均值作为对问题寻优结果的收敛度。

2） 多样性。若所得Pareto非劣解集均匀分布在决策空间中，则认为解保持了较好的多样性。定义如下：

两个性能指标的计算结果和与其他主流算法的对比情况如表2和表3所示。可以看出，在收敛度方面，本文算法在多次测试中取得了较满意的均值和方差。SCH测试函数的优化情况与NSGAⅡ和SPEA算法相当，而在ZDT1和ZDT2两个函数中，效果均明显好于NSGAⅡ，但略逊于SPEA。这与测试函数的特点及算法迭代的随机效果密切相关。解的多样性方面，对每个测试函数的均匀分布情况的计算均收到了较好的效果。且多次运行的结果所得多样性的方差值均较小，说明算法的稳定性较好。未来的研究将进一步改善算法，并分析用于其他问题的优化中。

5 结论

本文主要对基于粒子群算法实现多目标优化问题进行研究，提出了一种求解多目标优化问题的多目标粒子群算法。采用改进的外部存档方式保存非劣解集；利用密集距离保持解集的多样性，稀疏距离选取全局极值，引导粒子飞行，保证解集分布的均匀性。同时加入对粒子的越界处理，使得粒子在规定范围内飞行，保证收敛效果。通过对几个典型测试函数的仿真计算可以看出，该算法能较好地解决一般的多目标问题，得到满意的Pareto前沿，今后有望用于工程实践中的其他多目标优化问题。

参考文献：

[1] 陈深，肖俊阳，黄玉程，等. 基于改进量子粒子群算法的微网多目标优化调度[J]. 电力科学与技术学报，2015，30（2）：41-47.

[2] 冯琳，毛志忠，袁平.一种改进的多目标粒子群优化算法及其应用[J].控制与决策，2012，27（9）：1313-1319.

[3] 方欣欣，龚如宾，李大为. 基于余弦距离的多目标粒子群优化算法[J]. 电子科技，2016，29（03）：48-52+57.

[4] 陈萍，毛弋，童伟，邓海潮，陈艳平，胡躲华. 基于多目标粒子群算法的配电网多目标优化重构[J]. 电力系统及其自动化学报，2016，28（7）：68-72.

[5] 刘衍民，赵庆祯，牛奔，邵增珍.基于ε占优的自适应多目标粒子群算法[J].控制与决策，2011，26（1）：89-95.

[6] 刘华蓥，王静，许少华，孙毅.基于空间划分树的多目标粒子群优化算法[J].吉林大学学报：理学版，2011，49（4）：696-702.

[7] 徐鸣，沈希，马龙华，等.一种多目标粒子群改进算法的研究[J].控制与决策，2009，24（11）：1713-1718，1728.

[8] 刘衍民，牛奔，赵庆祯.多目标优化问题的粒子群算法仿真研究[J].计算机应用研究，2011，28（2）：458-460.

[9] 王丽，刘玉树，徐远清.基于在线归档技术的多目标粒子群算法[J].北京理工大学学报，2006，26（10）：458-460.

[10] Peng Chunhua， Sun Huijuan， Guo Jianfeng. Multi-objective optimal PMU placement using a non-dominated sorting differential evolution algorithm[J]. International Journal of Electrical Power and Energy Systems， 2010， 32（8）：886-892.

[11] 刘刚，彭春华，相龙阳.采用改进型多目标粒子群算法的电力系统环境经济调度[J].电网技术，2011，35（7）：139-144.

[12] 裴胜玉，周永权.基于Pareto最优解集的多目标粒子群优化算法[J].计算机工程与科学，2010，32（11）：85-88.

[13] Kalyanmoy Deb， Amrit Pratap， Sameer Agarwal， T. Meyarivan. A fast and elitist multiobjective genetic algorithm： NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary computation， 2002， 6（2）：182-197.endprint