基于分解的自适应多目标粒子群算法研究

朱玉菲 张纪会 段明

摘要： 针对多目标粒子群算法在选取全局最优解和保持种群多样性上存在的缺陷，本文提出了一种基于分解的自适应多目标粒子群优化算法。该算法采用切比雪夫聚合方法，将多目标问題聚合为若干个单目标问题，并对每一个单目标问题粒子的速度和位置更新公式进行改进，提高了算法搜索到Pareto解集的效率。同时，改进了惯性权重和加速因子，使其自适应调整，能够更好地平衡全局和局部搜索，采用网格技术存储最优解集，能有效保持进化群体的分布均匀性，并采用5个经典的两目标测试函数进行了仿真实验。实验结果表明，通过改进粒子群算法的速度和位置更新公式，可以提高非支配解对真实解的逼近程度，体现了本算法的有效性；多目标粒子群优化算法求得的Pareto解集，在解的收敛性和分布性上都有明显的提升。本算法为求解多目标优化问题提供了一种新的方法。

关键词： 切比雪夫分解； 网格技术； 粒子群优化； 多目标优化

中图分类号： TP393； TP273+.2文献标识码： A

通讯作者： 张纪会（1969），男，博士，教授，博士生导师，主要研究方向为控制理论与控制工程。Email： minedocnments@126.com多目标优化问题广泛存在于众多的科学领域中，而多目标优化是国内外许多专家学者研究的热点问题。然而在多目标的优化算法中，由于多目标问题的每个函数之间相互排斥，使多目标每个函数的解都达到最优是没有意义的，因此，国内外专家学者在研究多目标优化问题时求出的是多目标问题的一组解，而不是一个解，这组解集具有互不支配（nondominated set，NDS）关系，称为帕累托最优解集（paretooptimal set，POS），这些解集在目标空间上构成的前沿面称为Pareto前沿[1]。在处理多目标优化问题时，数学规划法是最早使用的一类方法，但是这些方法在处理多目标优化问题时却存在较大的局限性[2]。因此，为得到一组非支配解来估计帕累托前沿，并且这组解均匀分布在目标空间中，研究者们考虑使用一些其他方法直接处理多目标优化问题。近年来，绝大部分的多目标优化算法都是在帕累托这个概念的基础上发展起来[16]。学者们为了尽可能地提高算法的效率，在早期多目标优化算法基础上，又提出了一系列的第2代多目标优化算法[1，78]。上述研究在优化多目标时都是将多目标问题看成是一个整体进行优化[18]，但Zhang Q等人[910]提出了在多目标进化算法中使用数学规划中的分解策略，即通过某种聚合方法，将多目标优化问题转化为单目标优化问题进行优化。为了进一步提高算法的收敛性和鲁棒性，一些研究者在基于分解的多目标遗传算法（multiobjective evolutionary algorithm based on decomposition，MOEA/D）的基础上做了进一步研究，改进了MOEA/D[1112]。2008年，Peng W等人[13]在MOEA/D框架之下提出基于分解的多目标粒子群算法（multiobjective particle swarm optimizer based on decomposition，MOPSO/D）。在一些2目标和3目标测试函数上，MOPSO/D与非支配排序的多目标遗传算法的二代算法（nondominated sorting genetic algorithmII，NSGAII）相比，显示出更好的性能。基于此，本文提出了基于分解的自适应控制多目标粒子群优化算法（adaptive multiobjective particle swarm optimization algorithon based on decomposition，AMOPSO/D），惯性权重w不再固定不变而是动态变化的，以平衡全局开拓能力和局部搜索能力；针对粒子群收敛速度快，易陷入局部最优的缺陷，算法对粒子群的位置进行突变，自适应调整粒子群在目标空间中的搜索，以增加种群的多样性。同时，改进速度和位置更新公式，以提高算法搜索到Pareto解集的效率，并通过一系列2目标测试函数对算法性能进行验证，证明了其有效性。

1基于分解的自适应控制的多目标粒子群算法

1.1多目标优化问题的数学模型

对于多目标优化问题，其数学模型可描述为

min y=Fx=[f1x，f2x，L，fkx]（1）

s.t. x∈Ω

式中，Ω是n维决策空间；x=（x1，…，xn）T，x∈XRn为n维决策变量；fi1≤i≤k是目标函数；y=（y1，…，yk）T，y∈YRk为k维目标空间；Fx为n个由决策空间向k维目标空间的映射函数。

1.2切比雪夫聚合方法

分解策略是把多目标优化问题通过一定的方法转化为一组单目标优化问题，并同时优化这一组单目标问题。近年来，在许多元启发式方法中都使用了分解思想。MOEA/D中采用切比雪夫聚合方法（Tchebycheff）和权重求和法来处理多目标问题[10]。本文只采用Tchebycheff方法，Tchebycheff方法的计算公式为

min g（x|λi，z*）=max（1≤j≤k）λijfj（x）-zj（2）

式中，x∈Ω；λi=（λi1，…，λik）T是第i个粒子的权重向量，并满足λij≥0，1≤j≤k，λi1+…+λik=1；参考点为z*=z*1，…，z*kT，对于每一个j=1，…，k，有z*j=min1≤j≤kfjx|x∈Ω。因为函数g是关于权重向量λ的函数，所以，对式（2）求最小值时，总存在一个权重向量λ，使式（2）能得到一个最优解，并且原多目标优化问题的Pareto前沿面上应该有一个最优解与之相对应，如果权重向量λj是λi的邻居，那么g（x|λi，z*）的最优解与g（x|λj，z）的最优解应该相接近，这样，优化由权重向量λj构成的单目标子问题g（x|λj，z）的解，对优化单目标子问题g（x|λi，z*）的解有帮助。因此，在优化单目标子问题g（x|λi，z*）的解时，要确定权重向量λi的邻居权重向量。

青 岛 大 学 学 报 （ 工 程 技 术 版 ）第 33 卷

第1期朱玉菲， 等： 基于分解的自适应多目标粒子群算法研究

1.3保持種群多样性的策略

多目标优化问题通过切比雪夫聚合方法转化成单目标优化问题，所以在单目标优化算法中，许多能够提高算法性能的技术和策略都可引入该算法中。

2009年，均值粒子群优化算法（mean particle swarm optimization for function optimization，MeanPSO）被提出[14]，该算法主要用于解决单目标优化问题。算法的主要思想是在速度更新式中比较pbest和gbest的线性组合（pbestij+gbestij）2和（pbestij-gbestij）2，而不仅是将pbest和gbest与粒子的当前位置进行比较。通过分析传统粒子群算法速度的更新公式，提出新的速度更新公式。在每次迭代过程中，粒子i的速度和位置分别为

vij=wvij+c1r1（pbestij+gbestij）2-pij+c2r2（pbestij-gbestij）2-pij（3）

pij=pij+vij（4）

式中，w是惯性权重；c1和c2是加速因子；r1和r2是在0，1范围内取值的均匀分布随机数。

粒子群优化（particle swarm optimization，PSO）算法的收敛速度非常快，所以在用式（4）和式（5）计算时，所有的粒子在经过多次迭代后其位置都趋近于同一个点，这个点就是局部最优点，这时，所有粒子的搜索速度趋于0，位置也不再发生改变，这时就产生了粒子陷入了局部最优的情况。为了克服这种缺陷，提高本算法的开拓能力，本文将式（4）和式（5）改为

vij=wvij+r1（c1pbestij+c2gbestij）2-pij+r2（c1pbestij-c2gbestij）2-pij（5）

pij=pij+βvij（6）

式中，β是0，1上均匀分布的随机数。

惯性权重w具有平衡全局探测能力和局部搜索性能的作用，为了能更好地控制开拓和探索能力，专家学者们通过改进惯性权重w来对粒子群算法进行改进[1516]。2014年，敖永才等人[17]提出自适应惯性权重的改进粒子群算法，该算法减少了无效迭代的次数，提高了算法收敛到最优解的速度和稳定性。本文改进动态惯性权重和加速因子，使粒子在某一位置上不局限其进行全局搜索或局部搜索，在第t次迭代时，惯性权重和加速因子自适应调整为

w=αWmax-（Wmax-Wmin）tNt， c1=w+tNt， c2=w-tNt（7）

式中，Wmin和Wmax分别是w的上、下界；α是0，1上均匀分布的随机数；Nt为总的迭代次数，t为当前代数；c1，c2为加速因子，当迭代次数增加时，c1增加，c2减少。

本算法对粒子群的速度和位置更新公式进行改进，在一定程度上平衡了粒子的开拓能力和搜索性能，但粒子群的搜索速度经过几次迭代后仍然会越来越小，种群仍然会发生局部收敛。为了克服局部收敛问题，保持粒子群的多样性，本文在算法中使用变异操作，变异操作是依概率在粒子的位置上随机选择某一维位置，并对该位置进行突变，具体操作如下：

ifrand

pid=r and

end

变异操作使粒子位置发生改变，从而使种群从局部最优中跳出，在目标空间中重新进行搜索，这不仅保持了种群的多样性，而且其全局搜索性能也得到了提高。

1.4外部档案EA的保存

在保存非支配解时，由于非支配解的存储特别快，使保存的非支配解分布性特别差，使用拥挤距离并不能保证非支配解有较好的分布性。网格技术[18]的主要思想是将目标空间划分成不同的网格子空间，然后记录网格中解集的分布情况。它在多目标优化过程中能够保持种群的分布性，其最大优点是计算的复杂度小。新产生的非支配解分布在网格不同的子区域中，根据其分布的密集程度，对分布密度大的区域随机删除个体，以调整非支配解集在目标空间中的分布，从而达到获得均匀分布解集的目的。因此，在存储外部档案时，本文算法使用了网格技术，当EA中存储的数据个数大于设定值时，启动网格技术。其具体过程如下：

1）建立一个k维的超空间，把k维的超空间平均划分为nk个网格。网格划分时要在目标函数的取值范围内，且每个网格的大小都相等。

2）为超空间中每个网格分配索引号和网格坐标。

3）当种群中的所有粒子飞到对应的网格中后，利用网格坐标采用轮盘赌的方式，删除在网格中聚集密度大的个体。

1.5AMOPSO/D算法的流程

本算法的全局变量如下：

1）种群具有N个粒子x1，…，xN，第i个粒子的位置向量为pi，速度向量为vi，个体最优向量为pbesti。

2）定义第i个粒子的全局最优向量为gbesti。

3）一个参考点：z*=z*1，…z*iT。

4）在搜索过程中，每次迭代产生的非支配解都用一个外部档案EA来储存。

初始化为：

1）EA=。

2）邻居向量的选择。计算λi和λj（λi≠λj）的欧氏距离，按升序进行排序，选取前T个最小距离对应的权重向量λi1，…，λiT作为λi的邻居权重向量，λit表示第i个权重向量的第t个邻居权重向量。

3）初始化种群中粒子的位置和速度。每个粒子的初始位置设置为（0，1）上的随机数，服从均匀分布；粒子的初始速度设置为服从正态分布的随机数。

4）种群的个体最优值和全局最优值的初始化。for i=1，…，N，令pbesti=gbesti=pi。

迭代：

for i=1，…，N do

1）根据式（4）～式（6），更新种群中每个粒子的速度和位置，并依概率在粒子的位置上随机选择某一维位置，对该位置进行突变。

2）参考点Z的更新。forj=1，…，k如果zj

3）种群中每个粒子个体最优值的更新。如果gpi'|λi≤gpbesti|λi，那么pbesti=pi'。

4）种群中粒子全局最优值的更新。对于每一个j∈Bi，如果gpi'|λj≤gpbestj|λj，则gbestj=pi'。

5）更新邻域解。对于每一个邻居权重向量λj，j∈i1，…，iT，如果gpi'|λj，z≤gpj|λj，z，令pj=pi'，F（pj）=Fpi'。

6）更新EA。把EA中所有被支配的解从EA中移除，如果EA中不存在支配的解，将存入EA中。

7）终止条件。达到最大迭代次数，停止并输出EA，否则继续进行迭代。

2评价指标与参数设置

2.1测试函数

本算法在验证其性能时，测试函数采用2目标ZDT系列。测试函数的一组在目标空间上均匀分布的真实解集是已知的，所以可以用来评价本文算法的实验数据。

2.2算法的性能评价指标

多目标优化算法的性能评价指标有很多，如C指标、D指标和反向世代距离（inverted generational distance，IGD）指标[1920]等。IGD指标主要评估多目标优化算法中非支配解集对真实Pareto解集的逼近程度和在目标空间中分布的均匀性，所以本文利用IGD指标来评价实验得出的结果。IGD指标为

IGD=∑ni=1d2in

式中，将第i个真实的Pareto解和近似解中每个粒子的欧氏距离进行比较，与它欧氏距离最小的距离为di，n是真实的帕累托解的数目。IGD值越小，表明得到的近似解与真实的Pareto解的距离就越小，算法的收敛性就越好，在目标空间中的分布就越均匀，近似解与真实的Pareto前沿就越逼近。

2.3算法的实验参数设置

本算法使用ZDT系列的测试函数，种群大小设置为100，邻居数T为30，EA最大為500，Wmin=035，Wmax=10，变异概率Pm=05，最大迭代次数为300，网格膨胀参数为10-5，每一维的网格数为10。本算法得出的结果都是独立运行20次求出的平均值。

3实验结果与分析

各算法在IGD指标上的均值统计结果如表1所示。由表1可以看出，在2目标问题上，本算法在ZDT1～ZDT4测试函数上要明显比其他几个函数的IGD指标小，这体现了本算法比其他几个算法在收敛性和分布均匀性上都要好。对比AMOPSO/D和MOEA/D两类算法可以看出，本算法虽然在ZDT6测试函数上的IGD指标比MOEA/D算法大，但前4组测试函数的IGD指标比MOEA/D小，说明本算法在MOEA/D计算框架下，改进的粒子群优化算法在解的收敛性上具有巨大优势。表1各算法在IGD指标上的均值统计结果

测试函数NSGAIISPEA2MOEA/DSMPSOMOPSOAMOPSO/DZDT11.863 7×10-41.528 6×10-47.593 7×10-51.349 8×10-41.387 9×10-45.525 6×10-5ZDT21.914 5×10-41.561 9×10-45.841 5×10-51.401 3×10-41.431 4×10-44.288 8×10-5ZDT32.554 1×10-42.352 4×10-41.304 7×10-42.034 7×10-42.182 0×10-46.529 8×10-5ZDT42.471 4×10-41.425 7×10-43.059 4×10-41.373 9×10-41.893 6×10-45.332 2×10-5ZDT63.537 9×10-46.538 8×10-42.061 3×10-51.161 5×10-41.220 2×10-43.290 9×10-5表1中，有下划线的为优胜值。ZDT系列测试函数的真实值与在本算法上的估计值（500个目标）如图1所示。由图1可以看出，在2目标ZDT问题的收敛性上，AMOPSO/D的表现水平与真实值相当，但是AMOPSO/D相比于真实值均匀性很好；结合图1和表1可以看出，AMOPSO/D的IGD指标要比其他几个算法小，进一步说明AMOPSO/D求出的解比部分已知的其他优化算法产生的解要好。

综上所述，通过改进粒子群算法的速度和位置更新公式，可以提高非支配解对真实解的逼近程度，体现了本算法的有效性。

图1ZDT系列测试函数的真实值与在本算法上的估计值（500个目标）4结束语

本文在对MOEA/D计算框架进行分析的基础上，提出了基于分解的自适应控制多目标粒子群算法AMOPSO/D，该算法通过引入变异操作，保持了种群的多样性，避免陷入早熟收敛，改进的惯性权重和加速因子可平衡全局开拓能力和局部搜索性能；改进粒子速度公式和位置公式，不仅提高了算法搜索到非支配解集的效率，而且也提高了非支配解对真实解的逼近程度，在存储非支配解集时使用了网格技术，有效地保持整个种群的分布性。实验结果表明了该算法的有效性，但是本算法在解决3目标问题上还存在一定的缺陷，不能得到一个收敛性和分布性都比较好的Pareto前沿面，所以今后的主要工作是继续改进算法，使其能更好地解决3目标及更多目标优化的问题。

参考文献：

[1]Deb K， Kalyanmoy D. MultiObjective Optimization Using Evolutionary Algorithms[M]. New York： John Wiley & Sons， 2001.

[2]刘加光， 陈义保， 罗震. 连续体结构的模糊多目标拓扑优化设计方法研究[J]. 系统仿真学报， 2007， 19（5）： 10951099.

[3]Fonseca C M， Fleming P J. Genetic Algorithm for MultiObjective Optimization： Formulation， Discussion and Generation[C]//The 5th International Conference on Genetic Algorithms. San Mateo， CA： Morgan Kaufmann， 1993： 416423.

[4]Zitzler E， Thiele L. Multiobjective Optimization Using Evolutionary Algorithmsa Comparative Case Study[C]∥International Conference on Parallel Problem Solving from Nature. Berlin： Springer Berlin Heidelberg， 1998： 292301.

[5]Knowles J， Corne D. The Pareto Archived Evolution Strategy： A New Baseline Algorithm for Pareto Multiob Jective Optimisation[C]// Proc Congress on Evolutionary Computation. Washington， DC， USA： IEEE， 1999： 98105.

[6]Srinivas N， Deb K. Multiobjective Optimization Using NonDominated Sortingin Genetic Algorithms[J]. Evolutionary Computation， 2014， 2（3）： 221248.

[7]Deb K， Pratap A， Agarwal S， et al. A Fast and Elitist Multiobjective Genetic Algorithm： NSGAII[J]. IEEE Transactions of Evoluationary Computation， 2002， 6（2）： 182197.

[8]Zitzler E， Laumanns M， Thiele L. SPEA2： Improving the Strength Pareto Evolutionary Algorithm for Multiobjective Optimization[C]//Evolutionary Methods for Design， Optimization and Control with Applications to Industrial Problems. Athens Greece： Proceedings of the Eurogen， 2001： 1921.

[9]Zhang Q， Li H. MOEA/D： A Multiobjective Evolutionary Algorithm Based on Decomposition[J]. IEEE Transactions on Evolutionary Computation， 2007， 11（6）： 712731.

[10]Li H， Zhang Q. Multiobjective Optimization Problems with Complicated Pareto Set， MOEA/D and NSGAII[J]. IEEETransactions on Evolutionary Computation， 2009， 13（2）： 284320.

[11]Trivedi A， Srinivasan D， Sanyal K， et al. A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition[J]. IEEE Transactions on Evolutionary Computation， 2016， 21（3）： 440462.

[12]Wang R， Zhang Q， Zhang T. DecompositionBased Algorithms Using Pareto Adaptive Scalarizing Methods[J]. IEEE Transactions on Evolutionary Computation， 2016， 20（6）： 821837.

[13]Peng W， Zhang Q. A DecompositionBased MultiObjective Partile Swarm Optimization Algorithm for Continuous Optimization Problems [J]. IEEE International Conference on Granular Computation， 2008， 15（3）： 534537.

[14]Deep K， Bansal J C. Mean Particle Swarm Optimization for Function Optimization [J]. International Journal Computational Intelligence Studies， 2009， 1（1）： 7292.

[15]Shi Y， Eberhart R C. Parameter Selection in Particle Swarm Optimization [J]. International Conference on Evolutionary Programming， 1998， 1447（25）： 591600.

[16]董平平， 高東慧， 田雨波， 等. 一种改进的自适应惯性权重粒子群优化算法[J]. 计算机仿真， 2012， 29（12）： 283286.

[17]敖永才， 师奕兵， 张伟， 等. 自适应惯性权重的改进粒子群算法[J]. 电子科技大学学报， 2014， 43（6）： 874880.

[18]李召军， 王希诚. 一种基于网格的多目标优化方法[J]. 大连理工大学学报， 2012， 52（6）： 787793.

[19]邱兴兴， 张珍珍， 魏启明. 混合分解和强度帕累托多目标进化算法[J]. 计算机应用， 2014， 34（10）： 28802885.

[20]李飞， 刘建昌， 石怀涛， 等. 基于分解和差分进化的多目标粒子群优化算法[J]. 控制与决策， 2017， 32（3）： 403410.