PSO?算法和其他群體智能算法及其他優(yōu)化算法相比，具有形式簡單、易于使用、收斂速度較快等優(yōu)點(diǎn)，但在解決一些復(fù)雜優(yōu)化問題時(shí)，也會像其它算法一樣，存在難以擺脫局部最優(yōu)、執(zhí)行效率低、全局搜索能力和局部搜索能力難以平衡等缺陷。

為解決這些問題，研究者引入了群體智能算法的并行策略，常見的即將整個(gè)種群分為多個(gè)子種群，然后通過設(shè)計(jì)子種群間的信息交互機(jī)制來使多個(gè)子種群能在并行化執(zhí)行的同時(shí)使算法的性能不下降甚至得到提升，這種并行化策略又稱為多種群策略，設(shè)計(jì)群體智能算法的多種群策略的關(guān)鍵在于設(shè)計(jì)良好的子種群間的信息交互機(jī)制。

本文中，作者即采用這種并行策略來改進(jìn)PSO算法，同時(shí)在原有PSO基礎(chǔ)上，利用萊維飛行、混合粒子、正余弦學(xué)習(xí)因子等策略提高其全局勘探和局部開發(fā)能力，并且不同于固定劃分多種群，本文采用一種動態(tài)隨機(jī)重組的方法來提升個(gè)體信息交流效率——即改進(jìn)的動態(tài)多種群粒子群優(yōu)化算法（Improved?dynamic?multi-swarm?particle?swarm?optimization?algorithm，IDM-PSO）

00?文章目錄

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

2?改進(jìn)的動態(tài)多種群粒子群優(yōu)化算法

3?代碼目錄

4?算法性能

5?源碼獲取

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

可在作者微信公眾號：KAU的云實(shí)驗(yàn)臺 查找相應(yīng)內(nèi)容

02?改進(jìn)的動態(tài)多種群粒子群優(yōu)化算法

由于粒子群優(yōu)化算法在求解復(fù)雜多峰問題時(shí)易陷入局部最優(yōu)解，因此學(xué)者們采用了多種改進(jìn)方法提高算法全局搜索能力。包括作者前面實(shí)現(xiàn)的混合粒子群算法以及改進(jìn)量子粒子群算法等，除了這些以外，文獻(xiàn)[1]指出，多種群?PSO?算法運(yùn)行效率和精度遠(yuǎn)遠(yuǎn)高于單種群?PSO?算法。因此作者將嘗試通過多種群的策略改進(jìn)粒子群算法以提高其全局搜索能力。

2.1?動態(tài)多種群劃分策略

多種群PSO算法其實(shí)也是一種基于特殊鄰域拓撲結(jié)構(gòu)的局部PSO算法[2]?,相比于固定劃分多種群,?動態(tài)隨機(jī)重組可以避免過于限制粒子的自由,提升個(gè)體信息交流效率。文獻(xiàn)[3]基于分類的思想以適應(yīng)度值的均值和標(biāo)準(zhǔn)差為測度,通過評價(jià)粒子的位置關(guān)系將種群分為多個(gè)等級.?但是在迭代后期,優(yōu)秀種群會吸引更多個(gè)體加入,將導(dǎo)致粒子過于聚集,種群間信息交流困難。

所以,本文在此基礎(chǔ)上以適應(yīng)度值，升序的中位值為界劃分子種群,每一代都實(shí)行動態(tài)調(diào)整。適應(yīng)度值較小的為“頂層粒子”,較大的為“底層粒子”;再從兩者當(dāng)中分別抽出同等數(shù)量的粒子組成局部PSO模型,并確保3個(gè)種群規(guī)模均衡,分別為離最優(yōu)解較近的“優(yōu)勢群”、局部PSO模型的“混合群”?以及“劣勢群”。

“優(yōu)勢群”中的粒子適應(yīng)度值較小,需要繼承種群中最優(yōu)解的位置信息,縮小步長進(jìn)行更加細(xì)密的搜索;而“劣勢群”中的粒子則應(yīng)擴(kuò)大“步伐”,在向全局極值靠近的同時(shí)探索周圍新的優(yōu)解來提升開采能力;作為局部模型的“混合群””既包含較優(yōu)粒子，也包含較差粒子，將動態(tài)調(diào)整種群的多樣性,既要吸取個(gè)體經(jīng)驗(yàn),也要共享全局信息[4]。

2.2?各種群更新機(jī)制

2.2.1?優(yōu)勢群

粒子群算法在優(yōu)化后期收斂速度變得緩慢的主要原因是其難以擺脫當(dāng)前局部極值,導(dǎo)致精度下降。為增強(qiáng)優(yōu)勢群跳出局部最優(yōu)的能力，引入作者在前面的文章中提到的萊維飛行，萊維飛行以大小步間隔形式進(jìn)行，此類飛行方式加強(qiáng)了粒子活性及跳躍能力，擴(kuò)大粒子搜索范圍，有利于增強(qiáng)粒子多樣性，避免算法陷入局部最優(yōu)，能夠提升算法收斂精度和速度。因此將該方法引入對于優(yōu)勢群的更新中，可彌補(bǔ)算法優(yōu)勢群無更新的不足。

xlg(t)和xg(t)分別為第?t?次迭代時(shí)，經(jīng)萊維飛行更新后的全局最優(yōu)粒子位置和種群全局最優(yōu)粒子位置，α為步長控制因子，一般取0.01，用大小步長飛向原本小概率探索區(qū)域，使得搜索區(qū)域更加均勻。Levy（λ）為隨機(jī)搜索路徑，?代表點(diǎn)乘。

由于萊維分布十分復(fù)雜，無法實(shí)現(xiàn)，目前常用?Mantegna?算法模擬其飛行軌跡，其數(shù)學(xué)表達(dá)式如式所示：

其中，參數(shù)c與Levy?(l?)?~t^-l?中的?l?關(guān)系為?l=1+?c，且?0<?c￡?2，m?和?u?均服從正態(tài)分布，定義如式所示：

其中，方差

由式確定：

式中，G為伽馬函數(shù)，常數(shù)?c一般取1.5

為說明萊維飛行優(yōu)越性，下圖給出了二維空間中粒子飛行軌跡圖，記錄?1000?代內(nèi)的粒子位置變化情況。

同時(shí)，萊維飛行雖能使粒子擺脫局部最優(yōu)，但并不能保證更新后的粒子位置優(yōu)于原位置，所以為避免無意義的位置更新，本文引入貪婪算法的評價(jià)策略決定是否更新最優(yōu)粒子位置，即當(dāng)更新后的位置優(yōu)于原位置時(shí)，才進(jìn)行位置更新，否則保留原位置，實(shí)現(xiàn)過程如式所示：

其中，?xnewg(t)為貪婪算法更新后的粒子位置，?f?()代表粒子適應(yīng)度函數(shù)。

2.2.2?劣勢群

“劣勢群”中具有保留價(jià)值的粒子信息較少，其種群遠(yuǎn)離問題優(yōu)解，可以通過變異的方式在整個(gè)空間搜索最優(yōu)解，變異可以在整個(gè)搜索空間中尋找各種可能的解區(qū)域，也可以避免過早收斂和增加子種群的多樣性。變異判斷如下：

其中,r和N(0,1)是[0,1]之間的隨機(jī)數(shù),x為原始參數(shù)值,?GV(x)為變異后的值。當(dāng)第一個(gè)式子成立時(shí),可執(zhí)行式第二個(gè)式子對粒子進(jìn)行高斯變異操作。多次迭代后判斷式成立的幾率逐漸減小,粒子發(fā)生變異的幾率也逐漸降低。變異操作可在初始階段使粒子以較大概率發(fā)生變異,擴(kuò)大粒子在解空間中的搜尋范圍,保證了粒子群的多樣性。

除此之外，引入混合粒子的概念變更傳統(tǒng)速度更新的公式，混合粒子記為pmix(k)，pmix(k)的維度值由各粒子歷史最優(yōu)值隨機(jī)混合而成，如圖所示。圖中P1~PN為?N?個(gè)粒子的當(dāng)前最優(yōu)位置，pmix為由P1~PN各維度隨機(jī)選擇混合而成的粒子。

?由此得到的劣勢群位置和速度更新方式為：

式中：c3為混合學(xué)習(xí)因子，r3為(0,1)間隨機(jī)數(shù)。由式可知，混合粒子由當(dāng)前各粒子的歷史最優(yōu)混合而成，既繼承了各粒子的優(yōu)良維度，同時(shí)具有隨機(jī)性，兼顧了粒子多樣性和優(yōu)異性。混合粒子作為一個(gè)牽引因素引導(dǎo)粒子的速度更新，可以有效解決陷入局部最優(yōu)的問題，同時(shí)其自身優(yōu)異性也使粒子朝著較優(yōu)方向進(jìn)化。通過這樣兩個(gè)策略，多方向的隨機(jī)擾動在一定程度上增強(qiáng)了搜索過程中的多樣性.?這樣的尋優(yōu)方式非常適合“劣勢群”中的粒子在解空間中進(jìn)行波動性搜索,加深局部學(xué)習(xí)。

2.2.3?混合群

混合群介于兩者之間,由于個(gè)體間的差異在算法前期較大,側(cè)重于其認(rèn)知部分，可以實(shí)現(xiàn)多方交流,而在后期，加強(qiáng)全局極值的引領(lǐng)力，能夠促使粒子向最優(yōu)解的周圍聚集.?因此,學(xué)習(xí)因子引入余弦、正弦函數(shù),?使自身學(xué)子因子單調(diào)遞減，種群學(xué)習(xí)因子單調(diào)遞增。綜上，混合群的速度更新公式為：

2.2.4?非線性慣性權(quán)重

由于慣性權(quán)重因子影響PSO算法性能，其值較大時(shí)有利于全局范圍的搜索，較小的權(quán)重值有利于加快算法的收斂速度，對于局部的細(xì)致開發(fā)益處較大，因此可設(shè)置其在搜索初期權(quán)重因子較大，有助于提升全局搜索能力；在搜索后期，權(quán)重因子較小，有助于增強(qiáng)局部的開發(fā)能力，通過這種非線性慣性權(quán)重來平衡整個(gè)種群的局部和全局的勘探能力。

?

?

2.3?流程

算法流程如下：

?03?代碼目錄

對于每個(gè)測試函數(shù)，依次執(zhí)行dms_pso.m和PSO.m，再執(zhí)行result.m即可

部分主程序如下：

?

04?算法性能

4.1?測試函數(shù)

為了能夠驗(yàn)證改進(jìn)的動態(tài)多種群粒子群優(yōu)化算法的優(yōu)越性，本文選用4個(gè)CEC的標(biāo)準(zhǔn)測試函數(shù)Sphere、Griewank、Schwefel、Rosenbrock對算法的尋優(yōu)精度、跳出局部能力、全局尋優(yōu)能力進(jìn)行檢驗(yàn)。4個(gè)函數(shù)的表達(dá)式如下：

4.1.1?Sphere函數(shù)

Sphere?函數(shù)的自變量????的取值的范圍：-100＜????＜100；該函數(shù)存在唯一的一個(gè)全局的最小值，且當(dāng)??=(0,0,…,0)時(shí)，函數(shù)取得全局最小值?f1(x)?=?0。選擇該函數(shù)是對算法尋優(yōu)的精度進(jìn)行測試。

?

4.1.2?Rosenbrock函數(shù)

Griewank?函數(shù)的自變量????的取值的范圍：-600＜????＜600；該函數(shù)在整個(gè)的數(shù)?據(jù)分布含有大量局部極值，但是存在全局最小值?f2(x)?=?0，是一種比較復(fù)雜的多模的復(fù)雜性問題，因此選擇該函數(shù)目的是對算法是否跳出局部，能夠繼續(xù)搜索的?能力進(jìn)行測試。

4.1.3?Schwefel函數(shù)

Schwefel函數(shù)的自變量????的取值的范圍：-500＜????＜500；在xi=420有極小值，函數(shù)是一個(gè)典型的欺騙問題;有1個(gè)全局極小值點(diǎn);距離另一個(gè)局部最優(yōu)點(diǎn)很遠(yuǎn);因此如果陷入局部最優(yōu)就很難跳出,測試的是函數(shù)的全局搜索能力和跳出局部最優(yōu)的能力,對算法的要求較高,簡單的算法不太可能求解最優(yōu)解.

4.1.4?Rosenbrock函數(shù)

Rosenbrock?函數(shù)的自變量????的取值的范圍：-30＜????＜30；該函數(shù)是一單峰函數(shù)，?存在全局極小值，位于一個(gè)類似開口向上的拋物線的最低點(diǎn)處，雖然能夠比較容易找到，但是很難收斂到最低處，因此可以測試全局尋優(yōu)的能力。

4.2?測試結(jié)果

Sphere

?

Griewank

?

Schwefel

?

Rosenbrock

?

從測試結(jié)果可以看出，經(jīng)改進(jìn)后的PSO算法其全局尋優(yōu)能力和跳出局部最優(yōu)的能力都得到了較大的提升，這種提升在Schwefel函數(shù)中尤為顯著。

05?源碼獲取

https://mbd.pub/o/bread/mbd-ZJyTk5ly

另：如果有伙伴有待解決的優(yōu)化問題（各種領(lǐng)域都可），可以發(fā)我，我會選擇性的更新利用優(yōu)化算法解決這些問題的文章。

如果這篇文章對你有幫助或啟發(fā)，可以點(diǎn)擊右下角的贊/在看(????_??)?(不點(diǎn)也行)，若有定制需求，可私信作者。

參考文獻(xiàn)

[1]AO?S?Z，LIANG?J?J，SUGANTHAN?P?N.Dynamic?multis-warm?particle?swarm?optimizer?with?local?search?for?l-arge?scale?global?optimization?［C］//Hong?Kong：Proc?of?IEEE?SwarmIntelligence?Symposium，2008：3845-3852

[2]Gao?Y?L,?Yan?P.?Unified?optimization?based?on?multi-swarm?PSO?algorithm?and?cuckoo?search?algorithm[J].?Control?and?Decision,?2016,?31(4):?601-608

[3]Tong?Q?J,?Li?M,?Zhao?Q.?An?improved?particle?swarm?optimization?algorithm?based?on?classification[J].?Modern?Electronics?Technique,?2019,?42(19):?11-14.

[4]唐可心,梁曉磊,周文峰等.具有重組學(xué)習(xí)和混合變異的動態(tài)多種群粒子群優(yōu)化算法[J].控制與決策,2021,36(12):2871-2880.DOI:10.13195/j.kzyjc.2020.0898.

[5]侯維春,袁志鵬.混合動力汽車參數(shù)的動態(tài)重組多子群粒子群優(yōu)化[J/OL].機(jī)械設(shè)計(jì)與制造:1-8[2023-07-26].DOI:10.19356/j.cnki.1001-3997.20230529.002.

[6]楊洋,栗風(fēng)永.基于高斯變異粒子群優(yōu)化的短期負(fù)荷預(yù)測[J].計(jì)算機(jī)仿真,2023,40(01):125-130.