李媛媛,李文博,尚志豪

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

粒子群優(yōu)化算法是一種基于群體智能的優(yōu)化算法,它通過(guò)模擬智能群體中每個(gè)個(gè)體的行為來(lái)解決優(yōu)化問(wèn)題.主要應(yīng)用在工程設(shè)計(jì)[1]、控制工程[2]、路徑規(guī)劃[3]、計(jì)算機(jī)視覺(jué)[4]等方面.文獻(xiàn)[1]為了在鍛坯過(guò)程中找到最佳的工藝參數(shù),改善傳統(tǒng)數(shù)值模擬方法的不足,采用粒子群算法對(duì)參數(shù)進(jìn)行優(yōu)化,從材料本身和鍛壓成形節(jié)能的角度出發(fā),采用該算法找到最合適的參數(shù)結(jié)果.文獻(xiàn)[2]使用非線性PID (NLPID)控件取代了傳統(tǒng)的PID控件,提出了一種基于廣義對(duì)立學(xué)習(xí)算法的粒子群優(yōu)化算法來(lái)優(yōu)化NLPID控制器,成功抑制了系統(tǒng)超調(diào).文獻(xiàn)[4]提出了一種靈活的卷積自編碼器,利用粒子群優(yōu)化設(shè)計(jì)了一種架構(gòu)發(fā)現(xiàn)方法,該方法能夠自動(dòng)搜索所提出的柔性卷積自編碼器的最優(yōu)架構(gòu),無(wú)需任何人工干預(yù),大大減少計(jì)算資源,解除了傳統(tǒng)卷積自編碼器對(duì)卷積層和池化層數(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)值的同時(shí)加快整個(gè)優(yōu)化過(guò)程的收斂速度.這兩種改進(jìn)方式是針對(duì)原始PSO最經(jīng)典的改進(jìn)方法.其他的改進(jìn)算法通常都是在此基礎(chǔ)上進(jìn)行改進(jìn),方法包括：改變粒子拓?fù)浣Y(jié)構(gòu)、與其他算法結(jié)合、引入新的機(jī)制、或是對(duì)參數(shù)進(jìn)行修改.例如：為了克服傳統(tǒng)的Pareto最優(yōu)前沿形狀變化分解方法的不穩(wěn)定性,Zheng Jinhua等[7]提出了1種基于對(duì)抗分解和鄰域演化的動(dòng)態(tài)多目標(biāo)粒子群優(yōu)化算法;針對(duì)存在多個(gè)pareto最優(yōu)解且適應(yīng)度值相同的多模態(tài)多目標(biāo)優(yōu)化問(wèn)題,Liang Jing等[8]提出了一種具有自組織機(jī)制的多目標(biāo)粒子群優(yōu)化算法;Liu Yaxian等[9]通過(guò)將強(qiáng)化學(xué)習(xí)算法與粒子群算法結(jié)合起來(lái),得到了自適應(yīng)參數(shù);為了使算法尋優(yōu)過(guò)程中更輕松地跳出局部最優(yōu)值,徐利鋒等[10]在帶有收縮因子的粒子群算法基礎(chǔ)上引入了多級(jí)擾動(dòng)機(jī)制.

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

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

在粒子群算法中,每個(gè)粒子的位置代表了給定問(wèn)題的潛在解決方案,并使用適應(yīng)度函數(shù)來(lái)評(píng)判當(dāng)前位置的優(yōu)劣.群體中的粒子會(huì)通過(guò)信息共享機(jī)制來(lái)更新自身的速度和位置,從而更新整個(gè)群體.群體在迭代過(guò)程中不斷追尋最優(yōu)粒子,在解空間內(nèi)進(jìn)行搜索運(yùn)動(dòng),從而逐漸從無(wú)序向有序演變,最終達(dá)到在限制條件內(nèi)求得待解決問(wèn)題的帕累托最優(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)部分表示上一代歷史速度對(duì)當(dāng)前速度的影響,慣性權(quán)重w用來(lái)調(diào)節(jié)此影響的大小,從而調(diào)節(jié)粒子在解空間的搜尋范圍,使粒子全局搜索和局部開(kāi)采能力達(dá)到平衡.c1r1(pbestij(t)-xij(t))為粒子的自我認(rèn)知部分,c2r2(gbestj(t)-xij(t))為社會(huì)認(rèn)知部分.pbestij(t),gbestj(t)分別為粒子的個(gè)體歷史最優(yōu)位置和全局歷史最優(yōu)位置.加速度因子c1,c2分別用來(lái)調(diào)節(jié)粒子向自己歷史最優(yōu)位置和全局最優(yōu)位置學(xué)習(xí)的步長(zhǎng).隨機(jī)數(shù)r1,r2都取值[0,1]內(nèi),用以增加粒子搜索的隨機(jī)性.

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

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

2.1 種群劃分

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

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

(3)

(4)

圖1 子種群劃分方式

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

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

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

收縮因子φ定義式：

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

(10)

(11)

劣等子群更新公式：

(12)

2.4 普通子群更新策略

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

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

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

3.2 算法性能測(cè)試

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

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

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

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

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

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

3.3 對(duì)比實(shí)驗(yàn)

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

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

表4 算法參數(shù)表

實(shí)驗(yàn)結(jié)果分析：

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

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

表5 不同算法性能比較

4 結(jié)語(yǔ)

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