基于自適應擾動的粒子群優化算法

王敏,, 唐俊

WANG Min1,2,TANG Jun3

1. 湖南機電職業技術學院 信息工程系,湖南 長沙 410151

2. 湖南大學 計算機與通信學院湖南 長沙 410082

3. 湖南城建職業技術學院 設備工程系,湖南 湘潭 411101

1. Department Information Engineering, Hunan Mechanical & Electrical Polytechnic, Changsha 410151, China

2. College of Computer and Communication, Hunan University, Changsha 410082, China

3. Department Equipment Engineering, Hunan Urban Construction College, Xiangtan 411101, China

1 引言

粒子群優化算法(Particle Swarm Optimization,PSO)是一種群智能(Swarm Intelligence)優化算法，它源于對鳥群和魚群群體覓食行為的模擬[1]。由于PSO算法的概念簡單、易于實現、并且具有較快的收斂速度，因而被廣泛地應用于各種優化問題的求解[2-4]。

雖然 PSO算法在很多優化問題上表現出較好的性能，但是它還存在一些問題，如對參數敏感、群體多樣性較差和求解多峰問題時易陷入局部最優。針對這些不足之處，一些學者提出不同的策略來改進PSO算法的性能[5-10]。Shi和Eberhart[5]提出了一種帶有慣性權值的PSO算法，該方法在粒子的速度更新公式中加入了權值w，以控制粒子保留上一次飛行時速度的慣性權重。Liang等人[6]提出了一種廣泛學習的PSO算法(CLPSO)，該方法在速度更新公式中去除了粒子的社會項，并修改了粒子的認知項。朱冰等人[7]通過借鑒群體位置方差的早熟判斷機制，把基因換位和變異算子引入到算法中，提出了一種混合PSO算法。紀震等人[8]提出了一種智能單粒子算法，該算法的群體中只包含一個粒子。王志等人[9]利用PSO算法的快速收斂性和差分演化算法的搜索精度高的特點，提出了一種混合優化算法。在算法的中后期，該算法在最有位置的周圍隨機生成一定數量的粒子進行差分演化算法，以提高算法的搜索精度和收斂速度。介婧等人[10]提出了基于群體多樣性反饋控制的自組織PSO算法，實驗結果表明該算法具有較好的搜索能力。

在 PSO算法中，粒子的搜索行為取決于自身的歷史最優位置(pbest)和群體當前所找到的全局最優位置(gbest)。一旦pbest和gbest陷入局部最優，所有粒子也會很快收斂到該局部極小點[11]。粒子的速度將會快速下降至0，所有粒子將處于停滯狀態，使得很難跳出局部最優。針對此問題，本文提出了一種基于自適應擾動的PSO算法(ADPSO)，以確保粒子的速度不至于下降至 0，幫助停滯的粒子跳出局部最優。

2 基于自適應擾動的粒子群優化算法

2.1 粒子群優化算法

在 PSO算法中，群體中的每個粒子代表了問題搜索空間中的一個候選解，它具有速度V和位置X兩個分量。假設群體P(t)為當前群體，其大小為N。群體中第 i個粒子的位置和速度分別表示為：Vi(t)(vi1(t), vi2(t),…,vid(t))和 Xi(t)(xi1(t), xi2(t),…,xid(t))，其中，D為問題的維數，t指演化代數。在每一代，粒子通過學習自身的歷史最優搜索經驗和群體中的最優粒子的搜索經驗來調整當前的搜索行為。粒子根據以下公式來更新其速度和位置[5]：

其中，i=1,2,..,N, j=1,2,..,D，pbesti是第i個粒子的歷史最優位置，gbest是群體目前搜索到的最優粒子的位置。參數w是慣性權值，c1和c2是學習因子，r1和r2是分布在區間(0,1)的隨機數。

2.2 算法的提出

在演化過程中，粒子通過學習自身的歷史最優位置pbest和全局最優位置gbest來更新其速度和位置。因此，粒子具有飛向當前最好位置的趨勢。根據公式(1)，粒子在迭代過程中逐漸向pbest和gbest靠攏。一旦pbest和gbest陷入了局部最優(即pbest和gbest保持不變)，所有粒子的速度將會快速的趨近于 0。根據公式(2)，粒子將會陷入一點(Xi(t+1)=Xi(t)+0)，處于停滯狀態。如果當前群體找到的最優解不是全局最優解，則群體陷入了局部最優。圖 1給出了標準 PSO算法在求解 Weierstrass函數(D=30，全局最優解為 0)時速度和最優適應值的變化曲線(這里只給出了群體中某個粒子的速度在某一維上的變化情況，其它維上可得到類似的結果)。從圖中可以看出，在演化初期(適應值評估次數FEs<2000時)，粒子的速度較大(不為0)，PSO算法的收斂速度較快；隨著演化代數的增加，粒子的速度逐漸減小，PSO算法的收斂速度變慢；當粒子的速度趨近于0時，群體逐漸陷入局部最優。

上述分析表明，當群體粒子的速度趨近于 0時，PSO算法也將趨近于收斂。如果當前群體不是收斂到全局最優解，則算法陷入了局部最優。由于粒子的速度為 0，所有粒子將處于停滯狀態，很難跳出局部最優。為了克服這個問題，一些學者分別提出了粒子擾動的思想。何慶元等人[12]提出了帶有擾動項的 PSO算法(PSO-DT)，該方法在標準 PSO算法的速度更新公式中加入了一個擾動項以確保粒子的速度不至于下降到 0。理論分析表明，PSO-DT算法并未改變標準PSO算法的收斂條件。陳功貴等人[13]提出了隨機局部擾動策略以改善PSO算法在演化后期的收斂性能。張捷等人[14]針對混沌PSO算法中存在的盲目搜索問題，提出了動態混沌擾動PSO算法。該方法在最優值改變時進行較小的擾動，在最優值多次不變時進行動態擾動范圍的混沌擾動，以減小算法中存在的盲目搜索，提高搜索速度和效率。王小根等人[15]提出了在粒子平均位置或全局最優位置上加入高斯擾動，以阻止粒子的停滯。彭力等人[16]通過計算粒子的擁擠度來判斷群體是否陷入到局部最優。如果擁擠度大于某個閾值時，則認為群體陷入了局部最優，這時給群體加入擾動，以防止算法陷入局部最優。

圖1 標準PSO算法在求解Weierstrass函數時速度(左)和最優適應值(右)的變化曲線

圖2 ADPSO算法在求解Weierstrass函數時速度(左)和最優適應值(右)的變化曲線

雖然擾動策略可以確保粒子的速度不至于下降至 0，但是何時進行擾動仍然是一個不易解決的問題。彭力等人[16]認為以當前最優值為圓心，擁擠度因子為半徑的區域所包含粒子的數量大于某個閾值時，則進行擾動。但是擾動策略的執行取決于參數擁擠度因子和閾值的設置。針對這個問題，本文提出了一種自適應擾動的PSO算法(ADPSO)，該方法通過監視每個粒子的搜索狀態來自適應地執行擾動策略。在演化過程中，如果第i個粒子的歷史最優位置pbesti在M代里都沒有被改進，則認為該粒子可能陷入了局部最優，這時按照如下公式對第i個粒子執行擾動策略。

其中，k是一個1到D之間的隨機整數，G(0,1)是均值為0和標準方差為1的高斯隨機數。這里，我們沒有對速度的所有維進行擾動，而是只針對隨機選擇的某一維進行擾動。這是因為較大的擾動會使得Xi(t)和Xi(t+1)具有較大的差異，而較小的擾動更有利于算法的局部搜索。

圖2給出了ADPSO算法在求解Weierstrass函數(D=30，全局最優解為 0)時速度和最優適應值的變化曲線(和圖1一樣，這里只給出了群體中某個粒子的速度在某一維上的變化情況)。從圖中可以看出，在整個演化過程中，擾動策略使得粒子的速度不會下降至 0，這保證了 ADPSO算法有可能持續地改進群體最優適應值。和標準PSO算法相比(圖1所示)，ADPSO能獲得更高精度的解。

基于自適應擾動的 PSO算法(ADPSO)的步驟如下：

Step 1 隨機初始化群體中每個粒子的速度和位置，適應值評估次數FEs=0。

Step 2 計算所有粒子的適應值，FEs=FEs+N，產生初始粒子的歷史最優位置 pbest和全局最優位置gbest。對于第i個粒子，定義Ki為其歷史最優位置pbesti連續未被改進的代數，初始化Ki=0。

Step 3 對于每個粒子i，如果iKM≥，則根據公式(3)產生粒子的速度；否則根據公式(1)產生粒子的速度。根據公式(2)產生粒子的位置，計算粒子的適應值f(Xi)，FEs=FEs+1。

Step 4 如果第 i個粒子的適應值優于其歷史最優位置 pbesti，則將 pbesti更新為 Xi， pbesti連續未改變的代數 Ki置 0；否則 Ki=Ki+1。如果第 i個粒子的適應值優于全局最優位置 gbest，則將gbest更新為Xi。

Step 5 i=i+1，如果i≤N，則轉Step 3；否則轉Step 6。

與標準PSO相比，ADPSO對每個粒子增加了一個計數器 Ki來監視粒子的搜索狀態，如果 Ki的值大于閾值M，則認為該粒子可能處于停滯狀態，這時對該粒子實施擾動，有利于幫助粒子跳出局部極小點。在每一代里，根據 Ki的值從公式(1)和(3)中選擇一個速度更新模型來產生新的速度。因此，本文提出的ADPSO和標準PSO具有相同的計算時間復雜度。

3 仿真實驗

為了驗證算法的有效性，本文實驗中使用了9個多峰函數來測試算法的性能。表1描述了測試函數的名稱、維數和搜索范圍，所有函數的全局最值均為0。更詳細的函數定義見文獻[6]。

表1 測試函數

本文設計了兩類測試實驗：1) ADPSO算法與其它知名PSO算法的比較；2) ADPSO算法與其它基于擾動策略的 PSO算法的比較。對于第一類實驗，本文比較了 ADPSO、PSO、Cooperative PSO(CPSO-H)[17]和 Comprehensive Learning PSO(CLPSO)[6]的性能。在實驗中，所有算法的種群大小 N=40，最大適應值評估次數MAX_FEs=2.0e+05[6]。對于 ADPSO 和 PSO，c1=c2=1.50，w=0.73，M=10。對于CPSO-H和CLPSO，其參數設置見文獻[6]。對于第二類實驗，本文比較了 ADPSO、帶有擾動項改進的 PSO算法(PSO-DT)[12]和基于高斯擾動的量子 PSO算法(MQPSO)[15]的性能。在實驗中，所有算法的種群大小N=30，最大適應值評估次數MAX_FEs=1.5e+05。對于其它參數，ADPSO采用了第一類實驗中的設置，PSO-DT和MQPSO分別采用文獻[12]和[15]中的設置。

表2 ADPSO與PSO、CPSO-H、CLPSO的實驗結果比較

表2給出了ADPSO與PSO、CPSO-H、CLPSO的實驗結果比較。從中可以看出，ADPSO在所有測試函數上均優于PSO。特別是在函數F2、F3、F4和F6上，PSO陷入了局部最優，而ADPSO能找到滿意的解。與CPSO-H相比，ADPSO僅在函數F5上比CPSO-H差。CLPSO在函數F5、F7和F8上優于ADPSO，而對于剩下的6個函數，ADPSO均優于CLPSO。旋轉使得函數變得難以求解，影響了算法的性能。對于 Ackley，它的旋轉并沒有影響CLPSO和ADPSO，而較大的影響了CPSO-H的結果。對于Griewank和Weierstrass，ADPSO在非旋轉函數F3和F4上能找到全局最優解，而在選擇旋轉函數 F7和 F8上陷入了局部最優。圖 3給出了ADPSO與PSO在四個測試函數上的收斂過程，從中可以看出，ADPSO的收斂速度明顯快于PSO。

圖3 ADPSO和PSO在四個測試函數上的收斂曲線

表3 ADPSO與PSO-DT、MQPSO的實驗結果比較

表3給出了ADPSO與其它兩種基于擾動策略的PSO算法的比較。從表中可以看出，ADPSO在Rosenbrock和 Griewank函數上優于 PSO-DT和MQPSO，而對于Rastrigin函數，PSO-DT和MQPSO優于ADPSO。

4 結束語

本文針對 PSO算法在求解多峰函數時易陷入局部最優的問題，提出了基于自適應擾動的PSO算法(ADPSO)，以幫助停滯的粒子跳出局部最優。分析表明，本文提出的自適應擾動策略并未增加算法的復雜度，ADPSO和標準PSO具有相同的計算時間復雜度。在給定的多峰測試函數中，ADPSO優于其它五種PSO算法。

[1]Kennedy J, Eberhart R C. Particle swarm optimization[C]//Proc IEEE International Conference on Neural Networks, Perth, Australia. Piscataway, NJ: IEEE Service Center, 1995: 1942-1948.

[2]Liu B, Wang L, Yin Y H. An effective hybrid particle swarm optimization for no-wait flow shop scheduling[J].International Journal of Advanced Manufacturing Technology, 2007, 33:1001-1011.

[3]Wang J, Yin Z. A ranking selection-based particle swarm optimizer for engineering design optimization problems[J]. Structural and Multidisciplinary Optimization,2008, 37:131-147.

[4]Bao Z, Watanabe T. Mixed constrained image filter design using particle swarm optimization[J]. Artificial Life and Robotics, 2010, 15(3):363-368.

[5]Shi Y, Eberhart R C. A modified particle swarm optimize[C]//Proc IEEE Congress Evolutionary Computation,1998:69-73.

[6]Liang J, Qin A K, Suganthan P N. Comprehensive learning particle swarm optimizer for global optimization of multimodal functions[J]. IEEE Transactions on Evolutionary Computation, 2006, 10(3): 281-295.

[7]朱冰, 齊名軍. 混合粒子群優化算法[J]. 計算機工程與應用. 2012, 48(9):47-50.

[8]紀震, 周家銳, 廖惠連, 吳青華. 智能單粒子優化算法[J]. 計算機學報, 2010, 33(3):556-561.

[9]王志, 胡小兵, 何雪梅. 一種新的差分與粒子群算法的混合算法[J]. 計算機工程與應用. 2012, 48(6):46-48.

[10]介婧, 曾建潮, 韓崇昭. 基于群體多樣性反饋控制的自組織微粒群算法[J]. 計算機研究與發展,2008,45(3):464-471.

[11]Bergh F van den, Engelbrecht A P. A study of particle swarm optimization particle trajectories[J]. Information Sciences, 2006, 176(8): 937-971.

[12]何慶元, 韓傳久. 帶有擾動項的改進粒子群算法[J]. 計算機工程與應用, 2007, 43(7): 84-86.

[13]陳功貴, 楊俊杰, 孫永發, 鐘建偉. 隨機局部搜索擾動的粒子群優化算法[J]. 計算機應用, 2008, 28(1):94-96.

[14]張捷, 封俊紅. 基于動態混沌擾動的粒子群優化及其應用[J]. 計算機工程, 2011, 37(7):175-177.

[15]王小根, 龍海俠, 孫俊. 基于高斯擾動的量子粒子群優化算法[J]. 計算機應用研究, 2010, 27(6):2093-2096.

[16]彭力, 王茂海. 基于前饋擾動的粒子群改進算法[J]. 控制工程, 2012, 19(1):102-105.

[17]Bergh F van den, Engelbrecht A P. A cooperative approach to particle swarm optimization[J]. IEEE Transactions on Evolutionary Computation, 2004, 8(3):225-239.