雙尺度協(xié)同變異的離散粒子群算法

陶新民，王妍，趙春暉，劉玉

(哈爾濱工程大學信息與通信工程學院，黑龍江哈爾濱150001)

粒子群優(yōu)化(particle swarmoptimization，PSO)是Kennedy于1995年提出的一種群體智能優(yōu)化方法，具有概念簡單、調節(jié)參數(shù)少及全局收斂能力強等優(yōu)勢，得到了學術界的認可［1-2］.目前在工程設計和工業(yè)生產(chǎn)優(yōu)化等領域得到了成功的應用.PSO算法適合求解非線性連續(xù)優(yōu)化問題，為了將其用于解決離散問題，Kennedy于1997年提出解決0-1規(guī)劃問題的離散粒子群優(yōu)化算法(discrete particle swarmoptimization algorithm，DPSO)［3-5］.

然而傳統(tǒng)離散粒子群算法具有收斂精度低等問題［6-7］，因此，國內外學者提出各種方法對其性能進行改進.主要改進有以下3個方向:1)通過設置自適應的控制參數(shù)等手段來影響粒子的移動軌跡，改進算法的性能.如文獻［8］采用慣性權重線性下降法，使算法在進化初期搜索較大的解空間，后期在較小的區(qū)域精細搜索.文獻［9］設計了自適應的最大速度閾值參數(shù)，使粒子在搜索初期傾向于全局搜索，后期傾向于當前最優(yōu)解附近的局部搜索，有效實現(xiàn)粒子全局和局部搜索性能的平衡(velocity change discrete particle swarmoptimization，VCDPSO).2)通過增強粒子擺脫局部極小解的能力改進算法的性能.如文獻［10］通過對慣性因子采用自適應擾動機制來增強粒子群跳出局部最優(yōu)的能力(introducingdynamic diversity into a discrete particle swarmoptimization，DDPSO).3)通過增加粒子群多樣性，能擺脫群體陷入局部極小的可能，從而提高了搜索質量［11-12］.然而上述改進算法都是基于連續(xù)PSO算法易陷入局部極小值為出發(fā)點提出的，事實上DPSO算法的進化過程與連續(xù)PSO算法截然不同，上述連續(xù)狀態(tài)下的相關改進算法并不適合離散粒子群算法［13］.文獻［14］通過對DPSO中粒子的速度變化進行分析，提出一種雙速度狀態(tài)跟蹤的DPSO算法(novel binary particle swarmoptimization，NDPSO)，消除了原有算法對參數(shù)過于敏感的缺點，但由于算法增加了粒子狀態(tài)改變的隨機性，其性能受到影響.文獻［15］在分析DSPO算法粒子狀態(tài)轉移情況后，提出一種不同的離散化方法(Modifying diversity particle swarmoptimization，MDPSO)，降低了粒子在最優(yōu)解附近的發(fā)散性，然而也使算法易陷入局部最優(yōu).因此如何在提高算法局部搜索能力的同時，不影響算法逃出局部最優(yōu)解的能力值得深入研究.

本文在分析了傳統(tǒng)DPSO算法粒子狀態(tài)轉移情況的基礎上，提出一種雙尺度協(xié)同變異的離散粒子群算法(discrete particle swarmoptimization based on double-scale cooperation mutation，DSVMDPSO).該算法對當前最優(yōu)粒子進行粗細2種尺度的速度變異，這樣在提高算法局部開采能力的同時，保持了算法勘探能力，使其能有效逃出局部最優(yōu)解的同時提高了解的精度.

1 離散粒子群算法描述

實值粒子群優(yōu)化算法將優(yōu)化問題的每個潛在解看作搜索空間的一個“粒子”，粒子的適應值取決于優(yōu)化目標函數(shù)的值.每個粒子在搜索時根據(jù)自身的歷史最好點和群體內其他粒子的最好點進行狀態(tài)變化.為處理離散型優(yōu)化問題，Kennedy對實值粒子群算法進行修正，提出了二進制粒子群算法［3］.

設種群中有L個粒子，N維離散空間中，粒子i在時刻t的速度、位置、個體最好位置和全局最好位置分別用)表示，那么粒子i速度和位置的各維分量迭代公式［3］為

式中:i=1，2，…，L;j∈{1，2，…，N}表示粒子編碼中分量的維數(shù);r1j(t)和r2j(t)是(0，1)上均勻分布的隨機數(shù);w、c1和 c2是權重及加速系數(shù);ρ～U［0，1］是(0，1)區(qū)間上均勻分布的隨機變量;sig()表示sigmoid函數(shù)，本文取sig(x)=.文獻［7］規(guī)定粒子的最大速度|vmax|=4，這樣 0.018≤sig(vij(t+1))≤0.982.

由文獻［14-15］對粒子運動軌跡的分析可知，在個體極值和全局極值不相等時，粒子會在2個極值間來回震蕩，當c1和c2相等時粒子趨于隨機搜索，勘探能力較強，直到2個極值趨于一致;在2個極值相等且粒子不等于這2個極值的情況下，粒子會呈現(xiàn)向極值收斂的趨勢，逐漸向2個極值解逼近，勘探能力同樣較強;而當粒子收斂到全局最優(yōu)解時，如果w＞1時，粒子會隨著迭代而保持原有的狀態(tài)，變異的可能性降低，趨于陷入局部極值解;如果w≤1，則隨著迭代次數(shù)的增加，w會使當前粒子的速度趨于零，即使得當前粒子產(chǎn)生變異的概率趨近于0.5，很快發(fā)散出去，無法進行有效的局部搜索，如圖1所示.因此提高算法在最優(yōu)解附近的局部搜索能力，同時保持算法逃逸局部最優(yōu)解的能力是傳統(tǒng)DPSO算法需要解決的首要問題.

圖1 DPSO算法在最優(yōu)解附近進化示意Fig.1 Evolution of DPSO near optima

2 雙尺度協(xié)同變異的離散粒子群算法

我們知道變異操作能幫助算法逃出局部最優(yōu)解［18-20］，但根據(jù)DPSO算法的產(chǎn)生機理可知，在進化后期，最優(yōu)解往往存在于當前最優(yōu)解周圍，大尺度變異雖然有利于算法逃出局部最優(yōu)解，但無法保證逃逸后的新位置位于全局最優(yōu)解附近，在重新迭代時，因迭代次數(shù)的限制而無法收斂到全局最優(yōu)解.小尺度變異雖然有利于進行局部搜索，但又易使算法陷入局部極值解.因此如何設計變異尺度是協(xié)調離散粒子群算法勘探和開采能力的關鍵.

2.1 雙尺度協(xié)同變異算子

設粗尺度變異算子中包括的尺度個數(shù)為M，初始值可隨機設定為速度取值區(qū)間的隨機值:

隨迭代數(shù)增加，粗尺度變異算子按如下方式調整:

Re是取實部函數(shù)，K為當前進化代數(shù)，W是解空間的寬度，這里離散微粒群算法的速度范圍為［-5，5］，因此W取值為10.D的取值控制著震蕩的頻率，根據(jù)實驗統(tǒng)計設置為

設細尺度變異算子中包括的尺度個數(shù)為N，細尺度變異算子的初始值可隨機設定為W/4:

隨迭代數(shù)增加，細尺度變異算子按如下方式調整:

式中:C的取值與求解精度有關，控制著變異算子下降的速度，其值越小下降的越緩慢，這里取值為2.

如圖2為雙尺度協(xié)同變異算子隨迭代次數(shù)的變化，通過雙尺度協(xié)同變異算子能實現(xiàn)速度取值空間的覆蓋，如同粗細不同的顯微鏡，粗尺度變異算子好像一個粗鏡頭，能幫助算法快速定位到最優(yōu)解區(qū)域，具有一定的空間勘探能力;小尺度如同細的顯微鏡，對找到的目標進行細致觀察，在進化后期實現(xiàn)最優(yōu)解附近的精確搜索，具有較強的開采能力.

圖2 雙尺度協(xié)同變異算子隨迭代數(shù)變化曲線Fig.2 The curves of double-scale cooperation mutation operator with Iterations＇increasing

2.2 慣性權重參數(shù)設定

2.3 MSCMPSO 算法流程

1)算法的參數(shù)初始化設定;

2)按照離散粒子群算法式(1)進化;

3)根據(jù)式(2)進行粒子狀態(tài)的計算;

4)計算當前最優(yōu)解及每個粒子的個體極值解;

5)根據(jù)式(3)～(7)計算雙尺度協(xié)同變異算子值;

6)對當前最優(yōu)解的速度進行粗細2種尺度的變異，根據(jù)式(2)計算每一個粒子狀態(tài)，比較所有變異粒子的適應值，如果最好的適應值優(yōu)于當前最優(yōu)解，則將其替換為為當前新的最優(yōu)解;

7)循環(huán)直到終止條件.

3 算法優(yōu)化性能分析

設算法的變異尺度M、N都為5，選擇DeJong評測函數(shù)進行優(yōu)化，函數(shù)維度為20，每一維變量的編碼為20，這樣一個粒子的整個維度為400.

算法進行多尺度速度變異，計算每一個尺度速度變異的粒子與原有粒子編碼的海明距離的平均值，取迭代5次的結果如圖3所示.從圖中可以看出每次迭代的變異都是在不同大小的海明距離下進行的，這樣就保證了粒子會以不同大小步長在粒子取值空間進行搜索，這樣既保證了算法局部開采能力，同時也保證了算法逃逸局部極值解的能力.

圖3 與原有粒子編碼海明距離的平均值Fig.3 A mean of Hamming distance

4 實驗結果及分析

4.1 測試數(shù)據(jù)及實驗設計

為了分析本文算法的優(yōu)化性能，選擇文獻［16］和文獻［17］的5個Benchmark函數(shù)問題進行數(shù)值實驗，并與 DPSO 和其改進算法 DDPSO［10］/NDPSO［14］/MDPSO［15］及 VCDPSO［9］進行對比實驗.所有算法中 w在［0.9，0.4］隨代數(shù)線性遞減;c1、c2均為1，DDPSO 的擾動參數(shù) Pv=0.12，VCDPSO 的最大速度限制值的內部協(xié)調參數(shù)為 1.2，本文算法M=5，N=5，種群規(guī)模均為20，函數(shù)維度設置為20，每一位變量的編碼長度為20，每次運行2 000代，對每一個函數(shù)獨立運行30次.

4.2 基于單模態(tài)函數(shù)優(yōu)化性能對比實驗

圖4反映了不同 DPSO算法分別對 Delong、Rosenbrak函數(shù)進行優(yōu)化時適應度值隨迭代次數(shù)的變化圖.針對單模態(tài)函數(shù)優(yōu)化問題的實驗結果.從圖4(a)可以看出，對于DeJong函數(shù)本文算法隨迭代次數(shù)迅速向著最優(yōu)解區(qū)域靠近.對于復雜的單模態(tài)Rosenbrock函數(shù)山谷僅給算法提供很少的信息，使傳統(tǒng)DPSO算法很難在短時間內辨別搜索方向，易陷入局部最優(yōu).而圖4(b)表明本文算法采用雙尺度速度變異能夠有效地逃逸出局部極值點，使得算法能在短時間找到正確的搜索方向，下降速度較快.同時算法后期，由于細尺度變異使得算法在最優(yōu)解附近進行更加詳盡的搜索，提高了解的精度.

表1顯示了單模態(tài)函數(shù)問題的對比實驗結果，從各算法的最優(yōu)值和最差值的實驗結果可以看出，本文算法在所有函數(shù)上均由于其他算法，在Delong函數(shù)和Rosenbrock函數(shù)上最優(yōu)解搜索成功率達100%、94%.對于復雜的Rosenbrock函數(shù)問題，各個算法單次結果存在很大差異，由于函數(shù)的特殊性質以及隨機變異的引入，反而降低了DDPSO算法的搜索性能.VCDPSO由于采用了數(shù)值為1的權重系數(shù)以及變化速度極值的方式，因此經(jīng)過一定的迭代后也逃出了局部極小解.而本文提出的DSVMDPSO算法能夠在算法初始階段就通過粗尺度變異定位到全局最優(yōu)解區(qū)域，找到進化方向且通過細尺度速度變異進行局部精確解搜索.

圖4 不同DPSO算法對Delong和Rosenbrock函數(shù)優(yōu)化性能對比Fig.4 Comparison of different DPSO on Delong and Rosenbrock function

表1 DSVMDPSO和其他DPSO算法在單模態(tài)Benchmark問題上的數(shù)值對比Table 1 Comparison of the results on single-mode Benchmark function

4.3 基于多模態(tài)函數(shù)優(yōu)化性能對比實驗

多模態(tài)函數(shù)對比實驗結果如圖5所示.對于多模態(tài)Griewank函數(shù)，本文DSVMDPSO算法能夠在開始階段尋到全局最優(yōu)解區(qū)域，其全局搜索能力明顯優(yōu)于其他算法.多模態(tài)Rastrigrin函數(shù)是一個典型的用來測試算法全局搜索性能的函數(shù)，從圖5(b)和表2可以看出，雖然本文算法沒有在有限次的運行中都能找到近似全局最優(yōu)解0，但是只要給予足夠長的迭代次數(shù)，算法總能逃出局部極小點找到全局最優(yōu)解.圖5(c)為20維Ackley函數(shù)的運行結果，DSVMDPSO算法同樣能在算法初期尋到全局最優(yōu)解區(qū)域，然后利用DPSO進化和細尺度速度變異算子實現(xiàn)最優(yōu)解附近的局部精確解搜索.從表2的結果可以看出，本文算法大大改善了算法全局解尋優(yōu)能力及提高了解的精度，無論是傳統(tǒng)DPSO還是其他改進算法都不具備良好的穩(wěn)定性，而本文算法相對于其他算法，其穩(wěn)定性大大提高.

圖5 不同DPSO算法對Griewank、Rastrigrin和Ackley函數(shù)優(yōu)化性能對比Fig.5 Comparison of different DPSO on Griewank，Rastrigrin and Ack ley function

表2 DSVMDPSO和其他DPSO算法在多模態(tài)Benchmark問題上的數(shù)值對比Table 2 Comparison of the results on multimode Benchmark function

5 結論

本文提出了一種雙尺度協(xié)同變異的離散粒子群算法，結合實驗得到如下結論:

1)針對傳統(tǒng)離散粒子群算法的狀態(tài)轉移過程中存在最優(yōu)解區(qū)域局部搜索能力差的不足，提出一個雙尺度速度變異算子，該算子可以有效實現(xiàn)在最優(yōu)解附近精確的局部搜索，同時在算法初期利用粗尺度速度變異可以使粒子群進行發(fā)散式的全局搜索，從而快速定位到全局最優(yōu)解區(qū)域，在算法后期，由于粗尺度速度變異的震蕩性質在細尺度速度變異進行局部精確解搜索的同時，可幫助算法逃逸出局部極小解，實現(xiàn)算法勘探及開采能力的有機協(xié)調.

2)采用本文算法及其改進算法，對5個經(jīng)典Benchmark函數(shù)進行優(yōu)化，實驗結果表明本文算法在全局搜索性能及最優(yōu)解精度方面都有顯著提高.

需要指出的是，本文尚未考慮各種參數(shù)對算法性能的影響，這也是本課題下一階段研究的重點.

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

［2］陶新民，徐晶.改進的多種群協(xié)同進化微粒群優(yōu)化算法［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］潘全科，王凌，高亮.離散微粒群優(yōu)化算法的研究進展［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］張國富，蔣建國，夏娜.基于離散粒子群算法求解復雜聯(lián)盟生成問題［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］鐘一文，寧正元，蔡榮英.一種改進的離散粒子群優(yōu)化算法［J］.小型微型計算機系統(tǒng)，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］鐘一文，蔡榮英.求解二次分配問題的離散粒子群優(yōu)化算法［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］余伶俐，蔡自興.改進混合離散粒子群的多種優(yōu)化策略算法［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］許金友，李文立，王建軍.離散粒子群算法的發(fā)散性分析及其改進研究［J］.系統(tǒng)仿真學報，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混沌粒子群算法及其在結構優(yōu)化決策中的應用［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］楊光友，陳定方，周國柱.粒子個體最優(yōu)位置變異的粒子群優(yōu)化算法［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］王艷，曾建潮.多目標微粒群優(yōu)化算法綜述［J］.智能系統(tǒng)學報，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］.智能系統(tǒng)學報，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］陳杰，潘峰，王光輝.粒子群優(yōu)化方法在動態(tài)優(yōu)化中的研究現(xiàn)狀［J］.智能系統(tǒng)學報，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.