多策略融合的粒子群優化算法*

王惠敏,孫 瀅,高岳林

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

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

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

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

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

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

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

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

1 標準PSO算法

(1)

(2)

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

(3)

(4)

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

(5)

(6)

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

2 MFPSO算法設計

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

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

(7)

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

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

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

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

(9)

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

(10)

2.3 爬山算法思想

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

(11)

(12)

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

2.4 MFPSO算法的整體流程

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

算法1MFPSO算法偽代碼

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

Ouput:最優適應度值

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 仿真實驗

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

3.1 測試函數選取

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

表1 測試函數Tab. 1 Benchmark functions

3.2 消融實驗與分析

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

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

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

3.3 實驗結果數值實驗與分析

為了進一步驗證本文所提算法的有效性,將MFPSO算法與標準PSO算法、IPSO-VP、SA-PSO、FA、SOA、SSA在上述選取的測試函數中進行對比實驗,并進行實驗結果分析。本文對標準PSO算法進行改進,以標準PSO算法作為判別MFPSO算法性能的基準。同類型對比算法選取了包含不同優化策略和混合其他智能優化算法的改進PSO算法變體進行比較,體現MFPSO算法的優異性能。對比算法的參數選取遵循相應文獻中的默認設置。實驗結果如表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均可以找到其全局最優值,其余4種對比算法均未找到理論最優值。其中SSA并不能每一次都找到全局最優,穩定性較低,MFPSO算法在這2組實驗中以穩定性獲勝,這可能是由于MFPSO算法中的自適應速度、位置更新公式增大了粒子間的信息共享能力,從而有效提高了粒子質量并且提升了算法的收斂速度。在F2中,IPSO-VP算法相較于其他對比算法有更高的精度并且穩定性更強。然而,通過圖1中收斂曲線可知,MFPSO算法找到全局最優的速度更快,更具競爭性。在F4中,盡管IPSO-VP算法和MFPSO算法具有較高的穩定性,但只有MFPSO算法可以找到全局最優值,收斂精度更高。IPSO-VP算法、MFPSO算法和SSA在F6和F8中都取得了平均最優值,而MFPSO算法的收斂速度更快。這可能是由于爬山算法避免了粒子陷入局部最優,使算法不斷朝著全局最優的方向進化。在F7中,MFPSO算法和SSA優于其他對比算法,并且在獲得相同求解收斂精度的同時標準差最小。在F9中,SA-PSO算法在平均最優值、標準差指標上取得了本組實驗中最好的成績,MFPSO算法則排名第二。在F5,F10-F12中,MFPSO算法取得更好的平均最優值且發揮穩定,說明在自適應判斷機制的逆向思維的慣性權重變化較小時,有利于提升PSO算法的穩定性。

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

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

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

4 結束語

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