第5卷第5期 智能系统学报 Vol.5 No.5 2010年10月 CAAI Transactions on Intelligent Systems 0ct.2010 doi:10.3969/i.isgn.1673-4785.2010.05.001 多目标微粒群优化算法综述 王艳12，曾建潮2 (1.兰州理工大学电信工程学院，甘肃兰州730050：2.太原科技大学复杂系统和智能计算实验室，山西太原030024) 摘要：作为一种有效的多目标优化工具，微粒群优化(S0)算法已经得到广泛研究与认可.首先对多目标优化问题 进行了形式化描述，介绍了微粒群优化算法与遗传算法的区别，并将多目标微粒群优化算法(OPS0)分为以下几 类：聚集函数法、基于目标函数排序法、子群法、基于Pto支配算法和其他方法，分析了各类算法的主要思想、特点 及其代表性算法.其次，针对非支配解的选择、外部档案集的修剪、解集多样性的保持以及微粒个体历史最优解和群 体最优解的选取等热点问题进行了论述，并在此基础上对各类典型算法进行了比较.最后，根据当前MOS0算法的 研究状况，提出了该领域的发展方向. 关键词：多目标优化；微粒群优化算法：非支配解：外部档案：多样性 中图分类号：1P18文献标识码：A文章编号：16734785(2010)050037708 A survey of a multi-objective particle swarm optimization algorithm WANG Yan12,ZENG Jian-chao2 (1.College of Electrical and Information Engineering,Lanzhou University of Technology,Lanzhou 730050,China;2.Complex System and Computational Intelligence Laboratory,Taiyuan University of Science and Technology,Taiyuan 030024,China) Abstract:Particle swarm optimization(PSO)algorithms have been widely studied and approved as effective multi- objective paper optimizers.In this paper,first of all multi-objective problems were formally described,and the difference between a PSO and genetic algorithm (GA)was introduced.Then the taxonomy of current multi-objec- tive PSO(MOPSO)algorithms,which include aggregate functions,sorting based on objective functions,sub-popu- lation methods,Pareto dominated based algorithms,and other algorithms,was presented.Additionally,the main i- deas,features,and representative algorithms of each approach were analyzed.Secondly,hot topics in MOPSO al- gorithms such as selecting non-dominated solutions,pruning archive sets,maintaining the diversity of the solutions set,and selecting both the best personal and global solutions were discussed on the basis of which all typical algo- rithms were compared.Finally,several viewpoints for the future research of MOPSO were proposed according to the present studies. Keywords:multi-objective optimization;particle swarm optimization;non-dominated solutions;archive;diversity 在科学实践、工程系统设计及社会生产活动中，知道每个目标函数所占的权重，并且对目标给定的 许多问题都是多目标优化问题.通常多目标优化问次序也比较敏感. 题中的各个目标函数之间可能会存在冲突，这就意 微粒群优化(PS0)算法是1995年由Kennedy 味着多目标优化问题不存在惟一的全局最优解，使 和Eberhart提出的一种基于群体智能的优化算法， 得所有目标函数同时达到最优.为了达到总目标的 应用于单目标优化问题时表现出了快速收敛的特 最优化，需要对相互冲突的目标进行综合考虑，对各 点.随着对PS0研究的深入，该算法已经由用来解 子目标进行折衷.最初，多目标优化问题往往通过加 决单目标优化问题逐步拓展到用来解决多目标优化 权等方式转化为单目标优化问题，但这样需要事先 问题.1999年Moore和Chapman首次提出将PS0算 法应用于解决多目标优化问题，但这个思想未公 收稿日期：20090922. 基金项目：国家自然科学基金资助项目(60674104) 开发表.从此以后用PS0解决多目标优化问题开始 通信作者：曾建潮.E-mail:z心ngjianchao@263.net. 得到研究人员的关注，但直到2002年Coello等21和
·378 智能系统学报 第5卷 Ray等3]先后发表了多目标微粒群优化算法(MOP- X:(t+1)=X:(t)+V:(t+1). S0)的论文，继之多目标微粒群优化算法逐渐被研 式中：w为惯性权重，c、c2为加速常数，1、r2表示区 究者们重视，出现了大量研究成果1]， 间[0,1]内均匀分布的随机数，P:为粒子自身经历 纵观国内外该领域的研究情况，国外Sierra和 的最好历史位置，而P。为粒子所对应的全局最好 Colo在2006年发表了该领域较为全面的综述41， 位置，它是整个群体所经历的最好位置，X(t)与 但主要是针对2005年以前的MOPS0算法，那时 V(t)为微粒i在时刻t的位置与速度.式(1)表示 MOPS0算法的研究刚刚起步不久，研究成果并不是 微粒速度由3部分决定：惯性部分、认知部分和社会 很多.而国内该领域的综述非常少「o],并且只是简 部分，它们共同改变微粒飞行速度，但速度会受到最 单从算法设计和应用方面回顾了其研究进展，所以 大速度Vma的限制. 有必要对该领域进行一个较为全面的介绍， PS0算法与遗传算法不同，在PS0算法运行过 1多目标优化问题的数学描述 程中，没有选择或变异操作，因而种群的规模是固定 的，微粒不会被舍弃与替换，被替换的是迄今为止微 一般情况，多目标优化问题可以形式化描述为 粒经历的历史最好位置（称为个体极值，用P表 如下形式： 示)和群体的最好位置（称为全局极值，用g表 minY=f(X)=(f(X),(X),…f,(X)), 示)，种群中所有微粒的调整均依赖于pe和gt的 6:(X)≥0，i=1,2,…,k, 值.所以将PS0算法引入来解决多目标优化问题 h(X)=0,j=1,2,…,l. 时，Pe和gt的选取非常重要，而这在多目标进化 式中：决策向量XeR”,目标向量Y∈R”,f(X)(i= 算法的设计中是没有的. 1,2,…,r)是目标函数，g:(X)≥0和h(X)=0是约 束条件 3多目标微粒群算法分类 定义1个体间的支配关系：设p和q是进化 根据对多个优化目标处理方式以及种群最优解 群体中的任意2个不同的个体，称p支配9，则必须 选取方式，多目标微粒群算法大致可以分为以下几 满足下列2个条件： 类：聚集函数法、基于目标函数排序法、子群法、基于 1)对所有的子目标，P不比q差，即Hi∈{1,2， Pareto支配算法和其他方法. …,r},f(p)≤f(q); 3.1聚集函数法 2)存在一个子目标使p比q好，即31∈{1,2， 聚集函数法是解决多目标优化问题的一种最直 …,rf(p）<f(q). 接的方法，基本思想就是将多目标优化问题转换为 其中r为子目标的数量，此时p为非支配的，9为被 单目标优化问题.聚集函数可以是线性的，也可以是 支配的，定义为pq,“〉”表示支配关系， 非线性的，当聚集函数是线性时往往无法搜索到非 定义2 Pareto最优解集：对于决策空间中的向 凸解，当聚集函数是非线性的时候就可以解决这个 量X∈FCR,F是搜索区域，若在F区域内，X*是 问题了2]，在这种方法中较具有代表性的研究是文 非支配的，则X"是F内的一个Pareto最优解.由搜索 款8,13-14]. 空间中所有Pareto最优解组成的解集就称为Pareto 文献[8]分析了固定权重、突变权重和动态权 最优解集，即P‘={XEFIX是Parteto最优解}. 重这3种权重聚集方法.固定权重在优化过程中权 定义3 Pareto最优边界：Pareto最优解表现在 重是固定不变的，但计算量很大，并且无法找到非凸 目标空间上就是Pareto最优边界，或称为Pareto前 解.突变权重和动态权重可以克服这个缺点，只是突 沿(Pareto front),即PF*={f(X)eRIX∈P*. 变权重一般是周期函数的复合函数，变化比较频繁， 2微粒群优化(PS0)算法 变化的尺度由周期函数的外层函数决定.动态权重 在突变权重的基础上将复合函数变成了周期函数的 PS0算法是一种基于种群的启发式优化算法， 绝对值函数，这样变化的尺度相对突变权重要缓和 由于其参数设置少，实现简单，决策变量是实数，收 一些 敛速度快等特点，使其得到充分研究.标准PS0算 文献[13]使用了一种线性权重聚集法.在这类 法的运动方程如下： 方法中，整个群体被平均分成了若干个子群体，每个 V,(t+1)=wV(t)+cr1(P:-X(t))+ 子群体被赋予不同的权重，每个子群体中的微粒都 c2r2(P。-X:(t)), (1) 朝着自己所处子群中的最优解“飞行”，然后通过线
第5期 王艳，等：多目标微粒群优化算法综述 ·379· 性权重进行聚集，得到总目标下群体全局最优微粒 这几个子群体.然后根据支配关系找出每个子群体 文献[14]使用了一种类似于权重聚集的方法. 中的全局最优个体，它们构成一个非支配集，从中选 首先找到在每个目标下群体的全局极值和每个微粒 出群体的全局最优解. 在每个目标下的个体极值，然后用各目标下全局极 文献[l8]利用Pareto支配确定微粒的“飞行” 值的均值作为整个群体在总目标下的全局极值，并 方向，采用聚类的方法将微粒群分为几个子群，每个 通过判断每个微粒在每个目标下相对于该目标下全 子群体产生非支配解集，从其中随机选择一个作为 局极值的离散程度来选取该粒子在总目标下的个体 每个子群执行PS0算法时的全局最优解，子群间通 极值 过移植不同子群中的非支配解交换信息 以上3种方法都比较简单，容易实现.但是算法 3.4基于Pareto的方法 每迭代1次只能产生1个“最优解”，所以要得到接 现在的大多数研究主要集中于这种方法，借鉴 近PF的Pareto front则需要的迭代次数较大，从而 以前用进化算法解决多目标优化问题的一些成功经 带来的计算量就会较大.并且这3种方法都没有很 验，在进化过程中经常保持2个群体，一个是进化的 好地体现出Pareto支配的概念，没有精英解保留机 基本种群population,另一个是用来存储进化过程中 制，这样使解的质量受到影响， 的精英个体的群体archive.首先通过evaluate来确 3.2基于目标函数排序方法 定基本种群中个体的优劣，然后通过确定基本种群 在这种方法中目标函数通常要根据某个标准进 的全局最优个体和每个个体的历史最好位置，利用 行排序，然后按照此顺序对目标函数进行优化.比较 PSO公式进行更新，得到下一代基本群体.对ar- 具有代表性的方法是Hu和Eberhart的动态邻域策 chive一般要进行2种操作：update和truncate,前者 略51及其扩展]，前者主要针对2个目标函数在环 用来更新archive中的个体保持为进化中的最优个 形邻域上进行的优化，没有采用外部存储体保存精 体，后者是当要进人archive中实际个体的数目大于 英个体，后者在前者的基础上引入了精英解的保留 archive容量时，对其中个体进行修剪剔除 机制.这类方法的主要思想是首先根据第1个目标 通常具有精英解保留机制的MOPSO算法伪码 来计算当前考察微粒与其他微粒的距离，并根据距 如图1所示，其中Quality(pet)和Quality(gem)是 离建立若干个邻域，然后根据第2个目标函数选取 指个体历史最优位置的选取和种群全局最优微粒的 邻域最优解。 选取.Mutation是可以选择的，用来对微粒进行变 这类方法中目标函数的顺序是非常重要的，并 异，以保持基本种群的多样性 且这种方法处理的目标函数往往较少 Begin 3.3子群法 T=0 这类方法的基本思想是将整个群体划分为若干 Initizlize population For each particle 个子群，每个子群中进行单目标优化，然后通过子群 Evaluate fitness 间交换信息或将子群信息组合来产生群体的最优 Quality(pkot） 解.比较具有代表性的方法有Parsopoulos等的算 Endfor 法[81及其改进算法VEPS016],张利彪等的算法 Put nodominate solutions into archive Quality(gbe） 文献[8]针对2个优化函数的多目标优化问题 While T <Maxlt 提出了用2个子群体分别进行单目标优化，然后把 For each particle 第1个子群得到的最优解作为第2个子群更新速度 Update position Mutation 的全局最优解，将第2个子群的最优解作为第1个 Evaluate fitness 子群更新速度的全局最优解.文献[16]将此思想进 Update (p) 行了改进，把每一维目标作为一个子群，每个子群进 Endfor Update archive 行单目标优化得到最优解，并将其作为邻接子群更 Quality(gboe） 新速度的全局最优解。 T++ 文献[17]对2个目标函数同时进行优化，根据 Endwhile Report ressults in archive 多目标优化问题的特点将进化群体划分为第1个目 End 标下的全优、第1个目标下的半优、第2个目标下的 图1MOPS0算法伪码 全优、第2个目标下的半优以及2个目标下的全劣 Fig.1 Pseudocode of MOPSO
·380 智能系统学报 第5卷 该类方法中，比较具有代表性的算法有Coello 标的重要程度， 等提出的MOPS02.以及后来研究者对其进行的改 文献[21]对文献[5]中的自适应网格进行了改 进算法[821] 进，加入了非支配解集中微粒密度估计信息，在剔除 MOPSO算法是基于PSO求解多目标优化问题 密度较大网格中微粒的时候，确定了需要剔除的微 中最经典的算法，在这个算法中Coello等首次提出 粒的数量，给出了计算公式.并且该算法在全局最优 了除基本微粒群引入第2个群体来保存生成的非支 解的选取方式上也进行了改进， 配解，并第一次用（超）网格来保存精英解.文献[5] 3.5其他方法 是对文献[2]的改进，将原来固定的（超）网格变为 文献[23]提出了一种新的多目标微粒群算法： 自适应（超）网格，并使用了变异算子来更新种群微 EMOPSO,该算法在MOEA的基础上进行了修改.对 粒和决策变量的范围，变异尺度与进化代数成比例. 非支配解集分布性的保持提出了一种新颖的“hy- 这种方法成为后来研究者们改进的基础，也是研究 per-plane”方法，该方法在文献[5]中超网格的基础 者们对比算法优劣的重要参照 上，针对2个目标函数首先找到每一个目标的最小 文献[19]在文献[2]的基础上借鉴SPEA2算 值A和B,然后将这2点用直线连接，如果需要找到 法[2]中环境选择和配对选择策略，并使用了密度估 n个非支配解，则在此线段上均匀地再选择n-1个 计技术，提高了解的多样性和搜索精度.但该算法中 点，接着在这n-1个点上作直线AB的垂直线，非支 有3个群体，计算量较大 配解中距离此垂直线最近的点被选中，其余各点被 文献[20]在文献[2]的基础上对算法进行了2 删除.此算法为了避免早熟收敛而加入了扰动因子， 方面的改进：1)算法迭代到一定次数时对某个重要 随着迭代次数的增加，扰动因子逐渐减小.此算法对 目标进行单目标优化，以此来解决MOPS0中出现 约束处理方法以及参数自适应调整等方面都进行了 的难以找到边界点的问题；2)对超出边界的位置变 研究 量用一个随机数来取代.这2方面的改进主要提高 对于上述所分析的MOPSO算法及其特征如表 了Pareto解集的分布性，但要求事先知道各优化目 1所示， 表1经典MOPS0算法及其特征 Table 1 Characteristics of classic MOPSO 算 法 例子 archive 修剪archive 变异算子 &n选取 Parsopoulos等 无 无 单目标 聚集法 Baumgarther等u 无 无 单目标 张利彪等 无 无 评估选取 Hu和Eberhart 无 无 单目标 排序法 Hu和Eberhart例 有 单目标 Parsopoulos等 无 无 单目标 子群法 Parsopoulos等a 有 无 单目标 张利彪等 有 Pulido等 无 子群最优解交换 Coello等四 有 (超)网格 有 网格中微粒密度 Coello等 有 自证应网格 有 网格中微粒密度 基于Pareto方法 熊盛武等 有 密度和优劣信息 无 纶盘赌 Chamaani等 网格 有 网格和单目标 杨俊杰等2 有 自证应网格 无 密度和所支配的微粒个数 其他方法 Pulido等 有 hyper-plane 有 4多目标微粒群算法研究热点 对MOPS0算法的研究一般围绕以下研究热点进 行：如何选择非支配解、如何别除archive集中的个 用PS0解决多目标优化问题往往借鉴多目标 体以保持其良好的分布性、如何保持解集多样性和 进化算法中的成功经验，但MOPS0既不同于 hodt Pbent如何选取等 MOEA,又不同于用PS0解决单目标优化问题，当前
第5期 王艳，等：多目标微粒群优化算法综述 381· 4.1非支配解的选择 程度，在对archive集进行修剪时，拥挤距离大的微 对于这个问题的研究涉及到传统Pareto支配的 粒被保留下来，拥挤距离小的微粒被删除。 概念及后来研究者们对其发起的挑战.现有的大多 5)密度熵.这类方法具有一定的特点，但在 数研究都是基于传统Pareto支配机制的，即个体支 MOPSO中并不多见.其基本思想就是定义一个影响 配机制.2002年，Laumanns和Deb等提出e-支配概 函数来衡量archive集中每2个微粒间的相似程度， 念4后，其思想被借鉴与改进，2003年Mostaghim 而archive中微粒的密度是周围微粒对其影响因子 等[2将其引入到M0PS0算法中.8-支配是一种基 的聚集.当每个微粒的密度熵确定后，找出微粒中密 于格子的支配机制，格子的边长为ε，所以ε决定格 度最大的进行删除.这类方法中archive集更新时计 子的数目和大小.每个格子内只允许有1个解，这样 算复杂度为O(MWN2),M为子目标个数，N为rchive 支配的概念由原来个体间的比较转化为格子间的此 集大小 较，后来的研究中人们在选取非支配解时有些采用 6)聚类技术.这类修剪archive集的方法是借鉴 或改进了ε-支配的概念.文献[26]为了保特解集良 于多目标进化算法的一种技术，其基本思想是在算 好的分布性，针对原有ε-支配可能会丢失边界点的 法的每一次迭代过程中，通过聚类方法将整个r 情况提出了强ε-支配概念，在原有ε-支配概念的基 chive集中的非支配解分成若干个聚类，当聚类的个 础上又加人了个体支配的概念， 数超过一定数量时将距离最近的2个聚类合并，将 4.2 archive集的修剪 合并后的中心点作为新类的位置， 当前MOPS0算法中绝大多数都用到了容量受 4.3保持解集多样性 限的archive集来保存精英解，所以一般要对archive PS0算法最突出的一个特点就是收敛速度快， 集进行修剪，剔除掉一部分非支配解，archive集中 但这个特点同时也带来了算法早熟收敛的问题.为 的结果就是将来要输出的解，所以在剔除的过程中 了增加解的多样性，避免早熟收敛，将PS0应用于 要考虑到多目标优化问题的特点.研究者们一般在 解决多目标优化问题时往往借鉴多目标进化算法中 这个阶段考虑较多的是如何剔除archive集中的个 的变异算子，有的MOPS0算法对微粒进行变异的 体，保持解集良好的分布性.通常采用的方法有：随 同时对决策变量的范围进行变异，有的研究采用对 机选择1、小生镜技术29、网格技术25,72、拥挤 “飞”出可行域的微粒进行重新初始化的方法来保 距离039)、密度熵4、聚类技术3,356等。 持非支配解集中解的多样性， 1)随机选择.这类方法的基本思想是将算法迭 文献[5]提出了一种使用变异因子来更新基本 代过程中产生的非支配解存放于archive集中，当非 种群中微粒和决策变量范围的方法.该方法在搜索 支配解的个数超过rchive的容量时随机地删除ar 开始时对所有微粒进行变异，随着迭代次数的进行， chive集中的部分个体.这种修剪方法简单，容易实 种群中变异的微粒数量迅速下降，对每个决策变量 现，但没有充分考虑解集的分布性。 范围也采用同样操作.这样，算法可以有一个很强的 2)小生镜技术.这类方法一般通过小生镜技术 搜索能力，随着迭代次数的增加，变异算子的作用逐 给archive集中的非支配解分配适应度值，聚集程度 渐减小，从而避免了算法早熟.文献[32]也采用了 越大的微粒适应度越小.当非支配解个数超出a 同样的方法来保持解的多样性。 chive集的容量时，则删除其中适应度最小的部分个 文献[28,31]使用了小概率随机变异的方法来 体.这种修剪方法可以提高解集的分布性，但需要小 保持解集的多样性，这类方法的基本思想是在基本 生镜半径的先验信息，计算复杂度较大， 种群每次迭代的过程中随机选择（或从被支配解中 3)网格技术.现有的MOPS0算法很大一部分 选)很少一部分（例如变异概率为5%）微粒进行变 是在Coello等的MOPS0算法s]基础上改进的，而 异，以增强算法的全局搜索能力. 这个算法就是使用网格来保存非支配解的，所以现 文献[20]对超出边界的微粒不用传统方法中 有很多算法都采用这种方法来保存和修剪archive 将其拉至边界的处理方式，而是用一个可行域内的 集.这类方法的基本思想就是当非支配解个数大于 随机数将其替代，这样以增加解的多样性， archive容量时，根据网格中微粒的数量来决定删除 4.4pct和g的选取 哪些微粒 在PS0算法中，微粒是在种群全局最优位置 4)拥挤距离.近年来使用这类方法修剪archive g及个体历史最优位置pe的指导下“飞行”的.将 集的算法越来越多.这类方法的基本思想就是通过 PS0算法应用于解决多目标优化问题时，每次迭代 archive集中个体的拥挤距离来判断解之间的疏密 不再是仅仅产生一个单个的P值和ga值，而是