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

趙延龍，滑 楠，于振華

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

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

趙延龍*，滑 楠，于振華

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

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

粒子群優化；群體智能；梯度下降法；二次搜索；禁忌區域

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

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

1 二次搜索粒子群算法

1.1 PSO算法的基本原理

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

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

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

(1)

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

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

(2)

Xi當前搜索到的最優適應度值所對應的位置稱為個體極值：

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

(3)

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

Pg=(pg1,pg2,…,pgD)

(4)

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

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

(5)

xid=xid+vid

(6)

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

1.2 TSPSO算法的基本原理

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

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

(7)

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

(8)

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

定義1 極值陷阱。

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

定義2 禁忌區域。

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

2 TSPSO算法的實現

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

2.1 判斷極值陷阱

從文獻[8]有關PSO算法參數的設置中分析得出粒子搜索后期的尋優軌跡方程為：

(9)

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

(10)

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

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

2.2 二次搜索尋優

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

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

圖1 二次尋優流程

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

2.3 設定禁忌區域

(11)

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

(12)

圖2 函數F三維曲面

圖3 粒子Xi反射示意圖

(13)

(14)

(15)

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

(Xi-p′g)+Vi

(16)

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

2.4 粒子淘汰與生成

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

(17)

(18)

其中，ζ為常數，使得：

(19)

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

2.5 TSPSO算法流程

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

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

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

步驟3 計算xi的適應度值fi，經判斷若滿足終止條件，則輸出結果，否則繼續；

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

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

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

3 仿真分析

3.1 測試環境

軟件環境：Microsoft Windows 7操作系統，Matlab 7.8仿真平臺。

硬件環境：Intel core i5-3470，主頻3.20 GHz處理器，4 GB內存，聯想機型。

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

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

3.2 經典測試函數

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

表2 5種PSO算法對4種測試函數仿真結果

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

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

3.3 算法參數設置

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

3.4 仿真結果與分析

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

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

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

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

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

3.5 種群多樣性討論

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

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

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

4 結語

本文通過對標準PSO算法以及相關的改進算法進行研究分析，針對目前改進PSO算法的研究中存在的缺陷與不足，并結合梯度下降法的快速尋優特點，提出了一種基于二次搜索的粒子群優化(TSPSO)算法。該算法中首次提出二次搜索、極值陷阱、禁忌區域等概念，并通過對四種測試函數與其他改進PSO算法進行對照仿真實驗，結果表明TSPSO算法具有更快的收斂速度和更優的尋優性能。最后對TSPSO算法的種群多樣性進行討論，進一步驗證了改進算法的有效性與可靠性。然而本文也存在不足，例如如何確定禁忌區域的最長半徑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] 呂莉,趙嘉,孫輝.具有反向學習和自適應逃逸功能的粒子群優化算法[J].計算機應用,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] 湯可宗,肖絢,賈建華,等.基于離散式多樣性評價策略的自適應粒子群優化算法[J].南京理工大學學報,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].清華大學學報(自然科學版),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].東北石油大學學報,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] 韓文花,徐俊,沈曉暉,等.自學習粒子群與梯度下降混雜的漏磁反演方法[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] 湯可宗,李慧穎,李娟,等.一種求解復雜優化問題的改進粒子群優化算法[J].南京理工大學學報,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] 湯可宗.遺傳算法與粒子群優化算法的改進及應用研究[D].南京:南京理工大學,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] 周利軍,彭衛,曾小強,等.基于雜交變異的動態粒子群優化算法[J].計算機科學,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] 白俊強,尹戈玲,孫智偉,等.基于二階振蕩及自然選擇的隨機權重混合粒子群算法[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] 魏建香,孫越泓,蘇新寧.一種基于免疫選擇的粒子群優化算法[J]. 南京大學學報(自然科學版),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].北京:清華大學出版社,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—)，男，河北邢臺人，碩士研究生，主要研究方向：動態任務分配、群體智能； 滑楠(1974—)，男，陜西西安人，教授，博士，主要研究方向：動態任務分配； 于振華(1977—)，男，陜西西安人，副教授，博士，主要研究方向：信息物理融合、動態任務分配。

1001- 9081(2017)09- 2541- 06

10.11772/j.issn.1001- 9081.2017.09.2541

TP301.6

A