基于演化歷史信息的自變異協(xié)同量子行為粒子群優(yōu)化算法

趙 吉，傅 毅，梅 娟

(1.無錫環(huán)境科學(xué)與工程研究中心，江蘇無錫 214063； 2.江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院，江蘇無錫 214122)

基于演化歷史信息的自變異協(xié)同量子行為粒子群優(yōu)化算法

趙 吉1，2，傅 毅1，梅 娟1

(1.無錫環(huán)境科學(xué)與工程研究中心，江蘇無錫 214063； 2.江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院，江蘇無錫 214122)

提出一種基于演化歷史信息的自變異協(xié)同量子行為粒子群優(yōu)化算法(ESH-CQPSO ).該算法采用二維空間分割樹結(jié)構(gòu)記錄群體演化過程中的位置和適應(yīng)值，借助群體之間的協(xié)同機(jī)制確保增強(qiáng)搜索能力，提高優(yōu)化性能，防止過早收斂.通過空間分割機(jī)制可以獲得一個(gè)快速的近似適應(yīng)度函數(shù).這個(gè)近似值可以提高ESH-CQPSO中的變異策略，使得相應(yīng)的變異操作是一種無參數(shù)、多樣性的自適應(yīng)變異.對(duì)比其他傳統(tǒng)算法，通過對(duì)標(biāo)準(zhǔn)測(cè)試函數(shù)的實(shí)驗(yàn)結(jié)果表明，ESH-CQPSO算法在處理多峰和單峰測(cè)試函數(shù)時(shí)具有更好的優(yōu)化性能，收斂精度和收斂速度都得到了提高，證明該算法的有效性.

量子行為粒子群優(yōu)化；演化歷史信息；自適應(yīng)變異；二維空間分割；協(xié)同方式

1 引言

近年來，量子行為粒子群優(yōu)化算法(Quantum-behaved Particle Swarm Optimization,QPSO)[1]因?yàn)槠渌惴ê?jiǎn)單，優(yōu)化性能強(qiáng)而受到越來越多關(guān)注.類似于其他全局優(yōu)化算法[2]，QPSO也會(huì)受制于過早收斂至局部最優(yōu)的趨勢(shì)，這也是群體智能優(yōu)化算法的研究熱點(diǎn)，很多文獻(xiàn)都是圍繞這個(gè)問題展開的[3～6].深入研究發(fā)現(xiàn)，QPSO找到全局最優(yōu)解的能力主要取決于兩個(gè)方面：(1)跳出局部最優(yōu)點(diǎn)的能力;(2)探索搜索空間的能力.為此本文提出基于演化歷史信息的自變異協(xié)同量子行為粒子群優(yōu)化算法(Cooperative QPSO with adaptive mutation based on Entire Search History,ESH-CQPSO )以提高QPSO算法的優(yōu)化性能.

此前也有相關(guān)文獻(xiàn)提出了利用記憶的形式使用搜索歷史信息自適應(yīng)地引導(dǎo)搜索目標(biāo)[7～9]，但這些研究?jī)H僅使用了部分搜索歷史信息，而未使用的信息則被丟棄了.演化搜索歷史信息，包括估計(jì)解的位置和解的適應(yīng)值對(duì)于提高群體智能算法的性能都是有價(jià)值的信息.從直觀上看，它可以用來保持多樣性，引導(dǎo)搜索方向或指示有希望的搜索區(qū)域.此外，當(dāng)演化歷史信息中出現(xiàn)相同的最優(yōu)解時(shí)，它可以警告該搜索可能陷入局部最優(yōu).Yuen和Chow提出的非重復(fù)訪問機(jī)制[10]被應(yīng)用于遺傳算法(Genetic algorithm,GA)，從而保證非重復(fù)訪問遺傳算法(Continuous Non-revisiting Genetic Algorithm,cNrGA)中的解不會(huì)被重復(fù)訪問.實(shí)驗(yàn)證明cNrGA比大多數(shù)GA算法更加優(yōu)異.但該算法中的非重復(fù)訪問變異操作由于子空間限制而無法充分進(jìn)行搜索，為此引入?yún)f(xié)同進(jìn)化方法，利用二維空間分割機(jī)制，提出基于整個(gè)搜索空間帶有重疊子區(qū)域的自變異協(xié)同量子行為粒子群優(yōu)化算法，進(jìn)而促進(jìn)粒子的充分搜索能力以提高算法性能.

2 基于演化歷史信息的協(xié)同量子行為粒子群優(yōu)化算法

2.1 演化歷史信息方案

定義1 解x的子區(qū)域

假設(shè)x是搜索空間S中一個(gè)解，即x∈S，S被二維空間分割樹(Binary Space Portioning,BSP)T劃分為一組子區(qū)域H=∪ihi.如果x∈h并且h為T的一個(gè)葉節(jié)點(diǎn)，定義子區(qū)域h∈H為x的子區(qū)域.

在演化歷史信息方案中，所有訪問過的解的位置和適應(yīng)值[xi,f(xi)]都由BSP樹來保存.算法迭代過程中，整個(gè)搜索空間會(huì)被劃分為一組區(qū)域H.樹結(jié)構(gòu)中的每個(gè)節(jié)點(diǎn)代表了搜索空間的子區(qū)域.假設(shè)BSP樹中一個(gè)父節(jié)點(diǎn)P有兩個(gè)子節(jié)點(diǎn)m和n.子節(jié)點(diǎn)沿著第k維將P的子區(qū)域線性分割為兩個(gè)疊加的子區(qū)域，k的選取滿足m和n在k維上的距離最大，即k=argmax|m(k)-n(k)|.以這種方式，將QPSO算法之前產(chǎn)生的每個(gè)估計(jì)解記錄在樹的節(jié)點(diǎn)中.BSP樹在整個(gè)解過程中就記錄了搜索空間中的所有解，利用之前解的演化歷史信息對(duì)當(dāng)前解進(jìn)行分析.隨著迭代進(jìn)行，BSP樹會(huì)隨之增長(zhǎng).因?yàn)闃浣Y(jié)構(gòu)是依賴于每次迭代的解序列，所以BSP樹是一個(gè)隨機(jī)樹，每次迭代的拓?fù)浣Y(jié)構(gòu)都不同.

算法1 解x重疊子區(qū)域的偽代碼

輸入:(1)BSP樹T,(2)估計(jì)解x∈RD(D為維數(shù)),(3)搜索空間S

1.h=Πj[lj,uj]:=S

2. Curr-node:=root node ofT

3. While (Curr-node有左右兩個(gè)子節(jié)點(diǎn)m和n)

4. 根據(jù)i=argmax|m(i)-n(i)|獲得分割維度i，其中i=1,…,D

5. If (|m(i)-x(i)|≤|n(i)-x(i)|)

6. Curr-node:=child nodem

7.ui:=n(i)

8. Else

9. Curr-node:=child noden

10.lj:=m(j)

11.End

12.Loop

輸出:解x的重疊子區(qū)域h

2.2 基于演化歷史信息的自適應(yīng)變異機(jī)制

定義2 子區(qū)域鄰居

如果X?Y，節(jié)點(diǎn)y的子區(qū)域Y是葉子節(jié)點(diǎn)x的子區(qū)域X鄰居.

如果節(jié)點(diǎn)x的適應(yīng)值在其子區(qū)域X的鄰居中值是最小的，那么子區(qū)域X是最佳的.每一個(gè)子區(qū)域可以看作是一定鄰居數(shù)量的最優(yōu)值.當(dāng)找到最優(yōu)子區(qū)域的近似適應(yīng)度值后，子區(qū)域X的變異方向被定義為指向其最近的最優(yōu)子區(qū)域方向.

算法2 ESH-CQPSO中的變異算法

輸入:(1)需要變異的粒子x,(2)BSP樹T

1. {xi}:=在BSP樹T中記錄的粒子

2.H=∪ihi:=被分割的子區(qū)域組，其中hi是xi的子區(qū)域 /*搜索x的最近最優(yōu)子區(qū)域y*/

3. 搜索x的子區(qū)域h?H

4. 找到h的最近最優(yōu)子區(qū)域

5.y:=子區(qū)域h中的粒子 /*結(jié)束搜索x的最近最優(yōu)子區(qū)域y*/

6.α:=Random(0,1)

7.x′:=αx+(1-α)y

輸出:變異后的粒子x′

2.3 協(xié)同機(jī)制

搜索算法，包括隨機(jī)性算法(如量子行為粒子群算法和遺傳算法等)在解決規(guī)模問題的高維數(shù)據(jù)時(shí)都會(huì)遭遇“維數(shù)災(zāi)難”現(xiàn)象.粒子的每一個(gè)維度都會(huì)影響整體適應(yīng)值.因此，即使一些粒子某些維度上的值已經(jīng)非常接近全局最優(yōu)解的相應(yīng)維度值，但這些粒子仍然獲得較低的適應(yīng)值.協(xié)同運(yùn)作的重要性就在于，在粒子群中“好”的維度信息得以保存，并且可以防止可能有用的信息被不必要地丟棄；其操作簡(jiǎn)單易實(shí)現(xiàn)，在高維問題中可以有效改善算法性能[5,6].引入動(dòng)態(tài)協(xié)同機(jī)制[6]，可以分別對(duì)每一維進(jìn)行計(jì)算，并保存最有用的信息，以加速收斂.動(dòng)態(tài)協(xié)同進(jìn)化算法的程序步驟如算法3所示.

算法3 ESH-CQPSO中的協(xié)同進(jìn)化算法

輸入:粒子群P={p1,p2,…,pn}

1. for 粒子群中每個(gè)粒子

2. 根據(jù)QPSO算法產(chǎn)生5個(gè)粒子

3.pi:=pi-b選擇5個(gè)中最好的粒子

4.pc=plj

5. for 每個(gè)粒子pk，k=1,…,5

6.f=f(pk)

7. for 每一維j

8. iff(pc(j,pkj))

9.pij=pkj

10.Endif

11.pc=pi-b

12.End

13.pc=pi

14.End

15.End

輸出:進(jìn)化后的粒子群

2.4 基于演化歷史信息的自變異協(xié)調(diào)量子行為粒子群優(yōu)化算法

基于演化歷史信息的自變異協(xié)調(diào)量子行為粒子群優(yōu)化算法是一種實(shí)數(shù)編碼進(jìn)化算法.整個(gè)算法主要由四個(gè)部分組成，即群體初始化，進(jìn)化，變異和協(xié)同選擇.ESH-CQPSO算法的重點(diǎn)在于提高基于整個(gè)演化歷史信息的自變異操作，并且通過動(dòng)態(tài)協(xié)同機(jī)制選擇出最優(yōu)粒子.

算法4 ESH-CQPSO算法

輸入:(1)給定D維最小化問題F(·)；(2)搜索空間S?RD;(3)粒子群規(guī)模n

1. 初始化粒子群P={p1,p2,…,pn}

2. 計(jì)算每個(gè)粒子的適應(yīng)度值:Fi=F(pi)

3.Pbest-i:=pj

4.Gbest:=pj∈Pwherej=argmin{F(pi) } /*BSP樹初始化*/

5. 初始化BSP樹T僅包含根節(jié)點(diǎn)

6. fori:=1 ton

7. 將[pi,F(pi)]記錄到T中

8. Nexti/*BSP樹初始化結(jié)束*/

9. While未達(dá)到終止條件

10.fori=1,2,…,n

11.pi變異yi

12.利用QPSO更新公式獲得{pi1,…,pi4}[1]

13.{yi,pi1,…,pi4}根據(jù)動(dòng)態(tài)協(xié)同機(jī)制產(chǎn)生新的下一代粒子pi

14.Nexti/*BSP樹更新*/

15.fori=1,2,…,n

16.將[pi,F(pi)]記錄到T中

17.Nexti/*BSP樹更新結(jié)束*/

18.fori=1,2,…,n

19.ifF(pi)

20.Pbest-i=pi

21.Endif

22.Nexti

23.Gbest=pj∈Pwherej=argmin{F(pi) }

24.Loop

輸出：最優(yōu)解Gbest

3 實(shí)驗(yàn)設(shè)置

3.1 測(cè)試函數(shù)

本文采用一組標(biāo)準(zhǔn)測(cè)試函數(shù)對(duì)提出的算法進(jìn)行測(cè)試，驗(yàn)證其性能，如表1所示.其中f1(x)-f8(x)為經(jīng)典測(cè)試函數(shù).同時(shí)引入CEC14中提出的測(cè)試函數(shù)[11]，F(xiàn)3為單峰函數(shù)，F(xiàn)4，F(xiàn)6，F(xiàn)7和F16為簡(jiǎn)單多峰函數(shù)，F(xiàn)19為混合函數(shù).

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

3.2 算法設(shè)置

將提出的ESH-CQPSO算法與標(biāo)準(zhǔn)QPSO算法(SQPSO)，動(dòng)態(tài)協(xié)同QPSO算法(CCQPSO)[6]，連續(xù)非重復(fù)訪問遺傳算法(cNrGA)[10]，綜合學(xué)習(xí)QPSO算法(CLQPSO)[12]進(jìn)行性能比較.

對(duì)于SQPSO、ESH-CQPSO、CCQPSO及CLQPSO，收縮擴(kuò)張因子β從1線性遞減到0.5；對(duì)于cNrGA按交叉率rx=0.5進(jìn)行均勻交叉；CCQPSO和CLQPSO分別按文獻(xiàn)[6]和文獻(xiàn)[12]設(shè)置.所有算法種群的規(guī)模設(shè)置為100，對(duì)于f1(x)-f8(x)最大迭代次數(shù)設(shè)置為1000，CEC14測(cè)試函數(shù)最大迭代次數(shù)為5000.測(cè)試函數(shù)的維數(shù)D=30，每個(gè)測(cè)試函數(shù)獨(dú)立運(yùn)行30次，30次實(shí)驗(yàn)結(jié)束后獲得測(cè)試函數(shù)的最優(yōu)值、均值和方差.

4 實(shí)驗(yàn)結(jié)果及分析

利用不同算法優(yōu)化各測(cè)試函數(shù)30次所得到函數(shù)最優(yōu)、均值和方差如表2所示.從表2可以看出來，ESH-CQPSO對(duì)于絕大部分測(cè)試函數(shù)，不論是尋優(yōu)精度，還是穩(wěn)定性上都能獲得最佳效果.對(duì)于F4函數(shù)CLQPSO算法的均值和方差達(dá)到最優(yōu)，但ESH-CQPSO算法也能獲得最優(yōu)值，說明對(duì)于F4函數(shù)ESH-CQPSO搜索能力還是比較強(qiáng)，但穩(wěn)定性不夠.觀察表2中各算法的方差，除了F4、F16和F19以外，ESH-CQPSO算法方差都是最小的，說明對(duì)于絕大多數(shù)測(cè)試函數(shù)，ESH-CQPSO算法的穩(wěn)定性也是最好的.圖3(a)～圖3(m)分別展示了使用5種算法求解各測(cè)試函數(shù)的收斂曲線.優(yōu)化f1～f8函數(shù)時(shí)ESH-CQPSO都具有最佳尋優(yōu)精度，而且收斂速度遠(yuǎn)遠(yuǎn)快于其他算法.因?yàn)镋SH-CQPSO算法通過演化歷史信息，找到最優(yōu)子區(qū)域值后進(jìn)行自適應(yīng)變異操作，可以更快的搜索到最優(yōu)值，而且利用協(xié)同機(jī)制可以保留最優(yōu)信息，因此可以快速收斂到最優(yōu)值.雖然表2顯示對(duì)于f1、f2和F3，CCQPSO也能獲得最優(yōu)值，但從收斂曲線可以發(fā)現(xiàn)ESH-CQPSO的收斂速度要遠(yuǎn)快于CCQPSO.在F7和F16優(yōu)化過程中，ESH-CQPSO的優(yōu)化性能都要遠(yuǎn)好于另外4種算法.CLQPSO對(duì)于的F4優(yōu)化較好，雖然ESH-CQPSO算法的收斂速度最快，但在搜索后期的能力稍顯不足.從F19的收斂曲線可以看出，雖然各算法的收斂曲線比較相近，但ESH-CQPSO的求解能力還是最好的，收斂速度優(yōu)于其他算法，表現(xiàn)出了最好的收斂性能，在收斂速度和精度上都獲得了最佳結(jié)果.綜上所述，對(duì)比各算法，ESH-CQPSO算法具有更好的收斂性能.

表2 各測(cè)試函數(shù)的優(yōu)化結(jié)果

續(xù)表

為了判斷ESH-CQPSO算法與其他4種算法的性能是否存在顯著性差異，除了對(duì)算法的精度和收斂性進(jìn)行比較外，本文還進(jìn)行了Wilcoxon秩和檢驗(yàn)[13].表3給出了ESH-CQPSO算法與其他4種算法的Wilcoxon秩和檢驗(yàn)結(jié)果.從表3可以看出對(duì)于f1、f2和F19，ESH-CQPSO和CCQPSO的顯著性差異不大，而對(duì)于F7，SQPSO也能獲得和ESH-CQPSO相近的優(yōu)化性能.因此對(duì)于絕大多數(shù)測(cè)試函數(shù)，ESH-CQPSO算法都能獲得h=1，說明對(duì)比其他算法，ESH-CQPSO的優(yōu)化性能有顯著提高.由此可以看出不管是在單峰函數(shù)還是多峰函數(shù)中ESH-CQPSO算法都表現(xiàn)出良好的收斂性和搜索精度，優(yōu)化性能顯著提高.

表3 Wilcoxon秩和檢驗(yàn)結(jié)果

5 結(jié)論

早熟和多樣性是QPSO算法需要解決的問題，為此本文提出了基于演化歷史信息的自變異協(xié)同量子行為粒子群優(yōu)化算法(ESH-CQPSO).該算法利用二維空間分割樹(BSP)記錄演化過程中的估計(jì)解和適應(yīng)值，BSP樹將連續(xù)搜索空間進(jìn)行劃分為不同子區(qū)域，并且產(chǎn)生近似適應(yīng)值函數(shù)，從而獲得無參的自適應(yīng)變異.同時(shí)引入動(dòng)態(tài)協(xié)同機(jī)制，通過更好地利用上下文信息，在協(xié)同過程中各個(gè)維度上連續(xù)動(dòng)態(tài)地進(jìn)行更新，最大限度地利用任何新的信息，提高變異粒子的性能，防止算法進(jìn)入局部收斂，阻止早熟發(fā)生.通過實(shí)驗(yàn)結(jié)果表明，提出的ESH-CQPSO算法具有更好的尋優(yōu)能力，收斂速度和收斂精度都有所提高，是一個(gè)可靠的有效的全局優(yōu)化算法.本文提出的改進(jìn)算法能在理論上證明具有一定的優(yōu)越性，但在實(shí)際問題中還需要進(jìn)一步進(jìn)行測(cè)試，因此將ESH-CQPSO算法應(yīng)用于實(shí)際工程問題是今后的研究重點(diǎn)，下一步研究?jī)?nèi)容就是采用一定的工程問題作為應(yīng)用，如圖像分割、數(shù)據(jù)聚類、生物代謝途徑參數(shù)辨識(shí)等，進(jìn)一步驗(yàn)證ESH-CQPSO算法的性能.

[1]孫俊,方偉,吳小俊,等.量子行為粒子群優(yōu)化：原理及其應(yīng)用[M].北京:清華大學(xué)出版社,2011.31-50.

[2]Kennedy J,Eberhart R C.Particle swarm optimization[A].Proc of IEEE Int.Conf.on Neural Networks[C].Perth:IEEE Press,1995.1942-1948.

[3]劉朝華,李小花,章兢.精英免疫克隆選擇的協(xié)同進(jìn)化粒子群算法[J].電子學(xué)報(bào),2013,14(11):2167-2173. Liu Zhao-hua,Li Xiao-hua,Zhang Jing.Co-evolutionary particle swarm optimization algorithm based on elite immune clonal selection[J].Acta Electronica Sinica,2013,14(11):2167-2173.(in Chinese)

[4]Sun J,Fang W,Wu X J,Palade V,Xu W B.Quantum-behaved particle swarm optimization:analysis of individual particle behavior and parameter selection[J].Evolutionary Computation,2012,20(3):349-393.

[5]Li Y,Xiang R,Jiao L,et al.An improved cooperative quantum-behaved particle swarm optimization[J].Soft Computing,2012,16(6):1061-1069.

[6]Li Y,Jiao L,Shang R,et al.Dynamic-context cooperative quantum-behaved particle swarm optimization based on multilevel thresholding applied to medical image segmentation[J].Information Sciences,2015,294:408-422.

[7]Glover F,Laguna M.Tabu Search[M].New York:Springer,2013.3261-3362.

[8]Reynolds R G.An introduction to cultural algorithms[A].Proceedings of the Third Annual Conference on Evolutionary Programming[C].River Edge,NJ,USA ：World Scientific Publishing Co,Inc,1994.131-139.

[9]Farmer J D,Packard N H,Perelson A S.The immune system,adaptation,and machine learning[J].Physica D:Nonlinear Phenomena,1986,22(1):187-204.

[10]Yuen S Y,Chow C K.Continuous non-revisiting genetic algorithm[A].Proceedings of IEEE Conference Evolutionary Computation[C].Trondheim:IEEE,2009.1896-1903.

[11]Liang J J,Qu B Y,Suganthan P N.Problem definitions and evaluation criteria for the CEC 2014 special session and competition on single objective real-parameter numerical optimization[R].Singapore:Computational Intelligence Laboratory,Zhengzhou University,2013.

[12]陳偉,周頔,孫俊,須文波.一種采用完全學(xué)習(xí)策略的量子行為粒子群優(yōu)化算法[J].控制與決策,2012,27(5):719-723. Chen Wei,Zhou Di,Sun Jun,XU Wenbo.Improved quantum-behaved particle swarm optimization algorithm based on comprehensive learning strategy[J].Control and Decision,2012,27(5):719-723.(in Chinese)

[13]Li Zhonghua,He Chunhui,Li Jianming,Tan Hongzhou.Adaptive hierarchical artificial immune system and its application in RFID reader collision avoidance[J].Applied Soft Computing,2014(21):119-138.

趙 吉 女，1980年9月生，江蘇無錫人，博士，博士后，副教授.主要從事進(jìn)化智能算法理論與應(yīng)用等領(lǐng)域研究.

E-mail:queenji97@sohu.com

傅 毅 女，1981年11月生，安徽六安人，博士，博士后，副教授.主要從事計(jì)算機(jī)數(shù)值模擬、計(jì)算生物學(xué)等領(lǐng)域研究.

An Improved Cooperative QPSO Algorithm with Adaptive Mutation Based on Entire Search History

ZHAO Ji1,2,FU Yi1,MEI Juan1

(1.ResearchCentreofEnvironmentScience&Engineering,Wuxi，Jiangsu214063,China； 2.SchoolofIoTEngineering,JiangnanUniversity,Wuxi，Jiangsu214122,China)

An improved cooperative QPSO algorithm with adaptive mutation based on entire search history (ESH-CQPSO) is proposed.The proposed algorithm employs a binary space partitioning tree structure to memorize the positions and the fitness values of the evaluated solution.The cooperation mechanism between the solutions can ensure enhanced search capabilities,improve the optimize performance and prevent premature convergence.Benefiting from the space partitioning scheme,a fast fitness function approximation using the archive is obtained.The approximation is used to improve the mutation strategy in ESH-CQPSO.The resultant mutation is adaptive and parameter-less.Compared with other traditional algorithms,the experiment results on standard testing functions show that the proposed algorithm is superior regarding the optimization of multimodal and unimodal functions,with enhancement in both convergence speed and precision,which demonstrate the effectiveness of the algorithm.

quantum-behaved particle swarm optimization(QPSO);entire search history;adaptive mutate;binary space partitioning;cooperative method

2015-05-21;

2015-11-12;責(zé)任編輯：梅志強(qiáng)

國(guó)家自然科學(xué)基金(No.61300149，No.61105128，No.61502203);江蘇省青藍(lán)工程資助(No.2012-16);江蘇省自然科學(xué)基金(No.BK20131106);江南大學(xué)自主科研重點(diǎn)計(jì)劃(No.JUSRP51410B)；中國(guó)博士后科學(xué)基金(No.2014M560390)

TP301.6

A

0372-2112 (2016)12-2900-08

??學(xué)報(bào)URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.12.013