嵌入Cat映射的混合變異探路者算法及其應用

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

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

0 引 言

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

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

1 標準探路者算法

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

探路者算法中的位置向量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為種群規模,d為空間維度;在種群迭代過程中,選出適應度值最優的個體作為探路者,跟隨者均向它移動,更新方式為式2:

(2)

(3)

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

(4)

(5)

Dij=‖xi-xj‖

(6)

R1=αr2

(7)

R2=βr3

(8)

2 算法改進

2.1 混沌反向學習初始化種群

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

(9)

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

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

(10)

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

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

(11)

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

(12)

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

2.3 混合變異策略

(1)柯西變異。

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

(13)

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

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

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

(14)

(2)高斯變異。

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

(15)

(16)

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

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

(3)混合變異。

在PFA中引入柯西變異和高斯變異可以使得算法更加全面地探索解空間,從而有更大的可能找到最優解。柯西變異可以增加算法的全局搜索能力,因為它具有長尾分布,可以探索到遠離當前搜索點的區域;而高斯變異則可以增加算法的局部搜索能力,因為它可以更加精準地探索周圍區域,從而更容易找到局部最優解。所以,該文根據變異概率p將柯西變異和高斯變異融合為混合變異策略引入PFA當中,如公式17所示:

(17)

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

(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 時間復雜度分析

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

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

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

O(d+f(d))

進入迭代期,在探路者階段,探路者數目為1,假設計算自適應權重w的時間為t3,生成隨機數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))

在變異階段,最優個體進行柯西變異或高斯變異的時間為t12,計算最優個體適應度值的時間為f(d),利用貪婪策略判斷新最優個體是否代替舊最優個體的時間為t13,保留最優個體位置的時間為t14,對最優個體的每一維邊界處理的時間為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一致,執行效率并未下降。

3 實驗仿真與結果分析

3.1 實驗設計

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

表1 基準測試函數

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

表2 各算法實驗參數

3.2 尋優性能對比分析

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

表3 基準測試函數尋優結果對比

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

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

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

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

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

(19)

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

3.3 收斂曲線分析

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

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

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

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

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

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

3.4 CEC2017基準測試函數求解實驗

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

表4 CEC2017基準測試函數

表5 CEC2017基準測試函數尋優結果對比

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

4 壓力容器設計問題

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

(20)

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

表6 壓力容器設計問題最優方案

5 結束語

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