基于奖惩机制的协同多目标优化算法

伍大清，邵 明，李 悛，李 康

（1.南华大学计算机科学与技术学院，湖南 衡阳421001；2.东华大学旭日工商管理学院，上海200051；3.教育部计算智能与信号处理重点实验室，合肥 230039；4.上海工程技术大学管理学院，上海 200051）

基于奖惩机制的协同多目标优化算法

伍大清1，2，3，邵 明4，李 悛1，李 康2

（1.南华大学计算机科学与技术学院，湖南 衡阳421001；2.东华大学旭日工商管理学院，上海200051；3.教育部计算智能与信号处理重点实验室，合肥 230039；4.上海工程技术大学管理学院，上海 200051）

为提高已有多目标优化算法在求解高维复杂多目标优化问题上的解集分布性和收敛性，提出一种新的多目标微粒群优化算法。该算法基于多目标协同框架，将多种群奖惩机制进化算法用于求解分解后的若干单目标优化子问题，采用动态环形的拓扑结构，设计一种新型精英学习策略，获得逼近Pareto前沿的最优解集。通过典型的多目标优化函数进行测试验证，结果表明，与现有多目标优化算法相比，该算法不仅具有较好的收敛性能，而且解集分布性更均匀、覆盖范围更广。

多目标优化算法；协同；精英学习策略；拓扑结构；奖惩机制

DO I：10.3969/j.issn.1000-3428.2015.10.035

1 概述

在科学研究和工程设计中许多优化问题涉及多个目标同时优化，而且这些目标之间彼此冲突、相互制约，通常把这类型问题称为多目标优化问题（Multiobjective Optimization Problem，MOP），多目标优化问题一般情况下几乎找不到使得多个目标同时达到最优的解，通常采用帕累托最优解集平衡多个相互冲突

的目标。近年来，进化多目标优化前沿领域涌现出了不少新的求解思路和算法框架，如粒子群优化、人工免疫系统、分布估计算法、协同进化算法、基于偏好的算法、文化进化算法和基于分解的算法等，越来越多地被引入到进化多目标优化领域［1］，目的在于在多目标空间前端上找到一组分布具有尽可能好的逼近性、宽广性和均匀性帕累托解集。

目前，求解多目标优化问题的方法很多［2］。文献［3］提出的基于最小生成树的多目标进化算法；Eber-hart引入扩展内存存储Pareto最优解［4］，并将其作为群体的领导粒子，通过个体经验和群体经验单向共享信息引导粒子向最优值进化；文献［5］为了保持Pareto解集的分布性，采用了基于支配关系及适应度共享的策略；许多多目标进化算法都是把多目标优化问题当作一个整体来对待，而文献［6］构造了基于分解的多目标进化算法（MOEA/D）框架，在多目标进化算法中引入数学规划中较为成熟的分解策略［2］，算法将逼近整个帕累托前沿面的问题分解为一定数量的单目标优化问题，然后利用进化算法同时求解这些问题。文献［7］提出基于分解的均匀设计的多目标差分算法，文献［8］提出进化多目标优化的混合框架等，结果表明，基于分解的多目标进化算法是一种有效方法［9］，为求解进化多目标优化问题提供了一种新思路［2］。

本文基于合作协同的多目标进化算法框架，将基于奖惩机制以及精英学习策略的进化算法用于求解分解后的若干单目标优化子问题，提出一种基于奖惩机制的协同微粒群多目标优化算法（CCMPSO）。在该算法中，种群被划分成多个子种群分别优化不同的子问题，每个子种群采用环形的拓扑结构，每隔一定周期内动态地重组，以提高种群多样性。同时提出基于奖惩机制的微粒群优化算法速度更新方式，并设计了一种新型精英学习策略，以避免外部存档集陷入局部最优。

2 协同多目标优化算法

2.1 基本原理

基本单目标PSO算法中［10］的粒子仅通过跟踪个体最优和群体最优进行学习，显然，这是一个理想社会条件，而且在搜索的过程中很难平衡勘测与开发这对矛盾。而实际上除了个体最优与群体最优，粒子在运行过程中所处的邻域环境对它的影响非常大，如果对自身起推动（pull）作用的环境粒子进行奖励，对自身起阻碍（push）作用的环境粒子进行惩罚，将有助于粒子在多目标空间前端上快速找到一组分布具有尽可能好的逼近性、宽广性和均匀性帕累托解集。

因此，CCMPSO算法中引进局部邻居粒子N max，在每个小种群中，所有粒子的个体最优粒子所对应的适应度值排序，最大的适应度粒子将被选作N max，N max（t）=argmax｛f（Pbest1），f（Pbest2），…，f（Pbestn）｝。引入奖惩因子r2，判断每一代生成的新个体是否对Pareto解集做贡献，如果产生的新个体能支配外部存档集中的非支配解，则产生r2＞0的奖励因子，加快粒子的飞行速度，提高粒子勘测区域深度的能力；如果产生的新个体未能支配外部存档集中的非支配解，则产生r2＜0惩罚因子，将减缓粒子的飞行速度，提高粒子开发区域广度的能力，如图1所示。

图1 CCMPSO粒子运行过程自适应奖/惩学习过程

2.2 拓扑结构

CCMPSO中的子种群采用环形拓扑结构，为了粒子向周围环境中的不同的粒子学习，充分保持种群的多样性，每隔一定周期，子种群的结构进行重组，每个粒子所在的邻域粒子发生改变。CCMPSO动态种群结构如图2所示，具体过程在文献［11］中有详细的介绍。

图2 CCMPSO动态种群结构

2.3 粒子更新

粒子通过在搜索空间中以一定的速度飞行，粒子的飞行速度基于个体的飞行经验和群体的飞行经验以及环境的飞行经验动态调整，在D维的搜索空间，n个粒子通过竞争与协作来寻找问题的最优解。优化问题的过程可看做粒子不断更新的过程，粒子的速度和位移更新模型如下：

其中：i=1，2，…，n；d=1，2，…，D；r1，r2以及r3是学习因子，是服从U（0，1）分布的随机数，r1+r2+r3= 1；w是惯性系数；t表示迭代次数，χi（t）是第 t次迭代第i个粒子对应的位置向量；νi（t）是第t次迭代第i个粒子对应的速度向量；Pbesti是粒子个体最优；Achiνe是外部共享Pareto解集合，以及Nmax对邻域环境影响的奖惩粒子。参照文献［10］对粒子位置和速度越界进行处理。

显然，粒子速度位移更新模型受到4个部分之间的相互平衡和制约：（1）代表粒子有保持本身原来速度的趋势；（2）代表粒子有向本身历史最佳位置逼近的趋势；（3）反映了粒子受到周围环境邻域粒子的影响；（4）代表粒子间协同合作与知识共享的群体历史经验，有向群体历史最佳位置逼近的趋势。

2.4 精英学习策略

为了防止外部存档库中的粒子陷入局部最优，CCMPSO在外部存档中增加了一个精英学习策略，以增强算法跳出局部最优的能力，该策略通过外部扰动机制来改善搜索未知区域的能力，通过内部扰动机制来增强已知搜索区域的搜索深度，引入该策略，减缓了粒子收敛速度，能够为外部存档库中粒子提供有效信息找到更多的非劣解，获得种群多样性，如式（3）、式（4）所示：

其中，X1，X2为已知搜索区域外部存储库中的自由向量；未知搜索区域的Y1，Y22个新的搜索向量可由公式获得；c1，c2是0～1之间的随机数。外部存档集所有种群共享一个外部存档集，用来存储每次迭代产生的非劣解。如果档案集合中的非劣解数目超过其最大容量时，则需要在档案中筛选具有代表性的个体保留下来，将利用拥挤距离算法［12］来保持解群分布的均匀性，对产生新的非支配解进行择优处理。

2.5 共享外部存档集更新

CCMPSO中所有子种群共享一个外部存档集Achiνe，用来存储每次迭代产生的非劣解。在每次迭代之后进行更新，每个粒子全局最优位置视为非劣解的候选方案被存储在外部存档中，在不同的前沿面保存最终的解群即是算法求解的结果。通常外部存档集一般与种群的规模一致，如果数目超过设定的阈值时，则需要利用文献［13］中的拥挤距离算子将具有代表性的个体保留下来，从而保持解群分布的均匀性，伪代码如下所示：

2.6 算法描述

CCMPSO基于多目标技术，根据多目标优化问题个数将种群划分成多个子种群，利用基于奖惩机制的微粒群优化算法分别对各个子问题进行寻优处理，使用新型精英学习策略对外部存档进行更新，每个子种群在一定的学习周期内重组种群结构，通过共享的外部存档，相互协同合作寻找到分布尽可能好的逼近性、宽广性和均匀性Pareto最优解集合。CCMPSO算法流程如下：

Step1 初始化种群。随机初始化粒子数为N的群体以及对应的适应度，针对多目标问题的目标个

数N，将种群划分成N个子种群，各个粒子所对应的速度，算法终止条件为最大迭代次数T，初始化粒子的个体最优位置Pbest，外部存档集Achiνe以及局部邻居粒子N max，外部存档集初始化空集。

Step2 对种群中所有的粒子采用式（1）、式（2）更新粒子的速度和位置；并对粒子越界速度、位移进行处理。

Step3 计算新粒子的各个目标适应度值，判断是否能支配外部存档中的非支配解，若是则产生奖励因子；否则产生惩罚因子。分别更新 Pbest以及N max。

Step4 执行精英学习策略。

Step5 利用2.5节更新外部存档集，判断外部存档大小是否超过种群规模，若是，则使用拥挤距离更新外部存档。

Step6 迭代计数器累增1，是否能整除拓扑结构重组周期 G，如果是，则执行 Step7；否则执行Step8。

Step7 对所有粒子的拓扑结构进行重组，转Step2。

Step8 迭代次数累增1，判断是否满足算法终止条件。若满足，则执行Step6；否则转Step2。

Step9 输出Pareto最优前沿面，算法结束。

1 本刊辟有论著、专科护理、护理管理、护理教育、基础护理、心理卫生、个案护理、药物与护理、健康教育、社区护理、调查分析、经验交流、海外之窗、护士笔谈等栏目，欢迎广大护理人员踊跃投稿。

3 仿真实验结果与分析

3.1 测试函数

本文的实验部分通过5个不同类型的经典测试问题［14］来验证CCMPSO算法的有效性，表1列出了测试函数的表达式。实验结果与 CMPSO［15］，MOCLPSO［16］进行了比较。所有算法在每个测试函数上的初始种群大小NP均设置为100，算法终止条件均为迭代次数T=1 000，CCMPSO中惯性系数ω=0.729，拓扑结构重组周期G=8，其他算法中的控制参数设置同相应原文献。

表1 测试函数

在实验中，算法性能对比采用通用的2个性能评价标准：

（1）收敛性γ。γ测量算法最终获得的非支配解集Q与理论Pareto最优解的近似解集P*的逼近程度：

其中，di为目标空间中Q的个体i与其相邻个体间

其中，di为Q中的个体i与P*中距离最近个体在目标空间中的欧氏距离；γ的值越小说明算法获得的非支配解Q越接近真实的Pareto前沿，算法收敛性越好［17］。

3.2 参数敏感性分析

参数敏感性分析过程如下：

（1）奖惩机制特性分析

为了检验奖惩机制对粒子寻优的作用，以ZDT3函数为例，分别对粒子速度更新公式中是否包含

第3项环境影响部分进行了测试。

图3为1 000次迭代过程中1个粒子有无受到奖惩粒子影响的进化情况，图3（b）展示了CCMPSO算法中的粒子在进化过程中有明显被初始化的痕迹，是因为算法的多样性保持机制在一定情况下被激活所造成。从粒子进化图看，CCMPSO算法包含奖惩机制的速度更新模型，粒子更具有多样性，不易陷入局部极值。

图3 1 000次迭代过程中1个粒子进化的情况

（2）子种群拓扑结构重组周期G

CCMPSO所涉及的参数子种群拓扑结构重组周期G，以FON、ZDT3为例，结果如表2所示，间隔周期过小，会对粒子飞行造成扰动，所得到的支配解收敛性不足；间隔周期过大，种群多样性缺失容易陷入局部最优解；因此G取值为8。表3给出3种算法独立运行30次，每次迭代1 000次，在不同测试函数上的收敛性、多样性度量平均值和方差，实验数据表明，CCMPSO具有较强的鲁棒性。图4中给出在3个测试函数上的Pareto前沿面，仿真结果表明，结合精英学习策略以及动态拓扑结构重组策略，基于奖惩机制协同框架下的微粒群多目标优化算法CCMPSO，在解群分布的均匀性和宽广性方面明显优于其他算法。

表2 不同重组周期下FON、ZDT3函数多样性、收敛性度量结果

表3 3种算法分别求得5个测试函数评价指标比较

图4 测试函数SCH，ZDT3，ZDT6最优Pareto前沿面

4 结束语

针对现有多目标进化算法在求解高维复杂多目标优化问题时求解精度较差、解集分布不均匀等问题，本文提出一种基于合作协同的多目标进化算法CCMPSO。该算法引进奖惩机制对微粒群多目标进化算法进行综合改进，采用动态环形的拓扑结构以及精英学习策略，有效提升了CCMPSO的收敛性和解集分布性。通过对5个标准测试函数进行实验，结果表明，该算法与现有多种多目标算法相比，不仅具有较好的收敛性能，而且解集分布性也更均匀，覆盖范围更广。

［1］ 沈佳杰，江 红.基于多变异个体的多目标差分进化改进算法［J］.计算机工程，2014，40（5）：203-208，215.

［2］ 侯 薇，董红斌，印桂生.一种改进的基于分解的多目标进化算法［J］.计算机科学，2014，41（2）：114-118.

［3］ 李密青，郑金华.一种多目标进化算法解集分布广度评价方法［J］.计算机学报，2011，34（4）：647-664.

［4］ Coello C，Pulido G T.Handling Multiple Objectives with Particle Swarm Optimization［J］.IEEE Transactions on Evolutionary Computation，2004，8（3）：256-279.

［5］ Salazar-Lechuga M.Particle Swarm Optimization and Fitness Sharing to Solve Multi-objective Optimization Problem s［C］//Proceedings of IEEE CEC’05. Washington D.C.，USA：IEEE Press，2005：1204-1211.

［6］ Zhang Q.MOEA/D：A Multi-objective Evolutio-nary Algorithm Based on Decomposition［J］.IEEE Transactions on Evolutionary Computation，2007，11（6）：712-731.

［7］ Tan Y，Jiao Y，Li H，et al.MOEA/D Uniform Design：A New Version of MOEA/D for Optimization Problem s with M any Objectives［J］.Com puters&Operations Research，2013，40（6）：1648-1660.

［8］ Sindhya K.A Hybrid Framework for Evolutionary Multiobjective Optimization［J］.IEEE Transactions on Evolutionary Computation，2013，17（4）：495-511.

［9］ 薛 羽，庄 毅，顾晶晶，等.自适应离散差分进化算法策略的选择［J］.软件学报，2014，25（5）：984-996.

［10］ 伍大清.基于混合策略自适应学习的并行微粒群优化算法研究［J］.控制与决策，2013，28（7）：1086-1094.

［11］ Wu Daqing.A Dynamic Multistage Hybrid Swarm Intelligence Optimization Algorithm for Function Optimization［J］. Discrete Dynamics in Nature and Society，2012，（2012）.［12］ Said M，Ahamed A.Hybrid Periodic Boundary Condition for Particle Swarm Optimization［J］.IEEE Transations on Antennas and Propagation，2007，55（11）：3251-3256.

［13］ Pratap D K.A Fast and Elitist Multi-objective Genetic Algorithm：NSGA-II［J］.IEEE Transactions on Evolutionary Computation，2002，6（2）：182-197.

［14］ Coello C A，Cortes N C.Solving Multi-objective Optimization Problems Using an Artificial Immune System［J］.Genetic Programming and Evolvable Machines，2005，（6）：163-190.

［15］ Zhan Z H.Multiple Opulations for Multiple Objectives： A Co-evolutionary Technique for Solving Multiobjective Optimization Problem s［J］.IEEE Transactions on Cybernetics，2013，43（2）：445-463.

［16］ Huang V L，Suganthan P N，Liang J J.Comprehensive Learning Particle Swarm Optimizer for Solving Multiobjective Optimization Problem s［J］.International Journal of Intelligent System s，2006，21（2）：209-226.

［17］ 毕晓君.基于自适应差分进化的多目标进化算法［J］.计算机集成制造系统，2012，17（12）：2660-2665.

编辑 索书志

Cooperative Multi-objective Optimization Algorithm Based on Reward and Punishment Mechanism

WU Daqing1，2，3，SHAO Ming4，LI Quan1，LI Kang2
（1.School of Computer Science and Technology，University of South China，Hengyang 421001，China；2.Glorious Sun School of Business and Management，Donghua University，Shanghai200051，China；3.Key Laboratory of Intelligent Computing&Signal Processing，Ministry of Education，Hefei230039，China；4.School of Management，Shanghai University of Engineering Science，Shanghai200051，China）

To improve the convergence and distribution of Multi-objective Evolutionary Algorithm（MOEA）in dealing with large-dimensional Multi-objective Optimization Problem（MOP），a multi-objective particle swarm optimization algorithm based on human disciplinary behavior is proposed.The strategies such as promoting/punishment factor，the elite learning strategy as well as restructuring topology structure strategy with dynamic population in period are introduced in proposed algorithm，to make the algorithm have strong global search ability and good robust performance.Some typical multi-objective optimization functions are tested to verify the algorithm，and simulation results show that，compared with recent other algorithms，the algorithm can ensure good convergence while having uniform distribution and wild coverage area.

multi-objective optimization algorithm；cooperative；elite learning strategy；topology structure；reward and punishment mechanism

伍大清，邵 明，李 悛，等.基于奖惩机制的协同多目标优化算法［J］.计算机工程，2015，41（10）：186-191，198.

英文引用格式：Wu Daqing，Shao Ming，Li Quan，et al.Cooperative Multi-objective Optimization Algorithm Based on Reward and Punishment Mechanism［J］.Computer Engineering，2015，41（10）：186-191，198.

1000-3428（2015）10-0186-06

A

TP301

湖南省教育厅基金资助项目“基于协同演化计算的不确定信息车辆路径问题研究”（13C818）；湖南省衡阳市科技局科技计划基金资助项目“自学习演化计算在智能交通控制中的应用研究”（2013KG63）；教育部人工智能重点实验室基金资助项目“基于冷链云配送模式的车辆路径优化模型及协同控制研究”。

伍大清（1982-），女，讲师、博士，主研方向：多目标智能决策，智能计算；邵 明，副教授、博士；李 悛、李 康，讲师、博士。

2014-08-11

2014-11-26E-mail：dqw-1982@126.com