支持向量機輔助演化的算術優(yōu)化算法及其應用

田 露，劉 升

上海工程技術大學 管理學院，上海 201620

近年來，啟發(fā)式算法在工程優(yōu)化問題中越來越受歡迎，由于它們具有易于實現(xiàn)、無需梯度信息、躲避局部最優(yōu)等優(yōu)勢，可以很好地滿足不同領域實際問題的需求[1]。目前啟發(fā)式算法已被應用于參數(shù)優(yōu)化、特征優(yōu)化、集成約簡、原型優(yōu)化、加權投票集成以及核函數(shù)學習等機器學習領域[2-3]。

Abualigah等人于2021年受數(shù)學計算方法中算術運算符啟發(fā)提出了算術優(yōu)化算法（arithmetic optimization algorithm，AOA）[4]。該算法利用運算符的分布特性從候選解中尋找最優(yōu)解，由于其具有較好的尋優(yōu)性能，目前已被應用到一些問題中，如文獻[5]使用差分進化算法增強AOA的局部開發(fā)能力，并應用于多閾值分割問題中；文獻[6]使用高斯變異和正弦混沌策略改進AOA，以提升質子交換膜燃料電池模型識別的準確性；文獻[7]使用擁擠距離機制和精英非優(yōu)勢排序策略改進AOA，并用于求解多目標優(yōu)化問題；文獻[8]將SMA和AOA結合并利用隨機反向學習策略提高收斂速度，提出了隨機反向學習策略的黏菌與算術混合優(yōu)化算法；文獻[9]將灰狼信息反饋機制與反向學習引入AOA，并對非線性收斂系數(shù)MOP建立修正模型，提出了具有激活機制的多頭反向串聯(lián)算術優(yōu)化算法。

上述改進雖然提高了算法的尋優(yōu)性能，但由于進化過程中種群規(guī)模始終不變，改進策略僅在有限的種群數(shù)量內(nèi)增加了種群多樣性。為了進一步提高算法性能，本文從增加演化過程中種群數(shù)量的角度對AOA進行改進。AOA算法的子代生成方式為僅向當前全局最優(yōu)解靠近，該策略使種群中其他個體攜帶的信息沒有得到充分利用，種群多樣性也較差，算法極易陷入局部最優(yōu)解。因此本文引入平衡優(yōu)化器算法中的平衡池概念，充分利用種群中個體包含的信息，通過四種突變策略及其平均候選解，增加種群的多樣性。但考慮到隨著平衡池中個體數(shù)量的增加，個體評價次數(shù)也隨之增加，同時平衡池中較差個體所攜帶的信息也會對算法演化產(chǎn)生不利影響。因此，本文使用支持向量機對平衡池中的個體進行分類，首先對適應度值和距離進行歸一化處理，并將二者轉化為個體留存率，用該指標將個體劃分為優(yōu)勢個體和劣勢個體；然后將其轉化為訓練集用以訓練支持向量機模型；最后用訓練好的模型從平衡池中選出優(yōu)勢個體，保留前N個個體用于構建下一代平衡池。通過將SVMAOA與其他算法在基準測試函數(shù)與特征選擇問題上驗證表明SVMAOA具有較優(yōu)的性能。

1 算術優(yōu)化算法

算術優(yōu)化算法根據(jù)運算符不同的分布特性，在搜索空間內(nèi)中尋找最優(yōu)解。由于除法運算符（D）和乘法運算符（M）具有發(fā)散的性質，搜索過程中步長較長，可以保證在搜索前期對搜索區(qū)域充分探索，避免陷入局部最優(yōu)解。而減法運算符（S）和加法運算符（A）具有收斂的性質，搜索過程中步長短，可以保證在搜索后期對在幾個密集區(qū)域上對搜索區(qū)域進行深入探索搜索區(qū)域充分開發(fā)，增強局部尋優(yōu)能力。

1.1 數(shù)學優(yōu)化加速函數(shù)

在算法開始尋優(yōu)前，需要選擇搜索階段。設定隨機參數(shù)r1∈[0,1]與數(shù)學優(yōu)化加速函數(shù)（math optimizer accelerated，MOA）用于選擇搜索階段（即探索或開發(fā)）。當r1

其中，C_Iter為當前迭代次數(shù)，M_Iter為最大迭代次數(shù)。Min=0.2表示加速函數(shù)的最小值，Max=0.7表示加速函數(shù)的最大值。

1.2 探索階段

AOA在全局探索階段基于除法搜索策略和乘法搜索策略搜索，位置更新公式如下：

其中，r2∈[0,1]，當r2<0.5時，采用除法策略，否則采用乘法策略。μ為搜索過程控制參數(shù)，用以調節(jié)搜索過程，值為0.499。

為探索解空間的不同區(qū)域，保證解的多樣化，更新公式中考慮了一個隨機參數(shù)，即數(shù)學優(yōu)化概率（math optimizer probability，MOP），MOP計算公式如下：

其中，α為敏感參數(shù)，定義了迭代過程中的開發(fā)精度，值為5。

1.3 開發(fā)階段

AOA在局部開發(fā)階段基于加法搜索策略和減法搜索策略進行搜索。位置更新公式如下：

其中，r3∈[0,1]，當r3<0.5時，采用減法策略，否則采用加法策略。

2 支持向量機

支持向量機（support vector machine，SVM）是機器學習領域中經(jīng)典的分類算法之一，由Cortes等人于1995年提出[10]。SVM的核心思想是尋找一個保證分類精度的同時，使分類間隔最大化的最優(yōu)分類超平面。算數(shù)優(yōu)化算法在尋優(yōu)過程中，用于將個體劃分為優(yōu)勢個體和劣勢個體，因此可以將其視作一個二分類問題。其中，種群中所有個體xi(i=1,2,…,N)為樣本集，N為種群中個體數(shù)量，個體的優(yōu)劣為yi={ }

1,-1。

3 支持向量機改進的算術優(yōu)化算法

3.1 構建平衡池

AOA的個體更新方式為向當前全局最優(yōu)個體收斂，這種更新策略雖然能夠達到快速收斂的效果，但當前全局最優(yōu)個體若為局部最優(yōu)解而非真正的全局最優(yōu)解時，該策略極易導致算法陷入局部最優(yōu)。同時，AOA算法沒有充分利用除當前全局最優(yōu)個體以外的其他個體，忽略了種群其他個體所包含的信息，導致種群多樣性和全局搜索能力較差。

因此，本文引入平衡優(yōu)化器算法中平衡池的概念，池中除原始AOA算法子代生成方式外，還引入了基于成功歷史的自適應差分算法（success-history based adaptive DE，SHADE）的四種突變策略（DE/rand/1、DE/best/1、DE/rand/2和DE/best/2）生成的個體，以及以上個體的平均候選解，并根據(jù)演化階段自適應地選擇策略。

在探索階段，增加的兩種子代位置生成公式和平均候選解公式如下：

在開發(fā)階段，增加兩種子代位置生成公式平均候選解公式如下：

其中，xri,t為第t代種群中除當前全局最優(yōu)個體外隨機選擇的第i個個體，xpbest,t是從當前種群中隨機選擇適應度值排名在前100p%中的個體。

MOP為服從柯西分布的隨機數(shù)，其中μMOP初始值為0.5，1/c∈[5,20]。

公式中的MOP參數(shù)隨迭代次數(shù)的增加自適應地調整搜索步長。以上操作既保證了算法的收斂性，又避免僅向當前全局最優(yōu)個體收斂，保持了種群多樣性。本文使用測試函數(shù)對改進的SVMAOA算法與原始AOA算法的求解精度和收斂速度進行對比，以驗證構建平衡池策略的有效性。

3.2 支持向量機分類策略

針對AOA算法種群多樣性較差的特點，上文提出了構建平衡池策略以增加種群多樣性。由于僅參考適應度值可能導致種群多樣性的喪失，不能充分利用和探索未知的搜索空間，因此本文綜合考慮適應度值和個體間距離，并將其轉化為個體留存概率。同時當個體數(shù)量增加時，若對所有個體都進行適應度值評價，運行時間不可避免地會增加，因此本文使用支持向量機依據(jù)個體留存概率對平衡池中所有個體進行分類，在進化過程中保留優(yōu)勢個體，丟棄劣勢個體。

分類問題中的數(shù)據(jù)集以(X,D)的形式存在，本文中子代個體為D為留存標志。將子代個體按留存率進行降序排列，并使用n%的比例對數(shù)據(jù)集進行劃分，對前100p%的個體標記為1，代表保留，對剩余個體標記-1，代表丟棄。留存率由適應度值與個體間距離共同決定，為使適應度值與個體間距離處于同一數(shù)量級，對二者進行歸一化處理，計算公式如下：

其中，ymax和ymin分別為最大和最小適應度函數(shù)值，Dmax和Dmin分別為Di的最大和最小值，ε為一個極小值以避免出現(xiàn)零除法。

使用支持向量機輔助進化策略步驟如下：

步驟1計算種群中每個個體的留存率；

步驟2根據(jù)留存率轉換為訓練數(shù)據(jù)集；

步驟3利用數(shù)據(jù)集訓練分類器；

步驟4使用上一代保留的個體構建平衡池；

步驟5用分類器對個體分類，保留優(yōu)勢個體；

步驟6根據(jù)適應度值對優(yōu)勢個體排名，選擇前N個個體作為下一代種群。

使用支持向量機輔助進化的算術優(yōu)化算法（SVMAOA）偽代碼如下：

開始

初始化主要參數(shù)設置初始化種群

計算種群中每個個體的留存率

根據(jù)留存率將其轉換為訓練數(shù)據(jù)集

利用數(shù)據(jù)集訓練分類器

while t

根據(jù)式（1）更新MOA

if r1

使用式（2）、（5）、（6）、（7）生成子代個體及其平均候選解放入平衡池

Else

使用式（4）、（8）、（9）、（10）生成子代個體及其平均候選解放入平衡池

end if

通過分類器對平衡池中個體進行分類，保留優(yōu)勢個體

對優(yōu)勢個體進行排序，保留前N個個體

t=t+1；

end while

返回最佳位置

結束

SVMAOA具體實現(xiàn)流程如圖1所示。

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

3.3 時間復雜度

SVMAOA的計算復雜度分為以下幾部分：初始化過程、訓練分類器、構建平衡池解、對平衡池內(nèi)所有個體進行分類以及排序。設算法的種群規(guī)模為N，問題維度為D，最大迭代次數(shù)為T，則算法的時間復雜度如下。

初始化階段的復雜度為O(N×D)，計算個體留存率為O(N)；訓練分類器的時間復雜度為O(N lg N)；構建平衡池的時間復雜度為O(N×D×3)；使用分類器對平衡池內(nèi)所有個體進行分類的時間復雜度為O(N×D×3)；設優(yōu)勢個體的比例為α，則計算優(yōu)勢個體留存率的時間復雜度為O(3×N×α)，對優(yōu)勢個體排序的時間復雜度為O((N+3×α)lg(N+3×α))。

綜上所述，SVMAOA的時間復雜度為O(T(3ND+(N+3Nα)lg(N+3Nα))。

3.4 收斂性分析

定理1 SVMAOA在演化中全局最優(yōu)適應度值是單調非增的，即f(Xg,t)≤f(Xg,1)。

證明 根據(jù)算法的選擇策略，只有個體的適應度值小于全局最優(yōu)值時，才對全局最優(yōu)值進行更新，因此滿足下式：

其中，Xg,t為第t代時全局最優(yōu)個體的位置，因此全局最優(yōu)解的適應度值單調不增，證明完畢。

定理2算法的狀態(tài)空間內(nèi)的隨機過程是馬爾科夫鏈。

證明 將狀態(tài)空間從{X(t)}轉移到{X (t+1)}的過程記為X(t+1)=T(X(t))，SVMAOA算法可以將此過程表示為：

其中，Ta代表初始化過程，Tb代表構建平衡池過程，Tc代表選擇優(yōu)勢個體過程?？梢钥闯觯琗(t+1)只與X(t)有關，且三個過程均依賴于X(t)而不是t，算法的狀態(tài)空間內(nèi)的隨機過程是馬爾科夫鏈，證明完畢。

定理3算法的狀態(tài)空間{}X(t)收斂到全局最優(yōu)子集M*的概率為1。

證明SVMAOA算法從{X(t)}轉移到{X (t+1)}的狀態(tài)轉移概率為：

計算可得：

令

上式可表示為：

變換可得：

對兩邊求極限：

上述三個定理說明算法的狀態(tài)空間是單調不增的馬爾科夫鏈，且收斂于最優(yōu)集的概率為1，由此可得算法具有全局收斂性。

4 實驗仿真與結果分析

4.1 仿真實驗環(huán)境

本仿真測試環(huán)境為：仿真軟件為MATLAB 2018b，操作系統(tǒng)Windows 10，內(nèi)存為16.0 GB，CPU為AMD Ryzen 5 4600U，主頻2.10 GHz。

4.2 測試函數(shù)

為了選取合適的數(shù)據(jù)集劃分比例以及驗證SVMAOA的優(yōu)化效果和穩(wěn)定性優(yōu)于其他算法，本文對多個不同特點的測試函數(shù)進行函數(shù)優(yōu)化的對比測試，測試函數(shù)及其具體信息如表1所示。

表1 測試函數(shù)Table 1 Test function

4.3 參數(shù)選擇

由于數(shù)據(jù)集中優(yōu)勢個體與劣勢個體比例的劃分也對分類器的性能有顯著影響，優(yōu)秀樣本過多會導致一些劣勢個體無法區(qū)分，優(yōu)秀樣本太少會導致一些優(yōu)勢個體分類錯誤。本文分別對適應度值排名前20%、40%、60%和80%的優(yōu)勢個體打標簽+1，對剩余劣勢個體打標簽-1，以用來確定對算法尋優(yōu)性能最佳的數(shù)據(jù)集劃分策略，上述劃分策略分別用F20、F40、F60和F80表示，見圖2。

圖2 訓練集轉換策略示意圖Fig.2 Schematic diagram of training set conversion strategy

通過基準測試函數(shù)對上述策略進行實驗測試，種群規(guī)模設定為30，維數(shù)設定為30，最大迭代次數(shù)設定為500。

從表2可以看出，F(xiàn)40策略的SVMAOA可以使較多測試函數(shù)的尋優(yōu)精度達到最優(yōu)，同時具有一定穩(wěn)定性，整體表現(xiàn)最好。在接下來的實驗中，選擇F40的訓練集劃分策略。

表2 四種策略實驗結果Table 2 Experimental results of four strategies

4.4 對比算法與參數(shù)設置

本文將改進算法（SVMAOA）與原始算法（AOA）、其他學者改進的改進算法（DAOA、MOAOA、MFAOA[11]、IAOA[12]）以及其他算法（SSA[13]）進行比較。種群規(guī)模設定為30，維數(shù)設定為30，最大迭代次數(shù)設定為500，各算法的參數(shù)設置見表3。

表3 對比算法參數(shù)Table 3 Compare algorithm parameters

4.5 種群多樣性分析

本文使用Booth函數(shù)對AOA與SVMAOA迭代典型時刻的種群分布圖進行對比，以驗證構建平衡池的策略可以有效提升種群。Booth函數(shù)基本信息如表1所示，兩種算法在第5、50和100次迭代時刻的種群分布如圖3所示。

圖3中，迭代初期時AOA種群中有部分個體重疊，種群多樣性較差，且種群分布范圍較?。欢鳶VMAOA中種群分布更均勻，搜索空間更大，種群多樣性更佳。當?shù)?0次時，AOA中子代的分布以最優(yōu)解的橫縱坐標為參考，呈現(xiàn)十字形，而SVMAOA在平衡池三種子代生成策略的作用下，使子代生成過程不再僅以最優(yōu)解為參照，此使種群以環(huán)狀的分布圍繞在最優(yōu)解附近，明顯改善了AOA種群分布圖中的十字分布。當?shù)?00次時，AOA個體在原始的子代生成策略作用下，仍保持十字分布的狀態(tài)，有很大一部分個體沒有搜尋到最優(yōu)個體。而SVMAOA中的大部分個體已經(jīng)搜尋到（1，3）點，這是由于支持向量機分類器輔助演化過程，減少了評價次數(shù)，加快了種群的收斂速度。

圖3 種群多樣性對比圖Fig.3 Comparative map of population diversity

4.6 求解精度與收斂性分析

本文通過23個基準測試函數(shù)對算法性能進行對比實驗，為了避免偶然性帶來的結果偏差，算法在每個基準測試函數(shù)上運行30次并對其求均值和標準差，以對比算法的求解精度與穩(wěn)定性，實驗結果見表4。

表4 測試函數(shù)實驗結果Table 4 Experimental results of test function

F1~F7為單峰函數(shù)，一般用于檢測算法的全局尋優(yōu)性能。SVMAOA與原始AOA算法和SSA算法相比較，平均尋優(yōu)精度和標準差均有很大的提升，SVMAOA具有最佳的尋優(yōu)性能。與改進算法相比較，除在F5函數(shù)上SVMAOA的平均尋優(yōu)精度和標準差略差于DAOA算法以外，在其他測試函數(shù)中平均尋優(yōu)精度和標準差都表現(xiàn)最優(yōu)，SVMAOA算法相比于其他基于AOA的改進算法尋優(yōu)性能最佳?？傮w看來，SVMAOA在單峰測試函數(shù)中表現(xiàn)出較優(yōu)的尋優(yōu)性能。

F8~F23為多峰函數(shù)，一般用來評價算法的局部尋優(yōu)性能。SVMAOA與原始AOA算法相比較時，在F18函數(shù)上，兩種算法尋優(yōu)精度一樣，但是SVMAOA算法的標準差較小，穩(wěn)定性較高，在其他多峰測試函數(shù)中SVMAOA的最優(yōu)解平均尋優(yōu)精度和標準差均有很大的提升。與SSA相比較時，在F8函數(shù)上，SVMAOA算法平均尋優(yōu)精度雖略差于SSA算法，但標準差卻較小，算法在該函數(shù)上表現(xiàn)較穩(wěn)定。在F13函數(shù)上，SVMAOA的平均尋優(yōu)精度和標準差略差于SSA算法。在F14函數(shù)上，雖然SVMAOA相較于SSA平均尋優(yōu)精度雖略低，但標準差卻遠小，改進算法的魯棒性與其相比具有優(yōu)勢。在F14、F15函數(shù)上，SVMAOA的平均尋優(yōu)精度優(yōu)于SSA，但標準差卻略高。在其他多峰測試函數(shù)上，SVMAOA的平均尋優(yōu)精度和標準差都表現(xiàn)最佳。與其他改進算法相比較時，在F8函數(shù)上，DAOA的平均尋優(yōu)精度略優(yōu)于SVMAOA。在F13、F20函數(shù)上，DAOA的平均尋優(yōu)精度略和標準差均優(yōu)于SVMAOA。在F14函數(shù)上，MOAOA的平均尋優(yōu)精度略優(yōu)于SVMAOA。在F16、F17、F18函數(shù)上，SVMAOA相較于IAOA的平均尋優(yōu)精度較高，但標準差卻略差。在其他多峰測試函數(shù)中，SVMAOA相較于其他基于AOA改進的算法均表現(xiàn)出最佳的尋優(yōu)精度和穩(wěn)定性?？傮w看來，在多峰測試函數(shù)中，SVMAOA具有一定的競爭力。

以上實驗結果說明平衡池策略有效地增加了提升了算法的全局尋優(yōu)性能和局部尋優(yōu)性能，為了進一步說明使用支持向量機分類策略可以有效地篩選優(yōu)勢個體，避免劣勢個體對演化過程產(chǎn)生干擾，提升收斂速度，本文通過測試函數(shù)的迭代收斂曲線圖驗證SVMAOA算法的收斂速度。從圖4可以看出，SVMAOA在收斂速度上也優(yōu)于其他算法。

圖4 收斂曲線圖Fig.4 Convergence curve

4.7 Wilcoxon秩和檢驗

為檢驗SVMAOA算法與其他算法的顯著性差異，本文使用Wilcoxon秩和檢驗進行驗證。在α=5%顯著性水平下，若p<0.05則說明算法具有顯著差異，反之則說明算法差異不顯著。本文將SVMAOA與AOA、SSA、IAOA、MFAOA、DAOA、MOAOA在23個基準測試函數(shù)上進行30次運算，結果見表5。其中，N/A表示算法結果接近，無法進行顯著性判斷。在23個基準測試函數(shù)中，多數(shù)實驗結果均小于0.05，說明SVMAOA的優(yōu)越性在統(tǒng)計上是顯著的。對于函數(shù)F9、F10和F11，SVMAOA與其他算法間的差異不明顯，說明算法性能相當。

表5 Wilcoxon秩和檢驗結果Table 5 Wilcoxon rank sum test results

5 SVMAOA用于特征選擇問題

特征選擇作為特征工程的關鍵環(huán)節(jié)，不僅可以剔除無關特征、提高算法的學習效率[14]，還能從數(shù)據(jù)集中尋找最優(yōu)特征子集[15]，提高模型精確度。本文將選取盡可能少的特征得到較高的分類準確率作為目標，利用SVMAOA算法解決特征選擇問題。

5.1 建立模型

SVMAOA用于求解特征選擇問題時，個體代表一組特征子集，種群維度為數(shù)據(jù)集中特征數(shù)。由于特征選擇可以視作離散空間中的優(yōu)化問題，故本文基于二進制編碼方法，使用Sigmoid函數(shù)將個體向量轉化至0到1的區(qū)間內(nèi)，見式（24）。當值大于0.5時，將其置為1，反之置為0，0和1分別表示對應維度的特征沒有被選擇和被選擇。

v為了通過盡可能少的特征得到較高的分類準確率，本文將以式（25）作為適應度函數(shù)[17]：

其中，α和β為分類準確率和特征子集長度的控制權重，α∈[0,1]，β=1-β，本文α取0.85。γDR(D)為KNN（KNearest Neighbors）分類器錯誤率，k=5。||R為個體中被選擇的特征數(shù)，||N為數(shù)據(jù)集中特征數(shù)。

為評價SVMAOA用于求解特征選擇問題的優(yōu)劣，本文選取分類準確率與特征選擇個數(shù)作為衡量指標，分

類準確率定義見式（26）：

其中，TP為真正例樣本數(shù)，TN為真負例樣本數(shù)，P為正例樣本數(shù)，N為

5.2 實驗結果

為驗證算法在特征選擇問題中的性能，本文選用UCI中的7個數(shù)據(jù)集上進行測試，數(shù)據(jù)集信息見表6。

表6 實驗數(shù)據(jù)集Table 6 Experimental datasets

本文將SVMAOA并與原始AOA算法、其他學者改進算法以及其他群智能優(yōu)化算法進行對比，所有算法獨立運行10次，種群規(guī)模為30，最大迭代次數(shù)為100次，各算法參數(shù)設置見表3，實驗結果見表7。

表7 特征選擇實驗結果Table 7 Experimental results of feature selection

根據(jù)實驗結果可以看出，本文改進的SVMAOA算法用于求解特征選擇問題時，在所有數(shù)據(jù)集上的分類準確率均高于原始AOA算法和其他學者改進的算法。在D1、D3、D5、D6和D7數(shù)據(jù)集上數(shù)據(jù)集特征子集個數(shù)少于其他算法，在D2和D4數(shù)據(jù)集上略多于MFAOA算法?？傮w看來，在特征選擇問題中，本文提出的SVMAOA算法與其他算法相比表現(xiàn)出色，能夠有效地剔除無關特征，尋找到最優(yōu)特征子集，提高模型精確度。

6 結束語

為了克服AOA無法充分利用個體信息、種群多樣性較少等問題，構建了包含四種突變策略及其平均候選解的平衡池，充分利用種群個體所攜帶的信息，增加種群多樣性；并且通過支持向量機分類模型對平衡池中個體進行分類，以減少由于個體數(shù)量增多導致的評價次數(shù)增加，同時避免劣勢個體在演化過程中對算法造成的不良影響，逃離局部最優(yōu)解，使得算法獲得更好的收斂精度；最后根據(jù)留存率篩選個體，并用于下一代平衡池的構建。本文通過基準測試函數(shù)、統(tǒng)計檢驗Wilcoxon秩和檢驗和多樣性分析驗證算法性能，將SVMAOA與其他改進優(yōu)化算法、原始優(yōu)化算法進行對比，并在7個UCI標準數(shù)據(jù)集中進行特征選擇實驗，結果表明SVMAOA算法具有更優(yōu)的性能。

在未來的工作中，可以嘗試不同的平衡池更新策略。此外，還可以嘗試使用不同的分類器，以及不同的數(shù)據(jù)集劃分方式以增強算法性能。