多策略融合的粒子群優(yōu)化算法*

王惠敏,孫 瀅,高岳林

(1.北方民族大學 計算機科學與工程學院,寧夏 銀川 750021;2.北方民族大學 數(shù)學與信息科學學院,寧夏 銀川 750021;3.寧夏智能信息與大數(shù)據(jù)處理重點實驗室,寧夏 銀川 750021)

群智能優(yōu)化算法是一種受生物群體行為啟發(fā)而提出的優(yōu)化技術,是計算智能4個分支中的重要一支。由于群智能優(yōu)化算法具有快速性、并行性和魯棒性的優(yōu)點,近年來迅速發(fā)展并成為優(yōu)化領域的熱點研究方向之一。傳統(tǒng)智能優(yōu)化算法存在如算法規(guī)模冗余、復雜度過高、運算時間較長等缺點,而群智能優(yōu)化算法可以通過模擬生物行為來彌補這些缺點,并在該領域取得了豐富的成果[1-3]。群智能優(yōu)化算法包括模擬鳥群覓食行為的粒子群優(yōu)化算法(Particle Swarm Optimization, PSO)[4-5],模擬螢火蟲發(fā)光吸引其他個體的螢火蟲算法(Firefly Algorithm, FA)[6],模擬海鷗群體遷徙和捕食的海鷗優(yōu)化算法(Seagull Optimization Algorithm, SOA)[7]和模擬麻雀群體覓食行為的麻雀搜索算法(Sparrow Search Algorithm, SSA)[8]等類型。

傳統(tǒng)PSO[4]算法最初設計用于解決連續(xù)搜索空間中的函數(shù)極值問題,具有結構操作較為簡單、參數(shù)設置較少、計算內(nèi)存較小、收斂速度較快、算法性能優(yōu)越以及易于實現(xiàn)的優(yōu)點。該算法提出后得到了研究者的廣泛關注,用于解決實際優(yōu)化問題,例如路徑規(guī)劃問題[9]、參數(shù)辨識問題[10]和圖像處理問題[11]。然而,隨著信息技術的發(fā)展,實際優(yōu)化問題越來越復雜,傳統(tǒng)PSO算法面臨著收斂精度不高、易陷入局部最優(yōu)的嚴峻挑戰(zhàn)。針對這些問題,研究者們提出了許多改進的PSO變體,以提高算法的性能。LUO et al[12]提出的帶有壓縮因子的PSO算法改善了粒子難以跳出局部最優(yōu)的問題,并提高了算法的收斂速度,在工程優(yōu)化問題的解決中取得了顯著效果。一些研究者將離散問題的搜索空間映射到連續(xù)粒子運動空間中,成功地將PSO算法應用于解決離散問題[13],并通過改變粒子的鄰域拓撲結構提升算法的性能。許勝才等[14]將PSO算法與不同的拓撲結構相結合,使得粒子在前期能夠保證搜索范圍的同時在后期提高整個種群的收斂性,從而提高了算法的整體性能。相較于傳統(tǒng)PSO算法,量子PSO算法能夠保證粒子種群的多樣性并且防止算法過早收斂。李玥等[15]提出了改進的量子PSO算法,采用高斯擾動的局部吸引子和粒子加權方法,顯著提高了算法的優(yōu)化精度和穩(wěn)定性。此外,研究者們在調(diào)整參數(shù)取值、結合優(yōu)化策略或混合其他算法等方面做了許多改進工作。參數(shù)的選擇對算法也有不同程度的影響,目前比較流行的對慣性權重的選取策略仍然是SHI et al[16]提出的線性動態(tài)遞減慣性權重策略,在進化過程中增加了勘探和開發(fā)能力。改進粒子的速度和位置更新公式以提高算法性能是目前的研究熱點之一。李二超等[17]將粒子速度更新公式中個體最優(yōu)和群體最優(yōu)替換為其線性組合,提高了粒子之間信息共享的程度,增加了解的多樣性。引入其他智能優(yōu)化算法特性能夠得到性能更優(yōu)的混合算法,閆群民等[18]引入模擬退火操作提出的自適應模擬退火PSO算法,避免了PSO算法陷入局部最優(yōu)解。KASEB et al[19]則在PSO算法中加入遺傳算法的交叉算子和變異算子,進一步平衡算法的勘探與開發(fā)能力,改善了處理城市的風力條件的能力。

當前雖有大量的改進研究,但PSO算法的性能仍有進一步提升優(yōu)化的空間。為了改進標準PSO算法搜索精度較差和易陷入局部最優(yōu)的缺點,本文提出一種多策略融合的粒子群優(yōu)化(Multi-strategy Fusion Particle Swarm Optimization, MFPSO)算法。本文的貢獻如下:

(1)提出均值自適應判斷機制,有效判別粒子處于開發(fā)階段。自適應均值判斷機制與逆向思維的權重相呼應。提出的逆向思維的權重有利于提升算法的穩(wěn)定性以及全局尋優(yōu)的效率,并且能夠保證粒子的質(zhì)量和提升收斂速度。在局部尋優(yōu)時,擴大粒子的搜索范圍,避免后續(xù)粒子陷入局部最優(yōu),從而獲得更優(yōu)結果。

(2)引入線性組合速度更新公式、自適應位置更新公式,增加了全局搜索中粒子找到更優(yōu)位置的可能性,增加了解的多樣性,使算法朝著最優(yōu)解的方向演化。

(3)提出基于爬山算法思想[20]的局部搜索策略,通過隨機步長調(diào)整粒子的位置,降低粒子陷入局部最優(yōu)的概率。

(4)通過消融實驗對MFPSO算法的各個組件進行了驗證,并將其與標準PSO算法[5]、IPSO-VP算法[17]、SA-PSO算法[18]以及其他3種群智能優(yōu)化算法(FA[6],SOA[7],SSA[8])進行對比實驗。在12組測試函數(shù)中對每個算法進行對比實驗,以驗證本文所提MFPSO算法的有效性。實驗結果表明,MFPSO算法的收斂速度和收斂精度均優(yōu)于對比算法,提升了傳統(tǒng)PSO算法的性能。

1 標準PSO算法

(1)

(2)

粒子i在第k+1次迭代中的速度、位置邊界條件公式為:

(3)

(4)

個體、全局位置更新公式為:

(5)

(6)

公式(5)(6)中,函數(shù)f所得到的結果是適應度函數(shù)值。根據(jù)f來更新粒子群中個體極值pbesti和全局極值gbest的值,讓粒子i向著更好的方向進行迭代尋優(yōu)。

2 MFPSO算法設計

2.1 基于均值自適應判斷機制的逆向思維慣性權重策略

群智能優(yōu)化算法的尋優(yōu)過程一般分為全局勘探和局部開發(fā)2個階段。由于群智能算法有很大的隨機性,使用恰當?shù)倪m應度值特性判別條件作為評判搜索階段的參考指標更有意義。更好的判斷機制能夠幫助算法提升解的質(zhì)量,很多學者對此有不同的見解[17,21]。均值通常被用來體現(xiàn)一組數(shù)據(jù)的集中趨勢。在迭代過程中,當前適應度值小于均值時,說明算法距最優(yōu)值還有一定的偏差,粒子分布較為分散,此時適用全局搜索策略,提高算法的尋優(yōu)速度和粒子質(zhì)量。當前適應度值大于均值時,說明該粒子與粒子群整體的距離較小,粒子分布較為集中,此時適用局部搜索策略,擴大粒子的尋優(yōu)范圍避免陷入局部最優(yōu)。均值自適應判斷公式為:

(7)

w是標準PSO算法最重要的參數(shù)之一。慣性權重線性遞減策略提出較早,并未充分考慮到迭代過程中慣性權重與粒子整體適應度值變化的關聯(lián)[22]。有學者經(jīng)理論分析證實了權重線性遞增策略的有效性。本文結合均值自適應判斷機制創(chuàng)新性地提出逆向思維的慣性權重,前期粒子移動較后期有更大的隨機性,引入較小的w保持搜索精度,后期不需要一味地提高搜索速度,引入較大的w擴大粒子的搜索區(qū)域,避免粒子陷入局部最優(yōu)。同時采用小范圍線性遞增的w,能夠提升整個算法的穩(wěn)定性。逆向思維的慣性權重公式為:

該公式為慣性權重的調(diào)整提供了全新視角。根據(jù)參考文獻[17],此處人為設定wmin=0.4,wmax=0.9。(wmax-wmin)×0.2為慣性權重的值,根據(jù)進化進程在20%范圍內(nèi)遞增或遞減。在全局搜索時采用較小的w減少粒子在沒有希望的區(qū)域飛行,從而提高了解的質(zhì)量;在局部搜索時采用較大的w保證解的多樣性,避免算法早熟收斂。

2.2 線性組合速度更新和自適應位置更新公式

當算法處于全局搜索階段時,個體最優(yōu)和群體最優(yōu)的線性組合速度更新策略[17,23]能夠有效提升PSO算法的勘探能力和解的可靠性。粒子將從此線性組合中調(diào)整粒子間的影響力,更新速度。線性組合速度更新公式為:

(9)

自適應位置更新策略[21]具有不同的探測和開發(fā)能力。在勘探和開發(fā)階段采用不同的位置更新公式能夠提升算法的整體性能。位置更新公式(2)能夠保證算法局部勘探能力,幫助算法跳出局部最優(yōu),而將慣性權重引入位置更新公式中能夠提升解的精度,有助于加快算法的收斂速度,提高算法的全局開發(fā)能力。自適應位置更新公式為:

(10)

2.3 爬山算法思想

爬山算法[20]是對深度優(yōu)先搜索的一種改進,在結合其他算法解決實際問題時非常有效[24]。爬山算法從當前解的最近解空間中選擇最好的解作為當前解,只有在算法改進的情況下才會接受新的解。由于爬山算法是一種局部擇優(yōu)的方法,所得的解無好壞之分,粒子不會只向著大部分粒子認為有希望的地方飛行,這一缺陷恰好成為了MFPSO算法的優(yōu)點,使算法有更多的機會得到其他的解,有效避免粒子陷入局部最優(yōu)?；谂郎剿惴ㄋ枷氲墓浇M為:

(11)

(12)

公式(11)中,當前全局最優(yōu)值的鄰居極值rbestk的位置由當前全局最優(yōu)值gbestk的位置加入隨機步長rand得到鄰居極值,其中rand∈[0,1]。公式(12)中,將鄰居極值rbestk的值與當前全局極值gbestk的值進行比較,若f(rbestk)≤f(gbestk),則gbestk=rbestk;反之則保持不變。

2.4 MFPSO算法的整體流程

MFPSO算法的優(yōu)異性體現(xiàn)在:(1)提出均值自適應判斷機制,使得粒子選擇更合適的更新方式進行尋優(yōu),從而逐步提升解的質(zhì)量;引入逆向思維的慣性權重,在全局搜索時保持較小的搜索范圍保證一定的精確度,提供較優(yōu)解,在局部搜索時保持較大的搜索范圍,避免陷入局部最優(yōu);(2)引入線性組合速度更新公式,這一組合結合了社會認知部分和個體認知部分,尋優(yōu)時2個部分充分發(fā)揮作用,調(diào)整了全局最優(yōu)粒子的影響力。引入自適應位置更新公式,加快解的收斂速度;(3)引入爬山算法思想,使粒子躍出局部最優(yōu)。通過以上改進,讓算法朝著更好的方向進化,最終提升標準PSO算法的整體性能。算法偽代碼如下。

算法1MFPSO算法偽代碼

Input:初始化MFPSO算法參數(shù),包括種群N,維度D,迭代次數(shù)K,學習因子c1和c2,慣性權重w,位置邊界xmax和xmin,速度邊界vmax和vmin。

Ouput:最優(yōu)適應度值

1: 隨機生成初始化種群并且初始化粒子的位置和速度

2: 利用式(1)和式(2)計算種群的適應度值

4: whilek

5: 利用式(7)判斷本次更新方式

6: 利用式(8)更新慣性權重w

7: fori=1 toN

10: 更新個體計算適應度值

13: end if

15: 利用式(6)更新gbestk+1

16: end if

17: 利用式(11)和(12)更新gbestk

18: end for

19:k=k+1

20: end while

3 仿真實驗

本文實驗環(huán)境配置為Intel(R) Xeon(R) E-2224 CPU@3.40GHz,內(nèi)存16 GB,使用MATLAB2021b實驗平臺進行仿真。為了驗證算法的有效性,選取不同類型的測試函數(shù)進行消融實驗與對比實驗。MFPSO算法、IPSO-VP算法[17]、SA-PSO算法[18]、FA[6]、SOA[7]、SSA[8]分別在每組測試函數(shù)獨立運行30次,每個算法的迭代次數(shù)為1 000次。在本次實驗中,平均值代表算法運行30次找到全局最優(yōu)解的均值,標準差代表算法30次實驗找到解的穩(wěn)定程度。性能指標均越小越好,表現(xiàn)最好的用粗體表示。

3.1 測試函數(shù)選取

本文在經(jīng)典測試問題[25]中選取12個測試函數(shù)用于仿真實驗。由于算法在不同類型的測試函數(shù)上表現(xiàn)不同,選取F1-F4為單峰函數(shù),用于證明算法的收斂速度和尋優(yōu)精度;F5-F9為多峰函數(shù),是局部最小值的數(shù)量隨維數(shù)呈指數(shù)增長的多模態(tài)函數(shù);F10-F12為固定維函數(shù),只有部分局部極小值。函數(shù)具體名稱及全局最優(yōu)值見表1。

表1 測試函數(shù)Tab. 1 Benchmark functions

3.2 消融實驗與分析

為了驗證MFPSO算法各個部分的有效性,選擇基于均值自適應判斷機制的逆向思維的慣性權重優(yōu)化策略(S-PSO)。在除去自適應判斷機制的情況下選擇逆向思維的慣性權重分別應用全局優(yōu)化策略(G-PSO)和局部優(yōu)化策略(P-PSO)進行消融實驗。為節(jié)省空間,選取單峰函數(shù)F1、多峰函數(shù)F9、固定維函數(shù)F10進行消融實驗,實驗結果見表2。

表2 消融實驗結果Tab. 2 Ablation experiment results

從表2可以看出,僅靠一個全局優(yōu)化策略或者局部優(yōu)化策略的力量是不夠的,單個優(yōu)化策略對標準PSO算法有或多或少的改進,但是求解精度遠不及MFPSO算法。G-PSO策略在單峰函數(shù)F1上取得了很好的成績;在F10中的實驗結果比P-PSO策略相對較好,但收斂速度比MFPSO算法慢,說明G-PSO策略需要執(zhí)行局部優(yōu)化策略來進一步提升尋優(yōu)能力。P-PSO策略和S-PSO策略在3組實驗中的效果均沒有MFPSO算法好,P-PSO策略開始時在質(zhì)量較低的解中尋優(yōu)會造成算法早熟收斂,而在較優(yōu)解附近進行尋優(yōu)更有可能提升算法整體性能。S-PSO策略說明慣性權重的選取對算法整體性能影響很大,并且在F10中最優(yōu)值表現(xiàn)很好。只有有效的優(yōu)化策略相互補充才能更好地提升算法的整體性能,這進一步說明本文所提MFPSO算法的有效性。

3.3 實驗結果數(shù)值實驗與分析

為了進一步驗證本文所提算法的有效性,將MFPSO算法與標準PSO算法、IPSO-VP、SA-PSO、FA、SOA、SSA在上述選取的測試函數(shù)中進行對比實驗,并進行實驗結果分析。本文對標準PSO算法進行改進,以標準PSO算法作為判別MFPSO算法性能的基準。同類型對比算法選取了包含不同優(yōu)化策略和混合其他智能優(yōu)化算法的改進PSO算法變體進行比較,體現(xiàn)MFPSO算法的優(yōu)異性能。對比算法的參數(shù)選取遵循相應文獻中的默認設置。實驗結果如表3所示,收斂曲線如圖1所示。

表3 MFPSO算法與對比算法的實驗結果Tab. 3 Experimental results of MFPSO and comparative algorithms

圖1 收斂曲線Fig. 1 Convergence curve

由表3可知,在F1和F3中,MFPSO算法、IPSO-VP算法、SSA均可以找到其全局最優(yōu)值,其余4種對比算法均未找到理論最優(yōu)值。其中SSA并不能每一次都找到全局最優(yōu),穩(wěn)定性較低,MFPSO算法在這2組實驗中以穩(wěn)定性獲勝,這可能是由于MFPSO算法中的自適應速度、位置更新公式增大了粒子間的信息共享能力,從而有效提高了粒子質(zhì)量并且提升了算法的收斂速度。在F2中,IPSO-VP算法相較于其他對比算法有更高的精度并且穩(wěn)定性更強。然而,通過圖1中收斂曲線可知,MFPSO算法找到全局最優(yōu)的速度更快,更具競爭性。在F4中,盡管IPSO-VP算法和MFPSO算法具有較高的穩(wěn)定性,但只有MFPSO算法可以找到全局最優(yōu)值,收斂精度更高。IPSO-VP算法、MFPSO算法和SSA在F6和F8中都取得了平均最優(yōu)值,而MFPSO算法的收斂速度更快。這可能是由于爬山算法避免了粒子陷入局部最優(yōu),使算法不斷朝著全局最優(yōu)的方向進化。在F7中,MFPSO算法和SSA優(yōu)于其他對比算法,并且在獲得相同求解收斂精度的同時標準差最小。在F9中,SA-PSO算法在平均最優(yōu)值、標準差指標上取得了本組實驗中最好的成績,MFPSO算法則排名第二。在F5,F10-F12中,MFPSO算法取得更好的平均最優(yōu)值且發(fā)揮穩(wěn)定,說明在自適應判斷機制的逆向思維的慣性權重變化較小時,有利于提升PSO算法的穩(wěn)定性。

僅從以上指標出發(fā)衡量各優(yōu)化算法的整體性能還不足以說明MFPSO算法的優(yōu)異性能,需要進一步進行Wilcoxon秩和檢驗以證明MFPSO算法比其他6種對比算法具有顯著的性能優(yōu)勢。表3中,“+/≈/-”表示MFPSO算法優(yōu)于、近似于、劣于相應的對比算法。從統(tǒng)計結果可以看出,MFPSO算法的性能分別在F1-F6,F8,F11和F12這9組測試函數(shù)上顯著優(yōu)于上述6種對比算法;在F7和F10這2組測試函數(shù)中與相應對比算法獲得相似的結果;僅在F9中劣于AS-PSO算法。因此,MFPSO算法在上述12組基準函數(shù)上具有較好的性能,說明通過基于均值自適應判斷機制的逆向思維慣性權重策略、線性組合速度更新策略、自適應位置更新策略以及爬山算法對標準PSO算法的改進能夠有效平衡算法的勘探與開發(fā)能力,提升算法的搜索性能。

從收斂速度出發(fā),圖1中能夠明顯發(fā)現(xiàn)在面對相對容易尋優(yōu)的單峰函數(shù)F1-F4時,MFPSO算法在尋優(yōu)過程中的速度優(yōu)勢突出,且具有較高的精度。在F5中,IPSO-VP算法在前期表現(xiàn)最好,但是MFPSO算法后期收斂精度較高。后期大部分算法的粒子受全局歷史最優(yōu)個體粒子的影響較大,越來越多粒子被誘到局部最優(yōu)解處,此時大多數(shù)粒子跳出局部最優(yōu)位置的能力不斷降低,大部分對比算法已經(jīng)陷入局部最優(yōu)。MFPSO算法在迭代后期利用爬山算法為粒子提供了跳出局部最優(yōu)的能力,可以不間斷地更新全局最優(yōu),從而提高尋優(yōu)精度。在復雜多峰函數(shù)F6-F8中,尋優(yōu)難度增加,但MFPSO算法仍然表現(xiàn)出了較好的收斂速度和精度,擁有最好的尋優(yōu)性能。SA-PSO算法的優(yōu)勢突出體現(xiàn)在其融合模擬退火操作,但只在F9這組函數(shù)中表現(xiàn)較好,此時MFPSO算法的尋優(yōu)結果僅次于SA-PSO算法。在函數(shù)F10-F12中,隨著迭代的不斷進行,各個算法的收斂速度都較為緩慢,但MFPSO算法以精度優(yōu)勢取得了較對比算法更好的成績。

通過以上仿真實驗和結果分析可知,相較于6種對比算法,MFPSO算法在收斂精度和收斂速度上都體現(xiàn)出了較大優(yōu)勢,整體性能更好。這說明本文所提3種改進策略切實有效,使得算法具有良好的全局搜索能力和跳出局部最優(yōu)的能力,是一種值得采納和推廣的改進算法。

4 結束語

標準PSO算法在尋優(yōu)時存在收斂速度較慢、收斂精度較低和易陷入局部最優(yōu)等缺陷。針對以上不足,本文提出了MFPSO算法。首先,該算法通過引入基于均值自適應判斷機制的逆向思維慣性權重,在不同階段使用不同的更新方式幫助算法找到更好的尋優(yōu)結果。其次,引入了線性組合速度和自適應位置更新公式,調(diào)整了粒子之間的信息共享程度,增加了全局搜索時解的精度,從而提升了收斂速度。最后,利用爬山算法思想在局部搜索時給粒子提供更多找到全局最優(yōu)解的機會。相較于其他先進算法,各項仿真實驗結果表明MFPSO算法取得了最好的效果,提升了PSO算法的整體性能。然而,在個別數(shù)值實驗中MFPSO算法的表現(xiàn)還不夠理想,今后將繼續(xù)改進算法,提升算法在不同問題中的表現(xiàn)。