双尺度协同变异的离散粒子群算法

陶新民，王妍，赵春晖，刘玉

(哈尔滨工程大学信息与通信工程学院，黑龙江哈尔滨150001)

粒子群优化(particle swarmoptimization，PSO)是Kennedy于1995年提出的一种群体智能优化方法，具有概念简单、调节参数少及全局收敛能力强等优势，得到了学术界的认可［1-2］.目前在工程设计和工业生产优化等领域得到了成功的应用.PSO算法适合求解非线性连续优化问题，为了将其用于解决离散问题，Kennedy于1997年提出解决0-1规划问题的离散粒子群优化算法(discrete particle swarmoptimization algorithm，DPSO)［3-5］.

然而传统离散粒子群算法具有收敛精度低等问题［6-7］，因此，国内外学者提出各种方法对其性能进行改进.主要改进有以下3个方向:1)通过设置自适应的控制参数等手段来影响粒子的移动轨迹，改进算法的性能.如文献［8］采用惯性权重线性下降法，使算法在进化初期搜索较大的解空间，后期在较小的区域精细搜索.文献［9］设计了自适应的最大速度阈值参数，使粒子在搜索初期倾向于全局搜索，后期倾向于当前最优解附近的局部搜索，有效实现粒子全局和局部搜索性能的平衡(velocity change discrete particle swarmoptimization，VCDPSO).2)通过增强粒子摆脱局部极小解的能力改进算法的性能.如文献［10］通过对惯性因子采用自适应扰动机制来增强粒子群跳出局部最优的能力(introducingdynamic diversity into a discrete particle swarmoptimization，DDPSO).3)通过增加粒子群多样性，能摆脱群体陷入局部极小的可能，从而提高了搜索质量［11-12］.然而上述改进算法都是基于连续PSO算法易陷入局部极小值为出发点提出的，事实上DPSO算法的进化过程与连续PSO算法截然不同，上述连续状态下的相关改进算法并不适合离散粒子群算法［13］.文献［14］通过对DPSO中粒子的速度变化进行分析，提出一种双速度状态跟踪的DPSO算法(novel binary particle swarmoptimization，NDPSO)，消除了原有算法对参数过于敏感的缺点，但由于算法增加了粒子状态改变的随机性，其性能受到影响.文献［15］在分析DSPO算法粒子状态转移情况后，提出一种不同的离散化方法(Modifying diversity particle swarmoptimization，MDPSO)，降低了粒子在最优解附近的发散性，然而也使算法易陷入局部最优.因此如何在提高算法局部搜索能力的同时，不影响算法逃出局部最优解的能力值得深入研究.

本文在分析了传统DPSO算法粒子状态转移情况的基础上，提出一种双尺度协同变异的离散粒子群算法(discrete particle swarmoptimization based on double-scale cooperation mutation，DSVMDPSO).该算法对当前最优粒子进行粗细2种尺度的速度变异，这样在提高算法局部开采能力的同时，保持了算法勘探能力，使其能有效逃出局部最优解的同时提高了解的精度.

1 离散粒子群算法描述

实值粒子群优化算法将优化问题的每个潜在解看作搜索空间的一个“粒子”，粒子的适应值取决于优化目标函数的值.每个粒子在搜索时根据自身的历史最好点和群体内其他粒子的最好点进行状态变化.为处理离散型优化问题，Kennedy对实值粒子群算法进行修正，提出了二进制粒子群算法［3］.

设种群中有L个粒子，N维离散空间中，粒子i在时刻t的速度、位置、个体最好位置和全局最好位置分别用)表示，那么粒子i速度和位置的各维分量迭代公式［3］为

式中:i=1，2，…，L;j∈{1，2，…，N}表示粒子编码中分量的维数;r1j(t)和r2j(t)是(0，1)上均匀分布的随机数;w、c1和 c2是权重及加速系数;ρ～U［0，1］是(0，1)区间上均匀分布的随机变量;sig()表示sigmoid函数，本文取sig(x)=.文献［7］规定粒子的最大速度|vmax|=4，这样 0.018≤sig(vij(t+1))≤0.982.

由文献［14-15］对粒子运动轨迹的分析可知，在个体极值和全局极值不相等时，粒子会在2个极值间来回震荡，当c1和c2相等时粒子趋于随机搜索，勘探能力较强，直到2个极值趋于一致;在2个极值相等且粒子不等于这2个极值的情况下，粒子会呈现向极值收敛的趋势，逐渐向2个极值解逼近，勘探能力同样较强;而当粒子收敛到全局最优解时，如果w＞1时，粒子会随着迭代而保持原有的状态，变异的可能性降低，趋于陷入局部极值解;如果w≤1，则随着迭代次数的增加，w会使当前粒子的速度趋于零，即使得当前粒子产生变异的概率趋近于0.5，很快发散出去，无法进行有效的局部搜索，如图1所示.因此提高算法在最优解附近的局部搜索能力，同时保持算法逃逸局部最优解的能力是传统DPSO算法需要解决的首要问题.

图1 DPSO算法在最优解附近进化示意Fig.1 Evolution of DPSO near optima

2 双尺度协同变异的离散粒子群算法

我们知道变异操作能帮助算法逃出局部最优解［18-20］，但根据DPSO算法的产生机理可知，在进化后期，最优解往往存在于当前最优解周围，大尺度变异虽然有利于算法逃出局部最优解，但无法保证逃逸后的新位置位于全局最优解附近，在重新迭代时，因迭代次数的限制而无法收敛到全局最优解.小尺度变异虽然有利于进行局部搜索，但又易使算法陷入局部极值解.因此如何设计变异尺度是协调离散粒子群算法勘探和开采能力的关键.

2.1 双尺度协同变异算子

设粗尺度变异算子中包括的尺度个数为M，初始值可随机设定为速度取值区间的随机值:

随迭代数增加，粗尺度变异算子按如下方式调整:

Re是取实部函数，K为当前进化代数，W是解空间的宽度，这里离散微粒群算法的速度范围为［-5，5］，因此W取值为10.D的取值控制着震荡的频率，根据实验统计设置为

设细尺度变异算子中包括的尺度个数为N，细尺度变异算子的初始值可随机设定为W/4:

随迭代数增加，细尺度变异算子按如下方式调整:

式中:C的取值与求解精度有关，控制着变异算子下降的速度，其值越小下降的越缓慢，这里取值为2.

如图2为双尺度协同变异算子随迭代次数的变化，通过双尺度协同变异算子能实现速度取值空间的覆盖，如同粗细不同的显微镜，粗尺度变异算子好像一个粗镜头，能帮助算法快速定位到最优解区域，具有一定的空间勘探能力;小尺度如同细的显微镜，对找到的目标进行细致观察，在进化后期实现最优解附近的精确搜索，具有较强的开采能力.

图2 双尺度协同变异算子随迭代数变化曲线Fig.2 The curves of double-scale cooperation mutation operator with Iterations＇increasing

2.2 惯性权重参数设定

2.3 MSCMPSO 算法流程

1)算法的参数初始化设定;

2)按照离散粒子群算法式(1)进化;

3)根据式(2)进行粒子状态的计算;

4)计算当前最优解及每个粒子的个体极值解;

5)根据式(3)～(7)计算双尺度协同变异算子值;

6)对当前最优解的速度进行粗细2种尺度的变异，根据式(2)计算每一个粒子状态，比较所有变异粒子的适应值，如果最好的适应值优于当前最优解，则将其替换为为当前新的最优解;

7)循环直到终止条件.

3 算法优化性能分析

设算法的变异尺度M、N都为5，选择DeJong评测函数进行优化，函数维度为20，每一维变量的编码为20，这样一个粒子的整个维度为400.

算法进行多尺度速度变异，计算每一个尺度速度变异的粒子与原有粒子编码的海明距离的平均值，取迭代5次的结果如图3所示.从图中可以看出每次迭代的变异都是在不同大小的海明距离下进行的，这样就保证了粒子会以不同大小步长在粒子取值空间进行搜索，这样既保证了算法局部开采能力，同时也保证了算法逃逸局部极值解的能力.

图3 与原有粒子编码海明距离的平均值Fig.3 A mean of Hamming distance

4 实验结果及分析

4.1 测试数据及实验设计

为了分析本文算法的优化性能，选择文献［16］和文献［17］的5个Benchmark函数问题进行数值实验，并与 DPSO 和其改进算法 DDPSO［10］/NDPSO［14］/MDPSO［15］及 VCDPSO［9］进行对比实验.所有算法中 w在［0.9，0.4］随代数线性递减;c1、c2均为1，DDPSO 的扰动参数 Pv=0.12，VCDPSO 的最大速度限制值的内部协调参数为 1.2，本文算法M=5，N=5，种群规模均为20，函数维度设置为20，每一位变量的编码长度为20，每次运行2 000代，对每一个函数独立运行30次.

4.2 基于单模态函数优化性能对比实验

图4反映了不同 DPSO算法分别对 Delong、Rosenbrak函数进行优化时适应度值随迭代次数的变化图.针对单模态函数优化问题的实验结果.从图4(a)可以看出，对于DeJong函数本文算法随迭代次数迅速向着最优解区域靠近.对于复杂的单模态Rosenbrock函数山谷仅给算法提供很少的信息，使传统DPSO算法很难在短时间内辨别搜索方向，易陷入局部最优.而图4(b)表明本文算法采用双尺度速度变异能够有效地逃逸出局部极值点，使得算法能在短时间找到正确的搜索方向，下降速度较快.同时算法后期，由于细尺度变异使得算法在最优解附近进行更加详尽的搜索，提高了解的精度.

表1显示了单模态函数问题的对比实验结果，从各算法的最优值和最差值的实验结果可以看出，本文算法在所有函数上均由于其他算法，在Delong函数和Rosenbrock函数上最优解搜索成功率达100%、94%.对于复杂的Rosenbrock函数问题，各个算法单次结果存在很大差异，由于函数的特殊性质以及随机变异的引入，反而降低了DDPSO算法的搜索性能.VCDPSO由于采用了数值为1的权重系数以及变化速度极值的方式，因此经过一定的迭代后也逃出了局部极小解.而本文提出的DSVMDPSO算法能够在算法初始阶段就通过粗尺度变异定位到全局最优解区域，找到进化方向且通过细尺度速度变异进行局部精确解搜索.

图4 不同DPSO算法对Delong和Rosenbrock函数优化性能对比Fig.4 Comparison of different DPSO on Delong and Rosenbrock function

表1 DSVMDPSO和其他DPSO算法在单模态Benchmark问题上的数值对比Table 1 Comparison of the results on single-mode Benchmark function

4.3 基于多模态函数优化性能对比实验

多模态函数对比实验结果如图5所示.对于多模态Griewank函数，本文DSVMDPSO算法能够在开始阶段寻到全局最优解区域，其全局搜索能力明显优于其他算法.多模态Rastrigrin函数是一个典型的用来测试算法全局搜索性能的函数，从图5(b)和表2可以看出，虽然本文算法没有在有限次的运行中都能找到近似全局最优解0，但是只要给予足够长的迭代次数，算法总能逃出局部极小点找到全局最优解.图5(c)为20维Ackley函数的运行结果，DSVMDPSO算法同样能在算法初期寻到全局最优解区域，然后利用DPSO进化和细尺度速度变异算子实现最优解附近的局部精确解搜索.从表2的结果可以看出，本文算法大大改善了算法全局解寻优能力及提高了解的精度，无论是传统DPSO还是其他改进算法都不具备良好的稳定性，而本文算法相对于其他算法，其稳定性大大提高.

图5 不同DPSO算法对Griewank、Rastrigrin和Ackley函数优化性能对比Fig.5 Comparison of different DPSO on Griewank，Rastrigrin and Ack ley function

表2 DSVMDPSO和其他DPSO算法在多模态Benchmark问题上的数值对比Table 2 Comparison of the results on multimode Benchmark function

5 结论

本文提出了一种双尺度协同变异的离散粒子群算法，结合实验得到如下结论:

1)针对传统离散粒子群算法的状态转移过程中存在最优解区域局部搜索能力差的不足，提出一个双尺度速度变异算子，该算子可以有效实现在最优解附近精确的局部搜索，同时在算法初期利用粗尺度速度变异可以使粒子群进行发散式的全局搜索，从而快速定位到全局最优解区域，在算法后期，由于粗尺度速度变异的震荡性质在细尺度速度变异进行局部精确解搜索的同时，可帮助算法逃逸出局部极小解，实现算法勘探及开采能力的有机协调.

2)采用本文算法及其改进算法，对5个经典Benchmark函数进行优化，实验结果表明本文算法在全局搜索性能及最优解精度方面都有显著提高.

需要指出的是，本文尚未考虑各种参数对算法性能的影响，这也是本课题下一阶段研究的重点.

［1］POLIR，KENNEDY J，BLACKWELL T.Particle swarmoptimization:an overview［J］.SwarmIntell，2007，1(1):33-57.

［2］陶新民，徐晶.改进的多种群协同进化微粒群优化算法［J］.控制与决策，2009，24(9):1406-1411.TAO Xinmin，XU Jing.Multi-species cooperative particle swarmoptimization algorithm［J］.Control and Decision，2009，24(9):1406-1411.

［3］KENNEDY J，EBERHART R C.A discrete binary version of the particle swarmalgorithm［C］//Proc of the World Multiconference on Systemics，Cybemetics and Informatics.Orlando，1997:4104-4109.

［4］PAN Q K，TASGETIREN mF，LIANG Y C.A discrete particle swarmoptimization algorithmfor the no-wait flowshopscheduling problem［J］.Computers＆ Operations Research，2008，35(9):2807-2839.

［5］LIU Y，GU X P.Skeleton-network reconfiguration based on topological characteristics of scale-free networks and discrete particle swarmoptimization［J］.IEEE Transactions on Power Systems，2007，22(3):1267-1274.

［6］潘全科，王凌，高亮.离散微粒群优化算法的研究进展［J］.控制与决策，2009，24(10):1441-1449.PAN Quanke，WANG Ling，GAO Liang.The state-of-art of discrete particle swarmoptimization algorithms［J］.Control and Decision，2009，24(10):1441-1449.

［7］张国富，蒋建国，夏娜.基于离散粒子群算法求解复杂联盟生成问题［J］.电子学报，2007，35(2):323-327.ZHANGGuofu，JIANG Jianguo，XIA Na.Solutions of complicated coalition generation based on discrete particle swarmoptimization［J］.Acta Electronica Sinica，2007，35(2):323-327.

［8］钟一文，宁正元，蔡荣英.一种改进的离散粒子群优化算法［J］.小型微型计算机系统，2006，27(10):1893-1896.ZHONG Yiwen，NING Zhengyuan，CAIRongying.An improved discrete particle swarmoptimization algorithm［J］.Mini-micro Systems，2006，27(10):1893-1896.

［9］黄艳新，周春光.一种求解类覆盖问题的混合算法［J］.软件学报，2005，16(4):513-522.HUANG Yanxin，ZHOU Chungguang.A hybrid algorithmon class cover problems［J］.Journal of Software，2005，16(4):513-522.

［10］ALBERTOG V，RAFAELP.Introducing dynamic diversity into a discrete particle swarmoptimization［J］.Computer and Operation Research，2009，36(3):951-966.

［11］钟一文，蔡荣英.求解二次分配问题的离散粒子群优化算法［J］.自动化学报，2006，27(10):1893-1896.ZHONG Yiwen，CAI Rongying.Discrete particle swarmoptimization algorithmfor QAP［J］.Acta Automatica Sinica，2006，27(10):1893-1896.

［12］张长胜，孙吉贵，欧阳丹彤.一种自适应离散粒子群算法及其应用研究［J］.电子学报，2009，37(2):298-304.ZHANG Changsheng，SUN Jigui，OUYANG Dantong.A self-Adaptive discrete particle swarmoptimization algorithm［J］.Acta Electronica Sinica，2009，37(2):298-304.

［13］余伶俐，蔡自兴.改进混合离散粒子群的多种优化策略算法［J］.中南大学学报:自然科学版，2009，40(4):1047-1053.YU Lingli，CAIZixing.Multiple optimization strategies for improving hybrid discrete particle swarm［J］.Journal of Central South University:Science and Technology，2009，40(4):1047-1053.

［14］KHANESAR mA，TESHNEHLABM，SHOOREHDELImA.A novel binary particle swarmoptimization［C］//Proceedings of the 15th Mediterranean Conference on Control＆ Automation.Athens，Greece，2007:1-6.

［15］许金友，李文立，王建军.离散粒子群算法的发散性分析及其改进研究［J］.系统仿真学报，2009，21(15):4676-4681.XU Jinyou，LIWenli，WANG Jianjun.Research on divergence analysis of discrete particle swarmoptimization algorithmand itsmodification［J］.Journal of SystemSimulation，2009，21(15):4676-4681.

［16］张浩，张铁男，沈继红，等.Tent混沌粒子群算法及其在结构优化决策中的应用［J］.控制与决策，2008，23(8):857-862.ZHANG Hao，ZHANG Tienan，SHEN Jihong，et al.Research on decision-makingsof structure optimization based on improvedTent PSO［J］.Control and Decision，2008，23(8):857-862.

［17］杨光友，陈定方，周国柱.粒子个体最优位置变异的粒子群优化算法［J］.哈尔滨工程大学学报，2006，27(suppl):531-536.YANG Guangyou，CHEN Dingfang，ZHOU Guozhu.Particle swarmoptimization with mutation for best position of particles［J］.Journal of Harbin Engineering University，2006，27(suppl):531-536.

［18］王艳，曾建潮.多目标微粒群优化算法综述［J］.智能系统学报，2010，5(5):377-384.WANG Yan，ZENG Jianchao.A survey of a multi-objective particle swarmoptimization algorithm［J］.CAAITransactions on Intelligent Systems，2010，5(5):377-384.

［19］刘宏达，马忠丽.均匀粒子群算法［J］.智能系统学报，2010，5(4):336-341.LIU Hongda，MA Zhongli.A particle swarmoptimization algorithmbased on uniformdesign［J］.CAAITransactions on Intelligent Systems，2010，5(4):336-341.

［20］陈杰，潘峰，王光辉.粒子群优化方法在动态优化中的研究现状［J］.智能系统学报，2009，4(3):189-198.CHEN Jie，PAN Feng，WANG Guanghui.Reviewof the PSO research in dynamic environments［J］.CAAI Transactions on Intelligent Systems，2009，4(3):189-198.