多目标粒子群优化算法研究综述

冯 茜，李 擎，全 威，裴轩墨

1) 北京科技大学自动化学院，北京 100083 2) 华北理工大学机械工程学院，唐山 063210 3) 北京科技大学工业过程知识自动化教育部重点实验室，北京 100083

多目标优化问题具有多个相互冲突的目标函数，某一目标求得的最佳方案，不可能同时使得其他目标为最优值，甚至导致退化. 多目标优化[1]作为一类复杂的最优化问题，既被用于生产调度、城市运输、网络通信等系统的实时设计，又涉及工程设计、数据挖掘、资本预算等智能规划问题，无论是在理论研究还是工程实践中都具有深远的意义. 随着现实世界中问题所呈现的多元化、规模化发展模式，多目标优化问题面临着非线性、多维度、智能性、动态规划等多方面的严峻挑战.

传统的多目标优化方法主要有：加权求和法[2]、约束法[3]、目标规划法[4]、距离函数法[5]以及极大极小法[6]等. 这些优化方法大多是采取不同的策略将多目标问题分解为单目标问题，再使用单目标算法完成优化，依赖于先验知识，受限于Pareto前沿的形状. 尤其是当多目标问题呈现出非线性、高维度等复杂特性时，传统方法很难确保好的优化效果甚至不可行.

近年来，进化算法将生物信息融入元启发式算法之中，凭借其独特的更新机制，在组合优化和数值优化领域[7]均已取得了很多突破性研究成果.典型的多目标进化算法有：多目标粒子群算法[8]，多目标蜂群算法[9]，多目标蚁群算法[10]，多目标免疫算法[11]，多目标差分算法[12]等. 粒子群算法是一种受到自然界中鸟类群体觅食行为的启发而发展起来的进化算法，鉴于其实现简单、搜索高效、收敛快速等优势，不仅在各类复杂的实验测试中还是实际工程应用中，均得到了广泛应用.

1 基本粒子群算法

1995年，Kennedy和Eberhart两位博士[13]共同提出了粒子群优化算法(Particle swarm optimization，PSO). ven den Bergh[14]从理论角度对PSO算法的稳定性和收敛性进行了分析和证明. 2002年，Cello与Lechuga[15]正式发表了多目标粒子群优化算法的成果. 粒子群算法求解多目标优化问题，称为多目标粒子群（Multiobjective particle swarm optimization，MOPSO）算法.

PSO算法中，将鸟群的个体位置或食物当作优化问题的解，利用群体中个体与最优个体以及个体之间的信息交互，引导整个群体中个体在保留自身多样性信息的同时，朝向群体最优个体收敛，通过不断地更新逐渐找到最优解. 鸟群中个体被抽象为“粒子”，忽略其质量、体积，拓扑结构决定了每次迭代时“粒子”受到自身和群体状态信息的综合影响，即粒子的更新机制是通过种群历史最优粒子和个体历史最优粒子的有机结合得到，如图1所示. 粒子i下一时刻的速度 vi(t+1)是由当前速度 vi(t)、其自身最优位置 p bi(t)、全局最优位置gb(t)共同决定的，该粒子以更新后速度从当前位置 xi(t)移至新的位置 xi(t+1). 随着迭代的不断深入，整个粒子群体在“引领者”的带动下，完成决策空间中最优解的搜索.

图1 决策空间中粒子移动示意图Fig.1 Image of particle movement in the decision space

2 多目标粒子群算法存在的问题

多目标粒子群算法凭借其高效、快速的优势，成为了多目标优化的主要研究方向. 处理多目标优化问题时，既要克服传统多目标优化过程中的普遍性难点，又要考虑粒子群算法用于多目标优化时的针对性问题. 归纳如下：

（1）优化过程中，如何挑选“领导”粒子，带领整个种群在保留部分个体信息的前提下快速逼近帕累托前沿，即最优粒子选择策略；

（2）粒子群算法中，种群个体受到“最优”粒子的影响，由于收敛过快而导致“早熟”，如何引导粒子“跳出”局部最优，即多样性保持机制；

（3）外部存储集中非支配解的数量的急剧增加，如何引导种群在保障多样性的前提下，进一步提高搜索效率，以强化算法在收敛速度方面的优势，即收敛性提高手段；

（4）如何在优化过程的不同阶段，动态协调整体开发和局部搜索之间的关系，以获得最佳优化结果，即多样性和收敛性的平衡方法；

（5）为了提升算法性能而进行的迭代公式的改进、重要参数的动态整定以及粒子间信息交互方式的调整，即迭代公式、参数、拓扑结构的改进方案.

下面将从以上5个方面对近年来多目标粒子群优化算法的改进措施进行较为详细的介绍.

3 多目标粒子群算法改进措施

3.1 最优粒子选择策略

采用粒子群算法进行优化时，每次迭代都需要进行全局最优粒子（Global best particle, gbest）和个体最优粒子（Personal best particle, pbest）的选择.gbest作为整个种群的核心“领导者”，对整个优化过程的收敛速度、搜索效率以及“最优”结果会产生极大的影响；而每个粒子到目前为止自身的“最优”状态，对避免陷入局部最优，保持种群多样性并获得最好的优化结果起到重要作用. 因此，合理和有效的“最优”粒子选择机制具有重要意义. 单目标优化时，“最优”个体是唯一的，而多目标优化时，每次更新都可能产生“当前”最优解集，存储于外部存储集中. 随着优化进程的不断深入，最优解集的数量会急剧增加，这将会导致巨大的选择压力，而这一困难在处理高维度优化问题时会显得愈发突出.

为了能够高效带领种群收敛到真正的帕累托最优前沿又不失多样性，有些学者基于分解思想设计最优粒子选择策略. Zhu等[16]设计了一种基于外部存储集引导的择优策略，分配粒子对分解产生的子问题进行优化，有效提高了收敛速度.Li等[17]提出基于增强选择策略的更新机制. 通过切比雪夫聚集函数值、有利权重的切比雪夫值和随机选择三种方式，自适应切换聚集函数值，加强局部搜索. Ali与Khan[18]提出了基于综合学习策略的方法. Cheng等[19]基于动态加权聚合函数进行最优粒子的动态选择.

有些方法不是以适应度函数为粒子优先权的评估机制，而是基于指标衡量解的价值，进行最优粒子的选择. 比较典型的评价指标有：超体积指标[20]，R2指标[21]. Wu等[22]基于虚拟帕累托前沿对粒子进行评估. Li等[23]基于R2指标进行外部存储的维护以及最优粒子的选择.

基于Pareto排序的方法也是一类较为常用的优化方法. 小生境方法[24]是一种行之有效的多目标优化方法. Qu等[25]将物种形成策略[26]融入粒子群优化算法，所提出物种形成机制根据邻域结构生成多个小生境，采用并行方式搜索帕累托最优解. 自组织策略能够在加速小生境形成的同时避免子群之间的交叉. 仿真实验结果表明，该算法能够保持决策空间和目标空间中解的多样性，使得解分布更加均匀. 文献[27]基于密度聚类的思想进行领导粒子选择. 文献[28]将代理辅助策略与标准粒子群算法以及社会学习粒子群算法相结合，利用改进的帕累托存档学习方法来提高外部存储集当中候选解的质量，辅助最优粒子的选择，从而加速收敛. 文献[29]将代理辅助策略融入帕累托主动学习方法，以粒子群算法为数据知识库生成机制，构建虚拟空间中的代理模型代替适应度函数，根据改进的帕累托主动学习策略预先将粒子分类. 该方法基于解的预判断辅助优化，有利于节约计算成本，提高效率.

一些研究人员采用两种方式相结合的策略，共同进行最优粒子的选择. Liu等[30]融合了R2指标与分解的思想，Li等[17]提出将基于R2指标[31]和L2范数的分层R2排序算法和有利权重的切比雪夫聚集值相结合的外部档案更新策略. 李飞等[32]以R2指标和目标空间分解两种策略为衡量标准提出双层档案维护策略. 文献[33]基于解分布指标和超体积指标，将多目标优化问题转化为二目标问题，设计了将解集和解集中的解分层处理的粒子群算子. 实验结果表明，该方法能够获得良好的分布性和收敛性. Moubayed等[34]将分解与支配关系相结合，根据偏好进行排序，用分解方式将多目标问题转化为聚合问题，利用非支配关系进行外部存储集中最优粒子的选择.

有些文献通过改进排序方法来提高精英库中备选粒子的质量. Li等[35]提出了一种将综合排序策略与目标空间中基于切比雪夫距离的粒子密度信息相结合的最优粒子选择机制. Tang等[36]将非支配解存储后，将精英保留与循环排序方法相结合，以获得高质量的帕累托前沿.

3.2 多样性保持机制

粒子群算法在追求收敛速度快、搜索效率高的同时，往往会以多样性的缺失为代价，而影响最终的优化结果. 因此，研究人员从多个角度提出保持种群多样性的策略，并取得了显著的效果.

一些文献使用空间划分策略来保持多样性.这类方法主要是将目标空间分割为多个区域，根据个体在分割区域的分布情况，一边引导种群中的其它个体向某一区域“靠拢”，以加速收敛；一边保留其它区域的个体“特征”，以获得分布均匀、覆盖率广的Pareto前沿. 比较有代表性的方法主要有：网格划分法[37]和角度划分法[8]. 本团队提出了一种自适应角度划分法[38]，结合非支配解在角度区域中的动态分布，加强“低密度”区域或“无分布”区域相邻区域的探索，同时删除“高密度”区域多余粒子；同步实现gbest和pbest的选择，有利于保持种群多样性.

还有一些文献是基于种群划分的思想. 这类方法是将整个种群划分为多个子群，子群根据各自的引领者并行引导种群更新，共享外部存储集信息. Zhan等[39]将整个种群划分为相等规模的子群，每个子群体只针对一个目标进行优化，并根据目标确定每个子群的适应度，各子群间会以外部存储集为平台，共享各子群间信息，同时将精英学习机制融入外部存储集以增强多样性. 然而，通过研究发现[40]，这种策略有可能会导致选择压力的增加，并且增加时耗. Yang等[41]将整个种群动态划分为主群和多个子群，每个子群拥有各自的非支配解、子群拥挤距离以及指定目标，各子群为并行搜索，通过非支配排序和归一化结合机制选择出最优粒子. Luo等[42]将种群划分为子群并建立各子群的概率模型，分别使用粒子群算法和分布估计算法对概率模型进行更新，在解决复杂的多目标问题时表现出良好的能力. Yao等[43]采用竞争与合作技术促进子种群间的协同进化，有利于获得多样性良好以及分布均匀的Pareto前沿. Zhang等[44]提出在决策空间中基于欧氏距离进行种群划分的聚类策略，有利于种群多样性的保持. Liang等[45]将自组织机制引入决策空间中进行多峰多目标优化，将相似解置于邻域中，并从构建邻域中选择相应的领导者，以保证更好的种群多样性.

基于分解的优化方法有利于维护良好的种群多样性. 文献[46]采用基于分区的分解策略求得分布均匀的解. Dai等[47]从分解角度进行解的多样性维护，将目标空间分解为子区域，并采用相应的多样性保持策略. Qi等[48]基于分解方法在目标空间中自适应调整权值，使得每个子区域都有一个保证种群多样性的解.

Albaity等[49]将量子理论与粒子群算法的结合，以便帮助粒子产生全局最佳位置，提高种群多样性的同时，还保证了粒子群算法的全局收敛效果. Liu等[50]将文化理论算法与量子行为粒子群优化算法相融合，多次从信念空间知识中提取种群个体的测量信息，并根据历史知识设计了一种局部搜索算子，利于保持种群多样性. Pan等[51]基于速度的决策变量分析方法提出多样性增强策略，有效提高了优化过程中种群多样性.

Li等[52]采用全局边缘排序策略，同时结合种群粒子在目标空间中的个体密度信息，有利于多样性的维护. Cheng等[53]提出基于混合教学的循环拥挤排序方法，周期性调用教学阶段和学习阶段算法，利用种群中心值提高种群的整体搜索性能，同时加强粒子之间的信息交互，获得良好的收敛性的同时保持多样性.

喻金平等[54]基于博弈机制，通过精英粒子之间的博弈，确定最优粒子. 最优粒子从精英粒子中随机选择，有利于保持多样性，而外部存储集的省略，有助于提升收敛速度. Zhang等[55]提出基于竞争机制的学习策略. 首先，根据经典的非支配排序和拥挤距离筛选精英粒子. 其次，基于成对竞争策略的更新机制，精英粒子中竞争成功的粒子为当前种群中粒子引导更新方向. 最后，粒子通过向竞争赢家学习，更新位置和速度. 该算法不再使用广泛应用的外部档案存储和更新策略，取而代之的是基于精英粒子竞争以及学习策略的更新机制.

另外，变异操作是进化算法中多样性保持或增加的重要方式. 单目标优化中比较经典的变异策略，经过改进后用于进行多目标优化，如：快速下降法[56]、精英学习策略[57]、柯西变异[58]等，取得了良好的效果. Liu等[30]采用多项式变异进行外部档案中多样性维护，此外，当粒子个数未能满足所设定的更新条件时，应用高斯变异策略对种群个体的位置以及速度进行重新初始化. 张伟与黄卫民[59]根据收敛性能指标将种群进行区域划分，分别采取不同的变异策略. Yu等[28]使用混合变异采样策略增强解的多样性，提高了搜索效率.

杨景明等[60]根据不同阶段对收敛性的不同要求，应用多项式变异策略，以相邻两次迭代的最优解集得到的世代距离为自适应变异规模调整机制，分阶段进行变异操作. 韩敏与何泳[61]设计了一种高斯混沌变异策略，根据粒子个体与gbest间的距离自适应调整高斯变异幅度，引入Logistic混沌映射值，增加遍历性. 为了提高多样性，Moslemi与Zandieh[62]引入变异算子来保持群体的多样性，并且将网格与拥挤距离相结合进行全局最优粒子的选择. 多尺度混沌变异策略[58]被用来帮助算法“跳出”局部最优. 王学武等[63]基于三种变异算子设计变异策略，并根据随机数的值进行选择，以增强所得解的多样性.

3.3 收敛性的提高手段

虽然粒子群算法进行单目标优化时，在收敛性能方面具有显著优势，但是用于多目标优化时，由于目标数目和维度的增加，会导致解的数量急剧增多，为了能够既不失多样性，又快速获得最优解集，需要提高算法的收敛性能，有利于提高算法效率.

为了加速收敛，Peng等[64]设计了一种跟随非线性惯性权重系数变化的动态学习因子. Li等[65]采用岛屿模型将整个种群进行划分，生成的子群以并行运行方式提高算法的收敛速度. Xu等[66]以间隔迭代方式将多目标二分法线性搜索方法融入MOPSO算法，加强了局部搜索能力，以促进种群向真实帕累托前沿的收敛. Cheng等[67]基于局部最优粒子策略引导种群快速向帕累托最优前沿逼近.

聚类策略的引入，有利于提高种群的搜索速度. 于慧等[68]基于动态聚类思想划分种群，提高收敛速度的同时减少了种群多样性损失. Liu等[69]将种群划分后，通过子群间共享信息的协同进化方式提高收敛速度，以应对实际应用时环境变化快速的动态优化问题. Han等[70]采用多目标梯度方法，通过计算每个粒子全部单位方向的加权和确定多梯度下降方向，以加速收敛.

3.4 多样性和收敛性的平衡方法

通常情况下，我们希望在全局开发阶段，重视多样性的同时加速收敛，以提高搜索效率；另一方面，在局部搜索阶段，加强收敛性能的同时能够减少多样性损失，以避免算法过早收敛. 无论哪一阶段，都应对收敛性和多样性两个性能指标进行兼顾，以确保高效、精准的优化结果.

研究人员提出了多种策略对优化过程进行状态评估，自适应调整收敛性和多样性的权重，从而达到动态协调两个性能指标的目的. 平衡适应度估计策略[71]能够帮助实现外部存储集中非支配解的选择，并在外部档案上进一步运行进化搜索，加强了精英个体之间信息交换. 该策略由收敛性距离和多样性距离两部分构成，根据二者的权重系数动态平衡多样性与收敛性之间的关系. 合理的最优粒子选择机制可以协调整个搜索过程中收敛性和多样性的关系. 优化过程中，为了能够确保快速收敛的同时多样性得以维护，Hu与Yen[72]基于非支配解的分布熵进行环境估计，采用新颖的自适应动态方式，将最优粒子选择、外部存储集维护、参数调节以及扰动等环节均融于平行单元坐标系中.

设定参考点有利于减轻选择压力[73]，Wu等[74]以预定义的参考点为主要标准，以相邻粒子间欧几里德距离为附加选择标准，提高算法性能. 还使用估计策略识别进化状态，动态调整最优选择机制，加强开发阶段的收敛速度，维护探索阶段的多样性，通过平衡开发和探索之间关系的方式达到动态协调收敛性和多样性的目的. Figueiredo等[75]采用搜索过程中的目标空间超平面上的动态参考点以及聚集方法，促进多目标优化过程中收敛性和多样性之间的平衡关系.

此外，为了协调快速开发和深入探索之间的关系，Lin等[76]提出多搜索策略多目标粒子群算法，将收敛性和多样性作为两个不同目标，基于预设阈值分别采用不同的粒子速度更新策略. Hu等[77]提出偏重收敛性和多样性的两阶段策略，第一阶段基于聚合原理，第二阶段基于平行单元坐标系理论，以便在不同阶段针对性提高算法的收敛性和多样性. 受到鸟类觅食时线性和圆形行为的启发，Meza等[78]基于粒子群体的旋转和平移运动方式提出涡旋多目标粒子群优化算法. 线性运动帮助种群收敛，而圆形运动有助于个体分散搜索；参数选择基于粒子的动态行为，兼顾了收敛性和多样性. Pan等[79]采用增量熵方法设计自适应因子，调节收敛性和多样性之间的动态平衡关系，基于离散解耦策略分解目标，构建子群，通过协同进化实现多目标优化. 还有一些文献基于分解思想来权衡开发和探索之间的关系. Liu等[80]将瓶颈目标学习策略融入分解机制，Moubayed等[34]将Pareto支配与分解两种优化策略进行融合，用于权衡收敛性和多样性.

3.5 迭代公式、参数、拓扑结构的改进方案

为了提高粒子群算法的性能，一些文献还提出从迭代公式、参数整定以及拓扑结构等方面进行改进.

迭代公式改进方面，Lin等[71]增加粒子个体朝向全局最佳粒子的引领搜索项，使得粒子在搜索过程中有可能获得更多扰动. Yao等[43]增加了子群最优粒子的信息，同时还融入了相邻粒子信息.Pan等[51]提出了将认知学习部分删除，能够保证算法的收敛以及有效学习.

进化算法进行优化时，通常需要针对问题选择和调整算法[81]. 参数校正方面，Han等[82]提出了一种自适应飞行参数调节机制，利用多样性信息和种群速度信息，对全局探索和局部开发之间的关系进行平衡. 该算法的新颖之处就在于能够结合解分布熵同步完成飞行参数的调节以及全局最优粒子的选择. 夏立荣等[83]基于层次分析方法，设计出一种进化因子，通过度量进化状态自适应调节参数. Liu等[84]应用强化学习理论中的Q-Learning方法，以目标空间中Pareto前沿的粒子数量、决策空间中粒子间距为状态，以粒子群算法中3个主要参数— —惯性权重系数和两个认知加速度系数为动作，建立三维Q表，自适应调整算法参数.Hu等[85]通过改变参数来提高算法的鲁棒性，虽然可以防止算法陷入局部最优，收敛精度也有所提高，但大量“新”变量的引入有可能会增加计算复杂度[86]. Ding等[87]应用田口方法作为响应值来调整参数. Tang等[36]以保证收敛性能为参数选择原则，以开发和挖掘的不同偏好为目标设计了自适应参数调节机制，并且讨论了参数对收敛性能的影响.

拓扑结构方面，Yue等[88]提出的基于环形拓扑和特殊拥挤距离的多目标粒子群优化算法，在决策空间中，引入无需参数的环形拓扑结构帮助形成稳定的小生境，有利于减少多样性损失. 高海军与潘大志[89]采用星型拓扑结构，在收敛速度方面表现出一定的优势. Zhang等[44]对划分的子种群采用环形拓扑结构，有利于信息交互和保持多样性.

4 总结与展望

本文主要就多目标粒子群算法中最优粒子选择，多样性保持，收敛性提高，多样性与收敛性之间的平衡，以及迭代公式、参数、拓扑结构等改进措施进行了系统分析. 近几年来，算法自身性能得以提升，应用领域不断拓展，涌现出大量行之有效、独特新颖的先进成果. 然而，随着信息科学和计算技术的高速发展，多目标粒子群算法在优化效果上仍具有一定的提升空间. 今后的研究工作，可以从以下几个方面开展：

（1）多目标粒子群算法基础理论的研究. 目前的研究大多集中于算法性能改善以及应用范围推广，由于相关数学理论不够完备，与算法相关的收敛性、稳定性、参数鲁棒性以及计算复杂度等研究有待深入开展；

（2）动态环境评估机制的完善. 更新过程中，个体当前状态的反馈信息都将作为下次迭代如何实施的重要因素，这就要求能够客观、准确地对环境状态进行估计，而单一的评价指标难以全面衡量环境情况. 因此，多指标融合的动态环境评价策略尚需进一步改进；

（3）种群个体自学习、自组织能力的提高. 作为一类元启发式算法，随机性有利于多样性却不利于收敛，而高速的收敛又容易导致早熟，难以保证稳定的优化结果. 为了削弱算法中不确定因素的影响，获得高效、准确的优化效果，往往会对种群中个体加以引导，而引导策略大多是人为规定且基于主观偏好，缺乏客观性和有效性，因此，基于机器学习、深度学习、强化学习等先进理论的种群个体自学习、自组织能力的算法亟需进一步探究；

（4）自适应方法的拓展. 优化过程中不同阶段对探索能力和挖掘能力的需求有所不同，不同多目标优化算法在收敛速度和多样性能方面的表现也各有利弊. 单一策略或固定模式的算法融合很难适用于所有优化问题. 因此，为了促进算法对优化问题的适应性，基于进程估计和策略选择的自适应调整机制仍需不断优化.