毛雪迪,王 冰,夏煌智,張魯平,李永超

(牡丹江師范學院 數(shù)學科學學院,黑龍江 牡丹江 157000)

0 引 言

智能優(yōu)化算法是一類基于自然界生物進化、群體智能、神經(jīng)網(wǎng)絡(luò)等理論和方法而發(fā)展起來的優(yōu)化算法,這類算法通過模擬生物進化、群體社會行為等機制尋找最優(yōu)解或次優(yōu)解,具有全局優(yōu)化、魯棒性強等特點,在許多領(lǐng)域中得到了廣泛應用。2019年,Yapici等人提出了一種新的群智能優(yōu)化算法,即探路者算法(Pathfinder Algorithm,PFA)[1],它基于生物進化理論和群體智能原理,通過模擬生物進化和自然選擇的過程尋找最優(yōu)解。該算法具有自適應參數(shù)設(shè)置、多種探索策略、魯棒性強和高效性等特點,已經(jīng)在多個領(lǐng)域得到了廣泛的應用,如機器學習、信號處理、圖像處理等,然而,PFA也存在收斂速度慢、求解精度不高、容易陷入局部最優(yōu)等問題。文獻[2]通過借助PFA中探路者與跟隨者獨特的更新模式,成功地提升了灰狼優(yōu)化算法的尋優(yōu)性能,這種融合方式得到的優(yōu)化算法具有較高的收斂精度。文獻[3]在PFA中引入了一種向?qū)C制,使得帶有向?qū)C制的探路者個體能夠收集周圍個體的優(yōu)良信息,并將這些信息傳播給其它個體,同時,還引入了一種新型的變異概率pcR,以增強算法跳出局部最優(yōu)的能力。文獻[4]將教與學算法與PFA相結(jié)合,通過在跟隨者階段中引入指數(shù)步長算子優(yōu)化跟隨者個體提高了算法整體的尋優(yōu)精度和收斂速度。文獻[5]利用動態(tài)反向?qū)W習策略提升了初始種群質(zhì)量,提出一種新的躍遷檔案保存并創(chuàng)造新的最優(yōu)個體,引導陷入局部最優(yōu)的個體跳出當前位置;又提出一種雙跳模型協(xié)調(diào)算法的全局搜索和局部開發(fā)能力。

為解決上述問題,該文提出一種嵌入Cat映射的混合變異探路者算法(CHMPFA)。首先,利用混沌反向?qū)W習策略增加了初始種群的多樣性和分散性;其次,在探路者更新公式中加入衰減因子,在迭代過程中控制探路者的搜索步長從而控制搜索范圍;然后,利用隨機數(shù)對最優(yōu)個體進行混合變異,幫助其脫離當前區(qū)域向全局最優(yōu)值靠近;最后,通過在10個基準函數(shù)和12個CEC2017基準測試函數(shù)進行仿真實驗驗證策略的魯棒性,并將CHMPFA應用于壓力容器工程問題中,優(yōu)秀的尋優(yōu)結(jié)果進一步證明了改進算法的有效性。

1 標準探路者算法

在標準探路者算法中,種群只分為兩種類型:探路者和領(lǐng)導者,探路者為適應度值最好的個體,其余個體為跟隨者的角色。

探路者算法中的位置向量X將由N個維度為d的種群個體組成,每個個體定義為Xi=[xi1,xi2,…,xid],各維度的上界為ub=[ub1,ub2,…,ubd],下界為lb=[lb1,lb2,…,lbd],即種群隨機初始化為:

XN×d=rand(N,d)×(ub-lb)+lb

(1)

其中,N為種群規(guī)模,d為空間維度;在種群迭代過程中,選出適應度值最優(yōu)的個體作為探路者,跟隨者均向它移動,更新方式為式2:

(2)

(3)

探路者更新完后,跟隨者根據(jù)探路者位置進行更新,更新方式為式4:

(4)

(5)

Dij=‖xi-xj‖

(6)

R1=αr2

(7)

R2=βr3

(8)

2 算法改進

2.1 混沌反向?qū)W習初始化種群

為了改善種群質(zhì)量和提高算法的搜索性能,該文引入Cat混沌映射結(jié)合反向?qū)W習的方法[6]初始化種群。Cat映射是一個結(jié)構(gòu)簡單的二維可逆混沌映射,可以產(chǎn)生具有隨機性、分散性和復雜性的種群分布,能夠幫助算法從多個起點同時進行搜索,增加算法的全局搜索能力,其表達公式如下:

(9)

反向?qū)W習[7]則是一種基于貪心策略的啟發(fā)式算法,可以在有限的時間內(nèi)快速生成優(yōu)秀的種群,增加算法的局部搜索能力。將兩種方法結(jié)合起來使用,能夠在初始化種群時既考慮全局性又考慮局部性,提高算法的搜索效率和多樣性。此外,Cat混沌映射和反向?qū)W習還可以互相補充彼此的不足。Cat混沌映射在產(chǎn)生種群時具有一定的隨機性,容易產(chǎn)生多樣性,但可能會受到局部最優(yōu)解的影響,難以快速收斂;而反向?qū)W習雖然可以快速生成優(yōu)秀的種群,但可能會陷入局部最優(yōu)解,將兩種方法結(jié)合使用可以平衡二者之間的優(yōu)缺點,提高算法的搜索性能和魯棒性。

由混沌序列結(jié)合反向?qū)W習初始化種群,其步驟是:首先利用Cat映射產(chǎn)生初始種群xi(i=1,2,…,N),然后為每個初始解按公式10求其相應的反向解。

(10)

2.2 賦予衰減性的探路者更新方式

為解決探路者算法搜索效率和求解精度低等問題,該文提出將衰減因子引入PFA探路者更新公式中,隨著迭代的進程不斷降低衰減因子的大小,算法搜索空間的范圍也會逐漸縮小至最優(yōu)解附近,從而避免了算法過早陷入局部最優(yōu)區(qū)域的狀況,這能夠使算法快且準地找到理論最優(yōu)解,幫助算法改善了搜索效率和求解精度。提出的衰減因子是一個非線性遞減函數(shù),定義式如下:

(11)

其中,s∈[0,1]為衰減系數(shù)(該文選取s=0.5),控制算法收斂速度,t為當前迭代次數(shù)。引入衰減因子后的探路者更新公式如下:

(12)

通過衰減因子的非線性變化,使算法在不同階段的搜索更加高效。在算法初期,較大的衰減因子幫助探路者在解空間中進行更廣泛的搜索;隨著算法的迭代,較小的衰減因子幫助算法對局部區(qū)域進行更加精確的探索。

2.3 混合變異策略

(1)柯西變異。

柯西變異來源于柯西分布[8],一維柯西概率密度公式如下:

(13)

當λ=1時,是標準柯西分布。從圖1的標準柯西、高斯分布概率密度函數(shù)曲線觀察可知,柯西分布與高斯分布類似,主要差異表現(xiàn)為柯西分布峰值略小于高斯分布,柯西分布在原點處有較高的概率密度,在兩端有較低的概率密度,柯西分布的邊緣較長且扁平,比高斯分布更平緩的逼近于0。

圖1 標準柯西、高斯分布概率密度函數(shù)曲線

根據(jù)此特點對探路者和跟隨者位置更新后的最優(yōu)個體進行柯西變異,通過柯西算子的擾動特性提升算法的尋優(yōu)性能。當最優(yōu)個體無法跳出局部最優(yōu)解時,柯西算子能夠提供較長的步長幫助其個體跳出局部最優(yōu);當最優(yōu)個體向理論最優(yōu)值靠近時,柯西算子能夠提供較短的步長提升個體收斂速度?？挛髯儺惒呗詳?shù)學模型如下:

(14)

(2)高斯變異。

高斯算子可以防止種群陷入局部最優(yōu),增加種群的多樣性。為了提升PFA局部搜索的能力和跳出局部最優(yōu)的概率,對最優(yōu)個體進行高斯變異操作,高斯概率密度公式和高斯變異策略數(shù)學模型如下:

(15)

(16)

其中,μ表示期望,σ表示標準差,標準正態(tài)分布的期望和方差分別設(shè)置為0和1,Gaussian(σ)是由式15形成的標準正態(tài)分布的隨機變量。

由圖1可知高斯分布的概率密度函數(shù)呈現(xiàn)鐘形曲線,均值即為期望值,并且其方差較大、分布范圍較廣,所以當最優(yōu)個體處于局部最優(yōu)解時,高斯變異可以讓其位置發(fā)生微小變化,使得搜索過程可以繼續(xù)向周圍未被探索的區(qū)域擴展,從而增加逃離局部最優(yōu)的可能性。

(3)混合變異。

在PFA中引入柯西變異和高斯變異可以使得算法更加全面地探索解空間,從而有更大的可能找到最優(yōu)解?？挛髯儺惪梢栽黾铀惴ǖ娜炙阉髂芰?因為它具有長尾分布,可以探索到遠離當前搜索點的區(qū)域;而高斯變異則可以增加算法的局部搜索能力,因為它可以更加精準地探索周圍區(qū)域,從而更容易找到局部最優(yōu)解。所以,該文根據(jù)變異概率p將柯西變異和高斯變異融合為混合變異策略引入PFA當中,如公式17所示:

(17)

但是,變異后最優(yōu)個體位置無法保證優(yōu)于原始位置,所以在混合變異位置擾動后加入保優(yōu)策略,即貪婪策略,通過比較變異后最優(yōu)個體與原最優(yōu)個體的適應度值,選取適應度值最好的個體作為當前代的全局最優(yōu)解,則把變異后個體替換掉原始個體,判斷公式如下:

(18)

2.4 CHMPFA算法偽代碼

CHMPFA算法偽代碼如下:

Initialize PFA parameters

Initialize population using chaoticopposition-based learning

Calculate the fitness of initial population

Find the pathfinder

Whilet

Update pathfinder the position using Eq.(12) and check the bound

if new pathfinder is better than old

Update pathfinder

end

fori=2 to maximum number of populations

Update follower the position using Eq.(4) and check the bound

end

Calculate new fitness of members

Find the best fitness

if rand<0.5

Update best number position using Eq.(14)

else

Update best number position using Eq.(16)

end

Calculate the fitness of new best number

if new best fitness

Update best nember

end

Calculate new fitness of members

Find the best fitness

if best fitness

Pathfinder = best member

Fitness = best fitness

end

t=t+1;

end Whil

2.5 時間復雜度分析

時間復雜度是體現(xiàn)算法運行效率的重要指標,現(xiàn)假設(shè)種群規(guī)模為N,空間維度為d,最大迭代次數(shù)為Tmax,f(x)表示適應度函數(shù)。根據(jù)標準PFA流程可知,PFA的總時間復雜度為O(d+f(d)),現(xiàn)對CHMPFA的時間復雜度進行分析。

對于CHMPFA,在初始化種群階段,假設(shè)初始化算法參數(shù)的時間為t1,按適應度值對所有個體進行排序并選定探路者的時間為t2,由于通過混沌反向?qū)W習初始化種群個體的時間復雜度為O(N×d),且對每個個體計算適應度值的時間為f(d),則初始化種群階段的時間復雜度為:

T1=O(t1+N×f(d)+t2)+O(N×d)=

O(d+f(d))

進入迭代期,在探路者階段,探路者數(shù)目為1,假設(shè)計算自適應權(quán)重w的時間為t3,生成隨機數(shù)r1需要的時間為t4,計算A的時間為t5,更新探路者位置時間為t6,對探路者個體的每一維邊界處理的時間為t7,則探路者階段的時間復雜度為:

T2=O(t3+1×(t4+t5+t6+t7)×d)=O(d)

在跟隨者階段,CHMPFA更新跟隨者位置的方式與標準PFA保持一致,所耗費的時間并沒有增加。因此,跟隨者階段的時間復雜度也應與標準PFA一致為:

T3=O(d+f(d))

在變異階段,最優(yōu)個體進行柯西變異或高斯變異的時間為t12,計算最優(yōu)個體適應度值的時間為f(d),利用貪婪策略判斷新最優(yōu)個體是否代替舊最優(yōu)個體的時間為t13,保留最優(yōu)個體位置的時間為t14,對最優(yōu)個體的每一維邊界處理的時間為t15,則變異階段的時間復雜度為:

T4=O(1×d×(t12+t13+t15)+t14+1×f(d))=O(d+f(d))

綜上所述,CHMPFA的總時間復雜度為T=T1+Tmax(T2+T3+T4)=O(d+f(d))。因此,CHMPFA的時間復雜度與標準PFA一致,執(zhí)行效率并未下降。

3 實驗仿真與結(jié)果分析

3.1 實驗設(shè)計

為測試CHMPFA的性能,將CHMPFA與PSO[9],DE[10],WOA[11],BSA[12],SCA[13],ChOA[14],BOA[15]以及標準PFA[1]在10個基準測試函數(shù)(函數(shù)信息如表1所示)上進行30次獨立實驗,其中f1～f5為單峰函數(shù)(UN),有唯一的全局最優(yōu)解,目的是檢驗算法的尋優(yōu)能力和收斂速度;f6～f10為多峰函數(shù)(MN),有較多的局部最優(yōu)解,目的是驗證算法跳出局部最優(yōu)和避免過早收斂的能力。

表1 基準測試函數(shù)

為了實驗的公正性,所有算法均在Intel(R) Core(TM) i5—11260H CPU@2.60 GHz,Windows 10系統(tǒng),16 GB內(nèi)存,64位操作系統(tǒng)的計算機上進行尋優(yōu)測試,通過MATLAB R2021a軟件進行仿真實驗。統(tǒng)一設(shè)置實驗種群規(guī)模N為30,實驗最大迭代次數(shù)Tmax為1 000,每個算法在各基準測試函數(shù)上進行30次獨立實驗,將實驗得到的平均值(Mean)與標準差(S.D)數(shù)據(jù)進行統(tǒng)計,實驗參數(shù)如表2所示。

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

3.2 尋優(yōu)性能對比分析

實驗一:從表3記錄的10個基準測試函數(shù)實驗結(jié)果得知,相對于其余8種算法,該文改進的CHMPFA均有著最小的平均值與標準差。

表3 基準測試函數(shù)尋優(yōu)結(jié)果對比

從尋優(yōu)精度角度觀察,CHMPFA在各個基準測試函數(shù)上均取得了最小的平均值,且在4個單峰函數(shù)(f1,f2,f3,f4)與2個多峰函數(shù)(f8,f9)上找到了理論最優(yōu)值0。其原因是由于CHMPFA在初始化種群階段引入了混沌反向?qū)W習策略,使得初始種群在解空間中分布得更加均勻,為后續(xù)的優(yōu)化過程奠定了良好的基礎(chǔ),有助于避免種群陷入局部最優(yōu)值附近,從而增加全局搜索的可能性;在迭代前期,探路者更新步長較大,可以全面搜索整個解空間,以探索更廣泛的解空間,提高算法的全局搜索性能,在迭代后期,探路者更新步長逐漸減小,從而更加注重對局部解空間的探索,以期發(fā)現(xiàn)局部最優(yōu)解;當算法陷入局部最優(yōu)值時,CHMPFA以一定的變異概率進行柯西變異或者高斯變異使算法跳出局部最優(yōu)值所在區(qū)域,這樣的隨機性引入可以有效地增加算法的搜索廣度,避免算法過度依賴局部搜索,從而提高了算法的全局搜索能力,最終搜索到理論最優(yōu)值。

從尋優(yōu)穩(wěn)定性角度觀察,在函數(shù)f10上,CHMPFA的標準差僅次于WOA的標準差,但在其余9個基準測試函數(shù)上均取得了最小的標準差,表明CHMPFA在保證尋優(yōu)精度最高的同時尋優(yōu)穩(wěn)定性也處于較高水平。

實驗二:為了進一步評估CHMPFA的表現(xiàn),通過Wilcoxon秩和檢驗[16]來驗證與其它算法之間是否存在顯著的差異。該文選擇0.05作為顯著性水平進行Wilcoxon秩和檢驗,如果CHMPFA優(yōu)于對比算法,則p-value<0.05;如果CHMPFA與對比算法相當,則在數(shù)據(jù)中記錄為NaN;如果CHMPFA劣于對比算法,則p-value≥0.05,并且將這些數(shù)據(jù)以黑體表示。該文使用“+/=/-”符號來表示CHMPFA“優(yōu)于/相當于/劣于”對比算法。

根據(jù)表3的實驗結(jié)果可知,CHMPFA與標準PFA在9個基準測試函數(shù)上得到的p值遠小于顯著性水平0.05,表明CHMPFA在尋優(yōu)性能上優(yōu)于標準PFA,這是因為CHMPFA集成了混沌反向?qū)W習初始化種群策略、賦予衰減性探路者更新方式和混合變異策略,Cat混沌映射結(jié)合反向?qū)W習可以在初始階段就引導種群朝著全局優(yōu)勢方向進行搜索,從而提高算法的全局優(yōu)化性能;衰減因子幫助算法逐漸收斂到最優(yōu)解附近,提高算法的穩(wěn)定性和可靠性;對最優(yōu)個體進行變異提高了算法跳出局部最優(yōu)的概率,便于找到全局最優(yōu)解。除探路者算法本身之外,CHMPFA與除WOA外的6種算法在10個基準測試函數(shù)上得到的p值同樣遠小于顯著性水平0.05,說明CHMPFA較以上6種算法也有著更加優(yōu)秀的尋優(yōu)性能;而對于WOA,即使存在著與CHMPFA性能相當或較劣的現(xiàn)象,但也是少數(shù)情況,從整體算法性能看來,CHMPFA仍占據(jù)顯著優(yōu)勢。

實驗三:基于10個基準測試函數(shù)的平均絕對誤差(Mean Absolute Error,MAE),將所有算法的性能定量分析后進行排序,是評估算法有效性與可行性的可靠方法[17]。計算得到的MAE越小表示算法的平均結(jié)果與理論最優(yōu)結(jié)果的絕對誤差和越小,算法性能越優(yōu)秀,其計算公式為:

(19)

其中,avg_Bi表示算法得到的全局最優(yōu)解的平均值,?i表示選取基準測試函數(shù)的理論最優(yōu)值,Lf表示選取基準測試函數(shù)的個數(shù)。實驗結(jié)果顯示,CHMPFA的MAE的排名第一,進一步驗證了改進算法的魯棒性。

3.3 收斂曲線分析

所有算法對函數(shù)求解尋優(yōu)時的收斂曲線如圖2所示(選取部分函數(shù)f2,f5,f6,f8和f9),為了方便觀察曲線的收斂情況,對縱坐標取10為底的對數(shù)。

(a)f2收斂曲線 (b)f5收斂曲線 (c)f6收斂曲線 (d)f8收斂曲線 (e)f9收斂曲線

由圖2可知,CHMPFA在迭代前期收斂曲線下降較快,這是由于PFA初始階段的種群由混沌反向?qū)W習策略生成,相較于隨機生成種群,Cat映射生成的種群遍布整個搜索空間,再通過反向?qū)W習策略,增加種群多樣性的同時減少了個體重疊現(xiàn)象,更有利于探路者和跟隨者的位置更新。

在圖2(a)和圖2(b)的單峰函數(shù)圖像中,CHMPFA在f2函數(shù)上收斂速度較快,其余8種算法在尋優(yōu)性能上較弱于CHMPFA;對于函數(shù)f5,雖然在迭代結(jié)束時9種算法均未能找到理論最優(yōu)值,但是CHMPFA的尋優(yōu)精度相對較高,收斂曲線有持續(xù)下降的趨勢,這是由于衰減因子為探路者在迭代后期縮減探索范圍,使探路者帶領(lǐng)跟隨者在局部區(qū)域能夠更加精密的探索,不斷地向最優(yōu)解區(qū)域靠近,最終使得CHMPF在尋優(yōu)精度上優(yōu)于其它算法。

在圖2(c)～(e)的多峰函數(shù)圖像中,CHMPFA在f9函數(shù)上50次迭代內(nèi)就找到了理論最優(yōu)值0,而除WOA外其余7種算法均出現(xiàn)了不同程度的停滯現(xiàn)象,這是由于在PFA中加入了變異和貪婪選擇策略,以一定的概率選擇高斯變異或者柯西變異的最優(yōu)個體增強了跳出局部最優(yōu)的能力,該策略在CHMPFA尋優(yōu)過程中發(fā)揮著重要的作用;在函數(shù)f6和f8上,雖然所有算法均沒有跳出局部區(qū)域,但結(jié)合表3可知,CHMPFA的迭代曲線收斂速最快,在尋優(yōu)精度上遠超其它所對比的算法。

綜上所述,無論在單峰函數(shù)還是多峰函數(shù),在每個函數(shù)上CHMPFA的尋優(yōu)精度和收斂速度都十分出色,驗證了綜合三個改進策略CHMPFA的優(yōu)化效果。

3.4 CEC2017基準測試函數(shù)求解實驗

為了進一步評估CHMPFA的魯棒性,在CEC2017基準函數(shù)中選取部分多峰函數(shù)、混合函數(shù)(Hybrid Function,HF)與復合函數(shù)(Composition Function,CF)進行求解尋優(yōu),選取的函數(shù)如表4所示。設(shè)置初始種群規(guī)模為30,最大迭代次數(shù)為1 000,維度為30,各算法運行30次的平均值(Mean)與標準差(S.D)記錄在表5中。

表4 CEC2017基準測試函數(shù)

表5 CEC2017基準測試函數(shù)尋優(yōu)結(jié)果對比

根據(jù)表5可知,CHMPFA在12個CEC2017基準測試函數(shù)上尋優(yōu)所得的平均值和標準差均比其余算法的優(yōu),這是由于CHMPFA引入了混沌反向?qū)W習策略,賦予種群更深層次的多樣性,使初始種群不再隨機地遍布于搜索空間;并將衰減因子引入探路者公式中,幫助探路者更快地遍歷解空間,通過逐漸減小搜索步長從而加深對局部區(qū)域的開采,提高了找到全局最優(yōu)解的概率;由于CEC2017函數(shù)局部極值眾多,所以混合變異策略在CHMPFA尋優(yōu)過程中發(fā)揮著重要的作用,使算法能夠跳出局部極值向函數(shù)理論最優(yōu)值靠近。

4 壓力容器設(shè)計問題

壓力容器設(shè)計問題的目標是使各項費用總和最低。這一模型有4個決策變量:筒體厚度Ts(0≤x1≤99)、封頭厚度Th(0≤x2≤99)、筒體半徑R(0≤x3≤200)和圓柱形截面長度Ls(10≤x4≤200),以及4個約束條件,壓力容器設(shè)計問題數(shù)學模型如下:

(20)

表6記錄了9種算法優(yōu)化壓力容器設(shè)計的結(jié)果,CHMPFA獲得的最優(yōu)解為[Ts,Th,R,Ls]=[0.778 2,0.384 65,40.319 6,199.999 7],最優(yōu)值f(X)=5 885.334 5,CHMPFA比其它8種元啟發(fā)式算法的優(yōu)化效果出色,有較低的設(shè)計成本,在壓力容器設(shè)計問題中起到了良好的優(yōu)化效果。

表6 壓力容器設(shè)計問題最優(yōu)方案

5 結(jié)束語

為提升標準PFA的收斂速度和尋優(yōu)精度,提出了一種嵌入Cat映射的混合變異探路者算法(CHMPFA)。通過仿真實驗與其它8種具有代表性的智能優(yōu)化算法進行性能對比,驗證CHMPFA多種策略的有效性,并將CHMPFA應用于壓力容器問題中,其良好的優(yōu)化效果和穩(wěn)定性表明了CHMPFA的魯棒性。未來考慮應用CHMPFA解決多目標優(yōu)化問題或更為復雜的實際問題。