基于遺傳思想的改進粒子群優化算法

佘曉鑫，許波

(廣東石油化工學院計算機與電子信息學院，廣東 茂名 525000)

?

基于遺傳思想的改進粒子群優化算法

佘曉鑫，許波

(廣東石油化工學院計算機與電子信息學院，廣東 茂名 525000)

傳統的粒子群優化算法(Particle Swarm Optimization, PSO)在解決有關離散優化的問題時，容易發生早熟收斂，陷入局部最優等現象，從而得不到最優解。為了克服這種現象，提出了一種基于遺傳思想的改進PSO算法：利用繁殖法更好的搜索粒子的空間，經過繁殖后的粒子可以更好的從局部最優逃離,并對經典的測試函數進行了測試。測試結果表明, 與傳統的PSO算法相比, 改進算法的尋優效果較好，不僅能加快收斂速度，而且能找到同樣甚至更好的解。

粒子群算法；局部最優；群體智能；算法設計；遺傳算法；

粒子群算法(Particle Swarm Optimization, PSO)由美國電氣工程師Eberhart和社會心理學家Kennedy于1995年正式提出[1]，其源于對鳥群捕食行為的研究，模擬鳥群飛行覓食的行為，通過鳥之間的集體協作使群體找到最優[2]。假設一群鳥在一個空間里隨機地尋找食物，并且在這個空間里只有一份食物，同時所有的鳥都不知道食物在哪里，但是它們能判斷自己的位置距離要找的食物還有多遠。如果要找到食物的話，最簡單有效的方法就是搜索食物的附近的鳥，然后查找鳥的周圍的區域，利用在搜索的時候鳥的經驗和自身的經驗就可以很快的找出食物在哪里了。PSO 算法就從這種生物種群行為特性中得到啟發并用于求解優化問題[3]。如果將鳥的這種捕食行為與粒子群優化搜索最優解的方法相對應, 那么每個問題的解對應著搜索空間中的一只鳥，將這只鳥想象為一個只有位置和速度的“粒子”,每個粒子的適應值由一個給定的函數計算得出，粒子的飛行方向和飛行的距離由一個速度量決定。假設粒子知道它到目前為止發現的最好的位置即最優解的位置[4]。不僅如此，每一個粒子自己知道到目前為止，所搜索過的群體中最好的位置在哪里。由此看來求解最優解的過程就可以看成鳥類協作尋找食物的過程，最優解的位置就是食物的位置。

PSO算法具有算法簡潔，易于實現，需要調整的參數少，而且不需要梯度信息等優點，是解決非線性連續優化問題、組合優化問題和混合整數非線性優化問題的有效工具[5,6]。但該算法的全局搜索能力弱，經常發生早熟收斂的現象，容易陷入局部最優從而得不到最優解的情況。為此，筆者提出了一種基于遺傳思想的改進PSO算法。

1　基本粒子群算法

在粒子群算法中，每個個體稱為一個“粒子”同時對應著一個潛在的解[7]。PSO初始的時候隨機產生一群粒子(隨機解)，通過迭代的方式利用2個最優解來更新自己，一個是粒子個體到目前為止找到的局部最優解pbest，另一個是整個粒子群體到目前找到的全局最優解gbest。根據這2個最優解，粒子用式(1)和式(2)來更新自己的飛行速度和位置：

(1)

基本PSO算法的流程[8,9]如下：

1) 初始化。一開始設定粒子的各類參數：搜索范圍，種群規模，學習因子，算法的最大迭代數還有收斂度，粒子速度的范圍。從個體極值中找出最優的作為全局極值，并記錄下來。

2) 檢測粒子適應值。通過所給函數可以計算得出粒子的適應值，當結果比目前粒子本身經歷過的最優值pbest還要好，則更新pbest。比目前粒子群經歷的位置還好時更新gbest。

3) 迭代尋優。通過式(1)和式(2)對粒子的速度和位置進行更新。

4) 檢驗結果。如果當前迭代次數達到了預設定的最大次數或群體迄今為止搜索到的最優位置滿足預定的最小的適應閾值，則停止迭代，得出最優解。否則執行步驟2。

基本的PSO算法在單峰函數中較容易找到極值，因為其函數就只有一個解，所以找到的這個局部極值可以認為是全局最優解，但是多峰函數不同，局部的極值不一定是全局最優解，算法容易把局部最優解當作全局最優解得出結論，從而得不到所需要的最優解[10]。

2　算法改進思想

在基本粒子群算法的粒子速度公式基礎上，增加慣性權值w，位置更新公式不變。當w 較大時全局搜索能力強，局部搜索能力弱，有利于開拓；當w 較小時候全局搜索能力弱，局部搜索能力強，有利于收斂。所以一般把w的值設置為一個隨時間減少的函數。根據改進速度更新公式計算新粒子的速度：

(3)

(4)

式中，wmax、wmin分別為最大、最小慣性權值；nk表示此時的迭代次數；nmax為當前最大的迭代次數。

但是在解決一些問題的時候，改進算法還是不能有效的得出最優解，如多峰函數求解最優值的問題，因為多峰函數有多個局部最優值的“誤導”,使得函數還沒有找到最優解就陷入了局部最優中，即把局部最優解當成全局最優解來看待了，造成了算法的停滯。故筆者在上述改進的基礎上再做如下的改進，即當目前粒子的解等于粒子個體歷史所搜尋到的最優解pbest，或當粒子目前尋找到的解等于粒子群經歷過的歷史最優解gbest時，可以認為算法出現了上述的停滯狀態，這時將這個粒子與處于歷史局部最優的粒子進行雜交，利用式(5)、(6)和式(7)、(8)對粒子的位置和速度進行更新：

child1(xi)=piparent1(xi)+(1-pi)parent2(xi)

(5)

child2(xi)=piparent2(xi)+(1-pi)parent1(xi)

(6)

(7)

(8)

式中，pi是[0,1]之間的隨機數(經驗值為0.2)。

這種方法可以很好的搜索到整個粒子群的空間，快速的搜索到所有的解，當粒子陷入了局部最優時，容易跌入快速下降的陷阱，但經過迭代繁殖后粒子很容易脫離局部最優的束縛，同時產生同樣數目的子代，粒子的種群數目不變，保證了種群多樣性，這種方法的好處在于可以使粒子脫離局部最優的約束，避免了算法的停滯，加快收斂速度，而且找到了同樣甚至更好的解。

具體實現思路如下:計算粒子的適應度時，如果當前粒子的適應度等于歷史個體粒子的最優解pbest，或者當前粒子的適應度等于歷史全局最優解gbest時，將這個粒子與處于歷史局部最優的粒子進行雜交，利用式(5)、(6)和式(7)、(8)對粒子的位置和速度進行更新。如果粒子的個體極值pbest優于全局極值gbest，則將個體極值取代原來的全局極值，即更新gbest。

3　算法步驟

1)初始化。設定粒子的各類參數：搜索范圍，種群規模，慣性權值w的上下限，學習因子，算法的最大迭代數還有收斂度，粒子速度的范圍。從個體極值中找出最優的作為全局極值，并記錄下來。

2)按照所給函數計算粒子的適應值。

3)按照式(4)計算慣性權值w的值。

4)根據原公式對粒子更新位置，并對粒子進行位置限幅處理。

5)根據所給函數重新評價各粒子的適應值。

6)計算粒子的適應度，如果當前粒子的適應度等于粒子個體歷史所搜尋到的的最優解pbest，或者當前粒子的適應度等于粒子群經歷過的歷史最優解gbest時，將這個粒子與處于歷史局部最優的粒子進行雜交，利用式(5)、(6)和式(7)、(8)對粒子的位置和速度進行更新。

7)如果粒子的個體極值優于全局極值，則將個體極值取代原來的全局極值成為新的全局極值。

8)檢驗是否滿足結束的條件。如果當前迭代次數達到了預設定的最大次數或群體迄今為止搜索到的最優位置滿足預定的最小的適應閾值，則停止迭代，輸出最優解。否則返回步驟2)。

4　測試結果與分析

采用Matlab工具實現PSO算法，通過對基本粒子群算法和改進粒子群算法的函數測試曲線分析得出結論，采用函數為基本測試函數。

測試函數1(Ackley函數)：

這是一個無約束優化問題，函數為連續、旋轉、不可分離的多峰函數。主要通過一個余弦波形來調整指數函數,該函數特征是由余弦波調制而成的“峰”，使得該函數變得起伏不平。其全局最優解在邊緣上，如果算法的初始值在邊緣上，那么很快就可以解決問題，但在這里的形式更加普遍，維數可調整。其拓撲結構特征是：函數的周圍邊緣的部分平坦，在中間出現一個突出來的峰值，從而函數的圖形變得起伏不平。該多峰函數具有大量的局部最優點。測試結果如圖1所示。

圖1　Ackley函數測試結果

測試函數2(Rastrigin 函數)：

這個函數基于Sphere函數的基礎，運用了余弦函數產生了許多局部最優解，是一個比較復雜的多峰函數處理問題，該函數很容易陷入局部最優解，將局部最優作為最終結果，從而得不到全局最優解，全局最優解f(x)=0在點x=(0,…,0)處。測試結果如圖2所示。

圖2　Sphere函數測試結果

測試函數3(Shaffer函數):

該函數是一個多峰函數，有無數個極小值點，一般很難找到全局最優解，其中只有一個最小值的點，就是當函數在(0，0)的時候，函數有最小值為0。測試結果如圖3所示。

圖3　Shaffer函數測試結果

從測試結果圖1～圖3來看，基本粒子群算法在解決多峰函數的問題的時候容易陷入局部最優值，跌入快速下降的陷阱，得到的全局最優解往往偏差較大，而改進的粒子群算法在陷入局部最優的時候能較好的跳出局部最優解，繼續尋找，避免了算法停滯，最終得到的解往往比基本粒子群算法更好。

5　結語

提出了一種基于遺傳思想的改進PSO算法，并對經典的測試函數進行了測試，試驗結果表明，與傳統的PSO算法相比，改進的算法的尋優效果較好，不僅能加快收斂速度，而且能找到同樣甚至更好的解。

[1]紀震，廖惠連，吳青華. 粒子群算法及應用[M] .北京：科學出版社，2009：58～64.

[2]Xu Bo, Guan Qing , Chen Ke. Multi-agent Coalition Formation Based on Quantum-behaved Particle Swarm Optimization [J].Journal of Information and Computational Science, 2010,7(5):1059～1064.

[3]溫濤, 盛國軍, 郭權, 等. 基于改進粒子群算法的 Web 服務組合[J]. 計算機學報, 2013, 36(5): 1031～1046.

[4]范成禮, 邢清華, 范海雄, 等. 帶審斂因子的變鄰域粒子群算法[J]. 控制與決策, 2014, 29(4): 696～700.

[5]Mandal D, Kar R, Ghoshal S P. Digital FIR filter design using fitness based hybrid adaptive differential evolution with particle swarm optimization [J]. Natural Computing, 2014, 13(1): 55～64.

[6]Palafox L, Noman N, Iba H. Reverse engineering of gene regulatory networks using dissipative particle swarm optimization [J]. Evolutionary Computation, IEEE Transactions on, 2013, 17(4): 577～587.

[7]周新宇, 吳志健, 王暉, 等. 一種精英反向學習的粒子群優化算法[J]. 電子學報, 2013, 41(8): 1647～1652.

[8]溫雅, 李國, 徐晨. 一種帶交叉因子的雙向尋優粒子群優化算法[J]. 計算機應用研究, 2013, 30(1): 82～85.

[9]朱兆杰, 賈振紅, 覃錫忠,等. 基于改進的粒子群算法的移動互聯網擴散預測[J]. 計算機應用與軟件, 2015, 32(7):126～128.

[10]Xu Bo, Yang Zhaofeng, Ge Yu, et al. Coalition formation in multi-agent systems based on improved particle swarm optimization algorithm [J]. International Journal of Hybrid Information Technology，2015, 8(3)：1～8.

[編輯]洪云飛

2016-04-27

國家自然科學基金項目 (61272382), 廣東省云機器人(石油化工)工程技術研究中心項目 ( 2015B090903084)；廣東省教育廳青年創新人才類項目(自然科學類)(2015KQNCX099)。

許波(1982-), 男, 博士，副教授，現主要從事計算智能方面的教學與研究工作；E-mail:xubo807127940@163.com 。

TP18

A

1673-1409(2016)22-0004-05

[引著格式]佘曉鑫，許波.基于遺傳思想的改進粒子群優化算法[J].長江大學學報(自科版)，2016,13(22)：4～8.