應(yīng)用小生境和反向?qū)W習(xí)策略的量子粒子群算法

李志鵬，李衛(wèi)忠，江 洋，杜瑞超，劉 唐

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

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

本文提出一種應(yīng)用小生境和反向?qū)W習(xí)策略的量子粒子群算法(quantum-behaved particle swarm optimization algorithm using niche and opposition-based learning,NOL-QPSO)，以可拓理論為基礎(chǔ)構(gòu)造可拓粒子群算法模型，通過聚類在每代種群實(shí)現(xiàn)小生境的劃分；結(jié)合個(gè)體適應(yīng)度動(dòng)態(tài)共享技術(shù)，有效解決算法過早收斂的問題，增強(qiáng)尋優(yōu)能力；此外，針對(duì)最優(yōu)粒子自我學(xué)習(xí)能力受限的缺點(diǎn)，引入精英反向?qū)W習(xí)策略，將算法拓展到當(dāng)前種群以外的搜索空間，以增強(qiáng)解空間的開發(fā)。

1 量子粒子群算法

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

(1)

(2)

其中G是最大迭代次數(shù)。

QPSO的算法流程如下：

1) 初始化粒子群；

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

4) 更新xbest(k)；

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

7) 重復(fù)2)至6)，直到結(jié)束條件滿足。

2 應(yīng)用小生境和反向?qū)W習(xí)策略的量子粒子群算法

2.1 基于可拓理論的小生境構(gòu)造策略

QPSO算法用于具有多個(gè)局部極值的復(fù)雜優(yōu)化問題時(shí)，常常會(huì)出現(xiàn)收斂速度慢或早熟等問題，因此本文考慮通過小生境策略增強(qiáng)算法的全局性。小生境是源于生物學(xué)的一個(gè)概念[4]，其基本思想是根據(jù)某種規(guī)則把種群劃分為若干子種群，各個(gè)子種群動(dòng)態(tài)形成相對(duì)獨(dú)立的搜索域，從而在各搜索域?qū)饪臻g內(nèi)不同的局部最優(yōu)點(diǎn)展開同步搜索，完成最終優(yōu)化，避免了過早收斂或不同個(gè)體在同一空間出現(xiàn)過度搜索現(xiàn)象。該技術(shù)要考慮的關(guān)鍵問題之一是小生境的劃分，常用的方法是通過設(shè)定小生境半徑劃分子空間，這種方法雖簡(jiǎn)單可行，但對(duì)于復(fù)雜問題的求解效果并不理想。本文以物元可拓理論[5]為基礎(chǔ)，采用可拓聚類算法構(gòu)造小生境。

2.1.1 基本知識(shí)

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

定義1Xi對(duì)類Sl的關(guān)聯(lián)度Kx(Sl)計(jì)算準(zhǔn)則定義為

定義3 當(dāng)l=Γ時(shí)，Ro與類SΓ的關(guān)聯(lián)度則為類SΓ的自關(guān)聯(lián)度，可表示為

式中：nΓ是類SΓ的樣本數(shù)目；Ki(SΓ)是類SΓ第i個(gè)樣本的關(guān)聯(lián)度。

2.1.2 小生境構(gòu)造方法

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

步驟4 聚類調(diào)整完成后，更新各類中心物元，重新計(jì)算關(guān)聯(lián)度，重復(fù)新一輪的樣本歸類，直至歸類結(jié)果不變。

通過以上基于可拓理論的聚類過程，形成穩(wěn)定多樣的小生境，各子種群在相對(duì)獨(dú)立的空間尋優(yōu)，可以避免粒子群陷入局部極值，增強(qiáng)算法的全局性。

2.2 適應(yīng)度共享和精英反向?qū)W習(xí)策略

在粒子群優(yōu)化算法中，距最優(yōu)點(diǎn)越近的粒子，其位置更新越會(huì)受到較大限制，導(dǎo)致粒子群只能在局部極值鄰域進(jìn)行搜索，這是使粒子陷入局部最優(yōu)和影響算法尋優(yōu)精度的主要因素之一。因此，可以考慮通過強(qiáng)化精英粒子鄰域的搜索，優(yōu)化算法性能。為提高算法的搜尋能力，本文在小生境技術(shù)的基礎(chǔ)上，在算法中引入共享函數(shù)和精英反向?qū)W習(xí)策略。

共享函數(shù)[6]最先用于遺傳算法中個(gè)體間相鄰關(guān)系的度量。文獻(xiàn)[7]在粒子群算法中引入共享函數(shù)，當(dāng)搜索陷入局部最優(yōu)時(shí)，將種群劃分為兩部分，其中一部分繼續(xù)對(duì)局部最優(yōu)進(jìn)行搜索，而另一部分則重新初始化，并通過定義共享適應(yīng)度函數(shù)對(duì)尋優(yōu)范圍加以限制，當(dāng)個(gè)體再次陷入早熟區(qū)，則適當(dāng)增大其適應(yīng)度，促使粒子逸出。

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

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

(3)

(M為常數(shù))

(4)

其中：dnew為新粒子距局部最優(yōu)解Xlocal-best的距離；M為修正權(quán)值，可根據(jù)實(shí)際情況調(diào)整值的大小。不難看出：dnew越小，粒子距局部最優(yōu)解越近，為其賦予越大的適應(yīng)度，能夠使個(gè)體以更大概率突破局部限制，避免新群體再次陷入局部最優(yōu)。

另外，在量子粒子群算法中，全局最優(yōu)粒子往往會(huì)包含更多引導(dǎo)種群向全局最優(yōu)收斂的價(jià)值信息，對(duì)種群的進(jìn)化方向具有重要的引導(dǎo)作用。最優(yōu)粒子在當(dāng)前種群中的自我學(xué)習(xí)能力受限，會(huì)影響算法的全局搜索能力，因此有必要拓展到當(dāng)前種群以外的搜索空間對(duì)全局最優(yōu)粒子進(jìn)行深度挖掘。本文考慮引入精英反向?qū)W習(xí)策略，粒子群每達(dá)到一定迭代次數(shù)，對(duì)全局最優(yōu)粒子進(jìn)行一次反向?qū)W習(xí)，增強(qiáng)解空間的開發(fā)，提高算法精度。

(5)

精英反向粒子的引入，有效拓展了搜索空間，在一定程度上打破原小生境，促進(jìn)種群進(jìn)化。在本文算法中，利用迭代次數(shù)確定精英反向粒子的引入時(shí)機(jī)，即每迭代N次，算法進(jìn)行一次精英粒子反向?qū)W習(xí)，保證在一定概率范圍內(nèi)引導(dǎo)種群向更優(yōu)位置進(jìn)化。

3 仿真實(shí)驗(yàn)與結(jié)果分析

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

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

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

表1 測(cè)試函數(shù)

表2 實(shí)驗(yàn)數(shù)據(jù)

測(cè)試函數(shù)算法最優(yōu)值最差值均值方差運(yùn)行次數(shù)/收斂次數(shù)到達(dá)門限值平均迭代次數(shù)平均時(shí)間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 結(jié)束語

本文以可拓理論為基礎(chǔ)構(gòu)造算法模型，結(jié)合適應(yīng)度動(dòng)態(tài)共享和精英反向?qū)W習(xí)策略，提出一種改進(jìn)的粒子群算法——NOL-QPSO。

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

2) 加入適應(yīng)度動(dòng)態(tài)共享環(huán)節(jié)，通過引入共享函數(shù)調(diào)整適應(yīng)度，避免陷入早熟。

3) 通過測(cè)試函數(shù)實(shí)驗(yàn)，驗(yàn)證了本文所提算法的有效性。

本文算法表現(xiàn)出較好的性能，具有較強(qiáng)的適應(yīng)能力，全局搜索性更加優(yōu)越。對(duì)運(yùn)行效率的改善，將是后續(xù)研究的重點(diǎn)之一。

[1] 任俊亮,邢清華,李強(qiáng),等.采用自適應(yīng)概率粒子群算法的反導(dǎo)預(yù)警資源調(diào)度方法[J].空軍工程大學(xué)學(xué)報(bào)(自然科學(xué)版),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] 付強(qiáng),王剛,王明宇,等.基于小生境遺傳算法的制導(dǎo)雷達(dá)誤差估計(jì)[J].空軍工程大學(xué)學(xué)報(bào)(自然科學(xué)版),2011,11(06):50-53.

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

[6] 張珂,黃永峰,李星.一種基于適應(yīng)度和節(jié)點(diǎn)聚類的P2P拓?fù)浣７椒╗J].電子學(xué)報(bào),2010,38(7):1634-1640.

[7] 譚熠峰,孫婷婷,徐新民.基于動(dòng)態(tài)因子和共享適應(yīng)度的改進(jìn)粒子群算法[J].浙江大學(xué)學(xué)報(bào)(理學(xué)版),2016,43(6):696-700.

[8] 邵鵬,吳志健,周炫余,等.基于折射原理反向?qū)W習(xí)模型的改進(jìn)粒子群算法[J].電子學(xué)報(bào),2015,43(11):2137-2144.

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