微粒群算法的分析與展望

摘要：圍繞微粒群（PSO）算法的原理、特點(diǎn)、改進(jìn)、應(yīng)用等方面進(jìn)行全面綜述，并對其在理論研究和技術(shù)應(yīng)用兩方面的研究現(xiàn)狀和未來的發(fā)展方向進(jìn)行綜述。

關(guān)鍵字：微粒群算法；進(jìn)化計算；離散優(yōu)化；多目標(biāo)優(yōu)化

中圖分類號：TP18文獻(xiàn)標(biāo)識碼：A文章編號：1009-3044(2008)33-1378-03

Particle Swarm Optimization Algorithm Analysis and Forecast

ZHANG Jie

(Jiangsu food science college ，Huai'an 223003， China)

Abstract: Encompassment Particle Swarm Optimization (PSO) aspects and so on algorithm principle， characteristic， improvement， application carry on the comprehensive summary， and will apply two aspects to it in the fundamental research and the technology the research present situations and the future development direction carries on the summary.

Key words: particle swarm optimization algorithm; evolution computation; separate optimization; multi-objective optimization

1 引言

微粒群算法（PSO）是J.Kennedy和R.C.Eberhart[1]于1995年提出的一種新的進(jìn)化算法，借鑒了鳥群或魚群捕食過程的社會行為，將群體中的成員描述為空間內(nèi)一個沒有質(zhì)量、沒有體積的“微粒”，所有微粒通過一個適應(yīng)函數(shù)來確定其在空間中的適應(yīng)度。進(jìn)化初期，每個微粒的位置和速度都被隨機(jī)初始化，微粒在飛行過程中相互合作，根據(jù)自身和同伴的運(yùn)動狀態(tài)及時調(diào)整自己的速度和位置，以便在適應(yīng)值較好的位置降落。微粒群算法概念簡明，參數(shù)設(shè)置少，并能根據(jù)當(dāng)前的搜索情況動態(tài)調(diào)整搜索策略，對解決復(fù)雜環(huán)境中的優(yōu)化問題非常有效。目前已成功的運(yùn)用到電力、通訊、生物信息、醫(yī)學(xué)等各個領(lǐng)域。

2 標(biāo)準(zhǔn)微粒群算法

2.1 微粒群算法基本原理

微粒群算法將每一個可能產(chǎn)生的解表述為群中的一個微粒，每個微粒都有自己的速度和位置向量，以及一個由目標(biāo)函數(shù)決定的適應(yīng)值，所有微粒在搜索空間中以一定速度飛行，通過追隨當(dāng)前搜索到的最優(yōu)適應(yīng)值來尋找全局最優(yōu)。

在N維空間中有 M個微粒，每個微粒的位置表示一個潛在的解。設(shè)[2]

Xi=(xi1，xi2，..，xin)為微粒i的當(dāng)前位置；

Vi=(vi1，vi2，..，vin)為微粒i的當(dāng)前速度；

Pi=(pi1，pi2，..，pin)為微粒i所經(jīng)歷的最好位置，即為 Pbest；

Pg為群體中所有微粒所經(jīng)過的最好位置，也稱為 gbest。

則對于每一代，微粒i的第j維的進(jìn)化方程為：

vij(t+1)=ωvij(t)+c1rand()(pij(t)-xij(t))+c2Rand()(pg(t)-xij (t))(1)

xij(t+1)=xij(t)+vij(t+1) (2)

其中：ω為慣性權(quán)重 (inertia weight)，c1和c2為加速常數(shù) (accelerationconstants)，rand()和Rand()為兩個在 0，1范圍內(nèi)變化的隨機(jī)函數(shù)。在 (1)式中第一部分為微粒先前的速度；第二部分為 “認(rèn)知 (cognition)”部分，表示微粒本身的思考，通過自己的經(jīng)驗來判斷當(dāng)前的飛行；第三部分為 “社會 (social)”部分，表示微粒間的信息共享與相互合作，借鑒其他微粒的飛行經(jīng)驗來調(diào)整當(dāng)前的飛行。

2.2 算法基本流程

標(biāo)準(zhǔn)微粒群算法的流程如下：

1）隨機(jī)初始化微粒的位置和速度。

2）計算每個微粒的適應(yīng)值。

3）對于每個微粒，將其適應(yīng)值與所經(jīng)歷過的最好位置 Pi的適應(yīng)值進(jìn)行比較，若較好，則將其作為當(dāng)前的最好位置。

4）對每個微粒，將其適應(yīng)值與全局所經(jīng)歷的最好位置 Pg的適應(yīng)值進(jìn)行比較，若較好，則將其作為當(dāng)前的全局最好位置。

5）根據(jù)方程 (1)、(2)對微粒的速度和位置進(jìn)行進(jìn)化。

6）如未達(dá)到結(jié)束條件 (通常為足夠好的適應(yīng)值或達(dá)到一個預(yù)設(shè)的最大代數(shù))，則返回步驟 2）。

3 微粒群算法的改進(jìn)策略

微粒群算法作為一種新的進(jìn)化算法，經(jīng)過十多年的發(fā)展已獲得了很大的進(jìn)展。不同領(lǐng)域的專業(yè)人員都結(jié)合本專業(yè)的知識從不同側(cè)面對基本微粒群算法進(jìn)行改進(jìn)，并通過仿真實(shí)驗進(jìn)行驗證，取得不錯的效果，為微粒群算法的理論提供了佐證，很大程度上推動了微粒群算法的發(fā)展。

3.1 算法參數(shù)和結(jié)構(gòu)優(yōu)化

1）調(diào)整慣性權(quán)重ω

Shi，Eberhart[3-4]研究了慣性因子ω對優(yōu)化性能的影響：發(fā)現(xiàn)較大的ω值有利于跳出局部極小點(diǎn)，較小的ω值有利于算法的收斂，并先后提兩種調(diào)整方法。自適應(yīng)算法通過線性地減小ω值動態(tài)的調(diào)整參數(shù)ω，這使得算法在迭代初期探索能力較強(qiáng)，可以不斷搜索新的區(qū)域，之后開發(fā)能力逐漸增強(qiáng)，使算法在可能解周圍進(jìn)行細(xì)致搜索。模糊算法則是利用模糊規(guī)則動態(tài)調(diào)整參數(shù)ω的值，通過對當(dāng)前最好性能評價 (CBPE)和當(dāng)前慣性權(quán)重制定相應(yīng)的隸屬函數(shù)和模糊推理規(guī)則確定慣性權(quán)重ω的增量，結(jié)果顯示該方法能獲得與慣性權(quán)重遞減的算法類似甚至更好的結(jié)果。

2）增加收縮因子λ

Clerc首次提出了帶有收縮因子的微粒群算法，其數(shù)學(xué)表達(dá)式為：

vij(t+1)=λ[ωvij(t)+c1rand()(pij(t)-xij(t))+c2Rand()(pg(t) -xij(t))](3)

式中：λ=■為收縮因子，ω=c1+c2，ω>4

Eberhar和Shi分別利用Vmax和收縮因子來控制微粒的速度，并對兩種方法進(jìn)行比較，結(jié)果后者比前者通常能夠取得更好的收斂率。由于微粒可能偏離所期望的搜索空間導(dǎo)致在指定代數(shù)內(nèi)無法達(dá)到全局極值點(diǎn)，因此應(yīng)該預(yù)先設(shè)置搜索空間的大小或者設(shè)置參數(shù) Vmax=Xmax，以便對算法進(jìn)行限定，從而保證無論在收斂率還是搜索性能方面都有所改進(jìn)。

此外，研究者就其他參數(shù)對算法性能的影響也進(jìn)行了研究。P.N.Suganthan用實(shí)驗表明 c1和c2的值為常數(shù)時可以獲得較好的解，但不一定為 2。群體的初始化也對算法性能有所影響，但不十分明顯。

3）與其他算法結(jié)合

與遺傳算法的結(jié)合，Lovbjerg [5]提出了雜交算法.微粒被賦予一個雜交概率，再每次迭代中，依據(jù)雜交概率選定微粒然后微粒再兩兩雜交，微粒數(shù)目不會變化，用子代微粒代替父代微粒。

child1(Xi)=p *parent1(Xi)+(1-p)*parent2(Xi)

child2(Xi)=p *parent2(Xi)+(1-p)*parent1(Xi)(4)

其中，p是均勻分布在 0-1之間的隨機(jī)數(shù)，后代的速度向量由父母向量之和歸一化后得到：

Child1(Vi)=|parent1(Vi)|

Child2(Vi)=|parent2(Vi)| (5)

實(shí)驗證明，雜交微粒群算法收斂速度較快，搜索精度也較高.但調(diào)整參數(shù)較多，增加了算法的復(fù)雜性。

國內(nèi)學(xué)者，高鷹，謝勝利[6]將模擬退火思想引人到微粒群算法中，避免了微粒陷人局部最優(yōu)，提高了收斂性能。

Angeline[7]把進(jìn)化規(guī)劃中使用的競爭選擇方法引人微粒群算法，采用進(jìn)化計算中的錦標(biāo)賽選擇方法：將每個個體的適應(yīng)度基于當(dāng)前的位置與其他K個個體進(jìn)行比較，記下最差的一個得分，并根據(jù)比較結(jié)果進(jìn)行排序，用微粒群中最好一半的當(dāng)前位置和速度替換較差一半的位置和速度，同時保留每個個體所記憶的最好位置。實(shí)驗證明該方法是一種更具開發(fā)能力的算法機(jī)制，但易陷入局部最優(yōu)。

3.2 離散優(yōu)化

由于許多實(shí)際工程的優(yōu)化問題并非連續(xù)空間，微粒群算法必定要進(jìn)行離散空間擴(kuò)展。為了保持與連續(xù)空間的一致性，離散二進(jìn)制的威力速度和位置公式如下:

Vid (t+1)=wVid (t)+c1rand ()[Pid (t)-Xid (t)]+c2Rand[Pgd (t)-Xid (t)]

If (rand()S(Vid(t+1))) then Xid (t) =1

Else Xid(t)=0 (6)

式中，S(Vid(t + 1 ))= 1/[1+exp(-Vid)]為Sigmoid函數(shù)，速度分量Vid決定了位置分量取1和0的概率。同時，離散二進(jìn)制算法中，保留了V max，它起限制Xid取1和0的最終概率作用。

3.3 多目標(biāo)優(yōu)化

在社會生產(chǎn)及工程實(shí)踐中很多優(yōu)化問題都是多目標(biāo)優(yōu)化問題。傳統(tǒng)的多目標(biāo)優(yōu)化方法是將多目標(biāo)轉(zhuǎn)化為單目標(biāo)。而PSO在求解多目標(biāo)問題上有很大的優(yōu)勢，可以并行搜索空間多個解。文獻(xiàn)[8]首先將PSO運(yùn)用到尋求多目標(biāo)最優(yōu)問題上。文獻(xiàn)[9]針對直接使用PSO算法處理多目標(biāo)優(yōu)化問題很容易出現(xiàn)非劣最優(yōu)域的局部收斂提出了最優(yōu)解評估選取的PSO算法。

4 分析與展望

微粒群算法作為一種新興的進(jìn)化算法，相對于其它比較成熟的智能算法來說，微粒群算法的研究還處于起步階段，還存在很多問題有待深人研究和解決可以歸納為以下幾點(diǎn):

1）PSO 的理論研究。應(yīng)該注重算法收斂性、收斂速度、參數(shù)選取、參數(shù)魯棒性等方面的理論探討，包括多目標(biāo)、約束、離散和動態(tài)環(huán)境下PSO 算法的相關(guān)理論研究。

2）PSO 的算法研究。應(yīng)該注重高效PSO 的開發(fā)，提出合理的核心更新公式以及有效的均衡全局搜索和局部改進(jìn)的策略。考慮到No Free Lunch 定理以及特定問題的特殊性，應(yīng)該注重高效混合PSO方法的設(shè)計，包括PSO 與問題信息或規(guī)則、PSO 與神經(jīng)網(wǎng)絡(luò)、模糊邏輯、進(jìn)化算法、模擬退火、禁忌搜索、生物智能以及混沌等方法或策略的結(jié)合。另外，鑒于PSO 對算法參數(shù)的依賴性，提出合理選取參數(shù)的指導(dǎo)性方法或結(jié)論同樣值得重視。

3）PSO 的應(yīng)用研究。目前，PSO 的應(yīng)用大量局限于連續(xù)、單目標(biāo)、無約束的確定性優(yōu)化問題。因此，應(yīng)該注重PSO 在離散、多目標(biāo)、約束、不確定、動態(tài)等優(yōu)化問題上的探討和應(yīng)用。同時，PSO 的應(yīng)用領(lǐng)域也有待進(jìn)一步拓寬。就化工及自動化領(lǐng)域而言，問題的多極小性、多約束性、離散連續(xù)變量共存、非線性、多目標(biāo)性、不確定性等復(fù)雜性普遍存在，因此PSO 在該領(lǐng)域的研究與應(yīng)用是一個很有前景的課題。

參考文獻(xiàn)：

[1] Kennedy J， Eberhart R C. Particle Swarm Optimization[C]. IEEE International Conference on Neural Networks， IEEE Service Center， 1995:1942-1948.

[2] 曾建潮，介婧，崔志華.微粒群算法 [M].北京：科學(xué)出版社， 2004.

[3] Shi Y，Eberhart R C. A modified particle swarm optimizer[C]. Piscataway， NJ， IEEE Press. Proceedings of the IEEE International Conference on Evolutionary Computation，1998:69～73.

[4] Shi Y，Eberhart R C.Empirical study of particle swarmoptimization[C]. Piscataway， NJ， IEEEService Center. Proceedings of the 1999 Congress on Evolutionary Computation，1999:1945-1950.

[5] Lovbjerg MR . Ussen T K，Hybrid K T. Particle Swarm optimization With Breeding and Subpopulatious[C]. Prec Of Genetie and Evolutionary Computation Conference，2001.

[6] 高鷹，謝勝利.基于模擬退火的粒子群優(yōu)化算法[J].一計算機(jī)工程與應(yīng)用，2004(1): 47-50.

[7] Angeline P J.Using selection to improve particle swarm optimization[C]. Proceedings of the 1998 International Conference on Evolutionary Computation， NewYork，NY，USA:IEEE，1998:84-89.

[8] Schaffer J D.Multiple objective optimization with vector evaluated genetic algorithms[C]. The First Int'1 Conf on Genetic Algorith ms，Lawrence Erlba UITI，1985.

[9] 張利彪，周春光，馬銘.基于粒子群算法求解多目標(biāo)優(yōu)化問題[J].計算機(jī)研究與發(fā)展， 2004，41(7):1286-1291.

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。”