佘曉鑫，許波

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

?

基于遺傳思想的改進粒子群優(yōu)化算法

佘曉鑫，許波

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

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

粒子群算法；局部最優(yōu)；群體智能；算法設計；遺傳算法；

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

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

1　基本粒子群算法

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

(1)

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

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

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

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

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

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

2　算法改進思想

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

(3)

(4)

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

但是在解決一些問題的時候，改進算法還是不能有效的得出最優(yōu)解，如多峰函數(shù)求解最優(yōu)值的問題，因為多峰函數(shù)有多個局部最優(yōu)值的“誤導”,使得函數(shù)還沒有找到最優(yōu)解就陷入了局部最優(yōu)中，即把局部最優(yōu)解當成全局最優(yōu)解來看待了，造成了算法的停滯。故筆者在上述改進的基礎上再做如下的改進，即當目前粒子的解等于粒子個體歷史所搜尋到的最優(yōu)解pbest，或當粒子目前尋找到的解等于粒子群經(jīng)歷過的歷史最優(yōu)解gbest時，可以認為算法出現(xiàn)了上述的停滯狀態(tài)，這時將這個粒子與處于歷史局部最優(yōu)的粒子進行雜交，利用式(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]之間的隨機數(shù)(經(jīng)驗值為0.2)。

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

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

3　算法步驟

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

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

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

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

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

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

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

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

4　測試結果與分析

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

測試函數(shù)1(Ackley函數(shù))：

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

圖1　Ackley函數(shù)測試結果

測試函數(shù)2(Rastrigin 函數(shù))：

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

圖2　Sphere函數(shù)測試結果

測試函數(shù)3(Shaffer函數(shù)):

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

圖3　Shaffer函數(shù)測試結果

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

5　結語

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

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

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

[9]朱兆杰, 賈振紅, 覃錫忠,等. 基于改進的粒子群算法的移動互聯(lián)網(wǎng)擴散預測[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)；廣東省教育廳青年創(chuàng)新人才類項目(自然科學類)(2015KQNCX099)。

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

TP18

A

1673-1409(2016)22-0004-05

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