李 娥, 高興寶

(陜西師范大學數(shù)學與信息科學學院， 陜西 西安 710062)

0 引 言

群體智能產(chǎn)生于20世紀90年代, 它通過模擬生物群體行為來解決優(yōu)化問題的演化計算技術. 基于群體智能理論,Kennedy和Eberhart 提出了粒子群算法(PSO)[1-2], 其基本原理是通過群體中粒子跟蹤自己和群體所發(fā)現(xiàn)的最優(yōu)值, 修正前進方向和速度, 實現(xiàn)尋優(yōu). PSO算法由于理論簡單、易于實現(xiàn)、需要設置的參數(shù)少、收斂速度較快等特點,被廣泛應用于函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡優(yōu)化、模糊系統(tǒng)控制、電力系統(tǒng)優(yōu)化、車間調度、負荷經(jīng)濟分配[3-7]等領域. 然而在處理多局部極值問題時, 其存在難以跳出局部極值, 收斂效率低等缺陷. 針對這些問題, 作者提出了一種基于階段進化適應性策略的粒子群算法. 該算法把整個進化過程分為三個階段, 每個階段采用不同的進化策略. 與標準粒子群算法相比, 該算法的全局搜索能力、避免早熟的能力均有了顯著提高, 同時也提高了收斂速度.

粒子群算法[8]是一種模擬鳥類捕食行為的群體智能優(yōu)化算法. 鳥類在尋找食物的過程中, 每只鳥都會根據(jù)自己的飛行經(jīng)驗以及同群體中的其它個體的交流來改變自己的飛行方向或者調整飛行速度, 以便能更快速有效地找到食物所在地， PSO就是通過粒子間的相互作用和對解空間的并行搜索尋找最優(yōu)解. 用vi=(vi1,vi2,…,vin)表示第i個粒子的飛行速度,xi=(xi1,xi2,…，xim)表示其位置;pbesti表示粒子i所經(jīng)過的最好位置, 稱為個體最優(yōu);gbest表示群體中所有粒子當前最優(yōu)位置, 稱為全局最優(yōu);t表示進化代. 為討論方便, 設f(x)為適應度函數(shù),PSO流程如下:

步(1)迭代開始t=0，初始化粒子群: 給定群體規(guī)模n, 隨機產(chǎn)生每個粒子的速度vi和位置xi.

步(2)計算每個個體的適應值f(xi(t)).

步(3)確定個體最優(yōu)位置(pbesti(t)), 粒子i當前最優(yōu)位置由下式來確定:

步(4)確定群體最優(yōu)位置(gbest(t)), 它由下式確定:

gbest(t)∈{pbest1(t),pbest2(t),…,pbestn(t)}|f(gbest(t))

=max{f(pbest1(t)),pbest2(t)),…,pbestn(t))}

步(5)更新速度和位置:

vi(t+1)=vi(t)+c1r1(pbesti(t)-xi(t))+c2r2(gbest(t)-xi(t))

xi(t+1)=xi(t)+vi(t+1)

其中c1,c2是學習因子, 且為[0,2]上的常數(shù);r1,r2是[0,1]之間的隨機數(shù).

步(6)判斷是否達到終止條件. 若終止條件成立則停止; 否則t=t+1，轉步(2).

由于基本PSO的參數(shù)是固定的, 在求解某些優(yōu)化問題時精度較差，因此通過長期的研究, 人們對速度更新公式進行改進. 特別地, 文獻[9]在速度更新公式中加入了慣性權重w,即vi(t+1)=wvi(t)+c1r1(pbesti-xi)+c2r2(gbest-xi) ,其中w∈[0,1.4]是一常數(shù). 為了進一步提高粒子群算法的性能, 文獻[10,11]提出了如下慣性權重w線性遞減的改進:

其中T為最大迭代次數(shù),wmax為迭代至最大迭代次數(shù)時的慣性權重,wmin為初始慣性權重. 該算法在搜索初期具有較強的搜索能力, 而在后期又能夠得到較精確的結果, 從而大大提高了基本PSO的性能, 因此被稱為標準粒子群算法. 但對于多峰函數(shù)優(yōu)化問題, 易出現(xiàn)早熟現(xiàn)象. 為克服這一缺點, 本文提出了一種基于階段進化適應性策略的改進算法.

1 改進的粒子群算法

不像遺傳算法, 粒子群優(yōu)化算法一般采用實數(shù)編碼, 并且大多數(shù)情況也沒有選擇、交叉和變異操作, 因此算法結構相對簡單, 運行速度較快. 但在算法運行過程中, 如果某粒子發(fā)現(xiàn)一個當前最優(yōu)位置, 其他粒子將迅速向其靠攏. 如果該最優(yōu)位置為一局部最優(yōu)點,粒子群就無法在解空間重新搜索, 因此算法陷入局部最優(yōu), 出現(xiàn)了所謂的早熟收斂現(xiàn)象以及由此導致的收斂精度低和不易收斂等缺點, 尤其對高維問題更易出現(xiàn)上述現(xiàn)象. 針對上述問題, 受人類進化過程的啟發(fā), 我們將文獻[13]中遺傳算法的基于階段進化的適應性策略引入到粒子群算法, 提出了一種如下的改進方案, 稱為階段進化適應性策略粒子群算法(記作EPSO). 按照遺傳算法階段進化適應性策略, 我們將進化過程分為三個階段: 探索階段，開發(fā)階段和收斂階段. 在探索階段, 采用較大的群體規(guī)模、 慣性權重以增強粒子的探索能力, 并引入變異操作保持群體的多樣性; 在開發(fā)階段, 由于群體逐漸轉入面向局部的開發(fā)過程, 所以采用較小的群體規(guī)模和變化的慣性權重; 在收斂階段, 由于粒子要逐漸收斂到最優(yōu)解， 故采用小的群體規(guī)模和慣性權重, 且為避免早熟收斂, 引入變異操作. 根據(jù)多次反復試驗, 基于階段進化的適應性策略模型如下:

(1) 進化階段: 設α∈[0,0.5]最大進化代數(shù)為T, 三階段劃分如下:

第一階段(探索階段):I1=[0,T1],T1=αT.第二階段(開發(fā)階段):I2=[T1+1,T2],T2=T(1-α).第三階段(收斂階段):I3=[T2+1,T].

一般地, 取α=0.382.

(2) 群體規(guī)模: 固定參數(shù)群體規(guī)模為n, 在進化第一階段采用較大群體規(guī)模n1, 第二、三階段采用較小群體n2,n3,它們的選取不能過大也不能過小. 根據(jù)多次反復實驗，可取n1=n,n2=0.7n,n3=0.5n.

(3) 慣性權重: 第一階段采用較大的慣性權重, 一般可取w=0.8, 第二階段采用線性遞減的慣性權重[11], 即

第三階段采用較小的慣性權重, 一般可取w=0.4.

(4) 變異操作: 第一、第三階段引入變異操作，增加搜索空間多樣性和避免早熟現(xiàn)象. 因為搜索空間的多樣性同時受w和變異概率pm的影響, 且第一階段w取值較大，所以其變異概率相對要小一點, 一般可取pm=0.01; 第三階段w較小, 但由于粒子在這一階段要收斂, 還要避免早熟, 因此變異概率相對要大一點，但不能過大. 經(jīng)反復試驗, 可取pm=0.05. 變異操作按照如下公式進行:

其中r1,r2是[0,1]內的隨機數(shù).

2 數(shù)值仿真

本文用4個基準測試函數(shù)[14]在Matlab上進行數(shù)值仿真, 其參數(shù)設置如下: 群體規(guī)模為30, 最大迭代次數(shù)為1 000, 學習因子c1,c2均為2;wmax=0.9，wmin=0.4.為消除隨機干擾， 每個函數(shù)獨立運行30次, 然后取其平均值. 在同樣的參數(shù)設置下, 與標準粒子群算法進行比較.

例 1 Sphere Model 函數(shù)

顯然它是單峰可分的二次函數(shù), 且僅有一個全局極小點x*=(0,0,…,0),最優(yōu)值為f1(x*)=0. 圖1顯示了標準PSO算法和改進 PSO算法的最優(yōu)值隨迭代次數(shù)的變化曲線.

例2 Griewank函數(shù)

它具有大量局部極值點, 是不可分離的多峰函數(shù)，有一個全局極小點x*=(0,0,…,0), 最優(yōu)值為f2(x*)=0. 圖2顯示了標準PSO算法和改進PSO算法的最優(yōu)值隨迭代次數(shù)的變化曲線.

圖1 例1中最優(yōu)值隨迭代次數(shù)的變化曲線 圖2 例2中最優(yōu)值隨迭代次數(shù)的變化曲線

例3 Rastrigin函數(shù)

它是多峰函數(shù), 有一個全局極小點x*(0,0,…,0), 最優(yōu)值為f3(x*)=0. 圖3顯示了標準PSO算法和改進PSO算法的最優(yōu)值隨迭代次數(shù)的變化曲線.

圖3 例 3中最優(yōu)值隨迭代次數(shù)的變化曲線 圖4 例 4中最優(yōu)值隨迭代次數(shù)的變化曲線

例4 Schaffer's f6函數(shù).

譯員由于不能確認被告的意思而與被告展開了對話——對電話號碼的事情進行了澄清，以便把完整的意思翻譯給法官聽。這種澄清的行為對避免誤譯時是必要的。但是，本例中的問題是譯員自行與被告展開了對話，法官可能因此對譯員產(chǎn)生不信任并提出批評。比較好的調解策略是譯員先獲得法庭的許可。由于口譯過程一般以第一人稱進行，譯員應該讓法庭知道下面的請求是譯員提出的：“法官大人，譯員不是很明白被告的話，請允許譯員要求被告澄清。”在法官許可后再要求說話者澄清。譯員也會因為其專業(yè)性的調解行為而贏得法庭的尊重。

它是多峰函數(shù), 有一個全局極小點x*=(0,0), 最優(yōu)值為f4(x*)=0. 圖4顯示了標準PSO算法和改進PSO算法的最優(yōu)值隨迭代次數(shù)的變化曲線.

4個函數(shù)在標準PSO算法和改進PSO算法下的數(shù)值結果見表1.

表1 函數(shù)運行30次比較表

從表1可以看出，改進的PSO在F4函數(shù)上的效果明顯好于標準PSO，達到了理論最優(yōu)值. 其余3個函數(shù)雖沒有達到理論最優(yōu)值，但是從圖1至圖3可以看出，它們避免了早熟現(xiàn)象, 在要求的精度內收斂到了全局最優(yōu), 其結果好于標準PSO的結果. 改進的PSO在單峰函數(shù)上的效果不是很明顯，但它和標準的PSO相比提高了收斂速度.

3 結束語

PSO 算法理論簡單、易實現(xiàn)、需要設置的參數(shù)少、收斂較快等優(yōu)點, 但也存在著早熟收斂、收斂效率低的缺點， 本文針對這一缺點提出了一種改進算法, 即基于階段進化適應性策略的粒子群算法. 該算法把進化過程分為三個階段, 每個階段采用不同的慣性權重、 群體規(guī)模, 并在第一階段和第三階段引入了不同的變異操作, 以增強粒子跳出局部最優(yōu)的能力. 通過和標準粒子群算法比較的實驗結果可以看出, 該算法收斂到了全局最優(yōu)解, 具有較好的收斂性和收斂效率, 克服了PSO算法易“早熟”的缺點.

參考文獻

[1] Kennedy J, Eberhart R C. Particle swarm optimization[A]. Proc IEEE Conf on Neural Networks[C]. Piscataway: IEEE Press, 1995：1 942-1 948.

[2] Eberhart R C, Kennedy J. A new optimizer using particles warm theory[A]. Proc of the 6th International Symposium on Micro Machine and Human Science[C]. Nagoya, 1995：39-43.

[3] 劉華鎣, 林月娥, 齊名軍. 求解約束優(yōu)化問題的改進的粒子群算法[J]. 大慶石油學院學報, 2005, 29(4):73-75.

[4] He Z, Wei C, Yang L. Extracting rules from fuzzy neural network by particle swarm optimization[A]. Proc IEEE Conf on Evolutionary Computation[C]. Piscataway: IEEE Press, 1999：1 927-1 930.

[6] Pan Q K, Tasgetiren M F, Liang Y C. A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem[J]. Computers and Operations Research, 2008, 35:2 807-2 839.

[7] Panigrahi B K, Pandi V R, Sanjoy Das. Adaptive particle swarm optimization approach for static and dynamical economic load dispatch[J]. Energy Conversion and Management, 2008, 49: 1 407-1 415.

[8] 凡 濤, 陳光喜. 多目標粒子群優(yōu)化算法的改進及其應用[D]. 桂林：桂林電子科技大學碩士學位論文, 2010.

[9] Shi Y H, Eberhart R C. A modified particle swarm optimizer[A]. IEEE World Congress on Computational Intelligence [C]. Anchorage, 1998：69-73.

[10] Eberhart R C, Shi Y H. Comparing inertia weights and constriction factors in particle swarm optimization[A]. Proc 2000 Congress Evolutionary Computation[C]. Piscataway: IEEE Press, 2000：84-88.

[11] Kennedy J, Eberhart R C, Shi Y H. Swarm Intelligence[M]. San Francisco: Morgan Kaufman Publishers, 2001.

[12] 呂振肅, 侯志榮. 自適應變異的粒子群優(yōu)化算法[J]. 電子學報, 2004，(3): 416-420.

[13] 李敏強, 寇紀淞, 林 丹,等. 遺傳算法的基本理論與應用[M]. 北京: 科學出版社, 2002.

[14] 紀 震, 廖惠連, 吳青華. 粒子群算法及其應用[M]. 北京: 科學出版社, 2009.