一種改進的變權科莫多優化算法及其應用

梁少華，李林軒，葉青

長江大學計算機科學學院，湖北 荊州 434023

自然一直是許多元啟發式算法的靈感來源，如進化論中的自然選擇是遺傳算法[1](genetic algorithm,GA)靈感來源，鳥群覓食過程是粒子群算法[2](particle swarm optimization,PSO)靈感來源等。智能算法已經成功地解決各個領域的問題，包括旅行商問題[3]、最優控制理論[4]、醫學圖像處理技術[5]等。為解決更加棘手的問題，相關學者相繼提出鷹棲息算法[6](eagle perching optimization,EPO)、灰狼算法[7](grey wolf optimization,GWO)、科莫多算法[8](komodo mlipir mlgorithm,KMA)以及各種改進算法和方法，如加入PSO的混合鷹棲息算法[9]、混沌理論[10]、萊維(Levy)飛行[11-12]和動態權值[13]等方法應用于智能算法中。

KMA是2022年1月由SUYANTO等提出的新穎的元啟發優化算法，該算法有著遺傳算法和粒子群優化算法的諸多優點，可以通過不同階級個體的運動和繁殖尋找最優值，還提出通過種群自適應[14]來控制局部和全局尋優的平衡，使得KMA收斂速度較快和精度較高，并且在高維函數中具有延展性。但是KMA在復雜函數中仍存在局部收斂的問題。

為了進一步提高KMA的性能，改進KMA在收斂過程中存在的問題，筆者提出了一種改進的變權科莫多優化算法(VWCKMA)。主要創新和意義如下：①引入可變慣性權重因子[15]，將科莫多巨蜥的社會階級都賦予一個隨著迭代次數而改變的慣性權重，提升了種群的收斂速度和全局探索的能力；②引入了Tent混沌映射[16]初始化科莫多種群，提高初始化種群位置的質量，豐富了種群的多樣性，提高了收斂速度；③利用Tent混沌映射[17]有效調節種群的多樣性，幫助算法動態跳出局部最優，提高了收斂精度。

1 科莫多算法

在KMA中，隨機生成科莫多種群，根據適應度劃分種群為3種不同的社會階級。通過3種階級的不同運動，完成最后尋優的過程。其中大型雄性的運動行為用數學模型描述如下：

(1)

(2)

小型雄性的運動通過特定的概率隨機選擇一部分去靠近大型雄性，用數學模型描述如下：

(3)

(4)

2 改進科莫多算法以及算法流程

2.1 Tent混沌映射初始化粒子位置

目前大多數算法采用隨機初始化粒子的方式來表示，但是這容易造成個體集中在某一區域，分布不均衡?；煦缧蛄芯哂袃仍陔S機性和空間遍歷性，能夠在一定的空間范圍內不重復的無規律遍歷，能有效地避免局部最優解，實現全局優化。李兵等[18]將混沌理論應用于群智能算法的優化中，發現其優化效率高于一般隨機算法。

Tent混沌映射具有簡單的結構，同時迭代過程更加適合計算機的運行，并且Tent混沌映射的遍歷性更加均勻。單梁等[16]表明了Tent混沌映射的遍歷性要比logistic混沌映射[19]更好，因此，采用Tent混沌映射對種群進行初始化，式(5)是Tent混沌映射，其數學表達式為：

(5)

2.2 新增慣性權重策略及雌性運動

為了避免KMA在搜索過程中陷入局部最優值，在KMA中引入了一種新的參數稱為慣性權重，用于控制全局探索和局部搜索。對于大型雄性、雌性、小型雄性的運動分別引入不同的慣性權重w1、w2、w3，所有的權重都應該是變化的，并且相加時和為1。即：

w1+w2+w3=1

(6)

圖1 可變權值的迭代圖Fig.1 Iterative graph of time-varying weights

(7)

(8)

基于以上這些假設和因素，提出了一種新的可變慣性權重更新方法，定義為：

w1=cosθ

w3=1-w1-w2

(9)

可變慣性權重曲線如圖1所示。

將大型雄性運動的數學表達式(1)改進為：

(10)

KMA中雌性只存在有性繁殖或者無性繁殖的行為，根據自然界正常生理活動，新增雌性向大型雄性移動的新運動，其運動的數學表達式為：

(11)

最后，同樣對小型雄性的運動增加慣性權重w3，即對式(3)進行改進。則其數學表達式為：

(12)

2.3 新增Tent混沌映射擾動策略

在完成科莫多3種階級運動后，進行混沌擾動實現局部搜索。使用Tent混沌映射進行擾動，在科莫多個體周圍產生一些局部解，然后再與之前的最優解進行比較。具體的Tent混沌映射擾動步驟如下：

2.4 VWCKMA整體流程

VWCKMA的具體算法流程如圖2所示。

步驟1 初始化參數，初始化種群和維度大小，最小和最大的自適應種群規模的大小，最大迭代次數，最大混沌次數，大型雄性的個數；

步驟2 初始化種群，利用Tent混沌映射初始化科莫多個體群的位置；

步驟3 計算科莫多個體的適應度值，利用式(6)～式(9)計算不同社會階級科莫多的慣性權值；

步驟4 更新位置，根據式(2)和式(10)更新大型雄性的位置，式(11)更新雌性的位置，式(4)和式(12)更新小型雄性的位置；

步驟5 使用式(5)進行Tent混沌映射擾動，進行局部搜索。

步驟6 判斷是否得到最優解或達到最大的迭代次數，如果是算法搜索結束執行步驟7；否則返回到步驟3；

步驟7 輸出最優值信息。

圖2 VWCKMA的執行框架Fig.2 Implementation framework of VWCKMA

2.5 改進算法復雜度分析

KMA的時間復雜度為O(n×m×Max_iteration+f(n)+α1)(其中n，m，f(n)，α1和Max_iteration分別代表種群中個體的數量，維度，目標函數計算時間，適應度值排序過程的時間和最大迭代次數)VWCKMA時間復雜度分析如下：

1)Tent混沌映射初始化種群的時間復雜化為O(n×m)，則引入Tent混沌映射初始化種群的算法時間復雜度為O(n×m×Max_iteration+f(n)+α1+n×m)=O(n×m×Max_iteration+f(n)+α1)。 2)假設更新時變慣性權重的所需時間為t1，引入時變慣性權重后算法的時間復雜度為O(n×m×Max_iteration+f(n)+α1+t1)=O(n×m×Max_iteration+f(n)+α1)。

3)Tent混沌映射進行擾動的時間復雜度為O(n×m)，引用Tent混沌映射進行擾動的算法時間復雜度為O(n×m×Max_iteration+f(n)+α1+n×m)=O(n×m×Max_iteration+f(n)+α1)。

VWCKMA空間復雜度分析如下：加入Tent混沌映射初始化種群和慣性權重的優化策略均在KMA基礎上改進，未新增存儲空間。加入Tent混沌映射擾動策略后新增的空間復雜度為O(logk)(其中k為最大混沌次數)。與KMA相比略微增加了O(logk)，但是在現有計算機硬件水平中O(1)≈O(logk)。

綜上所述，相比KMA，筆者提出的VWCKMA沒有增加復雜度。

3 仿真實驗及分析

3.1 測試函數集

為了綜合檢驗VWCKMA具有效性和優越性，將VWCKMA同時與KMA，GWO算法和PSO算法對8個基準函數進行求解，單峰函數f1(x)～f3(x)，多峰函數f4(x)～f8(x)，函數信息如表1所示。

表1 基準函數

3.2 實驗數據及分析

參數設置相同，VWCKMA與KMA，GWO和PSO算法的迭代次數為200次，最大種群規模為200。在該條件下對30維度、100維度和500維度的8個基準函數獨立運行30次，進行尋優計算。計算出各個算法的均值和標準差(見表2)。其中最優者用黑體加下劃線標注。為了更加直觀地體現VWCKMA的優越性能，在30維度的測試函數中，繪制出部分測試基準函數的收斂曲線圖，如圖3所示。所涉代碼采用MATLAB R2020a軟件編寫，仿真實驗環境為：64位Windows操作系統，CPU型號為Intel Core i7-12700 F，機帶RAM為32 GB。

表2 4種算法在8個基準函數上的測試結果

圖3 基準函數的收斂曲線Fig.3 Convergence curve of benchmark functions

在同維度和迭代次數的情況下，表2的結果表明：VWCKMA在單峰函數f1(x)～f3(x)中能收斂到函數的理論最優值，其他算法都無法收斂到0。VWCKMA在多峰函數中，f4(x)～f6(x)函數均表現出收斂到函數理論最優值，在f7(x)和f8(x)函數中收斂精度最高。對比結果說明VWCKMA的精度高于KMA、GWO算法和PSO算法。對比500維度情況，f1(x)～f6(x)函數均收斂到函數理論最優值，f7(x)和f8(x)函數收斂精度仍最高，表明VWCKMA在高維情況下仍具有收斂的精準性。圖3表明：VWCKMA在f4(x)～f7(x)函數中平均迭代5次便能夠快速準確地收斂到最佳值，在f7(x)函數中KMA陷入局部最優值時VWCKMA能有效跳出局部最優值。無論從收斂精度還是速度上都遠遠高于PSO，GWO和KMA。說明該算法較其他3種元啟發算法具有收斂精度更高、速度更快的突出優勢。

綜上分析所得，VWCKMA與PSO、GWO和KMA比較，無論是在低維度還是高維度，無論在收斂精度還是收斂速度方面，無論是在單峰函數還是多峰函數情況下的尋優計算，VWCKMA都具有明顯的優勢。同時VWCKMA有較強的全局探索與局部搜索的能力和較快的收斂速度，且對于局部最優解有很強的抵抗性，能夠輕易地跳出局部最優解，找到函數的最優值。

4 應用

4.1 對象與方法

將VWCKMA應用在成都市空氣污染物PM2.5預測的實際問題中。通過MATLAB進行仿真實驗，選擇傳統的BP神經網絡[20]、粒子群優化神經網絡[21](PSO-BP)、科莫多優化神經網絡(KMA-BP)，以及改進科莫多優化神經網絡(VWCKMA-BP)4種模型分別對成都市空氣污染物PM2.5進行預測。為了公平性，4種預測模型的參數設定一致，參數設定如下：BP神經網絡的結構為5-10-5-1，輸入層到隱藏層之間的傳遞函數為Tansig函數，隱藏層到輸出層之間的傳遞函數為Poslin函數，學習率設置為0.4。樣本數據的選取來自于中國空氣質量在線監測分析平臺(https：//www.aqistudy.cn)，選取成都市2020年1月1日至2022年6月30日一共912條數據進行實驗。具體數據包括日期、AQI、質量等級、PM2.5、PM10、CO、NO2、SO2、O3。數據簡況見表3，由于篇幅有限列舉一部分數據。

評價指標在選取PM2.5的實際值和真實值的比較基礎上，再引入了平均相對誤差(EMR)，平均相對誤差均方誤差EMS，平均絕對誤差EMA，均方根誤差ERMS和預測準確率Pacc進行全方位的比較預測精度。預測模型都采用均方誤差函數作為算法的適應度函數，5個指標的數學定義分為：

(16)

(17)

(18)

(19)

(20)

表3 原始數據樣本

4.2 結果分析

在2020年1月1日至2022年6月30日的912條數據中選擇70%為訓練集，30%為測試集。4種預測模型的預測值與真實值的對比結果如圖4所示。VWCKMA-BP模型的預測值與真實值的比較結果如圖5所示。從圖5可清晰看出，VWCKMA-BP模型更加接近真實值，通過VWCKMA使得尋優精度得到有效提升。

圖4 PM2.5的預測值和真實值對比圖5 VWCKMA-BP的預測值和真實值對比Fig.4 Comparison of predicted and true Fig.5 Comparison of predicted and true values PM2.5 values of VWCKMA-BP

表4為4種預測模型在測試集上的EMR、EMS、EMA、ERMS和Pacc這5個指標的統計結果。從表4中可以看出不同優化策略對BP神經網絡的預測有較大的影響，VWCKMA-BP模型準確率達到85.085%。4種模型只有VWCKMA-BP模型使得平均絕對誤差低于6 μg/m3，均方根誤差低于60 μg/m3，均方誤差低于15%。改進算法在迭代次數上也有進一步的提升，KMA、PSO和VWCKMA的對比收斂曲線如圖6所示，VWCKMA的初始適應度值均優于其他兩種算法，這是Tent混沌映射初始化種群的結果。在迭代30次左右時，VWCKMA的函數適應度接近收斂值，其他算法適應度值均大于VWCKMA。以上結果表明VWCKMA-BP模型在預測空氣污染物PM2.5指標上有效可行。

表4 不同模型的指標統計結果對比

圖6 不同算法迭代收斂曲線對比Fig.6 Comparison of iterative convergence curves of different algorithms

5 結論

1)為進一步提高KMA性能，改進KMA在收斂過程中存在的問題，筆者提出根據隨迭代次數變化的慣性權值策略，提高收斂速度；利用Tent混沌映射初始化種群，保證種群多樣性，提高收斂速度；針對KMA易陷入局部最優解的問題，采用Tent混沌映射能夠有效跳出局部最優解，更加精確地對最優解進行搜索。

2)在仿真實驗中，將VWCKMA與PSO、GWO、KMA進行比較，選擇了8個不同性質的基準函數進行函數優化的實驗。實驗表明VWCKMA在函數尋優的收斂精度與速度方面具有突出優勢。

3)在實際應用中，使用VWCKMA-BP、PSO-BP、KMA-BP和BP神經網絡進行空氣污染物PM2.5的實際預測，實驗表明VWCKMA-BP模型預測準確率在4種模型中最高，達到85.085%，相比BP神經網絡預測準確率提高19.85個百分點。說明VWCKMA在函數優化以及實際優化問題方面的性能得到了顯著提高。后續可將VWCKMA嘗試應用于多目標優化解析中。