基于多種群多策略的競爭粒子群算法

李媛媛,李文博,尚志豪

(大連交通大學(xué) 軟件學(xué)院,遼寧 大連 116028)

粒子群優(yōu)化算法是一種基于群體智能的優(yōu)化算法,它通過模擬智能群體中每個個體的行為來解決優(yōu)化問題.主要應(yīng)用在工程設(shè)計[1]、控制工程[2]、路徑規(guī)劃[3]、計算機(jī)視覺[4]等方面.文獻(xiàn)[1]為了在鍛坯過程中找到最佳的工藝參數(shù),改善傳統(tǒng)數(shù)值模擬方法的不足,采用粒子群算法對參數(shù)進(jìn)行優(yōu)化,從材料本身和鍛壓成形節(jié)能的角度出發(fā),采用該算法找到最合適的參數(shù)結(jié)果.文獻(xiàn)[2]使用非線性PID (NLPID)控件取代了傳統(tǒng)的PID控件,提出了一種基于廣義對立學(xué)習(xí)算法的粒子群優(yōu)化算法來優(yōu)化NLPID控制器,成功抑制了系統(tǒng)超調(diào).文獻(xiàn)[4]提出了一種靈活的卷積自編碼器,利用粒子群優(yōu)化設(shè)計了一種架構(gòu)發(fā)現(xiàn)方法,該方法能夠自動搜索所提出的柔性卷積自編碼器的最優(yōu)架構(gòu),無需任何人工干預(yù),大大減少計算資源,解除了傳統(tǒng)卷積自編碼器對卷積層和池化層數(shù)量的禁錮,并證明了加入粒子群算法后的新的圖像分類算法遠(yuǎn)優(yōu)于其他同類算法.

標(biāo)準(zhǔn)粒子群優(yōu)化算法(standarding particle swarm optimization,SPSO)最初由Shi和Eb-erhart等[5]在1998年提出,它擁有慣性權(quán)重,是為了解決原始PSO算法易陷入局部最優(yōu)值而進(jìn)行的改進(jìn).帶有壓縮因子的粒子群優(yōu)化算法在1999年由Clerc等[6]提出,目的是在幫助粒子跳脫局部最優(yōu)值的同時加快整個優(yōu)化過程的收斂速度.這兩種改進(jìn)方式是針對原始PSO最經(jīng)典的改進(jìn)方法.其他的改進(jìn)算法通常都是在此基礎(chǔ)上進(jìn)行改進(jìn),方法包括：改變粒子拓?fù)浣Y(jié)構(gòu)、與其他算法結(jié)合、引入新的機(jī)制、或是對參數(shù)進(jìn)行修改.例如：為了克服傳統(tǒng)的Pareto最優(yōu)前沿形狀變化分解方法的不穩(wěn)定性,Zheng Jinhua等[7]提出了1種基于對抗分解和鄰域演化的動態(tài)多目標(biāo)粒子群優(yōu)化算法;針對存在多個pareto最優(yōu)解且適應(yīng)度值相同的多模態(tài)多目標(biāo)優(yōu)化問題,Liang Jing等[8]提出了一種具有自組織機(jī)制的多目標(biāo)粒子群優(yōu)化算法;Liu Yaxian等[9]通過將強化學(xué)習(xí)算法與粒子群算法結(jié)合起來,得到了自適應(yīng)參數(shù);為了使算法尋優(yōu)過程中更輕松地跳出局部最優(yōu)值,徐利鋒等[10]在帶有收縮因子的粒子群算法基礎(chǔ)上引入了多級擾動機(jī)制.

粒子群優(yōu)化算法的優(yōu)勢在于它可以快速收斂到最優(yōu)解,同時具有較好的全局搜索能力.在眾多應(yīng)用中,粒子群優(yōu)化算法已經(jīng)取得了良好的效果,但是在實際應(yīng)用中還是會出現(xiàn)易陷入局部最優(yōu)[11-12]、收斂性差[13-14]、求解精度低[15]等問題.為了減少這些問題對算法的影響,作者對標(biāo)準(zhǔn)粒子群算法進(jìn)行改進(jìn),提出基于Logistic混沌映射權(quán)重及混合高斯、柯西擾動變異,同時使用了收縮因子的多種群多策略競爭粒子群算法(multi-swarm multistrategy competitive particle swarm optimization,MMCPSO).為了獲得比標(biāo)準(zhǔn)粒子群算法更好的尋優(yōu)性能,作者將每一代的粒子群劃分為不同的子種群,并使用不同的更新機(jī)制來更新這些子種群,從而使粒子的全局搜索能力和局部開采能力在尋優(yōu)過程中達(dá)到平衡.

1 標(biāo)準(zhǔn)粒子群算法

在粒子群算法中,每個粒子的位置代表了給定問題的潛在解決方案,并使用適應(yīng)度函數(shù)來評判當(dāng)前位置的優(yōu)劣.群體中的粒子會通過信息共享機(jī)制來更新自身的速度和位置,從而更新整個群體.群體在迭代過程中不斷追尋最優(yōu)粒子,在解空間內(nèi)進(jìn)行搜索運動,從而逐漸從無序向有序演變,最終達(dá)到在限制條件內(nèi)求得待解決問題的帕累托最優(yōu)解的目的.

粒子速度和位置更新公式：

vij(t+1)=wvij(t)+c1r1(pbestij(t)-xij(t))+c2r2(gbestij(t)-xij(t)).

(1)

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

(2)

其中,vij(t)表示第t代粒子i在第j維度上的速度,wvij(t)部分表示上一代歷史速度對當(dāng)前速度的影響,慣性權(quán)重w用來調(diào)節(jié)此影響的大小,從而調(diào)節(jié)粒子在解空間的搜尋范圍,使粒子全局搜索和局部開采能力達(dá)到平衡.c1r1(pbestij(t)-xij(t))為粒子的自我認(rèn)知部分,c2r2(gbestj(t)-xij(t))為社會認(rèn)知部分.pbestij(t),gbestj(t)分別為粒子的個體歷史最優(yōu)位置和全局歷史最優(yōu)位置.加速度因子c1,c2分別用來調(diào)節(jié)粒子向自己歷史最優(yōu)位置和全局最優(yōu)位置學(xué)習(xí)的步長.隨機(jī)數(shù)r1,r2都取值[0,1]內(nèi),用以增加粒子搜索的隨機(jī)性.

2 改進(jìn)的粒子群算法MMCPSO

標(biāo)準(zhǔn)PSO尋優(yōu)過程一直伴隨著局部搜索能力不夠強,搜索精度差,處理復(fù)雜非線性多峰問題常陷入局部最優(yōu)等問題.為了擺脫這個困擾,MMCPSO根據(jù)同代種群粒子的適應(yīng)度值將粒子分別劃為3個子種群：優(yōu)等子群(superiors)、普通子群(ordinaries)、劣等子群(inf-eriors);針對不同子種群粒子的特點分別加入擾動變異、Logistic混沌映射、收縮因子3種不同策略來進(jìn)行粒子的更新;不同子種群產(chǎn)生的新一代粒子通過參與適應(yīng)度值競爭排序后,更新到不同的子種群;算法中的每個子種群會通過粒子更新公式,不同程度的參與引領(lǐng)整個種群更新.不同于標(biāo)準(zhǔn)PSO的所有粒子只對本身歷史最優(yōu)和全局歷史最優(yōu)進(jìn)行追逐,這種新的更新策略使整體算法尋優(yōu)全程擁有較強的全局和局部尋優(yōu)能力并兼具了易跳出局部最優(yōu)、保持種群多樣性的特性,彌補了標(biāo)準(zhǔn)PSO的不足.下面將詳細(xì)介紹MMCPSO的種群劃分方式和不同子種群的更新策略.

2.1 種群劃分

以求最小值問題為例,在MMCPSO中,每一代的所有粒子按照適應(yīng)度從低到高進(jìn)行競爭排序后,求得當(dāng)代種群適應(yīng)度的平均值和標(biāo)準(zhǔn)差.在求最小值的優(yōu)化問題中：取平均適應(yīng)度一倍標(biāo)準(zhǔn)差內(nèi)的粒子組成普通子群;取適應(yīng)度值小于普通子群的粒子組成優(yōu)等子群;取適應(yīng)度值大于普通子群的粒子為劣等子群.劣等子群向優(yōu)等子群和普通子群兩個子群按照合理的權(quán)重學(xué)習(xí)更新,盡快向兩個區(qū)域靠攏;普通子群使用帶有w慣性的更新公式,平衡普通子群粒子的全局和局部探索能力.

適應(yīng)度平均值和標(biāo)準(zhǔn)差的計算公式如下：

(3)

(4)

圖1 子種群劃分方式

2.2 優(yōu)等子群更新策略

優(yōu)等子群粒子已經(jīng)獲得了較優(yōu)的適應(yīng)度值,所以優(yōu)等子群進(jìn)行自我學(xué)習(xí)更新.同時,該種群粒子聚集在局部最優(yōu)解附近.為了避免陷入局部最優(yōu),同時又使粒子具備好的局部尋優(yōu)能力,作者設(shè)計了帶有局部開發(fā)能力強的高斯變異和具有兩翼分布概率且更易跳出局部最優(yōu)的柯西變異的粒子更新方式.

高斯-柯西變異算子GC定義式：

GC=αG+(1-α)C,0<α<1.

(5)

G=Gaussion(0,1)=rand(0,1)～N(0,1).

(6)

(7)

優(yōu)等子群粒子更新公式：

(8)

(9)

2.3 劣等子群更新策略

劣等子群中的個體通過主要向優(yōu)等子群學(xué)習(xí),兼顧受種群中心平均值牽引的方式更新.采用收縮因子對整個更新過程進(jìn)行壓縮,使劣等子群的粒子能快速脫離劣勢區(qū)域向優(yōu)勢區(qū)域收斂,同時又能對各個學(xué)習(xí)因子進(jìn)行調(diào)節(jié),均衡了該階段算法的收斂性能,避免在快速靠近優(yōu)等子群的過程中喪失了開發(fā)能力.

收縮因子φ定義式：

c=c1+c2+c3,c≥4.

(10)

(11)

劣等子群更新公式：

(12)

2.4 普通子群更新策略

普通子群粒子處于解空間合理位置范圍內(nèi),無明顯優(yōu)劣勢,該子群進(jìn)化過程中需要平衡算法的勘探和開采能力.SPSO算法使用的線性遞減權(quán)重w在一定程度上平衡了粒子的全局探索和局部開發(fā),但線性的調(diào)整方式在多維復(fù)雜非線性函數(shù)的優(yōu)化過程中常陷入局部最優(yōu).混沌映射作為非線性映射方式的一種,其產(chǎn)生的隨機(jī)序列具有良好的空間便利性.因此,作者在SPSO算法基礎(chǔ)上對權(quán)重w加入Logistic混沌映射,用非線性權(quán)重wL對粒子的速度進(jìn)行更新,使算法搜索能力均衡的同時又能很好地遍歷解空間,不易陷入局部最優(yōu).

Logistic混沌映射慣性權(quán)重wL定義式：

r(t+1)=4r(t)(1-r(t)),r(0)=rand(0,1)且r(0)≠{0,0.25,0.75,1}.

(13)

(14)

普通子群粒子更新公式：

(15)

(16)

圖2 慣性權(quán)重隨迭代次數(shù)變化圖

3 實驗

3.1 標(biāo)準(zhǔn)函數(shù)測試

選取11個基本測試函數(shù)與標(biāo)準(zhǔn)粒子群算法從尋優(yōu)精度、尋優(yōu)速度,跳出局部最優(yōu)的能力等方面進(jìn)行比對,來驗證MMCPSO算法的有效性.11個標(biāo)準(zhǔn)測試函數(shù)的基本信息由表1給出,fopt為函數(shù)最優(yōu)值.函數(shù)f1～f6是用來測試算法尋優(yōu)的快慢和所得解優(yōu)劣的單峰函數(shù),函數(shù)f7～f11為測試算法跳出局部最優(yōu),避免過早收斂的能力的多峰函數(shù).

3.2 算法性能測試

將MMCPSO與SPSO進(jìn)行對比實驗,給予2種算法相同的種群大小N=90和最大迭代次數(shù)tmax=150,令二者在一個30維的解空間內(nèi)對11個基本測試函數(shù)進(jìn)行最小值尋優(yōu).在相同的硬件條件下,運行兩個算法50次,記錄兩種算法50次的尋優(yōu)結(jié)果,分別求取平均值(Mean)和標(biāo)準(zhǔn)差(standard deviation,SD)作為評價算法性能的指標(biāo).算法參數(shù)設(shè)置見表2.

2種算法對基本測試函數(shù)的尋優(yōu)結(jié)果見表3.

表1 11個標(biāo)準(zhǔn)測試函數(shù)

表2 各算法參數(shù)表

表3 2種算法求解11個標(biāo)準(zhǔn)測試函數(shù)適應(yīng)度的平均值和標(biāo)準(zhǔn)差

繪制出FPSO和MMCPSO在求解11個標(biāo)準(zhǔn)測試函數(shù)時的適應(yīng)度曲線,以便更直觀的對比觀察2種算法的求解精度和收斂速度,如圖3、圖4、圖5所示.

(a)f1 (b)f2

(c)f3 (d)f4圖3 各算法f1～f4函數(shù)尋優(yōu)適應(yīng)度曲線

(a)f5 (b)f6

(c)f7 (d)f8圖4 各算法f5～f8函數(shù)尋優(yōu)適應(yīng)度曲線

(a)f5 (b)f6 (c)f6圖5 各算法f9～f11函數(shù)尋優(yōu)適應(yīng)度曲線

從表3可知,在標(biāo)準(zhǔn)測試函數(shù)f1～f4、f7～f9上MMCPSO算法的尋優(yōu)精度較FPSO算法有著明顯的數(shù)量級優(yōu)勢,在剩余的測試函數(shù)上新算法求得適應(yīng)度的平均值也更接近函數(shù)本身的最優(yōu)值.從圖3、圖4、圖5中各個測試函數(shù)的適應(yīng)度曲線可以看出新算法收斂速度更加迅速,又得益于變異機(jī)制和混沌映射慣性權(quán)重,跳出局部最優(yōu)解的能力也更強.

3.3 對比實驗

為了證明MMCPSO算法的優(yōu)越性,將其與3種典型的PSO變體進(jìn)行比較,包括自適應(yīng)慣性權(quán)重的全局PSO(GPSO-AW)[16]、動態(tài)維度自適應(yīng)PSO(DDAPSO)[17]和局部競爭PSO(LC-PSO)[18].具體的參數(shù)設(shè)置如表4所示.為確保用不同算法進(jìn)行實驗比較的公正性,測試函數(shù)的維度D設(shè)置為30,種群規(guī)模N設(shè)置為90,最大迭代次數(shù)t_max設(shè)置為150,每個算法獨立運行50次.

表5給出了MMCPSO算法和當(dāng)前3種PSO在11個基準(zhǔn)測試函數(shù)上的性能比較結(jié)果.

表4 算法參數(shù)表

實驗結(jié)果分析：

1)算法尋優(yōu)能力.將MMCPSO 算法與GPSO-AW、DDAPSO、LC-PSO 3個算法在多個單峰、雙峰函數(shù)下進(jìn)行測試,MMCPSO算法表現(xiàn)極佳.無論是在單峰測試函數(shù)f1、f3、f4、f5,還是多峰測試函數(shù)f2、f7～f9上,其求得的Mean值比其它算法更接近測試函數(shù)的最優(yōu)值.這說明該算法尋優(yōu)能力出眾.

2)算法穩(wěn)定性.在性能評價指標(biāo)中的SD值也遠(yuǎn)小于其它算法,這說明MMCPSO算法性能穩(wěn)定.美中不足的是在f6和f11上MMCPSO算法的表現(xiàn)都不如GPSO-AW算法.

表5 不同算法性能比較

4 結(jié)語

設(shè)計了1種可以根據(jù)不同子種群狀況,采用不同更新策略的改進(jìn)粒子群算法MM-CPSO.MMCPSO利用競爭學(xué)習(xí)機(jī)制和收縮因子加快了劣等子群學(xué)習(xí)速度;通過引入融合的變異算子和使用自適應(yīng)變異步長增大了優(yōu)等子群中粒子局部開發(fā)能力和跳出局部最優(yōu)的概率值;加入Logistic混沌映射慣性權(quán)重令普通子群更好地遍歷解空間.新的更新策略有效地避免種群在優(yōu)化單峰、多峰問題時早熟收斂和無法跳出局部最優(yōu)解.改進(jìn)后的算法在11個標(biāo)準(zhǔn)測試函數(shù)上的優(yōu)化表現(xiàn)表明采用不同子種群不同更新策略能夠有效取得探索和開發(fā)能力的最佳平衡.下一步的目標(biāo)是將該算法引入到深度學(xué)習(xí)中,幫助神經(jīng)網(wǎng)絡(luò)模型選取優(yōu)秀的初始權(quán)重和高效的網(wǎng)絡(luò)結(jié)構(gòu)模型.