應用小生境和反向學習策略的量子粒子群算法

李志鵬，李衛忠，江 洋，杜瑞超，劉 唐

(空軍工程大學 a.研究生院； b.防空反導學院， 西安 710051)

粒子群優化算法(PSO)是一種廣泛應用于工程領域優化求解的智能優化方法，與其他算法相比，簡單易行，易于理解，但面臨復雜的優化問題，基本粒子群算法存在早熟、易陷入局部最優和收斂速度慢等缺點[1]。針對這些問題，國內外學者對PSO算法做了很多研究，使算法性能得到優化，但對算法的易懂性、可操作性考慮較少。文獻[2-3]將結合量子力學與粒子群算法結合，提出了一種以變量δ勢阱為基礎的算法模型——量子粒子群(quantum particl swarm optimization,QPSO)算法。與PSO算法相比，該算法有更好的全局搜索能力，但慣性權值線性遞減的策略使算法仍易陷入局部極值，對于高維多極函數問題，算法在尋優能力、搜索精度、穩定性等方面有待改善。

本文提出一種應用小生境和反向學習策略的量子粒子群算法(quantum-behaved particle swarm optimization algorithm using niche and opposition-based learning,NOL-QPSO)，以可拓理論為基礎構造可拓粒子群算法模型，通過聚類在每代種群實現小生境的劃分；結合個體適應度動態共享技術，有效解決算法過早收斂的問題，增強尋優能力；此外，針對最優粒子自我學習能力受限的缺點，引入精英反向學習策略，將算法拓展到當前種群以外的搜索空間，以增強解空間的開發。

1 量子粒子群算法

在量子粒子群算法模型中，粒子被賦予了量子行為，其狀態通過波函數來描述。粒子在量子δ勢阱的基礎上不斷向局部吸引點靠近，粒子出現在空間某一處的概率通過求解薛定諤方程得出，從而利用蒙特卡羅模擬更新粒子位置，其方程具體描述為：

(1)

(2)

其中G是最大迭代次數。

QPSO的算法流程如下：

1) 初始化粒子群；

3) 求出個體適應度值xi(g)，并通過比較得到xi-best(g)；

4) 更新xbest(k)；

6) 位置更新：xi(g)=xi(g+1)，g=g+1；

7) 重復2)至6)，直到結束條件滿足。

2 應用小生境和反向學習策略的量子粒子群算法

2.1 基于可拓理論的小生境構造策略

QPSO算法用于具有多個局部極值的復雜優化問題時，常常會出現收斂速度慢或早熟等問題，因此本文考慮通過小生境策略增強算法的全局性。小生境是源于生物學的一個概念[4]，其基本思想是根據某種規則把種群劃分為若干子種群，各個子種群動態形成相對獨立的搜索域，從而在各搜索域對解空間內不同的局部最優點展開同步搜索，完成最終優化，避免了過早收斂或不同個體在同一空間出現過度搜索現象。該技術要考慮的關鍵問題之一是小生境的劃分，常用的方法是通過設定小生境半徑劃分子空間，這種方法雖簡單可行，但對于復雜問題的求解效果并不理想。本文以物元可拓理論[5]為基礎，采用可拓聚類算法構造小生境。

2.1.1 基本知識

設Q(k)=Xi,i=1,2,…,N}為含有N個樣本的初始種群，每個樣本特征維數為n，樣本I的數據模型可表示為

定義1Xi對類Sl的關聯度Kx(Sl)計算準則定義為

定義3 當l=Γ時，Ro與類SΓ的關聯度則為類SΓ的自關聯度，可表示為

式中：nΓ是類SΓ的樣本數目；Ki(SΓ)是類SΓ第i個樣本的關聯度。

2.1.2 小生境構造方法

步驟1 隨機選取k個待聚類樣本作為中心，形成k個初始類Sl,(l=1,2,…,k)。

步驟4 聚類調整完成后，更新各類中心物元，重新計算關聯度，重復新一輪的樣本歸類，直至歸類結果不變。

通過以上基于可拓理論的聚類過程，形成穩定多樣的小生境，各子種群在相對獨立的空間尋優，可以避免粒子群陷入局部極值，增強算法的全局性。

2.2 適應度共享和精英反向學習策略

在粒子群優化算法中，距最優點越近的粒子，其位置更新越會受到較大限制，導致粒子群只能在局部極值鄰域進行搜索，這是使粒子陷入局部最優和影響算法尋優精度的主要因素之一。因此，可以考慮通過強化精英粒子鄰域的搜索，優化算法性能。為提高算法的搜尋能力，本文在小生境技術的基礎上，在算法中引入共享函數和精英反向學習策略。

共享函數[6]最先用于遺傳算法中個體間相鄰關系的度量。文獻[7]在粒子群算法中引入共享函數，當搜索陷入局部最優時，將種群劃分為兩部分，其中一部分繼續對局部最優進行搜索，而另一部分則重新初始化，并通過定義共享適應度函數對尋優范圍加以限制，當個體再次陷入早熟區，則適當增大其適應度，促使粒子逸出。

引入共享函數，首先需要對個體相似度進行度量，常用的方法是利用hamming距離對個體進行度量。在進化算法中，hamming距離可以反映不同個體基因編碼間存在的差異，也可以對種群多樣性做出判斷。本文考慮以hamming距離為依據，選取距局部最優解較近的粒子，對適應度進行調整，從而能跳出早熟區做進一步尋優。但在迭代過程中，適應度更新后的個體可能會再次陷入原早熟區。為有效解決這一問題，本文利用共享距離D劃定共享區，提出一種適應度動態共享策略，對共享區內個體的適應度進行調節。

設在某次迭代中，含有若干粒子的群體收斂于Xlocal-best，個體i到Xlocal-best的距離用di表示，則：

(3)

(M為常數)

(4)

其中：dnew為新粒子距局部最優解Xlocal-best的距離；M為修正權值，可根據實際情況調整值的大小。不難看出：dnew越小，粒子距局部最優解越近，為其賦予越大的適應度，能夠使個體以更大概率突破局部限制，避免新群體再次陷入局部最優。

另外，在量子粒子群算法中，全局最優粒子往往會包含更多引導種群向全局最優收斂的價值信息，對種群的進化方向具有重要的引導作用。最優粒子在當前種群中的自我學習能力受限，會影響算法的全局搜索能力，因此有必要拓展到當前種群以外的搜索空間對全局最優粒子進行深度挖掘。本文考慮引入精英反向學習策略，粒子群每達到一定迭代次數，對全局最優粒子進行一次反向學習，增強解空間的開發，提高算法精度。

(5)

精英反向粒子的引入，有效拓展了搜索空間，在一定程度上打破原小生境，促進種群進化。在本文算法中，利用迭代次數確定精英反向粒子的引入時機，即每迭代N次，算法進行一次精英粒子反向學習，保證在一定概率范圍內引導種群向更優位置進化。

3 仿真實驗與結果分析

算法性能的優劣主要體現在尋優精度和收斂速度上。為評估算法性能，本文參照文獻[7]選取CEC2005 benchmark測試函數，分別對PSO算法、QPSO算法、文獻[9]提出的CLQPSO算法及本文的NOL-QPSO算法進行測試。實驗操作在 Intel(R) Core(TM) i7-4790 CPU@ 3.60 GHz計算機平臺上，利用64位Windows 7操作系統中的MATLAB 2014軟件編程實現。

測試函數如表1所示。Sphere函數為單峰曲面函數，其最小值0在零點取得；Rosenbrock函數是一個多峰值函數，其全局最優點在(1,1,…,1)取得，處于一個狹長、平滑的拋物線山谷內；Schaffer函數是復雜的二維函數，在解空間里有無數個極小值點，具有強烈的震蕩性；最小值0在(0,0)處取得，對其全局最優值的搜索難度較大；Rastrigrin函數和Griewank函數都是典型的非線性多模態函數，峰形高低起伏呈跳躍性。其中，Griewank函數搜索空間較廣，極小值的數目與維數有關，是優化算法常用的測試函數。Ackley函數是由數函數疊加適度放大后的余弦得到的連續性函數，余弦波的調制在相對平坦的曲面形成波峰，優化算法對其尋優時易陷入局部最優。

實驗結果如表2所示。由表2可見：PSO算法在運行中常陷入局部極值，其性能在幾種算法中是最差的；與PSO相比，QPSO算法的收斂速度明顯加快，但仍易陷入局部最優，搜索性較差；CLQPSO算法采用Levy概率分布的飛行策略，擴大了搜索空間，搜索到全局最優解的概率較高，但收斂速度有待改善。NOL-QPSO算法在大多數情況下表現良好，在尋優精度上，除了Schaffer函數、Rosenbrock函數的最差值和Griewank函數的最優值次于CLQPSO算法外，其余各值均優于其他算法。另外，NOL-QPSO算法搜索到全局最優解的概率明顯提高，到達門限值的平均迭代次數更少。從算法的平均運行時間來看，本文提出的算法與其他算法差別不大，在允許范圍內取得了更好的優化效果。

表1 測試函數

表2 實驗數據

測試函數算法最優值最差值均值方差運行次數/收斂次數到達門限值平均迭代次數平均時間SpherePSO1．62E-063．51E-055．27E-046．12E-0450/5059．263．27QPSO8．15E-109．95E-023．54E-035．24E-0350/5040．232．85CLQPSO4．87E-134．55E-112．65E-114．31E-1250/5051．773．41NOL-QPSP9．76E-201．64E-111．02E-172．08E-2250/5045．552．99RosenbrockPSO5．87E-089．62E-048．24E-045．16E-0350/4768．248．46QPSO4．52E-091．01E-012．04E-025．06E-0250/4656．656．52CLQPSO8．12E-206．25E-181．77E-188．00E-1950/4774．125．51NOL-QPSP9．01E-223．27E-175．96E-202．86E-2050/4861．745．20SchafferPSO2．66E+045．24E+043．57E+042．17E+0350/4487．257．14QPSO6．15E-115．95E-021．54E-024．67E-0250/4641．413．51CLQPSO4．62E-217．25E-181．62E-198．25E-1950/5058．235．65NOL-QPSP8．46E-241．64E-174．92E-222．08E-2250/5035．744．78RastriginPSO4．65E+069．15E+065．29E+066．81E+0450/41168．659．62QPSO1．46E-028．29E-024．91E-024．22E-0250/4354．125．25CLQPSO1．92E-084．27E-083．01E-083．00E-0850/49184．656．79NOL-QPSP5．94E-176．77E-142．41E-145．88E-1450/4951．637．52GriewankPSO3．15E+043．69E+043．41E+045．15E+0350/45214．859．14QPSO2．75E+001．05E+018．42E+004．88E+0050/4362．645．92CLQPSO1．58E-118．01E-022．41E-023．89E-0250/50235．205．12NOL-QPSP1．41E-085．44E-083．08E-082．88E-0850/5049．215．05AckleyPSO4．11E+042．49E+081．41E+082．10E+0850/47169．258．01QPSO5．06E+068．99E+067．85E+062．23E+0650/4756．269．55CLQPSO1．09E-105．29E-072．99E-075．33E-0750/49184．235．26NOL-QPSP8．29E-275．68E-226．72E-239．81E-2350/5042．506．52

4 結束語

本文以可拓理論為基礎構造算法模型，結合適應度動態共享和精英反向學習策略，提出一種改進的粒子群算法——NOL-QPSO。

1) 以可拓理論為基礎，將小生境策略用于量子粒子群算法，以改善算法的全局性。

2) 加入適應度動態共享環節，通過引入共享函數調整適應度，避免陷入早熟。

3) 通過測試函數實驗，驗證了本文所提算法的有效性。

本文算法表現出較好的性能，具有較強的適應能力，全局搜索性更加優越。對運行效率的改善，將是后續研究的重點之一。

[1] 任俊亮,邢清華,李強,等.采用自適應概率粒子群算法的反導預警資源調度方法[J].空軍工程大學學報(自然科學版),2014,15(6):45-48.

[2] SUN J,FENG B,XU W B.Particle swarm optimization with particle having quantum behavior[C]//Proceedings of Congress on Evolutionary Computation.Portland,USA:IEEE Press,2004:325-331.

[3] SUN J,XU W B,FENG B.Adaptive parameter control for quantum behaved particle Swarm optimization on individual level[C]//Proceedings of IEEE International Conference on Systems,Man And Cybernetics.Piscataway:IEEE Press,2005:3049-3054.

[4] 付強,王剛,王明宇,等.基于小生境遺傳算法的制導雷達誤差估計[J].空軍工程大學學報(自然科學版),2011,11(06):50-53.

[5] 楊春燕,蔡文.可拓學[M].北京:科學出版社,2014.

[6] 張珂,黃永峰,李星.一種基于適應度和節點聚類的P2P拓撲建模方法[J].電子學報,2010,38(7):1634-1640.

[7] 譚熠峰,孫婷婷,徐新民.基于動態因子和共享適應度的改進粒子群算法[J].浙江大學學報(理學版),2016,43(6):696-700.

[8] 邵鵬,吳志健,周炫余,等.基于折射原理反向學習模型的改進粒子群算法[J].電子學報,2015,43(11):2137-2144.

[9] 陳偉,周頔,孫俊,等.一種采用完全學習策略的量子行為粒子群優化算法[J].控制與決策,2012,27(5):719-723.