趙延龍，滑 楠，于振華

(空軍工程大學(xué) 信息與導(dǎo)航學(xué)院，西安 710077)(*通信作者電子郵箱1241492516@qq.com)

基于二次搜索的改進粒子群算法

趙延龍*，滑 楠，于振華

(空軍工程大學(xué) 信息與導(dǎo)航學(xué)院，西安 710077)(*通信作者電子郵箱1241492516@qq.com)

針對標準粒子群優(yōu)化(PSO)算法在求解復(fù)雜優(yōu)化問題中出現(xiàn)的早熟收斂問題，提出一種結(jié)合梯度下降法的二次搜索粒子群算法。首先,當全局極值超過預(yù)設(shè)的最大不變迭代次數(shù)時，判斷全局極值點處于極值陷阱中；然后，采用梯度下降法進行二次搜索，并以最優(yōu)極值點為中心、某一具體半徑設(shè)定禁忌區(qū)域，防止粒子重復(fù)搜索該區(qū)域；最后，依據(jù)種群多樣性準則生成新粒子，替代被淘汰的粒子。將二次搜索粒子群算法及其他四種典型的改進粒子群算法分別應(yīng)用于四種典型測試函數(shù)的優(yōu)化，仿真結(jié)果表明，二次搜索粒子群算法收斂精度最高提升了10個數(shù)量級，并且收斂速度較快更容易尋找全局最優(yōu)解。

粒子群優(yōu)化；群體智能；梯度下降法；二次搜索；禁忌區(qū)域

粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法[1]是在1995年由Eberhart和Kennedy提出的一種群體智能優(yōu)化算法。該算法以其實現(xiàn)簡便、精度高、收斂快等特點一直以來受到學(xué)術(shù)界的廣泛關(guān)注，并在解決科學(xué)研究以及理論計算等方面展示了其優(yōu)越性。但是標準PSO算法在尋優(yōu)中很容易出現(xiàn)早熟問題，因此對于PSO算法收斂性能的改進研究成為一個重要的發(fā)展趨勢。文獻[2]在PSO算法中引入反向?qū)W習與自適應(yīng)逃逸策略，并將改進算法應(yīng)用于函數(shù)優(yōu)化問題中，提高了收斂速度與性能；文獻[3]在PSO算法尋優(yōu)中增加粒子群離散多樣性評價策略，改善PSO算法尋優(yōu)后期粒子群的離散多樣性特征，提高了算法的收斂性能；文獻[4]為增強PSO算法跳出局部最優(yōu)的能力，結(jié)合模擬退火與粒子群算法的優(yōu)點，提出一種基于動態(tài)概率分布的混合粒子群算法，并應(yīng)用于散亂點與曲面的圖像匹配中，提高了匹配的準確率。然而這些改進算法并沒有從根本上解決早熟收斂的問題，同時也不能避免粒子群重復(fù)搜索同一區(qū)域而導(dǎo)致尋優(yōu)性能降低的問題。

本文結(jié)合梯度下降法[5]快速收斂的思想，提出一種基于二次搜索的改進粒子群優(yōu)化(Twice Search Particle Swarm Optimization, TSPSO)算法。該算法的基本思想是當全局極值保持相同的次數(shù)超過最大預(yù)設(shè)值時，判斷相應(yīng)的粒子落入極值“陷阱”中，利用梯度下降法對該粒子進行二次搜索，并以最終尋優(yōu)極值點為中心、某一確定長度為“半徑”設(shè)定禁忌區(qū)域，當其他粒子搜索到禁忌區(qū)域邊界時，對粒子的速度進行反射操作，防止粒子重復(fù)搜索同一區(qū)域，提高尋優(yōu)效率；并將落入極值陷阱中的粒子淘汰，依據(jù)種群多樣性準則，生成新粒子進行接下來的尋優(yōu)過程。

1 二次搜索粒子群算法

1.1 PSO算法的基本原理

PSO中，每個粒子由位置信息與速度信息組成，并且所有粒子由統(tǒng)一的目標函數(shù)來決定其相應(yīng)的適應(yīng)度值，然后粒子就追隨當前的個體及全局最優(yōu)值進行搜索。

假設(shè)有N個粒子構(gòu)成一個種群S，其中Xi表示D維搜索空間中的一個元素：

Xi=(xi1,xi2,…,xiD);i=1,2,…,N

(1)

Vi表示第i個粒子的“飛行”速度，記為：

Vi=(vi1,vi2,…,viD);i=1,2,…,N

(2)

Xi當前搜索到的最優(yōu)適應(yīng)度值所對應(yīng)的位置稱為個體極值：

Pi=(pi1,pi2,…,piD);i=1,2,…,N

(3)

種群S當前搜索到的最優(yōu)位置稱為全局極值：

Pg=(pg1,pg2,…,pgD)

(4)

接下來所有粒子按照如下公式來更新速度及位置信息：

vid=w*vid+c1r1(pid-xid)+c2r2(pgd-xid)

(5)

xid=xid+vid

(6)

式(5)中，w表示慣性權(quán)重；c1、c2表示學(xué)習速率；r1、r2表示滿足 [0,1]范圍內(nèi)均勻分布的隨機數(shù)。

1.2 TSPSO算法的基本原理

梯度下降法是一種無約束最優(yōu)化算法，具有計算過程簡單、初始收斂較快等特點，因此經(jīng)常作為其他算法的核心[6-7]，其基本思想是某一質(zhì)點沿著函數(shù)f(p)(p為D維向量)上梯度下降方向可以快速滑落至函數(shù)的極值點處，主要由兩部分組成：

1)計算搜索方向：按照下式計算負梯度，即最佳搜索方向。

(7)

2)計算搜索步長：λk取最優(yōu)步長必須滿足式(8):

(8)

針對PSO算法中全局極值Pg在若干次迭代后保持不變，造成粒子群體的多樣性降低、陷入局部最優(yōu)的問題，在TSPSO算法中，引入極值陷阱和禁忌區(qū)域兩個定義。

定義1 極值陷阱。

對于給定的D維空間中的某一曲面方程S(x)=1(x為D維向量)，在其中非平坦區(qū)域(梯度為非零向量)中存在某一粒子x0∈RD，當x0可以朝著負梯度的方向迅速收斂至陷阱的谷點(極值點)時，x0此刻所處的區(qū)域稱為極值陷阱。

定義2 禁忌區(qū)域。

當處于極值陷阱中的粒子，通過朝著負梯度方向收斂到極值點，為防止其他粒子重復(fù)搜索該“陷阱”從而增加時間開銷而設(shè)定的以該極值點為中心，某一定長為“半徑”的D維“圓域”空間稱為禁忌區(qū)域。

2 TSPSO算法的實現(xiàn)

TSPSO算法與標準PSO算法及其他改進算法相比增加了判斷極值陷阱、二次搜索尋優(yōu)、設(shè)定禁忌區(qū)域、粒子淘汰與生成四個部分，用來提高算法的搜索效率和尋優(yōu)性能。

2.1 判斷極值陷阱

從文獻[8]有關(guān)PSO算法參數(shù)的設(shè)置中分析得出粒子搜索后期的尋優(yōu)軌跡方程為：

(9)

r1、r2表示滿足[0,1]范圍內(nèi)均勻分布的隨機變量，對式(9)兩邊求期望得：

(10)

從式(10)中分析得出：粒子Xi最終搜索的期望為個體極值pi與全局極值pg的加權(quán)平均數(shù)。

TSPSO算法的優(yōu)點就是經(jīng)過若干次迭代后，當全局極值pg一直保持不變時，判斷pg處于極值陷阱中，此時對pg進行二次搜索，并記錄最終尋優(yōu)結(jié)果后將其淘汰，同時依據(jù)群體多樣性的準則生成新的粒子。這樣就避免了pg長時間對其他粒子的錯誤引導(dǎo)而導(dǎo)致的局部最優(yōu)。

2.2 二次搜索尋優(yōu)

二次搜索是指當全局極值pg處于極值陷阱中時，為了防止pg對其他粒子錯誤引導(dǎo)而導(dǎo)致局部最優(yōu)，需要對pg進行進一步的獨立尋優(yōu)搜索過程。為了兼顧效率與性能，本文選擇梯度下降法進行二次搜索尋優(yōu)。

假設(shè)對每一個粒子都有一個固定的評價函數(shù)，即算法的適應(yīng)度函數(shù)f(Xi)，并且函數(shù)f(·)在第i(i=1,2,…,D)維的偏導(dǎo)數(shù)存在，那么二次尋優(yōu)的流程如圖1。

圖1 二次尋優(yōu)流程

二次尋優(yōu)的優(yōu)勢是不僅在一定程度上減小了粒子受全局極值pg的誤導(dǎo)影響，同時利用梯度下降算法提高了搜索的精度，而且還可以將粒子群搜索尋優(yōu)與二次尋優(yōu)進行獨立操作，采用并行處理模式，有效提高尋優(yōu)的效率。

2.3 設(shè)定禁忌區(qū)域

(11)

在三維空間中的曲面圖如圖2所示。

(12)

圖2 函數(shù)F三維曲面

圖3 粒子Xi反射示意圖

(13)

(14)

(15)

將式(14)代入式(15)得到Xi經(jīng)反射后的方向向量V′i為：

(Xi-p′g)+Vi

(16)

通過對粒子速度方向進行反射操作，可以避免粒子重復(fù)搜索某一相同區(qū)域，有效提高算法的搜索效率。

2.4 粒子淘汰與生成

當某一粒子Xi經(jīng)過若干次迭代后進入極值陷阱中，為防止該粒子對其他粒子的誤導(dǎo)影響，需要對Xi進行單獨的二次搜索尋優(yōu)處理。為防止局部最優(yōu)，Xi已不再適合接下來的尋優(yōu)搜索過程，因此需將該粒子淘汰，并根據(jù)一定的準則生成新的粒子。文獻[9]中關(guān)于種群S多樣性的計算函數(shù)式為：

(17)

(18)

其中，ζ為常數(shù)，使得：

(19)

式(19)表示在搜索區(qū)域S的D重積分，且S即為該積分區(qū)域。

2.5 TSPSO算法流程

基于梯度下降法的二次搜索粒子群算法流程如下：

步驟1 確定慣性權(quán)重w，學(xué)習速率c1、c2，檢測極值陷阱的最大迭代次數(shù)MI以及粒子群體個數(shù)N；

步驟2 在給定范圍內(nèi)，隨機生成N個粒子位置xi、速度vi(i=1,2,…,N)信息；

步驟3 計算xi的適應(yīng)度值fi，經(jīng)判斷若滿足終止條件，則輸出結(jié)果，否則繼續(xù)；

步驟4 更新個體極值pi和全局極值pg，依據(jù)式(5)、(6)更新粒子速度和位置信息；

步驟5 判斷全局極值pg保持不變的次數(shù)是否超過預(yù)設(shè)最大值，滿足則跳至步驟6，否則返回步驟3；

步驟7 將與全局極值pg對應(yīng)的粒子淘汰，并依據(jù)種群多樣性準則生成新粒子進行替換，返回步驟3。

3 仿真分析

3.1 測試環(huán)境

軟件環(huán)境：Microsoft Windows 7操作系統(tǒng)，Matlab 7.8仿真平臺。

硬件環(huán)境：Intel core i5-3470，主頻3.20 GHz處理器，4 GB內(nèi)存，聯(lián)想機型。

本文選擇4種近幾年比較有代表性的改進粒子群算法進行對照仿真實驗：線性遞減權(quán)重粒子群優(yōu)化(Linearly Decreasing Weight Particle Swarm Optimization, LDWPSO)算法[10]、雜交粒子群優(yōu)化(Hybrid Particle Swarm Optimization, HPSO)算法[11]、自然選擇粒子群優(yōu)化(Natural Selection Particle Swarm Optimization, NSPSO)算法[12]、免疫粒子群優(yōu)化(Immune Particle Swarm Optimization, IPSO)算法[13]。

表1中，Sphere為單極值函數(shù)，當x為全0向量時f1(x)取到最優(yōu)值0；Griewank為單極值函數(shù)，但是在極值點的附近存在若干個背離極值點方向上的陡峭峽谷，容易陷入局部極值點之中，當x為全1向量時f2(x)取到最優(yōu)值0；Rastrigrin與Griewank函數(shù)都存在多個極值點，同樣容易陷入局部極值點中，當x為全0向量時均取到最優(yōu)值0。四種測試函數(shù)的優(yōu)化目標是在相應(yīng)搜索空間內(nèi)取得最小值。

3.2 經(jīng)典測試函數(shù)

表1 四種典型測試函數(shù)(維數(shù)=n)

表2 5種PSO算法對4種測試函數(shù)仿真結(jié)果

表3 5種PSO算法對四種測試函數(shù)花費時長比較

為驗證TSPSO算法的收斂性能，本文通過對相關(guān)參考文獻的研究，選取文獻[14]中四種典型的測試函數(shù)進行優(yōu)化實驗，各個測試函數(shù)的基本信息如表1所示。

3.3 算法參數(shù)設(shè)置

TSPSO算法中，檢測極值陷阱的最大迭代次數(shù)MI取值10；LDWPSO算法中，設(shè)置慣性權(quán)重w變化范圍0.8～0.2；HPSO算法中，雜交概率bc取值0.8，雜交池的大小比例bs取值0.1；IPSO算法中，檢測免疫的迭代次數(shù)DS取值8，免疫替換概率preplace取值0.5，精度eps取值10-10，粒子間最小距離取值10-10。四種改進PSO算法的慣性權(quán)重w、認知項權(quán)重c1和社會項權(quán)重c2分別取值0.8、2和2；粒子個數(shù)N取值50；迭代次數(shù)M分別取值1 000、2 000和3 000；搜索空間維數(shù)D分別取值10、20和30。

3.4 仿真結(jié)果與分析

通過Matlab 7.8仿真平臺對上述五種改進粒子群優(yōu)化算法進行仿真實驗，所得仿真結(jié)果如表2和圖4所示。

從表2中分析得出：總體上，本文提出的TSPSO算法在四種測試函數(shù)上的收斂精度均優(yōu)于LDWPSO、HPSO、NSPSO、IPSO四種算法。對于某一具體測試函數(shù)(尤其F2)，隨著空間維度的增加，TSPSO算法的收斂精度保持相對穩(wěn)定，而其他四種對照算法收斂精度則急劇降低，因此TSPSO算法更適合應(yīng)用于高維空間的函數(shù)優(yōu)化問題中。

圖4是在測試函數(shù)維度均為30，且5種PSO算法迭代次數(shù)均為1 000時的實驗結(jié)果(橫軸表示迭代次數(shù)，縱軸表示全局極值取10為底的對數(shù)后的結(jié)果)。從中分析得出：TSPSO算法的收斂速度和精度均優(yōu)于四種對照PSO算法。

為驗證TSPSO算法較其他四種改進PSO算法的尋優(yōu)效率，本文針對不同算法對同一測試函數(shù)收斂到相同精度的花費時長進行比較。結(jié)果如表3所示。

表3中各收斂精度以5種改進PSO算法中最低的精度為基準進行比較，從結(jié)果中分析得出：對于函數(shù)F1，在不同維度且收斂到相同精度條件下，TSPSO算法與其他4種改進PSO算法相比花費時長更短；對于函數(shù)F2，在維度為20和30且收斂到相同精度條件下，TSPSO算法與其他4種改進PSO算法相比花費時長更短；對于函數(shù)F3，在維度為30且收斂到相同精度條件下，TSPSO算法與其他4種改進PSO算法相比花費時長更短；對于函數(shù)F4，在維度為10且收斂到相同精度條件下，TSPSO算法與其他4種改進PSO算法相比花費時長更短。對于其他情況，TSPSO算法的花費時長與其他算法相比雖然不是最短，但相差很小，從算法的收斂精度方面考慮，可以忽略。因此TSPSO算法的尋優(yōu)效率總體上較優(yōu)。

3.5 種群多樣性討論

PSO算法中，種群多樣性指粒子群兩兩個體間的總體差異情況，表現(xiàn)在搜索空間中的離散分布程度，即種群多樣性越好，粒子群的離散程度越高，搜索范圍越廣，因此也就更容易尋找到全局最優(yōu)值。圖5給出了5種改進PSO算法按照式(17)中的種群多樣性公式計算得出的變化曲線，從中分析得出： LDWPSO算法在尋優(yōu)過程中種群多樣性保持能力最差，種群多樣性逐漸喪失，容易陷入局部最優(yōu)；HPSO、NSPSO、IPSO以及本文所提TSPSO四種算法在尋優(yōu)過程中種群多樣性基本保持在一定范圍內(nèi)波動，并且TSPSO算法的種群多樣性相對較優(yōu)，更容易尋找全局最優(yōu)值。

圖4 5種PSO算法對四種測試函數(shù)的全局極值進化曲線

圖5 5種PSO算法對四種測試函數(shù)的種群多樣性進化曲線

4 結(jié)語

本文通過對標準PSO算法以及相關(guān)的改進算法進行研究分析，針對目前改進PSO算法的研究中存在的缺陷與不足，并結(jié)合梯度下降法的快速尋優(yōu)特點，提出了一種基于二次搜索的粒子群優(yōu)化(TSPSO)算法。該算法中首次提出二次搜索、極值陷阱、禁忌區(qū)域等概念，并通過對四種測試函數(shù)與其他改進PSO算法進行對照仿真實驗，結(jié)果表明TSPSO算法具有更快的收斂速度和更優(yōu)的尋優(yōu)性能。最后對TSPSO算法的種群多樣性進行討論，進一步驗證了改進算法的有效性與可靠性。然而本文也存在不足，例如如何確定禁忌區(qū)域的最長半徑R沒有確定的計算方法，需要進一步研究。

References)

[1] KENNEDY J, EBERHART R. Particle swarm optimization [C]// Proceedings of the IEEE International Conference on Neural Networks. Piscataway, NJ: IEEE, 1995, 4: 1942-1948.

[2] 呂莉,趙嘉,孫輝.具有反向?qū)W習和自適應(yīng)逃逸功能的粒子群優(yōu)化算法[J].計算機應(yīng)用,2015,35(5):1336-1341.(LYU L, ZHAO J, SUN H. Particle swarm optimization algorithm using opposition-based learning and adaption escape [J]. Journal of Computer Applications, 2015, 35(5): 1336-1341.)

[3] 湯可宗,肖絢,賈建華,等.基于離散式多樣性評價策略的自適應(yīng)粒子群優(yōu)化算法[J].南京理工大學(xué)學(xué)報,2013,37(3):344-349.(TANG K Z, XIAO X, JIA J H, et al. Adaptive particle swarm optimization algorithm based on discrete estimate strategy of diversity [J]. Journal of Nanjing University of Science and Technology, 2013, 37(3): 344-349.)

[4] 羅磊,陳懇,杜峰坡,等.基于改進型粒子群算法的曲面匹配與位姿獲取[J].清華大學(xué)學(xué)報(自然科學(xué)版),2015,55(10):1061-1066.(LUO L, CHEN K, DU F P, et al. Surface fitting and position-pose measurements based on an improved SA-PSO algorithm[J]. Journal of Tsinghua University (Science and Technology), 2015, 55(10): 1061-1066.)

[5] LU C, SHENG W, HAN Y, et al. Phase-only pattern synthesis based on gradient-descent optimization [J]. Journal of Systems Engineering and Electronics, 2016, 27(2): 297-307.

[6] 許少華,宋美玲,許辰,等.一種基于混合誤差梯度下降算法的過程神經(jīng)網(wǎng)絡(luò)訓(xùn)練[J].東北石油大學(xué)學(xué)報,2014,38(4):92-96.(XU S H, SONG M L, XU C, et al. Training algorithm of process neural networks based on hybrid error gradient descent [J]. Journal of Northeast Petroleum University, 2014, 38(4): 92-96.)

[7] 韓文花,徐俊,沈曉暉,等.自學(xué)習粒子群與梯度下降混雜的漏磁反演方法[J].火力與指揮控制,2015,40(1):88-91.(HAN W H, XU J, SHEN X H, et al. Hybrid of self-learning particle swarm optimization and gradient descent based magnetic flux leakage lnversion [J]. Fire Control & Command Control, 2015, 40(1): 88-91.)

[8] 湯可宗,李慧穎,李娟,等.一種求解復(fù)雜優(yōu)化問題的改進粒子群優(yōu)化算法[J].南京理工大學(xué)學(xué)報,2015,39(4):386-391.(TANG K Z, LI H Y, LI J, et al. Improved particle swarm optimization algorithm for solving complex optimization problems [J]. Journal of Nanjing University of Science and Technology, 2015, 39(4): 386-391.)

[9] RIGET R, VESTERSTR?M J S. A diversity-guided particle swarm optimizer—the ARPSO [R]. Aarhus, Denmark: University of Aarhus, 2002.

[10] 湯可宗.遺傳算法與粒子群優(yōu)化算法的改進及應(yīng)用研究[D].南京:南京理工大學(xué),2011.(TANG K Z. Improvement and application of genetic algorithm and particle swarm algorithm research [D]. Nanjing: Nanjing University of Technology Institute of Computer Science and Engineering, 2011.)

[11] 周利軍,彭衛(wèi),曾小強,等.基于雜交變異的動態(tài)粒子群優(yōu)化算法[J].計算機科學(xué),2013,40(11A):143-146.(ZHOU L J, PENG W, ZENG X Q, et al. Dynamic particle swarm optimization based on hybrid variable [J]. Computer Science, 2013, 40(11A): 143-146.)

[12] 白俊強,尹戈玲,孫智偉,等.基于二階振蕩及自然選擇的隨機權(quán)重混合粒子群算法[J].控制與決策,2012,27(10):1459-1464.(BAI J Q, YIN G L, SUN Z W, et al. Random weighted hybrid particle swarm optimization algorithm based on second order oscillation and natural selection [J]. Control and Decision, 2012, 27(10): 1459-1464.)

[13] 魏建香,孫越泓,蘇新寧.一種基于免疫選擇的粒子群優(yōu)化算法[J]. 南京大學(xué)學(xué)報(自然科學(xué)版),2010,46(1):1-9.(WEI J X, SUN Y H, SU X N. A novel particle swarm optimization based on immune selection [J]. Journal of Nanjing University (Natural Sciences), 2010,46(1):1-9.)

[14] ZHAN Z H, ZHANG J, LI Y, et al. Adaptive particle swarm optimization [J]. IEEE Transactions on Systems, Man, and Cybernetics—Part B: Cybernetics, 2009, 39(6): 1362-1381.

[15] 溫正.精通MATLAB智能算法[M].北京:清華大學(xué)出版社,2015:106-192.(WEN Z. Proficient in MATLAB Intelligent Algorithm [M]. Beijing: Tsinghua University Press, 2015: 106-192.)

ZHAOYanlong, born in 1992, M.S. candidate, His research interests include dynamic task allocation, swarm intelligence.

HUANan, born in 1974, Ph. D., professor. His research interests include dynamic task allocation.

YUZhenhua, born in 1977, Ph. D., associate professor. His research interests include physical information fusion, dynamic task allocation.

Improvedparticleswarmoptimizationalgorithmbasedontwicesearch

ZHAO Yanlong*, HUA Nan, YU Zhenhua

(CollegeofInformationandNavigation,AirForceEngineeringUniversity,Xi’anShaanxi710077,China)

Aiming at the premature convergence problem of standard Particle Swarm Optimization (PSO) in solving complex optimization problem, a new search PSO algorithm based on gradient descent method was proposed. Firstly, when the global extremum exceeds the preset maximum number of unchanged iterations, the global extremum was judged to be in the extreme trap. Then, the gradient descent method was used to proceed twice search, a tabu area was constituted with the center of optimal extremum point and the radius of specific length to prevent particles repeatedly search the same area. Finally, new particles were generated based on the population diversity criteria to replace the particles that would be eliminated. The twice search algorithm and other four improved algorithms were applied to the optimization of four typical test functions. The simulation results show that the convergence accuracy of the twice search particle swarm algorithm is higher up to 10 orders of magnitude, the convergence speed is faster and it is easier to find the global optimal solution.

Particle Swarm Optimization (PSO); swarm intelligence; gradient descent; twice search; tabu area

2017- 03- 27;

2017- 05- 31。

趙延龍(1992—)，男，河北邢臺人，碩士研究生，主要研究方向：動態(tài)任務(wù)分配、群體智能； 滑楠(1974—)，男，陜西西安人，教授，博士，主要研究方向：動態(tài)任務(wù)分配； 于振華(1977—)，男，陜西西安人，副教授，博士，主要研究方向：信息物理融合、動態(tài)任務(wù)分配。

1001- 9081(2017)09- 2541- 06

10.11772/j.issn.1001- 9081.2017.09.2541

TP301.6

A