趙 吉，傅 毅，梅 娟

(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é)同機制確保增強搜索能力，提高優(yōu)化性能，防止過早收斂.通過空間分割機制可以獲得一個快速的近似適應(yīng)度函數(shù).這個近似值可以提高ESH-CQPSO中的變異策略，使得相應(yīng)的變異操作是一種無參數(shù)、多樣性的自適應(yīng)變異.對比其他傳統(tǒng)算法，通過對標準測試函數(shù)的實驗結(jié)果表明，ESH-CQPSO算法在處理多峰和單峰測試函數(shù)時具有更好的優(yōu)化性能，收斂精度和收斂速度都得到了提高，證明該算法的有效性.

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

1 引言

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

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

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

2.1 演化歷史信息方案

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

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

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

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

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

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

2. Curr-node:=root node ofT

3. While (Curr-node有左右兩個子節(jié)點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)變異機制

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

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

如果節(jié)點x的適應(yīng)值在其子區(qū)域X的鄰居中值是最小的，那么子區(qū)域X是最佳的.每一個子區(qū)域可以看作是一定鄰居數(shù)量的最優(yōu)值.當找到最優(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é)同機制

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

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

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

1. for 粒子群中每個粒子

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

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

4.pc=plj

5. for 每個粒子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

輸出:進化后的粒子群

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

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

算法4 ESH-CQPSO算法

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

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

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

3.Pbest-i:=pj

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

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

6. fori:=1 ton

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

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

9. While未達到終止條件

10.fori=1,2,…,n

11.pi變異yi

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

13.{yi,pi1,…,pi4}根據(jù)動態(tài)協(xié)同機制產(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è)置

3.1 測試函數(shù)

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

表1 測試函數(shù)

3.2 算法設(shè)置

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

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

4 實驗結(jié)果及分析

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

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

續(xù)表

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

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

5 結(jié)論

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

E-mail:queenji97@sohu.com

傅 毅 女，1981年11月生，安徽六安人，博士，博士后，副教授.主要從事計算機數(shù)值模擬、計算生物學(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é)任編輯：梅志強

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

TP301.6

A

0372-2112 (2016)12-2900-08

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

10.3969/j.issn.0372-2112.2016.12.013