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

佘曉鑫，許波

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

?

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

佘曉鑫，許波

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

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

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

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

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

1　基本粒子群算法

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

(1)

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

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

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

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

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

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

2　算法改進(jìn)思想

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

(3)

(4)

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

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

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

(5)

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

(6)

(7)

(8)

式中，pi是[0,1]之間的隨機(jī)數(shù)(經(jīng)驗(yàn)值為0.2)。

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

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

3　算法步驟

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

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

3)按照式(4)計(jì)算慣性權(quán)值w的值。

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

5)根據(jù)所給函數(shù)重新評(píng)價(jià)各粒子的適應(yīng)值。

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

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

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

4　測(cè)試結(jié)果與分析

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

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

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

圖1　Ackley函數(shù)測(cè)試結(jié)果

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

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

圖2　Sphere函數(shù)測(cè)試結(jié)果

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

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

圖3　Shaffer函數(shù)測(cè)試結(jié)果

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

5　結(jié)語

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

[1]紀(jì)震，廖惠連，吳青華. 粒子群算法及應(yīng)用[M] .北京：科學(xué)出版社，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]溫濤, 盛國(guó)軍, 郭權(quán), 等. 基于改進(jìn)粒子群算法的 Web 服務(wù)組合[J]. 計(jì)算機(jī)學(xué)報(bào), 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]周新宇, 吳志健, 王暉, 等. 一種精英反向?qū)W習(xí)的粒子群優(yōu)化算法[J]. 電子學(xué)報(bào), 2013, 41(8): 1647～1652.

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

[9]朱兆杰, 賈振紅, 覃錫忠,等. 基于改進(jìn)的粒子群算法的移動(dòng)互聯(lián)網(wǎng)擴(kuò)散預(yù)測(cè)[J]. 計(jì)算機(jī)應(yīng)用與軟件, 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

國(guó)家自然科學(xué)基金項(xiàng)目 (61272382), 廣東省云機(jī)器人(石油化工)工程技術(shù)研究中心項(xiàng)目 ( 2015B090903084)；廣東省教育廳青年創(chuàng)新人才類項(xiàng)目(自然科學(xué)類)(2015KQNCX099)。

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

TP18

A

1673-1409(2016)22-0004-05

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