基于多模態(tài)優(yōu)化問題的粒子群算法研究

瞿博陽，謝 亮，李 超，劉凱松，喬百豪

(中原工學(xué)院 電子信息學(xué)院，河南 鄭州 450007)

多模態(tài)優(yōu)化(Multi-Modal Optimization，MMO)[1]問題是指包含多個全局或局部最優(yōu)解的優(yōu)化問題，如桁架結(jié)構(gòu)優(yōu)化、圖像分割、電動汽車感應(yīng)電機設(shè)計等都屬于MMO問題。優(yōu)化求解此類問題難度較高，要求算法在尋優(yōu)過程中既要避免過早收斂(收斂于某個峰值點)，又要保證解的多樣性(找到多個峰值點)。對于MMO問題而言，找到多個最優(yōu)解具有許多好處：能為決策者提供更多有用的信息；有助于對問題中隱含的關(guān)系屬性進行研究；能夠為決策者提供更多可靠的選擇；有助于提高算法求得全局最優(yōu)解的概率。因此，提出一種能有效求解MMO問題的方法非常重要。

進化算法經(jīng)常用于求解MMO問題，但存在求解過程復(fù)雜、效率不夠高、多樣性較差等不足之處[2]。粒子群算法(Particle Swarm Optimization，PSO)是由Kennedy J等提出的一種新興的進化算法[3]。PSO算法的搜索原理來自對鳥類覓食行為的模仿，PSO算法中每個粒子以動態(tài)變化的速度在搜索空間中不斷地搜索最優(yōu)解，每個粒子在搜索空間中的位置坐標都代表待優(yōu)化問題的“潛在可行解”。PSO算法結(jié)構(gòu)簡單，魯棒性強，在工程實踐領(lǐng)域有著十分廣泛的應(yīng)用[4-6]，具有很高的研究價值。針對MMO問題，本文研究了兩種拓撲結(jié)構(gòu)的PSO算法模型，在原算法的基礎(chǔ)之上引入線性遞減慣性權(quán)重進行改進，并使用15個多模態(tài)測試函數(shù)[7]對改進后的算法進行對比測試。

1 多模態(tài)優(yōu)化問題

(1)

PSO算法中每個粒子包含兩個動態(tài)變量：位置x(t)、速度v(t)。其中，x(t)表示候選解，x(t)∈X。通過PSO算法的不斷優(yōu)化，當種群中的某個粒子滿足x(t)∈Xbest時，視為成功找到MMO問題的一個解。PSO算法的作用相當于一個“過濾器”，通過不斷“篩選”，盡可能多地找到MMO問題的最優(yōu)解Xbest(見圖1)。

圖1 PSO求解MMO問題

2 粒子群優(yōu)化算法

PSO算法有許多不同的拓撲結(jié)構(gòu)，主要有環(huán)型結(jié)構(gòu)、星型結(jié)構(gòu)、四群集型和馮·諾依曼型[8-9]4種，如圖2所示。不同的拓撲結(jié)構(gòu)決定了種群中粒子們共享信息的方式，同時還會影響算法的收斂速度和避免早熟的能力。

對于星型結(jié)構(gòu)，每個粒子節(jié)點都處于連接狀態(tài)，搜索信息在全局范圍內(nèi)共享，因此這種拓撲結(jié)構(gòu)也被稱作“全局拓撲(global topology)”或“全拓撲(all topology)”。對于環(huán)型結(jié)構(gòu)，每個粒子個體與兩個相鄰的粒子相連接，僅僅與其左右兩個鄰居共享信息，因此粒子之間的平均距離非常大，形成了若干個局部搜索區(qū)。本文主要研究星型拓撲結(jié)構(gòu)和環(huán)型拓撲結(jié)構(gòu)的粒子群算法。

(a) 環(huán)型結(jié)構(gòu) (b) 星型結(jié)構(gòu) (c) 四群集型 (d) 馮·諾依曼型 圖2 PSO算法的拓撲結(jié)構(gòu)

2.1 星型拓撲結(jié)構(gòu)粒子群算法

星型結(jié)構(gòu)PSO算法的速度以及位置更新公式為：

vi(t+1)=wvi(t)+c1r1[pi-xi(t)]+c2r2[pg-xi(t)]

(2)

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

(3)

式中:vi(t+1)表示第i個粒子的當前速度；wvi(t)表示“速度部分”，代表歷史速度對當前速度的影響；c1r1[pi-xi(t)]表示“認知部分”，代表粒子自身歷史經(jīng)驗對當前速度的影響；c2r2[pg-xi(t)]表示“社會部分”，代表種群中其他粒子對當前粒子速度的影響；w表示慣性權(quán)重，取值小于1；c1和c2是兩個加速常量；r1和r2是0到1范圍內(nèi)均勻分布的隨機數(shù)；t表示當前迭代次數(shù)；pi表示第i個粒子所找到的歷史最優(yōu)解，即“個體最優(yōu)”，pg表示種群中所找到的全局最優(yōu)解，即“全局最優(yōu)”；xi(t)和xi(t+1)分別表示第i個粒子的當前坐標位置以及下一時刻的坐標位置。

星型結(jié)構(gòu)PSO算法的流程為：初始化種群，設(shè)定種群規(guī)模，隨機生成對應(yīng)數(shù)量的個體，根據(jù)式(1)中目標函數(shù)f(X)計算個體們的適應(yīng)度值，更新個體最優(yōu)和全局最優(yōu)，隨后根據(jù)式(2)、(3)更新粒子速度以及位置，循環(huán)迭代，直到找到所有最優(yōu)解或達到評價次數(shù)為止(見圖3)。

圖3 星型結(jié)構(gòu)PSO算法流程

2.2 環(huán)型拓撲結(jié)構(gòu)粒子群算法

環(huán)型結(jié)構(gòu)PSO算法的速度更新公式為：

vi(t+1)=wvi(t)+c1r1[pi-xi(t)]+c2r2[nbest,i-xi(t)]

(4)

環(huán)型結(jié)構(gòu)PSO算法與星型結(jié)構(gòu)PSO算法的不同點在于“社會部分”，c2r2[nbest,i-xi(t)]表示第i個粒子的“鄰域最優(yōu)”。nbest,i取pi-1、pi、pi+1中適應(yīng)度值最高的一個。環(huán)型結(jié)構(gòu)PSO的每個粒子通過左右相鄰粒子的鄰域最優(yōu)與種群中其他粒子共享最優(yōu)解的信息，如圖4所示。圖中，nbest,i=pi=nbest,i-1=nbest,i+1，依此類推。每3個相連的粒子相互形成一個小生境[10-12]，每個小生境中的粒子可能擁有同1個的鄰域最優(yōu)，也可能擁有3個不同的鄰域最優(yōu)，并朝著各自的領(lǐng)域最優(yōu)移動。

圖4 環(huán)型結(jié)構(gòu)PSO的信息交流

環(huán)型結(jié)構(gòu)PSO算法流程為：初始化種群，設(shè)定種群規(guī)模，隨機生成對應(yīng)數(shù)量的個體，根據(jù)式(1)中的目標函數(shù)f(X) 計算個體們的適應(yīng)度值，更新個體最優(yōu)和鄰域最優(yōu)，隨后根據(jù)式(4)、(2)更新粒子速度以及位置，循環(huán)迭代，直到找到最優(yōu)解或達到評價次數(shù)為止(見圖5)。

圖5 環(huán)型結(jié)構(gòu)PSO算法流程

2.3 線性遞減慣性權(quán)重的引入

慣性權(quán)重w的大小從一定程度上決定了PSO算法的收斂速度以及搜索范圍。當w的值比較大時，整個種群的全局搜索性能更強，而當w較小時，則更有利于粒子們進行局部搜索。算法剛開始搜索時，全局搜索更能增強算法跳出局部最優(yōu)的能力，而隨著搜索過程的不斷進行，適當?shù)販p小w，加強局部搜索，可以提高解的精度。

為了使算法搜索的多樣性以及精度得到提高，引入線性遞減慣性權(quán)重，讓w從wmax線性減小到wmin，具體計算公式為：

(5)

式中：wmax、wmin分別被設(shè)定為0.9、0.4；t為當前迭代次數(shù)；tmax為最大迭代次數(shù)。

3 評價方法

成功率(SR)和峰值比(PR)可用于評估算法求解MMO問題的能力。

SR是指成功找到所有最優(yōu)解的次數(shù)NSR與總運行次數(shù)run的比例。計算成功率時，需要根據(jù)參數(shù)精確度ε和小生境半徑radius來確定某一次運行是否成功找到最優(yōu)解。當候選解對應(yīng)的適應(yīng)度值與實際最優(yōu)值的誤差在ε之內(nèi)時，計算候選解與實際最優(yōu)解的歐幾里德距離，若所求得的距離差在radius以內(nèi)，則視為成功找到了一次最優(yōu)解。

PR按照公式(6)計算：

(6)

式中:run表示運行次數(shù)；NPFi表示每次運行所找到的最優(yōu)解的個數(shù)；NPR表示運行run次后所找到的最優(yōu)解的個數(shù)；NKP表示已知最優(yōu)解的個數(shù)。PR值越大表示算法性能越好。

4 實驗及結(jié)果分析

本文選取文獻[7]中提出的15個復(fù)雜的測試函數(shù)對兩種不同拓撲結(jié)構(gòu)的PSO算法進行測試。表1中給出了這些多模態(tài)測試函數(shù)的相關(guān)屬性。表中每個多模態(tài)測試函數(shù)包括3個不同的維度，每個維度下，測試函數(shù)所包含的最優(yōu)解的數(shù)量也不同，因此，每種算法都需要對不同維度下的測試函數(shù)進行獨立求解。

表1 測試函數(shù)簡介表

表3給出了改進后兩種PSO算法的成功率(對于二者求解成功率均為0的問題，表中未列出)。星型結(jié)構(gòu)PSO算法求解5維f1時成功率為0.353，求解10維f1時成功率為0；環(huán)型結(jié)構(gòu)PSO算法求解5維f1時成功率為0.627，求解10維f1時成功率為0.098；星型結(jié)構(gòu)PSO算法求解2維f2時成功率為0，環(huán)型結(jié)構(gòu)PSO算法求解2維f2時成功率為1。星型結(jié)構(gòu)PSO算法求解5維f4時成功率為0.059，環(huán)型結(jié)構(gòu)PSO算法求解5維f4時成功率為0.313。星型結(jié)構(gòu)PSO算法求解6維f7時成功率為0，環(huán)型結(jié)構(gòu)PSO算法求解6維f7時成功率為0.039。從實驗結(jié)果可以看出，改進后的環(huán)型結(jié)構(gòu)PSO算法成功率更高。

表2 參數(shù)設(shè)定表

表3 兩種PSO算法的成功率(SR)

表4給出了改進后兩種PSO算法峰值比(對于二者均未成功找到最優(yōu)解的問題，表中未列出)。對于5維f1，星型結(jié)構(gòu)18次成功找到最優(yōu)解，環(huán)型結(jié)構(gòu)43次成功找到最優(yōu)解，峰值比分別為0.353和0.843；對于10維f1，星型結(jié)構(gòu)未能成功找到最優(yōu)解，環(huán)型結(jié)構(gòu)找到3次，峰值比分別為0和0.059。除去20維的f13，改進后環(huán)型結(jié)構(gòu)PSO算法求解剩余測試函數(shù)的效果均遠遠優(yōu)于改進后的星型結(jié)構(gòu)PSO算法。

表4 兩種PSO算法的峰值比(PR)

從表3和表4可以看出，通過成功率和峰值比的結(jié)果對比，改進后的環(huán)型結(jié)構(gòu)PSO算法在求解MMO問題時，具有更高的精度和更好的搜索多樣性。

5 結(jié) 語

針對傳統(tǒng)算法在求解MMO問題時，存在求解過程復(fù)雜、多樣性差等不足，提出用環(huán)型結(jié)構(gòu)PSO算法和星型結(jié)構(gòu)PSO算法求解MMO問題，并引入了線性遞減慣性權(quán)重來提高算法的精度和多樣性。通過仿真實驗，改進后的環(huán)型結(jié)構(gòu)PSO算法具有更強的全局搜索能力和局部搜索能力，能夠避免陷入MMO問題的局部最優(yōu)解，有著更好的穩(wěn)定性，在求解MMO問題是有效和可行的。星型結(jié)構(gòu)PSO算法則需要進一步提高其局部搜索能力。