【学术论文】多目标微粒群优化算法综述

第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值，而是

.382 智能系统学报 第5卷 一组非支配解，如何选择合适的p和g来指导 数目标时不会出现的问题就会凸现出来，空间复杂 种群中微粒的“飞行”就显得非常重要了. 度、时间复杂度以及选择压力等都将是需要重点考 通常对于pket的选取一般都基于Pareto支配概 虑的问题.如何用PS0解决高维多目标优化问题将 念，新产生的p与原来的pt进行比较，选择非支 是研究者们未来一段时间研究的内容之一 配者作为算法迭代中的P,若二者不存在支配关 2)MOPSO算法自适应参数的选择.现在MOP- 系，则随机选择其中之一即可.但也有算法根据所支 S0算法对处理单目标优化问题的PS0算法中的参 配的群体中微粒的个数来选择3] 数没有作太大调整，但多目标优化问题与单目标优 ga的选取是MOPS0算法设计中的关键，gb 化问题的特征相差较大，如何根据多目标优化问题 的选取在很大程度上与archive集的修剪及更新方 自身的特点来自适应调整MOPSO参数，这方面的 式相关.get选取最简单最直接的方法就是从ar 研究已经开始，估计将会成为今后一段时间研究的 chive集中随机选取一个微粒作为基本种群更新的 另一个热点 全局最优解7,4，切.文献[28]采用轮盘赌概率方法 3)有效的算法停止准则.现有的MOPS0算法 从archive中选取精英微粒作为g,文献[30]通过 中，绝大多数算法都是通过预先设置迭代次数来停 随机从archive中选取2个微粒，从多个目标函数中 止算法，因为算法进化到哪一代就达到最优往往是 随机选取1个目标进行比较的方法来选取gt·张 无法判断的.在单目标PS0算法中，当gm在一定代 利彪等4]使用最优解评估选取的方式来选择种群 数内不再变化就可以认为算法已经收敛到了最优 更新的g,文献[38]也使用了这种方法 解，可以停止迭代.但这种策略是不能直接应用于 现有MOPSO算法中，gbet的选取除了随机选择 MOPS0,因为在算法的执行过程中很少会出现这种 外，通过密度信息来进行选择的也较多.文献[2,5] 情况，即使有部分解与上一代相同，但多少个解相同 使用（超）网格中微粒的密度信息，密度小者优先的 就能说明算法已经收敛于Pareto front,至今还没有 方法来选取g,后来在其算法基础上进行改进的 这方面的证明 一些算法一般沿用了这种方式，或对其稍作调 整2 参考文献： 还有其他的一些选取g的方法.文献[26]使用 [1]MOORE J,CHAPMAN R.Application of particle swarm to 了一种极值变异的方法来选择g,首先从archive中 multi-objective optimization[R].Aubur,USA:Depart- 随机选择一个非支配解，然后将此解与当前g比较， ment of Computer Science and Software Engineering,Au 较好者作为此次迭代的g,若两者一样好，则根据极 burn University,1999. 值变异概率来决定get是否需要重新从archive中随机 [2]COELLO COELLO C A,LECHUGA M S.MOPSO:a pro- 选择.文献[35]将距离当前微粒最近的archive集中的 posal for multiple objective particle swarm optimization 非支配解作为更新群体所用的g [C]//Congress on Evolutionary Computation(CEC2002). Honolulu,USA,2002,2:1051-1056. 总结与展望 [3]RAY T,KANG T,CHYE S K.An evolutionary algorithm for constrained optimization[C]//Proceedings of the Genet- 本文首先简要介绍了进化多目标优化及多目标 ic and Evolutionary Computation Conference.Las Vegas, 微粒群优化研究概况，然后根据对多个优化目标处 USA,2000:771-777. 理方式以及种群最优解选取方式，将多目标微粒群 [4]REYES-SIERRA M,COELLO COEELO C A.Multi-objec- 算法大致分为聚集函数法、基于目标函数排序法、子 tive particle swarm optimizers:a survey of the state-op-the- 群法、基于Pareto支配算法和其他方法，并对上述各 art [J].International Joumal of Computational Intelligence 类算法的基本思想进行了分析，对各类算法中具有 Research,2006,2(3):287-308. 代表性的算法进行了详细介绍.最后对当前多目标 [5]COELLO COELLO C A.PULIDO G T,LECHUGA M S. Handling multiple objectives with particle swarm optimiza- 微粒群算法的4个研究热点进行了讨论.虽然多目 tion[J].IEEE Transactions on Evolutionary Computation, 标微粒群算法从出现至今不足10年，但其发展是非 2004,8(3):256-279. 常迅猛的，在今后的研究中以下几个方向应该引起 [6]COELLO COELLO C A,PULIDO G T.Using clustering 研究者们的重视. techniques to improve the performance of a multi-objective 1)如何用PS0算法处理高维(m>5)多目标 particle swarm optimizer[J].Lecture Notes in Computer 优化问题.对于高维多目标优化问题想要找到一组 Science,2004,3102:225-237. 合适的Pareto最优解是很困难的，许多在处理低维 [7]CAGNINA L.ESQUIVEL S,COELLO COELLO C A.A

第5期 王艳，等：多目标微粒群优化算法综述 ·383· particle swarm optimizer for multi-objective optimization 237. [J].Joumal of Computer Science Technology,2005,5 [19]熊盛武，刘麟，王琼，等.改进的多目标粒子群算法[J] (4):204-210. 武汉大学学报：理学版，2005,51(3)：308312. [8]PARSOPOULOS K E,VRAHATIS M N.Particle swarm op- XIONG Shengwu,LIU Lin,WANG Qiong,et al.Im- timization method in multiobjective problems[C]//Proceed- proved multi-objective particle swarm algorithm[J].Wu- ings of ACM Symposium on Applied Computing SAC han University Joumal:Natural Science Edition,2005,51 2002).Madrid,Spain,2002:603607. (3):308-312. 9]HU Xiaohui,EBERHART R C.SHI Yuhui.Particle swarm [20]CHAMAANI S,MIRTAHERI S A.TESHNEHLAB M,et with extended memory for multiobjective optimization[C] al.Modified multi-objective particle swarm optimization for IEEE Swarm Intelligence Symposium.Indianapolis,USA, electromagnetic absorber design[J].Progress in Electro- 2003:193-197. magnetics Research,2008,79:353-366. 「10]郑友莲，樊俊青.多目标粒子群优化算法研究[J].湖北 [21]杨俊杰，周建中，方仍存，等.基于自适应网格的多目标 大学学报：自然科学版，2008,30(4)：351-355. 粒子群优化算法[J].系统仿真学报，2008,20(21)： ZHENG Youlian,FAN Junging.Study on multi-objective 5843-5847. particle swarm optimization algorithm[J].Journal of Hubei YANG Junjie,ZHOU Jianzhong,FANG Rengcun,et al. University:Natural Science,2008,30(4):351-355. Multi-objective particle swarm optimization based on adap- [11]曾建潮，介婧，崔志华.微粒群算法[M].北京：科学出 tive grid algorithms [J].Joural of System Simulation, 版社，2004：9-13. 2008,20(21):5843-5847. [12]郑金华.多目标进化算法及其应用[M].北京：科学出 [22]ZITZLER E,LAUMANNS M,THIELE L.SPEA2 impro- 版社，2007：910. ving the strength Pareto evolutionary algorithm[R].Zur- [13]BAUMGARTNER U,MAGELE Ch,RENHART W.Pa- ich,Swiss:ETH Zurich,2001. reto optimality and particle swarm optimization[J].IEEE [23 PULIDO G T,COELLO COELLO C A,SANTANA- Transactions on Magnetics,2004,40(2):1172-1175. QUINTERO L V.EMOPSO:a multi-objective particle [14]张利彪，周春光，马铭，等.基于粒子群算法求解多目标 swarm optimizer with emphasis on efficiency C]//Pro- 优化问题[J].计算机研究与发展，2004,41(7)：1286- ceedings of 4th International Evolutionary Multi-criterion 1291」 Optimization.Matsushima,Japan,2007:272-285. ZHANG Libiao,ZHOU Chunguang,MA Ming,et al.So- [24]LAUMANNS M,THIELE L,DEB K,et al.Combining lutions of multi-objective optimization problems based on convergence and diversity in evolutionary multi-objective particle swarm optimization[J].Journal of Computer Re- optimization[J].Evolutionary Computation,2002,10 search and Development,2004,41(7):1286-1291. (3):263-282. [15]HU Xiaohui,EBERHART R C.Multiobjective optimiza- [25 MOSTAGHIM S,TEICH J.The role of dominance in tion using dynamic neighborhood particle swarm optimiza- multi-objective particle swarm optimization methods[C]// tion[C]//Proceedings of the 2002 Congress on Evolution- Proceedings of the 2003 IEEE Swarm Intelligence Sympo- ary Computation.Honolulu,USA,2002:1677-1681. sium.Indianapolis,USA,2003:26-33. [16]PARSOPOULOS K E,TASOULIS D K,VRAHATIS M N. [26]蒋浩，郑金华，陈良军.一种求解多目标优化问题的粒 Multiobjective optimization using parallel vector evaluated 子群算法[J].模式识别与人工智能，2007,20(5)： particle swarm optimization[C]//Proceedings of the IAST. 606610. ED International Conference on Artificial Intelligence and JIANG Hao,ZHENG Jinhua,CHEN Liangjun.A particle Applications(AIA2004).Innsbruck,Austria,2004:823- swarm algorithm for multi-objective problem[J].Pattern 828. Recognition and Artificial Intelligence,2007,20 (5 ) [17]张利彪，周春光，刘小华，等.求解多目标优化问题的一 606610. 种多子群体进化算法[J].控制与决策，2007,22(11)： [27]金欣磊，马龙华，刘波，等.基于动态交换策略的快速多 1313-1320. 目标粒子群优化算法研究[J].电路与系统学报，2007， ZHANG Libiao,ZHOU Chunguang,LIU Xiaohua,et al. 12(2):78-82. A multiple subswarms evolutionary algorithm for multi-ob- JIN Xinlei,MA Longhua,LIU Bo,et al.A fast multi- jective optimization problems[J].Control and Decision, objective particle swarm optimization based on dynamic ex- 2007,22(11):1313-1320. change strategy J].Joumal of Circuits and Systems, [18]PULIDO G T,COELLOCOELLO C A.Using clustering 2007,12(2):7882. techniques to improve the performance of a particle swarm [28]李宁，邹形，孙德宝，等。基于粒子群的多目标优化算法 optimizer[C]//Proceedings of the Genetic and Evolution- [J].计算机工程与应用，2005,23：4346. ary Computation Conference.Seattle,USA,2004:225- LI Ning,ZOU Tong,SUN Debao,et al.Multi-objective

.384 智能系统学报 第5卷 optimization utilizing particle swarm[J].Computer Engi- SUN Xiaoqiang,ZHANG Qiuming.A particle swarm opti- neering and Applications,2005,23:43-46. mization method for multi-objective optimization[J].Com- [29]SALAZAR-LECHUGA M,ROWE J E.Particle swarm op- puter Engineering and Applications,2006,18:40-42. timization and fitness sharing to solve multi-objective opti- [36 ]JANSON S,MERKLE D.A new multi-objective particle mization problems[C]//Proceedings of Congress on Evolu- swarm optimization using clustering applied to automated tionary Computation.Edinburgh,UK,2005:1204-1211. docking[C]//Proceedings of Hybrid Metaheuristics.Bar- 「30]王小刚，李明杰，王福利，等，一种新的多目标粒子群算 celona,Spain,2005:128-141. 法的研究与应用[J].东北大学学报：自然科学版， [37]王俊年，刘建勋，陈湘州.一种多目标微粒群算法及其 2008,29(10):1377-1380. 收敛性分析[J].计算机工程与应用，2007,43(22)： WANG Xiaogang,LI Mingjie,WANG Fuli,et al.Study 53-55. on a new MOPSO and its applications [J].Joumal of WANG Junnian,LIU Jianxun,CHEN Xiangzhou.Multi- Northeaster University:Natural Science,2008,29(10): objective particle swarm optimization and its convergence 1377-1380 analysis[J].Computer Engineering and Applications, [31]李中凯，谭建荣，冯毅雄，等.基于拥挤距离排序的多目 2007,43(22):5355. 标粒子群优化算法及其应用[J].计算机基础制造系 [38]胡德峰，张步涵，姚建光.基于改进粒子群算法的多目 统，2008,14(7)：1329-1336. 标最优潮流计算[J].电力系统及其自动化学报，2007， LI Zhongkai,TAN Jianrong,FENG Yixiong,et al.Multi- 19(3):51-57. objective particle swarm optimization algorithm based on HU Defeng,ZHANG Buhan,YAO Jianguang.Improved crowding distance sorting and its application[J].Computer particle swarm optimization algorithm for multi-objective Integrated Manufacturing Systems,2008,14(7):1329- optimal power flow[J].Proceedings of CSU-EPSA,2007, 1336. 19(3):51-57. [32]王辉，钱锋.基于拥挤度与变异的动态微粒群多目标优 作者简介： 化算法[J].控制与决策，2008,23(11)：1238-1242. 王艳，女，1975年生，博士研究 WANG Hui,QIAN Feng.Improved PSO-based multi- 生，讲师.主要研究方向为智能计算、多 objective optimization by crowding with mutation and parti- 目标优化等，发表学术论文近10篇 cle swarm optimization dynamic changing[J].Control and Decision,2008,23(11):1238-1242. [33]王洪刚，马良，李高雅.多目标微粒群优化算法[J].计 算机工程与应用，2008,44(34)：6466. WANG Honggang,MA Liang,LI Gaoya.Multi-objective 曾建潮，男，1963年生，教授、博士生 particle swarm optimization[J].Computer Engineering and 导师、博士，中国自动化学会系统仿其专 Applications,2008,44(34):6466. 业委员会副主任委员，中国计算机学会 [34]宋武，郑金华.基于密度熵的多目标粒子群算法[J].计 Petri网专业委员会委员，山西省系统工程 算机工程与应用，2007,43(26)：4144. 学会、山西省自动化学会和计算机学会副 SONG Wu,ZHENG Jinhua.MOPSO algorithm based on 理事长，山西省自动化学会学术委员会主 density entropy[J].Computer Engineering and Applica- 任.主要研究方向为智能计算、复杂系统建模与仿真等.承担或 ions,2007,43(26):4144. 完成包括国家自然科学基金、国家科技攻关项目等30余项，获 [35]孙小强，张求明.一种基于粒子群优化的多目标优化算 山西省科技进步奖、自然科学奖5项.发表学术论文300余篇， 法[J].计算机工程与应用，2006,18：4042. 被SC,E检索100余篇，出版专著3部