維度學(xué)習(xí)探路者算法

孫哲中，劉 昊，陳 洋

（遼寧科技大學(xué) 理學(xué)院，遼寧 鞍山114051）

元啟發(fā)式算法分為三類：基于生物群智能［1］、基于物理現(xiàn)象［2］和基于進(jìn)化的元啟發(fā)式算法［3］。探路者算法（Pathfinder algorithm，PFA）是基于生物群智能的元啟發(fā)式算法，由Yapici等［4］于2019年提出。該算法具有簡單、易于實(shí)現(xiàn)且魯棒性強(qiáng)的優(yōu)點(diǎn)，但其收斂速度慢、易陷入局部最優(yōu)，因此需不斷對其進(jìn)行改進(jìn)。文獻(xiàn)［5］將差分進(jìn)化算法（Differential evolution，DE）的變異算子集成到PFA中提高收斂精度。文獻(xiàn)［6］提出一種基于教學(xué)策略的PFA算法，用于求解函數(shù)和工程優(yōu)化問題。文獻(xiàn)［7］使用PFA優(yōu)化分?jǐn)?shù)階傾斜積分微分控制器，用于多源電力系統(tǒng)的自動發(fā)電控制。文獻(xiàn)［8］將PFA用于求解太陽能光伏系統(tǒng)在多邊之間的優(yōu)化配置和集成問題。文獻(xiàn)［9］使用改進(jìn)PFA優(yōu)化混合埃爾曼神經(jīng)網(wǎng)絡(luò)（Hybrid elman neural network，ENN），并用于固體氧化物燃料電池模型的評估。

PFA種群在位置更新時不可避免地會產(chǎn)生越界個體，需對這類個體進(jìn)行越界處理，使超過搜索邊界的個體位置重新回到搜索空間。常見的越界處理方法有重新初始化法和邊界限定法。重新初始化是將越界個體在搜索空間中重新進(jìn)行隨機(jī)初始化。這種處理方法在迭代過程中通常比較粗糙，且無法保留越界個體已經(jīng)搜索到的歷史維度信息。邊界限定法則是尋找越界個體中的越界維度信息，將越界維度限制在離其最近的邊界上。這種處理方法盡管能夠保留越界個體的維度信息，但對越界維度利用率差。

為解決PFA在簡單問題中收斂速度慢、收斂精度差以及對維度信息利用不充分的問題，本文提出了一種改進(jìn)PFA，稱為維度學(xué)習(xí)探路者算法（Dimension learning pathfinder algorithm，DLPFA）。維度學(xué)習(xí)由限制維度策略和加強(qiáng)維度策略組成。限制維度是針對越界個體的改進(jìn)策略，將發(fā)生越界的維度信息替換為當(dāng)前領(lǐng)導(dǎo)者個體對應(yīng)的維度信息。這種策略利用精英個體的領(lǐng)導(dǎo)能力，能夠使越界個體回歸搜索空間的同時向精英個體方向移動，從而提高算法的收斂速度。加強(qiáng)維度是針對位置更新不成功的個體提出的改進(jìn)策略，首先，將領(lǐng)導(dǎo)者維度信息的極值作為搜索邊界，并在其中隨機(jī)初始化一個示范個體，隨機(jī)初始化有利于保持種群多樣性，而利用領(lǐng)導(dǎo)者的維度信息作為搜索邊界有利于當(dāng)前個體與領(lǐng)導(dǎo)者的信息交流；其次，在種群中隨機(jī)選擇一個個體作為信息個體，來加強(qiáng)種群之間的信息交流和共享；最后，當(dāng)前個體通過向示范個體和信息個體雙重學(xué)習(xí)來更新位置。因此，維度學(xué)習(xí)策略能夠有效地利用個體的維度信息，幫助其跳出局部最優(yōu)的同時提升收斂速度。

1 探路者算法

群居動物通常有鮮明的等級區(qū)分制度，PFA模擬群居動物分級方式，將種群分為領(lǐng)導(dǎo)者和跟隨者兩部分。在規(guī)模為N的種群中，選取最優(yōu)秀的個體為領(lǐng)導(dǎo)者，領(lǐng)導(dǎo)者根據(jù)自己以往經(jīng)驗(yàn)尋找獵物，進(jìn)行位置更新

種群中除領(lǐng)導(dǎo)者外的其余個體為追隨者，追隨者位置更新策略

PFA算法流程如圖1所示。

圖1 PFA算法流程圖Fig.1 Flow chart of PFA algorithm

2 維度學(xué)習(xí)探路者算法

2.1 限制維度學(xué)習(xí)策略

種群在位置更新的過程中難免會出現(xiàn)越界個體。為了利用領(lǐng)導(dǎo)者對算法搜索方向的引導(dǎo)，合理利用其維度信息來處理越界個體有利于提升算法的收斂速度。限制維度學(xué)習(xí)策略旨在讓領(lǐng)導(dǎo)者引導(dǎo)越界個體重新回到搜索空間，同時實(shí)現(xiàn)越界個體合理共享領(lǐng)導(dǎo)者的維度信息，具體策略為

2.2 加強(qiáng)維度學(xué)習(xí)策略

種群中的個體在迭代時，由于學(xué)習(xí)策略的限制，常存在位置不更新的情況。因此，提出一種并行的加強(qiáng)維度學(xué)習(xí)策略，提高迭代中位置更新的成功率。首先，將適應(yīng)值改變與否作為判斷個體是否發(fā)生位置更新的依據(jù)，若當(dāng)前個體的適應(yīng)值未改變，則執(zhí)行加強(qiáng)維度學(xué)習(xí)，具體策略為

隨機(jī)維度變化的數(shù)學(xué)模型描述為

式中：randi是從集合{1,Dim}中隨機(jī)抽取的一個元素，當(dāng)randi=Dim時，vct是［0，1］區(qū)間上服從均勻分布的維數(shù)為Dim的隨機(jī)向量；否則，rand是［0，1］區(qū)間上服從均勻分布的隨機(jī)數(shù)。

2.3 DLPFA算法的實(shí)現(xiàn)步驟

步驟1初始化參數(shù)：種群的規(guī)模N、函數(shù)評價最大次數(shù)FEmax、最大迭代次數(shù)Tmax、合作系數(shù)αmax=2和αmin=1、吸引系數(shù)βmax=2和βmin=1。

步驟2初始化種群并計(jì)算對應(yīng)的適應(yīng)值；根據(jù)適應(yīng)值排序并確定領(lǐng)導(dǎo)者和跟隨者。

步驟3按式（1）更新領(lǐng)導(dǎo)者的位置信息，并用式（7）處理越界個體。

步驟4按式（3）更新跟隨者的位置信息，并用式（7）處理越界個體。

步驟5計(jì)算所有個體的適應(yīng)值，若個體位置更新不成功，使用式（8）更新該個體并計(jì)算其適應(yīng)值。

步驟6根據(jù)適應(yīng)值排序并確定領(lǐng)導(dǎo)者和跟隨者。

步驟7若不滿足終止條件，返回步驟3；否則終止算法，輸出最優(yōu)解。

3 實(shí)驗(yàn)結(jié)果與統(tǒng)計(jì)分析

3.1 測試函數(shù)

為了驗(yàn)證改進(jìn)算法DLPFA的有效性，將其與經(jīng)典的粒子群優(yōu)化算法（Particle swarm optimization，PSO）［10］、渦流搜索算法（Vortex search，VS）［11］、樹生長算法（Tree growth algorithm，TGA）［12］及PFA進(jìn)行對比，選擇5個經(jīng)典的Benchmark測試函數(shù)，對其進(jìn)行性能測試。

（1）Step函數(shù)

此函數(shù)又稱階梯函數(shù)，由一系列水平線段組成，在定義域內(nèi)自變量趨近于無窮時，會在給定的間隔上出現(xiàn)不同的階躍現(xiàn)象，并且在每個階躍間會產(chǎn)生大量局部極值，因此，尋優(yōu)難度大。該函數(shù)是不連續(xù)的階梯函數(shù)，可以檢驗(yàn)算法的收斂精度。

（2）Rastrigin函數(shù)

此函數(shù)是一個多峰函數(shù)，在(x1,x2,…,xDim)=（0，0，…，0）達(dá)到全局極小點(diǎn)，在{xd∈(-5,12,5,12),范圍內(nèi)大約有10Dim個局部極小點(diǎn)［13］。該函數(shù)局部最優(yōu)點(diǎn)的數(shù)量隨維數(shù)指數(shù)遞增，可以檢驗(yàn)算法的全局搜索能力。

（3）Griewank函數(shù)

此函數(shù)有多個局部極小點(diǎn)，局部極小點(diǎn)的個數(shù)與函數(shù)問題中的維數(shù)有關(guān)。xd=±kπd(d=1,2,…,Dim)是該函數(shù)的極小值。該函數(shù)可以檢測算法跳出局部最優(yōu)的能力。

（4）Ackely函數(shù)

此函數(shù)是指數(shù)函數(shù)疊加適度放大的余弦函數(shù)而得到的連續(xù)型函數(shù)。該函數(shù)在一個平坦的區(qū)域由余弦波調(diào)制成大量孔或峰，易使算法陷入局部最優(yōu)。當(dāng)目標(biāo)函數(shù)的維度增加時，該函數(shù)局部最優(yōu)解呈指數(shù)遞增，最優(yōu)解的搜索難度大。因此，常被用于檢測算法的全局收斂速度和搜索精度。

（5）Rosebrock函數(shù)

此函數(shù)的每個等高線呈拋物線形，全局最小值在拋物線形的山谷中，是一個非凸函數(shù)，要找到全局最小值相當(dāng)困難。該函數(shù)為優(yōu)化算法提供的信息比較有限，算法很難辨別搜索方向，最優(yōu)解的查找十分困難。因此，該函數(shù)常用于檢測算法的全局探索能力和局部開采能力。基準(zhǔn)測試函數(shù)的相關(guān)信息詳見表1。

表1 基準(zhǔn)測試函數(shù)信息Tab.1 Parameters of benchmark functions

3.2 實(shí)驗(yàn)結(jié)果

為了方便對比，五種算法均取最大函數(shù)評價次數(shù)FEmax=30 000，最大迭代次數(shù)Tmax=600，種群規(guī)模N=50，取最大函數(shù)評價次數(shù)和最大迭代次數(shù)為終止條件。同時，為了減少隨機(jī)數(shù)對算法性能的影響，每種算法在每個測試函數(shù)上均獨(dú)立運(yùn)行30次，取30次的實(shí)驗(yàn)結(jié)果進(jìn)行統(tǒng)計(jì)分析。實(shí)驗(yàn)結(jié)果詳見表2。實(shí)驗(yàn)將均值、標(biāo)準(zhǔn)差和最優(yōu)值作為評價指標(biāo)。均值和最優(yōu)值能評價算法的收斂精度，標(biāo)準(zhǔn)差反映算法的魯棒性。取均值為排名依據(jù)，均值越小，排名越高，均值相等時，排名相同。

表2 五種算法的比較結(jié)果Tab.2 Comparison between five algorithms

對于f1，DLPFA、PSO以及PFA找到了最優(yōu)值0，但DLPFA標(biāo)準(zhǔn)差最低，均值也取到最優(yōu)值0，說明其具有更好的穩(wěn)定性。對于f2，相比于其他算法，DLPFA均值和最優(yōu)值都最低，具有更好的收斂精度。對于f4和f5，DLPFA均值和標(biāo)準(zhǔn)差遠(yuǎn)低于其他算法，具有更好的收斂精度和穩(wěn)定性。對于f3，相比于其他算法，DLPFA仍取到最小均值，最優(yōu)值和標(biāo)準(zhǔn)差僅稍遜于VS。綜上，DLPFA在維度學(xué)習(xí)策略下的收斂精度有所改善，魯棒性也有提升。

五種算法對于5個測試函數(shù)的收斂曲線如圖2所示。對于f1和f5，DLPFA和PFA收斂速度相似，但DLPFA收斂精度明顯優(yōu)于PFA。對于f2、f3和f4，DLPFA的收斂曲線均位于其他算法下方，且能快速收斂到全局最優(yōu)附近。這表明DLPFA對于其他算法收斂速度和收斂精度有著明顯優(yōu)勢。

圖2 五種算法的仿真結(jié)果Fig.2 Simulation results of five algorithms

3.3 Wilcoxon符號秩檢驗(yàn)

Wilcoxon符 號 秩 檢 驗(yàn)（Wilcoxon rank sum test，WRST）是一類非參數(shù)檢驗(yàn)方法，它不對數(shù)據(jù)分布作特殊假設(shè)，適用于復(fù)雜數(shù)據(jù)兩兩比較的假設(shè)檢驗(yàn)。為了進(jìn)一步檢驗(yàn)DLPFA算法的收斂性能，對五種算法的實(shí)驗(yàn)結(jié)果進(jìn)行WRST非參數(shù)檢驗(yàn)，結(jié)果見表3?！癏+”代表正的秩和，“H-”代表負(fù)的秩和；P值（Probability value，P_value）用于檢測兩個算法是否有明顯差異，當(dāng)P_value＞0.05時，說明兩個算法無明顯差異；獲勝者（winner）用于記錄DLPFA與其他對比算法的差異情況，當(dāng)P_value＜0.05，且H+＜H-時，表示在5%的顯著性水平下DLPFA相比于其他算法的收斂性能有明顯優(yōu)勢，winner記為“+”；當(dāng)P_value＜0.05，且H+＞H-，表示在5%的顯著性水平下DLPFA的收斂性能弱于對比算法，winner記為“-”；P_value＞0.05表示兩種算法在5%的顯著性水平下無明顯差異，winner記為“=”。

表3 五種算法的WRST對比結(jié)果Tab.3 WRST comparison between five algorithms

對于全部基準(zhǔn)測試函數(shù)，DLPFA的P_value均低于0.05，且H+均小于H-，表明DLPFA在5%的顯著性條件下的收斂性能相比于其它對比算法都有明顯優(yōu)勢。

4 維度學(xué)習(xí)策略的推廣

PSO是經(jīng)典的啟發(fā)式算法，將維度學(xué)習(xí)策略用于PSO驗(yàn)證其是否具有普適性，改進(jìn)后的算法稱為維度學(xué)習(xí)粒子群優(yōu)化算法（Dimension learning particle swarm optimization，DLPSO）。CEC2017基準(zhǔn)測試函數(shù)集用于驗(yàn)證DLPSO的有效性，測試函數(shù)的相關(guān)信息見表4。設(shè)種群大小為50，維度為30，慣性權(quán)重從0.9線性遞減到0.4，學(xué)習(xí)因子c1=c2=2。PSO與DLPSO兩種算法在每個測試函數(shù)上獨(dú)立運(yùn)行30次，均值的統(tǒng)計(jì)結(jié)果見表5。

表4 CEC2017測試函數(shù)信息Tab.4 Parameters of CEC2017 benchmark functions

表5 兩種算法的比較結(jié)果Tab.5 Comparison between two algorithms

在29個測試函數(shù)中，DLPSO在24個測試函數(shù)上的收斂性能明顯強(qiáng)于PSO；僅在5個測試函數(shù)上的收斂性能弱于PSO，分別是F4、F6、F7、F9及F29。將維度學(xué)習(xí)策略應(yīng)用到PSO中，提高了算法跳出局部最優(yōu)的能力，收斂速度與精度也明顯提升。表明該策略是有效的，且能應(yīng)用于其他算法。

5 結(jié)論

提出一種基于維度學(xué)習(xí)的探路者算法DLPFA。為了克服PFA的缺點(diǎn)，使用限制維度策略進(jìn)行越界處理，該策略具有很強(qiáng)的維度信息共享能力，能提高算法的收斂速度。在位置更新階段融入加強(qiáng)維度策略，利用領(lǐng)導(dǎo)者生成的示范個體和種群中隨機(jī)選擇的個體進(jìn)行位置再更新，充分發(fā)揮精英個體的領(lǐng)導(dǎo)能力，同時加強(qiáng)與種群的信息交流，增強(qiáng)種群多樣性，進(jìn)而幫助個體跳出局部最優(yōu)。5個經(jīng)典的Benchmark測試函數(shù)實(shí)驗(yàn)結(jié)果表明，DLPFA明顯優(yōu)于其余四種算法。維度學(xué)習(xí)策略在PSO算法上的成功應(yīng)用表明該策略具有普適性。