一种多尺度协同变异的粒子群优化算法

软件学报ＩＳＳＮ　ｌＯＯＯ一９８２５，ＣＯＤＥＮ　ＲＵＸＵＥＷ　Ｅ—ｍａｉｌ：ｊＯＳ＠ｉｓｃａｓ．ａｃ．ｃａ　ＪｏｕｒｎａｌｏｆＳｏｆｔｗａｒｅ，２０１２，２３（７）：１８０５—１８１５【ｄｏｉ：１０．３７２４／ＳＰ．Ｊ．１００１．２０１２．０４１２８】　ｈｔｔｐ：／／ｗｗｗ．ｊｏｓ．ｏｒｇ．ｃｎ　◎中国科学院软件研究所版权所有．　Ｔｅｌ／Ｆａｘ：＋８６－１０—６２５６２５６３　一种多尺度协同变异的粒子群优化算法　陶新民Ｈ，刘福荣　，刘　玉　，童智靖　（哈尔滨工程大学信息与通信工程学院，黑龙江哈尔滨　１５０００１）　（黑龙江省电力有限公司，黑龙江哈尔滨　１５００９０）　Ｍｕｌｔｉ－Ｓｃａｌｅ　Ｃｏｏｐｅｒａｔｉｖｅ　Ｍｕｔａｔｉｏｎ　Ｐａｒｔｉｃｌｅ　Ｓｗａｒｍ　Ｏｐｔｉｍｉｚａｔｉｏｎ　Ａｌｇｏｒｉｔｈｍ　ＴＡＯ　Ｘｉｎ．ＭｉｎＨ，ＬＩＵ　Ｆｕ．Ｒｏｎｇ　，ＬＩＵ　Ｙｕ　，ＴＯＮＧ　Ｚｈｉ．Ｊｉｎｇ　（Ｃｏｌｌｅｇｅ　ｏｆＩｎｆｏｒｍａｔｉｏｎ　ａｎｄ　Ｃｏｍｍｕｎｉｃａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｈａｒｂｉｎ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｕｎｉｖｅｒｓｉｔｙ，Ｈａｒｂｉｎ　１５０００１，Ｃｈｉｎａ）　（Ｈｅｉｌｏｎｇｊｉａｎｇ　Ｅｌｅｃｔｒｉｃ　Ｐｏｗｅｒ　Ｃｏｍｐａｎｙ　Ｌｉｍｉｔｅｄ，Ｈａｒｂｉｎ　１　５００９０，Ｃｈｉｎａ）　＋Ｃｏｒｒｅｓｐｏｎｄｉｎｇ　ａｕｔｈｏｒ：Ｅ－ｍａｉｌ：ｔａｏｘｉｎｍｉｎ＠ｈｒｂｅｕ．ｅｄｕ．ｃａ，ｈｔｔｐ：／／ｗｗｗ．ｈｒｂｅｕ．ｅｄｕ．ｃｎ　Ｔａｏ　ＸＭ，Ｌｉｕ　ＦＲ，Ｌｉｕ　Ｙ，Ｔｏｎｇ　ＺＪ．Ｍｕｌｔｉ－Ｓｃａｌｅ　ｃｏｏｐｅｒａｔｉｖｅ　ｍｕｔａｔｉｏｎ　ｐａｒｔｉｃｌｅ　ｓｗａｒｍ　ｏｐｔｉｍｉｚａｔｉｏｎ　ａｌｇｏｒｉｔｈｍ．　Ｊｏｕｒｎａｌ　ｏｆＳｏｆｔｗａｒｅ，２０１２，２３（７）：１８０５—１８１５（ｉｎ　Ｃｈｉｎｅｓｅ）．ｈｔｔｐ：／／ｗｗｗ．ｊｏｓ．ｏｒｇ．ｃｎ／ｌＯ００—９８２５／４１２８．ｈｔｍ　Ａｂｓｔｒａｃｔ：Ｔｏ　ｄｅａｌ　ｗｉｔｈ　ｔｈｅ　ｐｒｏｂｌｅｍ　ｏｆ　ｐｒｅｍａｔｕｒｅ　ｃｏｎｖｅｒｇｅｎｃｅ　ａｎｄ　ｌｏｗ　ｐｒｅｃｉｓｉｏｎ　ｏｆ　ｔｈｅ　ｔｒａｄｉｔｉｏｎａｌ　ｐａｒｔｉｃｌｅ　ｓｗａｌ＇ｎｌ　ｏｐｔｉｍｉｚａｔｉｏｎ　ａｌｇｏｒｉｔｈｍ，ａ　ｐａｒｔｉｃｌｅ　ｓｗａｌ＇ｉｒｌ　ｏｐｔｉｍｉｚａｔｉｏｎ（ＰＳＯ）ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　ｍｕｌｔｉ—ｓｃａｌｅ　ｃｏｏｐｅｒａｔｉｖｅ　ｍｕｔａｔｉｏｎ，　ｉｓ　ｐｒｏｐｏｓｅｄ，ｗｈｉｃｈ　ｉｓ　ｇｕａｒａｎｔｅｅｄ　ｔｏ　ｃｏｎｖｅｒｇｅ　ｔｏ　ｔｈｅ　ｇｌｏｂａｌ　ｏｐｔｉｍａｌ　ｓｏｌｕｔｉｏｎ　ｗｉｔｈ　ｐｒｏｂａｂｉｌｉｔｙ　ｏｎｅ．Ｔｈｅ　ｓｐｅｃｉａｌ　ｍｕｌｔｉ—ｓｃａｌｅ　Ｇａｕｓｓｉａｎ　ｍｕｔａｔｉｏｎ　ｏｐｅｒａｔｏｒｓ　ａｒｅ　ｉｎｔｒｏｄｕｃｅｄ　ｔｏ　ｍａｋｅ　ｔｈｅ　ｐａｒｔｉｃｌｅｓ　ｅｘｐｌｏｒｅ　ｔｈｅ　ｓｅａｒｃｈ　ｓｐａｃｅ　ｍｏｒｅ　ｅｆｉｆｃｉｅｎｔｌｙ．Ｔｈｅ　ｌａｒｇｅ－ｓｃａｌｅ　ｍｕｔａｔｉｏｎ　ｏｐｅｒａｔｏｒｓ　ｃａｎ　ｂｅ　ｕｔｉｌｉｚｅｄ　ｔｏ　ｑｕｉｃｋｌｙ　ｌｏｃａｔｅ　ｔｈｅ　ｇｌｏｂａｌ　ｏｐｔｉｍａｌ　ｓｐａｃｅ　ｄｕｒｉｎｇ　ｅａｒｌｙ　ｅｖｏｌｕｔｉｏｎ．Ｔｈｅ　ｓｍａｌｌ－ｓｃａｌｅ　ｍｕｔａｔｉｏｎ　ｏｐｅｒａｔｏｒｓ，ｗｈｉｃｈ　ａｒｅ　ｇｒａｄｕａｌｌｙ　ｒｅｄｕｃｅｄ　ａｃｃｏｒｄｉｎｇ　ｔｏ　ｔｈｅ　ｃｈａｎｇｅ　ｏｆ　ｔｈｅ　ｆｉｔｎｅｓｓ　ｖａｌｕｅ　ｃａｎ　ｉｍｐｌｅｍｅｎｔ　ｔｈｅ　ａｃｃｕｒａｃｙ　ｏｆ　ｔｈｅ　ｓｏｌｕｔｉｏｎ　ａｔ　ｔｈｅ　ｌａｔｅ　ｅｖｏｌｕｔｉｏｎ．Ｔｈｅ　ｐｒｏｐｏｓｅｄ　ｍｅｔｈｏｄ　ｉｓ　ａｐｐｌｉｅｄ　ｔｏ　ｓｉｘ　ｔｙｐｉｃａｌ　ｃｏｍｐｌｅｘ　ｆｕｎｃｔｉｏｎ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｐｒｏｂｌｅｍｓ，ａｎｄ　ｔｈｅ　ｃｏｍｐａｒｉｓｏｎ　ｏｆ　ｔｈｅ　ｐｅｒｆｏｒｍａｎｃｅ　ｏｆ　ｔｈｅ　ｐｒｏｐｏｓｅｄ　ｍｅｔｈｏｄ　ｗｉｔｈ　ｏｔｈｅｒ　ＰＳＯ　ａｌｇｏｒｉｔｈｍｓ　ｉｓ　ｅｘｐｅｒｉｍｅｎｔｅｄ．Ｔｈｅ　ｒｅｓｕｌｔｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ｐｒｏｐｏｓｅｄ　ｍｅｔｈｏｄ　ｃａｎ　ｅｆｆｅｃｔｉｖｅｌｙ　ｓｐｅｅｄ　ｕｐ　ｔｈｅ　ｃｏｎｖｅｒｇｅｎｃｅ　ａｎｄ　ｉｍｐｒｏｖｅ　ｔｈｅ　ｓｔａｂｉｌｉｙｔ．　Ｋｅｙ　ｗｏｒｄｓ：ｐａｒｔｉｃｌｅ　ｓｗａｒｍ　ｏｐｔｉｍｉｚａｔｉｏｎ；ｐｒｅｍａｔｕｒｅ　ｃｏｎｖｅｒｇｅｎｃｅ；ｍｕｌｔｉ－ｓｃａｌｅ；ｃｏｏｐｅｒａｔｉｖｅ　ｍｕｔａｔｉｏｎ；ｆｔｎｅｓｓ　摘要：为了改善粒子群算法易早熟收敛、精度低等缺点，提出一种多尺度协同变异的粒子群优化算法，并证明了　该算法以概率１收敛到全局最优解．算法采用多尺度高斯变异机制实现局部解逃逸．在算法初期阶段，利用大尺度变　异及均匀变异算子实现全局最优解空间的快速定位；随着适应值的提升，变异尺度随之降低；最终在算法后期阶段，　利用小尺度变异算子完成局部精确解空间的搜索．将算法应用６个典型复杂函数优化问题，并同其他带变异操作的　ＰＳＯ算法比较，结果表明，该算法在收敛速度及稳定性上有显著提高．　关键词：　粒子群算法；早熟收敛；多尺度；协同变异：适应度　中图法分类号：ＴＰ１８　文献标识￣ｉｑ－：Ａ　・基金项目：国家自然科学基金（６１０７４０７６）；国家博士后科学基金（２００９０４５０１ｌ８）；中国博士点新教ＩＪ￣（２００９２３０４１２００１７）；黑　龙江省博士后科学基金（ＬＢＨ．Ｚ０８２２７１　收稿时间：２００９　１ｌ一１７；修改时间：２０１１－０４—２５，２０１１－０６—２４；定稿时间：２０１卜１Ｏ一０８　１８０６　Ｊｏｕｒｎａｌ　ｏｆ　Ｓｏｆｔｗａｒｅ软件学报Ｖｏ１．２３，Ｎｏ．７，Ｊｕｌｙ　２０１２　粒子群算法（ｐａｒｔｉｃｌｅ　ｓｗａｒｍ　ｏｐｔｉｍｉｚａｔｉｏｎ，简称ＰＳＯ）是由Ｅｂｅｒｈａｒｔ博士提出的一种基于群体智能的优化算　法。其基本思想源于对鸟群捕食行为的研究．由于其简单、易实现、收敛快等优点，在目标函数优化、神经网　络训练等方面都有很好的表现，其应用涉及系统控制、模式识别、通信工程等各个领域．然而，早熟和收敛慢０－５］　一直是困扰粒子群算法的两个难题．　在避免粒子群算法早熟收敛的研究中，很多改进方案被提了出来，包括变更公式法　分群方法等．对ＰＳＯ的　参数进行自适应选择策略，在改善算法的性能方面也取得了良好的效果，如在惯性权值中引入随机成分【６Ｉ７Ｊ、利　用模糊逻辑调节惯性权值［８Ｉ９】、采用一个的二级ＰＳＯ优化一级ＰＳＯ参数【　】、利用Ｑ．学习调节参数【ｌｌＪ、　采用自适应评论策略调节参数（挖】等．此外，Ｚｈａｎｇ等人［”】通过评价每个粒子的性能改善指标自适应调节惯性权　值、粒子数以及粒子邻域大小；Ｒａｔｎａｗｅｅｒａ等人【】　】通过引入时变加速因子和时变惯性权因子，有效地增强了算　法的局部搜索能力；Ｚｈａｎ等人提出的自适应粒子群优化算法（ａｄａｐｔｉｖｅ　ｐａｒｔｉｃｌｅ　ｓｗａｒｍ　ｏｐｔｉｍｉｚａｔｉｏｎ，简称　ＡＰＳＯ）［　】采用数学统计的技术对算法运行过程中的种群位置分布信息和适应值信息进行分析，并以此定义了　一个称为“进化因子（ｅｖｏｌｕｔｉｏｎａｒｙ　ｆａｃｔｏｒ）”的变量ｆ．ＡＰＳＯ采用模糊逻辑的方法对厂的取值进行模糊划分，从而估　计算法运行的不同进化状态，并根据不同的进化状态设计有效的参数自适应控制策略以加快算法的求解速度，　取得了良好效果．　近年来，许多学者又将进化算法中的变异操作引入ＰＳＯ．如文献【ｌ６】通过对粒子引入一个小概率随机变异　操作来增加种群多样性（ｄｉｓｓｉｐａｔｉｖｅ　ＰＳＯ，简称ＤＰＳＯ），这样虽然可以对解空间进行更好的搜索，但如果变异率控　制不当极易导致原始种群的混乱，达不到局部精确搜索的目的．在此基础上，文献［１７］给出了一种变异操作随时　间变化的自适应层次ＰＳＯ算法（ｓｅｌｆ－ｏｒｇａｎｉｚｉｎｇ　ｈｉｅｒａｒｃｈｉｃａｌ　ＰＳＯ，简称ＨＰＳＯ），确定了自适应参数的选择方式．但　由于该算法没有考虑速度公式中惯性因素的影响，使得算法仍然未能迅速而有效地逃离局部极小值．文献［１８】　为了提高种群多样性和搜索速度之间的平衡，对阈值设定进行了改进，并结合群体自动分家机制，提出一种自适　应逃逸的微粒群算法（ｓｅｌｆ－ａｄａｐｔｉｖｅ　ｅｓｃａｐｅ　ＰＳＯ，简称ＡＥＰＳＯ）．然而，上述算法在变异时均采用单一的均匀变异机　制，逃逸能力大为减弱，使改进ＰＳＯ算法在有限的迭代次数内无法实现全局最优解的探索．因此，如何增强算法　的逃逸能力，使其在快速定位到最优解区域的同时提高最优解的精度，值得我们进一步加以研究．　鉴于此，本文提出一种多尺度协同变异的自适应粒子群算法（ｍｕｌｔｉ．ｓｃａｌｅ　ｃｏｏｐｅｒａｔｉｖｅ　ｍｕｔａｔｉｎｇｌｙ　ｓｅｌｆ－　ａｄａｐｔｉｖｅ　ｅｓｃａｐｅ　ＰＳＯ，简称ＭＡＥＰＳＯ）．该算法利用不同大小方差的自适应高斯变异机制实现解空间的探索，这种　多个或大或小的变异机制能够促使整个种群以尽量分散的变异尺度来对解空间进行更加详尽的探索．高斯变　异的范围随着适应值的变小逐渐降低，在算法后期有利于提高最优解的精度．同时，利用均匀算子维护种群多样　性．通过对不同评测函数进行测试，均验证了新算法优良的优化性能．　１标准粒子群算法　一个由，，１个粒子组成的群体在ｎ维搜索空间中以一定速度ｖＦ（ｖｆｌ，ｖｆ２，…，ｖ　）　飞行，粒子的好坏由一个事先　设定的适应值函数来确定，每个粒子在搜索时根据目前为止自身搜索到的历史最好点ｐ尸　１　ｆ２，…　）　也称为　ｐｂｅｓｔ）和整个群体中所有粒子发现的最好点ｐ　（ｐｇ１，Ｐｇ２，．．．　）　也称为ｇｂｅｓｔ）进行位置Ｘｉ￣（Ｘｉ１，ｘｆ２，…　ｆ　）　的变化．　粒子迭代过程中速度与位置的更新公式为　Ｖｉｄ（ｆ＋１）＝ｗ×Ｖｊｄ（ｔ）＋Ｃ１×　×（Ｐｆｄ（ｆ）一勘（ｆ））＋ｃ２×ｒ２×（Ｐｇｄ（ｆ）一　（ｆ））　％Ｏ＋１）＝　（ｆ）＋　＋１）　（１）　（２）　其中，ｒ１和　是均匀分布在［０，１】范围内的随机数，用来保持群体的多样性；。ｌ和Ｃ２为学习因子，使粒子具有向群体　中优秀个体学习的能力：　为惯性权重，起着权衡局部和全局最优能力的作用．粒子的每维速度被在一个最　大速度为　的范围内．　２多尺度协同变异粒子群算法　粒子群算法迭代过程中，如果某个粒子发现了一个当前最优位置，其他粒子会迅速向其靠拢．如果该最优位　陶新民等：一种多尺度协同变异的粒子群优化算法　１８０７　置是局部最优点，粒子群就无法在解空间内重新搜索，算法就会陷入局部最优，从而出现早熟收敛的现象．为了　避免这种情况的发生，此时，如果我们对粒子的速度进行变异，就可以改变粒子的前进方向，使粒子进入解空间　的其他区域搜索，从而有可能发现新的个体最优位置和种群最优位置，增加算法找到全局最优解的几率．　然而，在上述提到的通过增加变异操作来帮助算法逃出局部最优的改进算法中，粒子的逃逸能力都取决于　均匀变异尺度，均匀变异虽然具有很强的逃离原点的能力，但是由于我们事先无法预知函数局部极值间的距离，　因此无法给出合适的变异尺度．如果初始尺度较大，则无法保证所逃离到的新位置的适应值一定优于现有的最　优解，尤其是在算法进化后期最优解可能就存在于现有最优解周边的区域，这样，通过单纯的均匀变异无法确定　更优的位置，最终因迭代次数的使其无法收敛到全局最优解．为此，本文提出一种多尺度协同变异粒子群优　化算法，算法的逃逸能力取决于不同尺度方差的高斯变异算子，不同尺度的变异有助于算法在搜索空间中进行　分散式搜索．同时，变异尺度随着适应度的提升逐渐减少．这样，在保证算法逃逸能力的同时，提高了最优解的　精度．　２．１多尺度高斯变异算子　设尺度个数为　首先初始化多尺度高斯变异算子的方差：　∞’＝（　，ｃｒ；∞，．．．，　）　（３）　初始时，方差一般设定为优化变量的取值范围；随着迭代次数的增加，多尺度高斯变异算子的方差会随之进　行调整，具体调整方式如下：首先，根据适应值函数厂的大小对种群中的粒子由小到大排序；然后对其进行组合，生　成　个子群，每个子群的粒子个数为Ｐ＝Ｎ／Ｍ．Ｋ是当前迭代次数，计算每一个子群的适应度值：　旦ｆ一１　｜　ＦｉｔＸ￣’＝∑，（　）／Ｐ，ｍ＝１，２，．．．，Ｍ　，　（４）　不同变异尺度之间相互竞争，根据适应能力的不同设置不同的变异能力．因此，第ｍ个变异算子的标准差为　＼Ｍ・，　ＦｉⅨ　－ＥＭ　ＦｉⅨ　ｘｐ　｛￡　＝ｍａｘ（ＦｉｔＸ（Ｋ），　一　，．．．，　￡　）　（６）　只￡Ｙ　＝ｍｉｎ（ＦｉｔＸ（ｘ），　，．．．，ＦｉｔＸ（ＭＫ　）　（７）　根据每个子群适应度得到的　个不同尺度算子随迭代次数的变化如图１所示，由于变异算子的进化是一　个递归过程，排在后面的变异算子可能很大，因此，对变异算子的标准差作如下规范：如果　”＞Ｗ／４，则　”：Ｉ　Ｗ／４一　”Ｉ　（８）　其中，Ｗ为待优化变量空间的宽度．重复上式，直到满足　＜Ｗ／４．　磺　迭代次数Ⅳ　Ｆｉｇ．１　Ｃｈａｎｇｉｎｇ　ｏｆ　ｄｉｆｆｅｒｅｎｔ　ｓｃａｌｅ—ｖａｒｉａｔｉｏｎｓ　ｗｉｔｈ　ｉｔｅｒａｔｉｏｎｓ　ｗｈｅｎ　１１４－－５　图ｉ　Ｍ＝５时不同尺度方差随迭代次数的变化示意图　１８０８　Ｊｏｕｒｎａｌ　ｏｆ　Ｓｏｆｔｗａｒｅ软件学报Ｖｏ１．２３，Ｎｏ．７，Ｊｕｌｙ　２０１２　从图１可以看出，随着迭代次数的变化，不同尺度算子的方差变化情况不同．本文提出的多尺度变异算子能　够实现整个解空间的覆盖性搜索，其中，大尺度（　＝５）变异算子具有振荡性质，完成对解空间的粗搜索，使粒子快　速定位到最优解周围；而小尺度（　＝１，２，３，４）变异算子呈递减趋势，在进化后期完成局部精确解的探索．为了最大　范围地实现空间勘探能力，进行完多尺度高斯变异后，按公式（９）进行一次均匀变异操作，比较变异后所有粒子的　适应值，取最好的位置作为新的逃逸点．阈值　用来保存种群中第ｄ维的当前速度阈值且其值恒大于Ｏ；ｒａｎｄ为　～个均匀分布在［０，１】范围内的随机数．　Ｉｆ（Ｖｉｄ＜　ｔｈｅｎ　Ｖｉｄ＝ｒａｎｄｘ　。。　（９）　２．２勘探和开采能力的自适应协同　我们知道，任何一种进化算法都存在勘探和开采两类不同的操作，ＰＳＯ算法随着迭代次数的增加粒子会收　敛于某个最优个体，多样性逐渐丧失．为了防止粒子陷入局部最优，上述算法通过变异操作改善种群多样性来提　高算法的全局搜索能力．然而在算法后期，变异操作往往会使微粒群不能进行精确的局部搜索．因此，如何协调　勘探和开采能力是进化算法性能提高的关键．为此，本文算法采用两种方式实现勘探和开采能力间的均衡．　首先，本文算法采用ＨＰＳＯ中消除了速度惯性部分的公式进行更新，这样就使得ＰＳＯ进化只负责整个算法　的开采能力，当速度小于一定阈值时，给予速度一个变异操作——逃逸运动，描述如下：　Ｉｆ（Ｖ　ｔｈｅｎ　ｒｒｆｉ）＝。　ｎ　ｆ（ｘ，＋ｍ　ｄｎ×　，　＿厂（　＋　ｄｎ×　）　Ｉｆ　ｆ（ｘｉ＋ｒａｎｄｎ×　Ｖｉｄ＝ｒａｎｄｎ￣　Ｅｌｓｅ　）＜ｆ（ｘｉ＋ｒａｎｄ×　）　ｖ￣ｄ＝ｒａｎｄｘ　＿ｍ“　（１０）　ＰＳＯ算法进化公式消除了惯性部分，使粒子速度快速下降．这样，在有限迭代次数内能进行多次逃逸，提高了　种群多样性，增强了算法全局搜索性能．另外，本文算法的逃逸运动采用多尺度高斯变异方式，小尺度能够保证　精确解局部搜索能力，避免了ＨＰＳＯ算法进化后期因下降过快和均匀变异导致无法进行详细局部搜索的不足．　另外，公式（１０）中阈值的大小将会对算法的执行效果产生一定影响：如果阈值过大，则会导致逃逸次数增加，　从而打乱ＰＳＯ种群进化的原有结构，使算法无法进行局部深度搜索，开采能力下降；阈值过小，则会导致微粒速　度需较长时间达到逃逸条件，在有限的迭代次数内无法进行有效的全局搜索，勘探能力下降．为此，结合文献［１　８】’　本文给出一种自适应的阈值设定方法．设微粒各维速度间相互，并对每维速度均给予一个不同的阈值，当该　维度中有多个微粒速度达到这个值时，闽值就自动下降，通过这种方式达到动态调整微粒速度的目的．具体描述　如下：　Ｇｄ（ｆ）＝ＧｄＯ一１）＋∑ｃｉａ（ｔ）　其中，　（ｆ）＝０，Ｖｉａ（ｔ）＞Ｔａ．　（１１）　Ｉｆ　Ｇａ（ｔ）＞ｋｌ　ｔｈｅｎ　Ｇｄ（ｔ）＝Ｏ；Ｔａ＝　如　（１２）　其中，ｋｌ，ｋ２为常数，Ｓｉｚｅ为种群大小，频率Ｇｄ（ｔ）表示种群第ｄ维速度曾经发生逃逸的总次数．ｋ１标记调整阈值乃　和频率　（ｆ）的条件值，如用来控制阈值速度下降的幅度．通过控制粒子飞行速度的方式，不仅能够保证算法的全　局解空间勘探性能，同时在算法后期还能使粒子群进行精确的局部搜索，保证算法的收敛速度．　２．３算法流程　多尺度协同变异的粒子群优化算法的流程如下：　（１）　种群的初始化：随机初始化微粒的速度、位置、全局最优解，计算微粒的适应度，同时作为微粒的个体　陶新民等：一种多尺度协同变异的粒子群优化算法　１８０９　最优位置．反复进行Ⅳ次，共生成Ⅳ个初始微粒群；　（２）　对每个微粒，比较其适应度和它经历过的最好位置适应度，如果更好，则更新该微粒最好位置；　（３）对每个微粒，比较其适应度和群体所经历的最好位置的适应度，如果更好，则更新全局最好位置；　（４）　根据公式（１）ＰＳＯ进化公式调整微粒的速度；　（５）利用公式（１１）判断微粒是否需要逃逸；　（６）　若满足逃逸条件，则利用公式（１０）进行逃逸；　（７）更新微粒的位置：　（８）　根据公式（４）～公式（７）计算多尺度变异算子；　（９）　根据公式（１１）、公式（１２）计算每一维速度的阈值；　（１０）判断终止条件，若满足则终止，否则转到步骤（２）．　３多尺度协同变异粒子群算法分析　３．１算法的优化机理分析　为了说明方便，设优化函数，　）只有一个自变量函数，如图２所示，多尺度变异算法中种群的某一个粒子经　过多次迭代后到达ａ点，经过小尺度逃逸后，向下“下山”找到个体口　，经过ＰＳＯ算法进化到口”，然后经过大尺度变　异后找到适应值更高的粒子６，则粒子ｂ被选择进入下一世代，经过ＰＳＯ若干代进化找到粒子ｂ　．粒子ｂ　经过大　尺度逃逸操作找到了粒子ｃ，则粒子ｃ被选择进入下一个世代，经过ＰＳＯ进化和小尺度逃逸最终找到最优解ｃ　．　由上可知，多尺度逃逸操作将整个解空间看作是一个山谷，经过大尺度变异逃逸操作进行“下山”以寻求适应值　更高的区域（日　６，ｂ　ｃ）．大尺度逃逸操作用于搜索全局解空间，是粗搜索．如果大尺度逃逸操作找到了适应值　更高的区域，则ＰＳＯ进化操作和小尺度变异操作在该区域进行局部搜索，以寻求更高精度的解（Ⅱ　日　，口　口”，６　６　，ｃ　ｃ　）．因此，本文算法是一种勘探和开采能力相互交替进行的搜索算法，具有全局和局部两层邻域搜索机制，　从而保证了算法全局和精确的局部寻优性能．　Ｆｉｇ．２　Ｍｅｃｈａｎｉｓｍ　ｏｆ　ｃｏｏｐｅｒａｔｉｖｅ　ｍｕｌｔｉ－ｓｃａｌｅ　ｅｓｃａｐｅ　图２多尺度协同逃逸优化机理　３．２算法的收敛性分析　引理１．设Ａｘｆａ＝ｖ　，　１，　—Ⅳ（０，１），则　Ⅳ（　，　．　（１３）　证明：由公式（２）可得：　ＡＸｉｄ：Ｃ１×　×（Ｐｉｄ—Ｘｉｄ）＋Ｃ２×ｒ２×（Ｐ　～Ｘｉｄ）　设　＝Ｃ１×（ｐ　一Ｘｉｄ），　＝Ｃ２×（ｐ　一　）　则　（１４）　１８１０　Ｊｏｕｒｎａｌ　ｏｆ　Ｓｏｆｔｗａｒｅ软件学报Ｖｏ１．２３，Ｎｏ．７，Ｊｕｌｙ　２０１２　Ａｘｉｄ＝　＋　×　（１５）　由于ｒｌ，ｒ２￣Ｎ（Ｏ，１），显然　Ⅳ（　，Ｄ　．对于ＭＡＥＰＳＯ算法来说，在粒子运行过程中，公式（１Ｏ）定期给粒子一个　较大的高斯变异速度冲量，使得Ａｘｉｄ在搜索过程中始终是非零高斯变量．　定义１．定义优化问题（ｐ）的全局最优粒子集合为　ｆ　’：　≠　，ｆ（ｘ）＞ｆ（ｘ　）｝　（１６）　对于微粒种群ｘ，令　Ｃ　兰　，ｎ　Ｉ表示微粒种群ｘ中包含最优粒子的个数．　定义２．如果对于任意的初始状态　均有　１ｉｍＰ｛ｌ９（　（　））≥１ｌ　（０）＝　）＝１　．，（１７）　则称算法以概率１收敛于全局最优解．　定理１．多尺度协同变异的微粒群算法以概率１收敛．　由引理１可知，　ｆ　Ⅳ（　，　，由公式（１０）ｎ－￣ｌｌ，ＭＡＥＰＳＯ算法是一种带有变异操作的进化策略算法．在　ＭＡＥＰＳＯ算法中，微粒种群序列｛　证明：记尸０（　＝Ｐ｛　９　，　≥Ｏ｝是一个有限齐次可约马尔可夫链，对于任意初始状态　，算法以概　率１收敛于全局最优粒子集合　．证明如下：　）＝Ｏ），由贝叶斯条件概率公式有　Ｐ｛　（　（　＋１））＝０　Ｊｌ９（　（　））≠Ｏ）×Ｐ｛ｌ９（　（　））≠ｏ）＋　Ｐ｛ｌ９（　（　＋１））＝０ｌｌ９（　（　））＝０）×Ｐ｛ｌ９（　（　））＝Ｏ｝　由微粒群算法的保优性质可得尸｛ｔ　又由公式（１０）可知，　Ｒ（　＋１）＝Ｐ｛ｌ９（　（　＋１））＝Ｏ）　＝（１８）　１））＝０１　飙　）≠０｝＝０，所以，　（１９）　（２０）　Ｐｏ（　＋１）＝Ｐ｛ｌ９（　（　＋１））＝０１｜９（　（　））＝Ｏ｝×Ｐｏ（　）　尸｛一９（　＋１））＞０Ｉ　记　）＝０｝＞０　：ｒｒＡｎＰ｛Ｏ（Ｘ（Ｋ＋１））＞０Ｉｌ９（　（　））＝Ｏ），Ｋ：０，ｌ，２，…　则　（２１）　Ｐ｛ｌ９（　（　＋１））＞０Ｉｌ９（　（　））＝０）≥　＞０　所以，　（２２）　Ｐ｛ｌ９（　（　＋１））＝０Ｉｌ９（　（　））＝０｝＝１一Ｐ｛ｌ９（　（Ｋ＋１））≠０ｌ　（　（　））＝０｝　≤１一Ｐ｛　（　（　＋１））＞１Ｉｌ９（　（　））：０｝　≤１一　＜１　（２３）　因此，　０≤Ｐｏ（Ｋ＋１）≤（１一　）×Ｐｏ（Ｋ）≤（１一　）　ｘＰｏ（Ｋ一１）≤…≤（１－４）ｎ　×　（０）　因为ｌｉａ（１一孝）ｒ　“＝０，１≥Ｐｏ（Ｏ）≥０，所以，　一（２４）　０￣＜　ｌｉｍ　ｐ。（　）≤　．＋（１一　）　‘Ｐｏ（Ｏ）＝０　（２５）　故ｌｉｍＰ０（０）＝０，因此，　Ｋ　∞　ｌｉｍＰ｛ｌ９（　（　））≥１Ｉｘ（ｏ）＝Ｘｏ｝＝１一ｌｉｍＰ｛ｌ９（　（　））＝０Ｉｘ（ｏ）＝Ｘｏ）≥１一ｌｉｍ昂（　）＝１　Ｋ＿’∞　∞　））＞１ｌｘ（ｏ）＝Ｘｏ）＝１．定理１得证．　（２６）　口　所以１ｉｍＰ｛　（　．．因此，ＭＡＥＰＳＯ算法以概率１收敛于全局最优粒子集合　．　３．３算法计算时间复杂度分析　对于传统ＰＳＯ算法，一个粒子每维分量进行更新所需要的运算如下：５次乘法运算，５次加法运算．假设乘法　和加法运算所需要的时间分别为　和　．实验中，设置传统ＰＳＯ算法中的粒子数量为ｍ，维数为　所需迭代次　陶新民等：一种多尺度协同变异的粒子群优化算法　１８ｌ１　数为　１，则传统的ＰＳＯ算法完成优化所需的平均时间为ｄｘｍｘｎｌ×（５　＋５　）．对于本文算法，如果尺度个数Ｍ＝５，　所需迭代次数为　２，则一个粒子进行更新、变异所需要的运算如下：１１次乘法运算，１０次加法运算．因此，算法完　成优化所需的平均时间为ｄｘｍｘｎ２×（１１Ｔｍ＋ｌＯ　）．由此得出，当ｎｌ　２　２时，本文算法的平均时间与传统ＰＳＯ算法相　当．由于本文算法进化初期大尺度变异算子快速定位最优解附近区域的勘探能力和进化后期小尺度变异算子　的深度开采能力，使算法搜索到问题最优解所需的迭代次数远远小于传统ＰＳＯ算法及其改进算法，ｎ２＜＜　】／２，图　３～图８中，本文算法与其他算法收敛速度的对比结果可以证明这一点．因此，从某种意义上说，本文算法找到问题　最优解所需的平均时间与传统ＰＳＯ算法不相上下，因此并没有提高传统ＰＳＯ算法的时间复杂度．　ｊ型　闰　迭代次数Ⅳ　Ｆｉｇ．３　Ｃｏｎｖｅｒｇｅｎｃｅ　ｐｅｒｆｏｒｍａｎｃｅ　ｃｏｍｐａｒｉｓｏｎ　ｏｆ　３０．ｄｉｍｅｎｓｉｏｎ『盘６ｌｅｔ　ｆｕｎｃｔｉｏｎ　图３　３０维Ｔａｂｌｅｔ函数收敛情况对比图　ｊ四　卿　籁　闺　０　５００　１０００　ｌ５００　２０００　迭代次数Ⅳ　Ｆｉｇ．５　Ｃｏｎｖｅｒｇｅｎｃｅ　ｐｅｒｆｏｒｍａｎｃｅ　ｃｏｍｐａｒｉｓｏｎ　ｏｆ　３０．ｄｉｍｅｎｓｉｏｎ　Ｒｏｓｅｎｂｒｏｃｋ　ｆｕｎｃｔｉｏｎ　图５　３０维Ｒｏｓｅｎｂｒｏｃｋ函数收敛情况对比图　堪　蚓　圆　。　迭代次数Ⅳ　Ｆｉｇ．７　Ｃｏｎｖｅｒｇｅｎｃｅ　ｐｅｒｆｏｒｍａｎｃｅ　ｃｏｍｐａｒｉｓｏｎ　ｏｆ　３０－ｄｉｍｅｎｓｉｏｎ　Ｒａｓｔｒｉｇｒｉｎ　ｆｕｎｃｔｉｏｎ　图７　３０维Ｒａｓｔｒｉｇｒｉｎ函数收敛情况对比图　ｊ型　蜊　氟　闺　迭代次数Ⅳ　Ｆｉｇ．４　Ｃｏｎｖｅｒｇｅｎｃｅ　ｐｅｒｆｏｒｍａｎｃｅ　ｃｏｍｐａｒｉｓｏｎ　ｏｆ　３０－ｄｉｍｅｎｓｉｏｎ　Ｑｕａｄｒｉｃ　ｕｆｎｃｔｉｏｎ　图４　３０维Ｑｕａｄｒｉｃ函数收敛情况对比图　趔　蚓　闺　迭代次数Ⅳ　Ｆｉｇ．６　Ｃｏｎｖｅｒｇｅｎｃｅ　ｐｅｒｆｏｒｍａｎｃｅ　ｃｏｍｐａｒｉｓｏｎ　ｏｆ　３０．ｄｉｍｅｎｓｉｏｎ　Ｇｒｉｅｗａｎｋ　ｆｕｎｃｔｉｏｎ　图６　３０维Ｇｒｉｅｗａｎｋ函数收敛情况对比图　蜊　闭　０　迭代次数Ⅳ　Ｆｉｇ．８　Ｃｏｎｖｅｒｇｅｎｃｅ　ｐｅｒｆｏｒｍａｎｃｅ　ｃｏｍｐａｒｉｓｏｎ　ｏｆ　３０．ｄｉｍｅｎｓｉｏｎ　Ｓｃｈａｆｆｅｒ　ｆｕｎｃｔｉｏｎ　图８　３０维Ｓｃｈａｆｆｅｒ函数收敛情况对比图　１８１２　Ｊｏｕｒｎａｌ　ｏｆ　Ｓｏｆｔｗａｒｅ软件学报Ｖｏ１．２３，Ｎｏ．７，Ｊｕｌｙ　２０１２　４对比实验及结果分析　为了验证本文算法的优化性能，选择文献［１８】中的６个Ｂｅｎｃｈｍａｒｋ函数：Ｔａｂｌｅｔ，Ｑｕａｄｒｉｃ，Ｒｏｓｅｎｂｒｏｃｋ，　Ｇｒｉｅｗａｎｋ，Ｒａｓｔｒｉｇｉｎ，Ｓｃｈａｆｆｅｒ　Ｆ７进行数值实验．其中，前３个函数为单模态函数，后３个函数为多模态函数．６个函　数当自变量取合适值时，极值都为０．将本文算法与传统ＰＳＯ算法及其改进的ＤＰＳＯ，ＨＰＳＯ，ＡＥＰＳＯ算法进行对　比实验．５种算法参数设置如下：采用线性下降惯性权重，ｗ在［Ｏ．９５，０．４】之间随迭代数线性递减；ｃ１，ｃ２均为　１．４，ＤＰＳＯ中Ｃｖ＝０．００１，ＡＥＰＳＯ和本文算法的　ｌ＝５，／＜７２＝１０，本文算法Ｍ＝５，初始方差　为优化变量的范围，ｚ　０．５，　种群规模均为２Ｏ，函数维度为３Ｏ，每次运行６　０００代，每个函数运行５０次．　４．Ｉ单模态Ｂｅｎｃｈｍａｒｋ函数对比实验　图３～图５反映了５种算法处理单模态Ｂｅｎｃｈｍａｒｋ函数的对比结果．如图３、图４所示，对于简单的Ｔａｂｌｅｔ　函数和Ｑｕａｄｒｉｃ函数，本文算法能够迅速定位到最优解０的附近区域．对于复杂的单模态Ｒｏｓｅｎｂｒｏｃｋ函数，由于　函数山谷提供的信息量很少，使传统的ＰＳＯ算法很难在短时间内辨别搜索方向，易陷入局部最优．从图５可以看　出，本文算法能够在短时间内找到正确的搜索方向，下降速度较快，这是由于在进化初期采用大尺度变异算子对　解空间进行大范围搜索的结果；而其他算法单一的均匀变异机制具有一定的盲目性，因此下降得比较缓慢，减缓　了算法的收敛速度．　为了进一步证明本文算法的优越性，分别统计５种算法在处理６个Ｂｅｎｃｈｍａｒｋ函数问题时运行５０次所得　的最优值、最差值、中值、平均值和标准差，单模态问题的统计结果见表１．可以看出，本文算法在各项数值上　均优于其他算法，特别是对于Ｔａｂｌｅｔ函数，５０次寻优实验能够１００％地找到最优解．Ｔａｂｌｅｔ函数和Ｑｕａｄｒｉｃ函数的　统计数据显示，某些情况下，ＤＰＳＯ和ＨＰＳＯ的性能比传统的ＰＳＯ算法更差．这是因为仅通过单一的均匀变异和　消除速度惯性部分的做法，使算法丧失了全局解空间的勘探能力．由于粒子群算法属于随机搜索算法，因此稳定　性是衡量算法好坏的重要标准．表１显示，ＰＳＯ及其他改进算法在Ｑｕａｄｒｉｃ和Ｔａｂｌｅｔ函数优化问题上具有较好的　稳定性，但对于复杂的Ｒｏｓｅｎｂｒｏｃｋ函数。由于很难确定最优解搜索方向，因此各种算法单次结果差异很大．而本　文算法单次得到的解之间的差异性相对较小，５０次实验中寻优率达到９４％，因此算法具有更好的稳定性和健　壮性．　　．Ｔａｂｌｅ　１　Ｐｅｒｆｏｒｍａｎｃｅ　ｃｏｍｐａｒｉｓｏｎ　ｏｆ　ＭＡＥＰＳＯ　ａｎｄ　ｏｔｈｅｒ　ＰＳＯ　ａｌｇｏｒｉｔｈｍｓ　ｉｎ　ｕｎｉ—ｍｏｄｅｌ　ｆｕｎｃｔｉｏｎ　表１　ＭＡＥＰＳＯ和其他ＰＳＯ算法在单模态Ｂｅｎｃｈｍａｒｋ问题上的性能对比・　函数　算法　ＰＳ０　ＤＰＳＯ　乃８ｌｅｔ　ＨＰＳＯ　ＡＥＰＳＯ　最小值　６．２ｅ－２２　１．４ｅ—ｌｌ　２１ｅ一２６　．中间值　ｌ＿１ｅ－２０　１．８ｅ－１０　２．５ｅ一２４　５．６ｅ—ｌ２４　平均值　１．１ｅ－１９　１．６ｅ－１０　３．９ｅ一２４　２．６ｅ—ｌ２２　方差　８．２ｅ－１９　ｌ＿３ｅ－１１　４．７ｅ－２４　８．１ｅ－１２２　最大值　５．６ｅ一１８　２．８ｅ－１０　１．６ｅ－２３　６．９ｅ－ｌ２ｌ　１．２ｅ－１２８　ＭＡＥＰＳＯ　ＰＳｏ　ＤＰＳ０　０（１００％１　０．７２２　７．８ｅ－０４　０　７０．６５　３．５ｅ—Ｏ３　０　１．２ｅ＋２　３．８ｅ－０３　０　１．１ｅ＋２　２．０ｅ－３　０　４．８ｅ＋０２　１．Ｉｅ—Ｏ２　Ｑｕａｄｒｉｃ　ＨＰＳＯ　ＡＥＰＳ０　ＭＡＥＰＳＯ　ＰＳＯ　０．２５５　４．４ｅ－１１　１．６７５５ｅ一２ｌ５　４．８７３　１．１９８　６．５ｅ－１０　４．１３４０ｅ一０８１　７７．２４　ｌ＿４１２　１．２ｅ－０９　３．１２７７ｅ一０１０　９３．７１　０．８ｌ１　１＿４ｅ－０９　１．１７０３ｅ一００９　１．５ｅ＋０２　３．８３７　７．５ｅ－０９　４．３７８８ｅ一００９　１．０ｅ＋０３　ＤＰＳＯ　Ｒｏｓｅｎｂｒｏｃｋ　ＨＰＳＯ　ＡＥＰＳＯ　８．２ｅ一０２　５．３ｅ－０２　２．３ｅ－０３　２０．６４　７２．５７　８．３２２　３２．０８　１．９ｅ＋０２　１２．２８　３２．１　７　１．１ｅ＋０２　１　７．１　９　１．７ｅ＋０２　６．９ｅ＋０２　７９．６９　ＭＡＥＰＳＯ　０（９４％）０　２．９２７３ｅ一００７　１．６４３０ｅ一００６　１．１１５５ｅ－００５　４．２多模态Ｂｅｎｃｈｍａｒｋ函数对比实验　从图６～图８可以看出，对于３个多模态函数，本文算法能够比其他算法在较少迭代次数内定位到全局最优　解附近的区域，全局搜索能力明显优于其他算法．从表２可知，ＭＡＥＰＳＯ算法的中值、平均值和标准差等各项数　据均显著优于其他算法，显示了新算法的稳定性和健壮性．在处理多模态Ｇｒｉｅｗａｎｋ函数和Ｒａｓｔｒｉｇｒｉｎ函数优化问　陶新民等：一种多尺度协同变异的粒子群优化算法　１８１３　题时，在有限次代数内几乎全部找到了问题的最优解，寻优率分别达到９５．５％和９２％．由于Ｓｃｈａｆｆｅｒ函数的特殊　性质　其他算法通过增加均匀变异操作未能找到问题的最优解０，而本文算法在５０次的实验中有２２％的机会找　到了全局最优解．虽然本文算法对于多模态问题没有在每次运行都能找到全局最优解，但是只要给予足够长的　迭代次数。ＭＡＥＰＳＯ算法总能逃出局部最优找到全局最优解．从表２中最优解和最差解实验结果之间的差异可　以看出，无论是ＰＳＯ算法还是其他改进算法，对于处理多模态函数优化问题的稳定性都很差，而本文算法相对于　其他算法而言稳定性大为提高，这些都是由于本文算法采用了多尺度变异算子使得算法能够在搜索空间内进　行分散式搜索的结果．　Ｔａｂｌｅ　２　Ｐｅｒｆｏｒｍａｎｃｅ　ｃｏｍｐａｒｉｓｏｎ　ｏｆ　ＭＡＥＰＳＯ　ａｎｄ　ｏｔｈｅｒ　ＰＳＯ　ａｌｇｏｒｉｔｈｍｓ　ｉｎ　ｍｕｌｔｉ—ｍｏｄｅｌ　ｆｕｎｃｔｉｏｎ　表２　ＭＡＥＰＳＯ和其他ＰＳＯ算法在多模态Ｂｅｎｃｈｍａｒｋ问题上的性能对比　函数　算法　ＰＳＯ　ＤＰＳＯ　Ｇｒｉｅｗａｎｋ　ＨＰＳＯ　ＡＥＰＳＯ　最小值　６．７ｅ—ｌ１　４．４ｅ－１２　１．１ｅ—ｌ６　０　中间值　１．９６ｅ－０２　１．７ｅ－０２　９．９ｅ—Ｏ３　８．６ｅ－０３　平均值　２．６ｅ一０２　２．５ｅ－０２　１．５ｅ－０２　１．２ｅ－Ｏ２　方差　２．８ｅ－０２　３．３ｅ－０２　２．１ｅ一０２　１．６ｅ一０２　最大值　０．１０８　０．１４７　８．５ｅ一０２　６．６ｅ－０２　ＭＡＥＰＳＯ　ＰＳＯ　ＤＰＳＯ　Ｒａｓｔｒｉｇｒｉｎ　ＨＰＳｏ　ＡＥＰＳＯ　０（９５．５％１　３Ｏ－８７　７．２ｅ一０９　ｌ２．９３　０　０　５６．７１　７．０ｅ一０６　２６＿８６　４．０ｅ－１２　１．０１０２ｅ一０１０　５５．１８　０．２０１　２９．Ｏ２　０．５７７　６．２１８４ｅ一０１０　１．２－３ｌ　０．４９８　８．９６３　１．０８７　４．３９７４ｅ一００９　８１．５９　２．０５８　５５．８１　３．９８０　ＭＡＥＰＳＯ　ＰＳＯ　ＤＰＳｏ　０（９２％）２．４ｅ＋０２　８２－３５　０　２．９ｅ＋０２　１．５ｅ＋０２　２．０４６７ｅ一００８　２．９ｅ＋０２　１．３ｅ＋０２　７．０９００ｅ一００８　３０．９１　３１．１７　２．４５６０ｅ一００７　３．５ｅ＋０２　２．３ｅ＋０２　Ｓｃｈａｆｆｅｒ　ＨＰＳＯ　ＡＥＰＳＯ　１．９ｅ＋０２　４４．５７　２．４ｅ＋０２　１．２ｅ＋０２　１．９ｅ＋０２　１．１ｅ＋０２　２２．４２　３９．１９　２．１ｅ＋０２　２．３ｅ＋０２　ＭＡＥＰＳＯ　０（２２％１　０．２９７４　１．４３９７　２．２６７６　９．０６０６　４．３不同初始参数　对算法性能的影响　为了验证初始阈值参数对本文算法性能的影响，利用不同取值范围的Ｓｃｈａｆｆｅｒ，Ｇｒｉｅｗａｎｋ，Ｒｏｓｅｎｂｒｏｃｋ及　Ｒａｓｔｒｉｇｒｉｎ函数进行实验，实验中取不同的初始值，实验结果如图９所示．　熠　乃初始化参数　Ｆｉｇ．９　Ｅｆｆｅｃｔ　ｏｆ　ｉｎｉｔｉａｌ　ｐａｒａｍｅｔｅｒｓ　Ｔａ　ｏｎ　ｐｅｒｆｏｒｍａｎｃｅ　图９不同　初始化参数对算法性能的影响　我们可以看出，阈值取【０．１，０．９】时获得的最优解最为理想．这是由于，在算法初始阶段充分利用了多尺度高　斯变异算子的大尺度实现快速的全局最优解区域定位，提高了算法全局搜索性能．在进化的中后期，由于本文算　法的阈值自适应调节，使得阈值随着迭代次数的增加而下降，最终利用小尺度变异实现局部最优解空间的搜索．　因此，在优化变量取值较宽且搜索空间复杂时，可以选取较大的初始阈值，这样可以在算法初期阶段有效地提高　算法的全局最优解的搜索能力．　１８１４　Ｊｏｕｒｎａｌ　ｏｆ　Ｓｏｆｔｗａｒｅ软件学报Ｖｏ１．２３，Ｎｏ．７，Ｊｕｌｙ　２０１２　５结束语　本文提出一种新的多尺度变异粒子群算法，利用不同大小方差的高斯变异机制实现解空间的搜索，这种多　个或大或小的变异机制能够促使整个种群以尽量分散的变异尺度来对解空间进行更加详尽的探索．同时，高斯　变异的范围随着适应值的变小也逐渐缩小，有利于提高最优解的精度．同时，利用均匀变异算子维护种群多样　性．通过６个Ｂｅｎｃｈｍａｒｋ函数进行测试，结果表明，新算法能够在算法初期快速定位到最优解附近区域，进而使得　微粒通过进化ＰＳＯ及小尺度变异算子向着最优精确解空间逼近，使其在进化过程中保持局部最优解空间开采　的能力，加快了算法的收敛速度．其中，不同尺度个数对本文算法性能的影响将是本课题下一阶段研究的重点．　Ｒｅｆｅｒｅｎｃｅｓ：　［１】Ｋｅｎｎｅｄｙ　Ｊ，Ｅｂｅｒｈａｒｔ　Ｒ．Ｐａｒｔｉｃｌｅ　ｓｗａｒｍ　ｏｐｔｉｍｉｚａｔｉｏｎ．Ｉｎ：Ｐｒｏｃ．ｏｆｔｈｅ　ＩＥＥＥ　Ｉｎｔ’１　Ｃｏｎ￣ｏｎ　Ｎｅｕｒａｌ　Ｎｅｔｗｏｒｋｓ．Ｐｉｓｃａｔａｗａｙ：ＩＥＥＥ　Ｐｒｅｓｓ　１９９５．１９４２－１９４８．　【２］Ｓｈｉ　Ｙ，Ｅｂｅｒｈａｒｔ　Ｒ．Ａ　ｍｏｄｉｉｆｅｄ　ｐａｒｔｉｃｌｅ　ｓｗａｒｎｌ　ｏｐｔｉｍｉｚｅｒ．Ｉｎ：Ｌｅｅ　Ｊ　Ｋ，Ａｎｄｒｅｗ　Ｂ，Ｓｅｈｍｉｄ　Ｂ，ｅｄｓ．Ｐｒｏｃ．ｏｆ　ｔｈｅ　ＩＥＥＥ　Ｉｎｔ’１　Ｃｏｎｆ．ｏｎ　Ｅｖｏｌｕｔｉｏｎａｒｙ　Ｃｏｍｐｕｔａｔｉｏｎ．Ｐｉｓｃａｔａｗａｙ：ＩＥＥＥ　Ｐｒｅｓｓ，１９９８．６７—７３．［ｄｏｉ：１０．１　１０９／ＩＣＥＣ．１９９８．６９９１４６】　ｏｐｏｕｌｏｓ　ＫＥ，Ｖｒａｈａｔｉｓ　ＭＮ．Ｏｎ　ｔｈｅ　ｃｏｍｐｕｔａｔｉｏｎ　ｏｆ　ａｌｌ　ｇｌｏｂａｌ　ｍｉｎｉｍｉｚｅｒｓ　ｔｈｒｏｕｇｈ　ｐａｒｔｉｃｌｅ　ＳＷａｌＴＩＩ　ｏｐｔｉｍｉｚａｔｉｏｎ．ＩＥＥＥ　Ｔｒａｎｓ．ｏｎ　【３］　ＰａｒｓＥｖｏｌｕｔｉｏｎａｒｙ　Ｃｏｍｐｕｔａｔｉｏｎ，２００４，８（３）：２１　１－２２４．【ｄｏｉ：１０．１　１０９／ＴＥＶＣ．２００４．８２６０７６】　ｅａ　ＩＣ．Ｔｈｅ　ｐａｒｔｉｃｌｅ　ｓｗａｒｌＴｌ　ｏｐｔｉｍｉｚａｔｉｏｎ　ａｌｇｏｒｉｔｈｍ：Ｃｏｎｖｅｒｇｅｎｃｅ　ａｎａｌｙｓｉｓ　ａｎｄ　ｐａｒａｍｅｔｅｒ　ｓｅｌｅｃｔｉｏｎ．Ｉｎｆｏｒｍａｔｉｏｎ　Ｐｒｏｃｅｓｓｉｎｇ　【４］　ＴｒｅｌＬｅｔｔｅｒｓ，２００３，８５（９）：３１７－３２５．【ｄｏｉ：１０．１０１６／Ｓ００２０・Ｏｌ９０（Ｏ２）００４４７—７］　　Ｊ．Ｔｈｅ　ｆｕｌｌｙ　ｉｎｆｏｒｍｅｄ　ｐａｒｔｉｃｌｅ　ＳＷｆｌＸＩＴＩ：Ｓｉｍｐｌｅｒ，ｍａｙｂｅ　ｂｅｔｔｅｒ．ＩＥＥＥ　Ｔｒａｎｓ．ｏｎ　Ｅｖｏｌｕｔｉｏｎａｒｙ　【５］　Ｍｅｎｄｅｓ　Ｒ，Ｋｅｎｎｅｄｙ　Ｊ，ＮｅｖｅｓＣｏｍｐｕｔａｔｉｏｎ，２００４，８（３）：２０４－２１０＿【ｄｏｉ：１０．１　１０９／ＴＥＶＣ．２００４．８２６０７４１　　Ｓ，Ｖａｌｌｅ　ＹＤ，Ｖｅｎａｙａｇａｍｏｏｒｔｈｙ　ＧＫ，Ｈａｒｌｅｙ　ＲＧ．Ａ　ｃｏｍｐａｒｉｓｏｎ　ｏｆ　ＰＳＯ　ａｎｄ　ｂａｃｋｌ￣Ｉｒｏｐａｇａｔｉｏｎ　ｆｏｒ　ｔｒａｉｎｉｎｇ　ＲＢＦ　ｎｅｕｒａｌ　［６］　Ｍｏｈａｇｈｅｇｈｉｎｅｔｗｏｒｋｓ　ｆｏｒ　ｉｄｅｎｔｉｉｃａｔｆｉｏｎ　ｏｆ　ａ　ｐｏｗｅｒ　ｓｙｓｔｅｍ　ｗｉｔｈ　ＳＴＡＴＣＯＭ．Ｉｎ：Ｓｈａｒｋａｗｉ　Ｍ，Ｌｅｒｍａｎ　Ｋ，Ｇａｌｓｔｙａｎ　Ａ，ｅｄｓ．Ｐｒｏｃ．ｏｆ　ｔｈｅ　ＩＥＥＥ　Ｓｗａｒｍｌｎｔｅｌ１．Ｓｙｒｕｐ．Ｐｉｓｃａｔａｗａｙ：ＩＥＥＥＰｒｅｓｓ，２００５．３８卜３８４．【ｄｏｉ：１０．１１０９／ＳＩＳ．２００５．１５０１６４６］　ｈａｒｔ　ＲＣ，Ｓｈｉ　Ｙ．Ｐａｒｔｉｃｌｅ　ｓｗａｒｍ　ｏｐｔｉｍｉｚａｔｉｏｎ：Ｄｅｖｅｌｏｐｍｅｎｔｓ，ａｐｐｌｉｃａｔｉｏｎｓ　ａｎｄ　ｒｅｓｏｕｒｃｅｓ．Ｉｎ：Ｐｈａｍ　Ｔ，ｅｄ．Ｐｒｏｃ．ｏｆ　ｔｈｅ　２００１　（７】　ＥｂｅｒＣｏｎｇｒｅｓｓ　ｏｎ　Ｅｖｏｌｕｔｉｏｎａｒｙ　Ｃｏｍｐｕｔａｔｉｏｎ．Ｐｉｓｃａｔａｗａｙ：ＩＥＥＥ　Ｐｒｅｓｓ，２００１．８１—８６．【ｄｏｉ：１０．１１０９／ＣＥＣ．２００１．９３４３７４】　　Ｙ，Ｅｂｅｒｈａｒｔ　ＲＣ．Ｆｕｚｚｙ　ａｄａｐｔｉｖｅ　ｐａｒｔｉｃｌｅ　ｓｗａｒｌｎ　ｏｐｔｉｍｉｚａｔｉｏｎ．Ｉｎ：Ｐｈａｍ　Ｔ，ｅｄ．Ｐｒｏｃ．ｏｆ　ｔｈｅ　２００１　Ｃｏｎｇｒｅｓｓ　ｏｎ　Ｅｖｏｌｕｔｉｏｎａｒｙ　［８］　ＳｈｉＣｏｍｐｕｔａｔｉｏｎ．２００１．１０１－１０６－【ｄｏｉ：１０．１１０９／ＣＥＣ．２００１．９３４３７７】　ｏｒ　Ｓ，Ｖｅｎａｙａｇａｍｏｏｒｔｈｙ　ＧＫ，Ｇｕｄｉｓｅ　ＶＧ．Ｏｐｔｉｍａｌ　ｐｓｏ　ｆｏｒ　ｃｏｌｌｅｃｔｉｖｅ　ｒｏｂｏｔｉｃ　ｓｅａｒｃｈ　ａｐｐｌｉｃａｔｉｏｎｓ．Ｉｎ：Ｉｓａｓｉ　Ｐ，Ｈｅｍａｎｄｅｚ　ＪＣ，　【９］　ＤｏｃｔＣｌｒｋ　ａＪＡ．ｅｄｓ．Ｐｒｏｃ．ｏｆｔｈｅ　ＣＥＣ　２００４　Ｃｏｎｇｒｅｓｓ　ｏｎ　Ｅｖｏｌｕｔｉｏｎａｒｙ　Ｃｏｍｐｕｔａｔｉｏｎ．Ｐｉｓｃａｔａｗａｙ：ＩＥＥＥ　Ｐｒｅｓｓ，２００４．１３９０—１３９５．【ｄｏｉ：１０．　１　１０９／ＣＥＣ．２００４．１３３１０５９】　ｊｅｎｅｊａｄ　Ｍ，Ａｆｓｈｉｎｍａｎｅｓｈ　Ｆ，Ｍａｒａｎｄｉ　Ａ，Ａｒａａｂｉ　ＢＮ．Ｉｎｔｅｌｌｉｇｅｎｔ　ｐａｒｔｉｃｌｅ　ｓｗａｒｌＴｌ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｕｓｉｎｇ　Ｑ—ｌｅａｒｎｉｎｇ．Ｉｎ：Ｓｈｉ　ＹＨ，　［１Ｏ】　ＫｈａＡｒａｂｓｈａｈｉ　Ｐ．ｅｄｓ．Ｐｒｏｃ．ｏｆ　ｔｈｅ　ＩＥＥＥ　Ｓｗａｒｍ　Ｉｎｔｅｌ１．Ｓｙｍｐ．Ｐｉｓｃａｔａｗａｙ：ＩＥＥＥ　Ｐｒｅｓｓ，２００６．７－１２．　ｈｙ　Ｇ．Ｉｍｐｒｏｖｉｎｇ　ｔｈｅ　ｐｅｒｆｏｒｍ【１１】　Ｄｏｃｔｏｒ　Ｓ，Ｖｅｎａｙａｇａｍｏｏｒｔａｎｃｅ　ｏｆ　ｐａｒｔｉｃｌｅ　ｓｗａｒ／ｎ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｕｓｉｎｇ　ａｄａｐｔｉｖｅ　ｃｒｉｔｉｃｓ　ｄｅｓｉｇｎｓ．Ｉｎ：　Ｓｈａｒｋａｗｉ　Ｍ，Ｌｅｒｍａｎ　Ｋ，Ｇａｌｓｔｙａｎ　Ａ，ｅｄｓ．Ｐｒｏｃ．ｏｆ　ｔｈｅ　ＩＥＥＥ　Ｓｗａｒｍ　Ｉｎｔｅｌ１．Ｓｙｍｐ．Ｐｉｓｃａｔａｗａｙ：ＩＥＥＥ　Ｐｒｅｓｓ，２００５．３９３—３９６．【ｄｏｉ：１０．　１　１０９／ＳＩＳ．２００５．１５０１６４９］　［１２】　Ｚｈａｎｇ　Ｗ，Ｌｉｕ　Ｙ，Ｃｌｅｒｃ　Ｍ．Ａｎ　ａｄａｐｔｉｖｅ　ＰＳＯ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｒｅａｃｔｉｖｅ　ｐｏｗｅｒ　ｏｐｔｉｍｉｚａｔｉｏｎ．Ｉｎ：Ｗｏｎｇ　ＫＰ，ｅｄ．Ｐｒｏｃ．ｏｆ　ｔｈｅ　６ｔｈ　Ｉｎｔ’Ｉ　Ｃｏｎｆｉ　ｏｎ　Ａｄｖａｎｃｅｓ　ｉｎ　Ｐｏｗｅｒ　Ｓｙｓｔｅｍ　Ｃｏｎｔｒｏｌ，Ｏｐｅｒａｔｉｏｎ　ａｎｄ　Ｍａｎａｇｅｍｅｎｔ．Ｈｏｎｇ　Ｋｏｎｇ：Ｉｎｓｔｉｔｕｔｉｏｎ　ｏｆ　Ｅｌｅｃｔｒｉｃａｌ　Ｅｎｇｉｎｅｅｒｓ，２００３．　３０２－３０７．　　Ｙ，Ｃｈｕｎｇ　ＨＳ．Ａｄａｐｔｉｖｅ　ｐａｒｔｉｃｌｅ　ＳＷａｌＴＵ　ｏｐｔｉｍｉｚａｔｉｏｎ．ＩＥＥＥ　Ｔｒａｎｓ．ｏｎ　Ｓｙｓｔｅｍ，Ｍａｎ，ａｎｄ　Ｃｙｂｅｍｅｔｉｃｓ，２００９，　【１３】　Ｚｈａｎ　ＺＨ，Ｚｈａｎｇ　Ｊ，Ｌｉ３９（６）：１３６２—１３８１＿【ｄｏｉ：１０．１１０９／ＴＳＭＣＢ．２００９．２０１５９５６】　ｅ　ＸＦ，Ｚｈａｎｇ　ＷＪ，Ｙａｎｇ　ＺＬ．Ａ　ｄｉｓｓｉｐａｔｉｖｅ　ｐａｒｔｉｃｌｅ　ｓｗａｒｍ［１４】　Ｘｉ　ｏｐｔｉｍｉｚａｔｉｏｎ．Ｉｎ：Ｔｕｒｎｅｒ　Ｋ，Ｗｏｌｐｅｒｔ　Ｄ，ｅｄｓ．Ｐｒｏｃ．ｏｆ　ｔｈｅ　ＩＥＥＥ　Ｉｎｔ’１　Ｃｏｎｆｉ　ｏｎＥｖｏｌｕｔｉｏｎａｒｙＣｏｍｐｕｔａｔｉｏｎ．Ｐｉｓｃａｔａｗａｙ：ＩＥＥＥ　Ｐｒｅｓｓ，２００２．１４５６－１４６１．【ｄｏｉ：１０．１１０９／ＣＥＣ．２００２．１００４４５７】　ｎａｗｅｅｒａ　Ａ。Ｈａｌｇａｍｕｇｅ　ＳＫ，Ｗａｔｓｏｎ　ＨＣ．Ｓｅｌｆ－Ｏｒｇａｎｉｚｉｎｇ　ｈｉｅｒｒｃｈｉａｃａｌ　ｐａｒｔｉｃｌｅ　ｓｗａｒｌｎ　ｏｐｔｉｍｉｚｅｒ　ｗｉｔｈ　ｔｉｍｅ—ｖａｒｙｉｎｇ　ａｃｃｅｌｅｒａｔｉｏｎ　【ｌ５】　Ｒａｔｃｏｅｆｆｉｅｎｔｓ．ＩＥＥＥ　Ｔｒａｎｓ．ｏｎ　Ｅｖｏｌｕｔｉｏｎａｒｙ　Ｃｏｍｐｕｔａｉｏｎ，２００４，８（３）：２４０－２５５．【ｄｏｉ：１０．１　１０９／ＴＥＶＣ．２００４．８２６０７１】　陶新民等：一种多尺度协同变异的粒子群优化算法　１８１５　［１６］Ｈｅ　Ｒ，Ｗａｎｇ　ＹＪ，Ｗａｎｇ　Ｑ，Ｚｈｏｕ　ＪＨ，Ｈｕ　ＣＹ．Ａｎ　ｉｍｐｒｏｖｅｄ　ｐａｒｔｉｃｌｅ　ｓｗａｒｍ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｂａｓｅｄ　ｏｎ　ｓｅｌｆ－ａｄａｐｔｉｖｅ　ｅｓｃａｐｅ　ｖｅｌｏｃｉｔｙ．　Ｊｏｕｒｎａｌ　ｏｆ　Ｓｏｆｔｗａｒｅ，２００５，１６（１２）：２０３６—２０４４（ｉｎ　Ｃｈｉｎｅｓｅ　ｗｉｔｈ　Ｅｎｇｌｉｓｈ　ａｂｓｔｒａｃｔ）．ｈｔｔｐ：ｌｌｗｗｗ．ｊｏｓ．ｏｒｇ．ｏｎ／１０００．９８２５／１６／２０３６．ｈｔｍ　［ｄｏｉ：１０．１３６０￣ｏｓ１６２０３６］　【１７］Ｔａｏ　ＸＭ，Ｘｕ　Ｊ，Ｙａｎｇ　ＬＢ．Ｉｍｐｒｏｖｅｄ　ｃｌｕｓｔｅｒ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　ｋ－ｍｅａｎｓ　ａｎｄ　ｐａｒｔｉｃｌｅ　ｓｗａｒｍ　ｏｐｔｉｍｉｚａｔｉｏｎ．Ｊｏｕｒｎａｌ　ｏｆＥｌｅｃｔｒｏｎｉｃｓ＆　Ｉｎｆｏｒｍａｔｉｏｎ　Ｔｅｃｈｎｏｌｏｇｙ，２０１０，３２（１）：９２－９７（ｉｎ　Ｃｈｉｎｅｓｅ　ｗｉｔｈ　Ｅｎｇｌｉｓｈ　ａｂｓｔｒａｃｔ）．　●Ａ　［１８］Ｐｅｎｇ　Ｙ，Ｐｅｎｇ　ＸＹ，Ｌｉｕ　ＺＱ．Ｓｔａｔｉｓｔｉｃ　ａｎａｌｙｓｉｓ　ｏｎ　ｐａｒａｍｅｔｅｒ　ｅｆｆｉｃｉｅｎｃｙ　ｏｆｐａｒｔｉｃｌｅ　ｓｗａｒｌｎ　ｏｐｔｉｍｉｚａｔｉｏｎ．Ａｃｔａ　Ｅｌｅｃｔｒｏｎｉｃａ　Ｓｉｎｉｃａ，２００４，　３２（２）：２０９－２１３（ｉｎ　Ｃｈｉｎｅｓｅ　ｗｉｔｈ　Ｅｎｇｌｉｓｈ　ａｂｓｔｒａｃｔ）．　附中文参考文献：　［１６］赫然，王永吉，王青，周津慧，胡陈勇．一种改进的自适应逃逸微粒群算法及实验分析．软件学报，２００５，１６（１２）：２０３６—２０４４　ｈｔｔｐ：／／ｗｗｗ．ｊｏｓ．ｏｒｇ．ｃｎ／１０００—９８２５／Ｉ６／２０３６．ｈｔｍ［ｄｏｉ：１０．１３６０／ｊｏｓ１６２０３６］　【１７】陶新民，徐晶，杨立标，刘玉．一种改进的粒子群和Ｋ均值混合聚类算法．电子与信息学报，２０１０，３２（Ｉ）：９２—９７．　ｔ１８］彭宇，彭喜元，刘兆庆．微粒群算法参数效能的统计分析．电子学报，２００４，３２（２）：２０９—２１３．　陶新Ｆｉ￣（１９７３一），男，安徽蚌埠人，博士，副　刘玉（１９８５一），男，硕士，主要研究领域为智　能计算，信号处理．　教授，主要研究领域为进化计算，网络安　全，智能信号处理．　刘福荣（１９７Ｏ一），女，博士，副教授，主要研　究领域为故障诊断，群智能计算，人工　智能．　■一　信号处理，模式识别．　童智靖（１９８５一），男，硕士，主要研究领域为