劉紫燕梁水波袁 浩孫昊堃梁 靜

(貴州大學大數據與信息工程學院，貴州 貴陽 50025)

近年來，元啟發(fā)式算法由于其簡單性、靈活性和較高的魯棒性，已經被廣泛應用于解決越來越多的工程問題。一般來說，元啟發(fā)式算法模擬自然現象建立數學模型，元啟發(fā)式算法主要包括進化算法、群體智能算法和物理現象算法。

基于進化的算法受達爾文進化論的啟發(fā)，保留了種群中最好的個體作為后代來執(zhí)行相關操作。基于進化的算法主要包括遺傳算法(GA)[1]、進化策略(ES)[2]、差分進化策略(DE)[3]。基于群體智能的算法模擬生物群體中的智能行為來建立數學模型，如覓食方式、遷徙路線、交配選擇和信息共享機制等。此類算法主要包括粒子群算法(PSO)[4]、灰狼優(yōu)化算法(GWO)[5]、蟻獅優(yōu)化算法(ALO)[6]、鯨魚優(yōu)化算法(WOA)[7]、麻雀搜索算法(SSA)[8]、蝴蝶優(yōu)化算法(BOA)[9]等?；谖锢憩F象的算法受到物理現象的啟發(fā)，主要算法包括黑洞算法(BH)[10]、引力搜索算法(GSA)[11]、均衡優(yōu)化算法(EO)[12]等。

均衡優(yōu)化算法是學者Afshin Faramarzi受控制容積質量平衡物理現象啟發(fā)而提出的一種優(yōu)化算法。Yang等人[13]對風光新能源參與調控的電網無功優(yōu)化進行建模，采用均衡優(yōu)化算法進行無功優(yōu)化求解得出最優(yōu)的組合方案。Wunnava等人[14]針對基本的均衡優(yōu)化算法的搜索空間中不良粒子隨機分散問題，提出了一種根據適應度值自適應決定的改進均衡優(yōu)化算法。Gupta等人[15]利用高斯變異和基于種群劃分和重建概念的附加探索性搜索機制來改進基本均衡優(yōu)化算法，并應用到實際的工程問題中。

但是上述算法并未考慮到均衡算法易受局部極小值影響的、多樣性低、收斂速度慢的問題。本文提出了一種改進的均衡優(yōu)化算法，算法主要利用Sin混沌映射來初始化種群以增加算法的搜索能力；采用非線性自適應權重策略，以便搜索代理可以自適應的探索搜索空間，平衡開發(fā)和探索階段；在算法的搜索過程中，通過單純形法的反射、擴張和收縮運算對較差位置的代理進行改進。最后，通過10個基準函數及其Wilcoxon秩和檢測和部分CEC2014測試函數的仿真實驗結果對比了改進的均衡優(yōu)化算法與其他智能優(yōu)化算法的性能，驗證了所提算法的有效性。

1 均衡優(yōu)化算法

1.1 算法背景

均衡優(yōu)化算法(EO)是一種基于控制體積質量平衡模型的新型元啟發(fā)式算法，其利用通用質量平衡方程來研究控制體積中非反應性成分的濃度，質量平衡方程體現了控制容積內質量進入、離開及生成的物理過程，一般采用一階微分方程來描述，公式如式(1)所示:

式中:V為控制容積，VdC/dt代表控制容積的變化率，C代表控制容積的濃度，Q為進出控制容積的容量流率，Ceq表示期望為全局最優(yōu)的平衡狀態(tài)下的濃度。G是控制容積內的質量生成速率。式(1)是時間相關的方程，因此當VdC/dt達到0時，可以達到穩(wěn)定的平衡狀態(tài)。VdC/dt可以被簡化為Q/V，定義為流動率λ，因此，式(1)可以重新組合為式(2)。

對式(2)兩邊取積分得式(3):

通過求解式(3)可得:

式中:F為指數項系數，C0控制容積在時間t0的初始濃度。

1.2 算法優(yōu)化原理

EO主要基于式(4)進行迭代優(yōu)化。算法的具體操作過程和參數設計如下。

初始化 在迭代次數iter＝1時，使優(yōu)化變量在一定的上限和下限范圍內隨機初始化，如式(6)所示:

式中:N是優(yōu)化變量的數量，Cmin表示第i個候選解，Cmin、Cmax分別為優(yōu)化變量的下限向量與上限向量，randi是d維隨機向量，每個元素值均為0～1的隨機數。根據式(6)初始化候選解方案后，使用式(7)進行迭代更新位置。

指數項系數F向量F i t＝a1sign(r－0.5)(eλi t t－1)被稱為指數項系數，旨在搜索過程中保持開發(fā)和探索之間的平衡。其表達式如式(9)所示:

式中:a1是控制全局探索能力的值，a1的值越高，算法的全局探索能力越高，反之，則越低。sign為符號函數，r、λ均代表維度與優(yōu)化空間維度一致的隨機數向量，其值均為0至1的隨機數。

質量生成速率G i生成率G i是EO中的主要因素之一，會影響算法局部尋優(yōu)能力，該參數的定義如下:

2 改進均衡優(yōu)化算法

2.1 Sin混沌化初始種群

群智能優(yōu)化算法的種群初始化方法會影響算法的收斂速度和求解精度。EO算法利用隨機生成的數據作為初始信息，減少了算法的多樣性和整體優(yōu)化效果。由于混沌運動具有隨機性、規(guī)律性和遍歷性[16]，在求解函數優(yōu)化問題時，這些特性使算法更容易擺脫局部最優(yōu)解，從而保持種群多樣性并提高全局搜索能力，因此可以用來代替隨機初始化。文獻[17]驗證了Sin混沌與Logistic混沌相比具有更明顯的混沌特性，本文采用采用Sin混沌對EO算法進行種群初始化。式(12)為Sin混沌映射的表達式:

為了防止在[－1，1]之間產生不動點和零點，式中的初始值不能取0。

2.2 非線性自適應權重

局部開發(fā)和全局探索作為優(yōu)化算法的兩個重要階段，過度的開發(fā)能力會抑制搜索代理向全局最優(yōu)解發(fā)展的趨勢，過多的探索能力會降低優(yōu)化精度。因此，在兩個階段之間找到合適的轉換可以提高優(yōu)化算法的性能。均衡算法中的a1的變化直接影響搜索和開發(fā)之間的平衡，從而影響算法的性能。但是a1的值是在原算法中是經驗設定的且為固定值，從而導致EO算法具有隨機性和局限性。

本文采用非線性自適應權重，可以通過迭代次數自適應的調整參數a，以減少隨機性對算法的影響，所提出的非線性自適應權重a通過式(13)表示:

式中:amin、amax分別為收斂因子的最小值和最大值，t為當前迭代次數，T為總迭代次數，gammaincinv為逆不完全伽馬函數。如圖1所示，非線性自適應權重a非線性地從2遞減到最小值amin，在算法迭代前期，種群全局搜索最優(yōu)解，此時應該給予足夠的搜索空間發(fā)散種群，因此給予一個較大的收斂步長有利于算法的開發(fā)；在算法迭代中后期，算法逐漸收斂，個體開始進行局部搜索，此時給予一個較小的收斂步長有利于算法進行局部探索。

圖1 權重系數改進前后對比

因此，在式(7)中引入非線性自適應權重后，可以有效平衡探索和開發(fā)，更新方程變換為如式(14)所示:

2.3 單純形法

單純形法是指在空間中構造一個多面體，找出該多面體每個頂點的適配度并進行比較，找出最佳、次最佳和最差，通過反射、收縮、擴張等操作更新最差，形成一個新的多面體。它是一種局部搜索方法，具有使用方便、適用范圍廣、收斂速度快等特點。如圖2所示，設最優(yōu)點為X G，次優(yōu)點為X B，X C為最優(yōu)點X G與次優(yōu)點X B的中心，對于一個最差點X S，g是X S到除X S以外的所有頂點的質心X的方向向量，反射、收縮、擴張運算如下:

圖2 單純形法的四種操作

反射運算:X R＝X C＋α(X C－X S)，X R是執(zhí)行反射運算后的點，即反射點，X E＝X C＋γ(X R－X C)為反射系數，通常X E＝X C＋γ(X R－X C)。

擴張運算:X E＝X C＋γ(X R－X C)，X E是執(zhí)行擴張運算后的點，即擴張點，γ為擴張系數，通常λ＝2。

內收縮運算:X W＝X C－β(X S－X C)，X W是執(zhí)行內收縮運算后的點，即內壓縮點，β為內收縮系數，通常β＝0.5。

外收縮運算:X T＝X C＋β(X C－X S)，X T是執(zhí)行外收縮運算后的點，即外收縮點，β為外收縮系數，通常β＝0.5。

本文利用單純形法的反射、擴張和收縮運算對當前較差個體進行改進，增加算法跳出局部最優(yōu)的能力。

2.4 改進均衡優(yōu)化算法步驟

根據以上策略描述，以下為SMEO的具體步驟:

①設置算法參數:種群規(guī)模N、維度d、參數a1、amin、amax、最大迭代次數T、反射系數α、擴張系數γ、內外收縮系數β。

②利用Sin混沌初始化個體。

③計算每個個體的適應度值并根據式(7)確定當前平衡狀態(tài)池狀態(tài)。選出當前最優(yōu)的三個位置為Xα、Xβ、Xδ，對應的適應度值為f(Xα)、f(Xβ)、f(Xδ)。中心位置為X C＝(Xα＋Xβ)/2。

④對最差的位置X S進行反射操作，得到反射點X R。

⑤如果f(X R)＜f(Xα)，即反射的方向正確，將執(zhí)行擴張操作得到f(X E)，若f(X E)＜f(Xα)，則用X E代替X S；反之，則用X R代替X S。

⑥如果f(X R)＞f(X S)，即反射方向不正確，需執(zhí)行外收縮操作得到X T，若f(X T)＜f(X S)，則用X T代替X S。

⑦如果f(Xα)＜f(X R)＜f(X S)，執(zhí)行內收縮操作得到X W，若f(X W)＜f(X S)，則用X W取代X S，反之，則用X T代替X S。

⑧根據式(14)更新其他個體的位置。

⑨判斷算法是否滿足結束條件，若滿足，則算法結束；否則，執(zhí)行步驟③。

3 改進均衡優(yōu)化算法實驗結果及分析

3.1 基本測試函數

為了驗證本文改進均衡優(yōu)化算法(SMEO)的有效性，采用國際上通用的10個經典測試函數進行仿真實驗，均來自CEC2005測試集。這些測試函數分為三類:單峰、多峰和組合函數。

函數f1－f6是只有一個全局最優(yōu)值的單峰函數，單峰函數用于評價算法的局部搜索能力和收斂速度。函數f7－f9是多峰函數，與單峰函數不同，多峰函數具有多重局部最優(yōu)解，隨著問題規(guī)模的增大，局部最優(yōu)解的數目也會增加。多峰函數對于評價算法的探索能力具有重要的參考價值。f10是復合函數，與多峰函數的不同之處在于它的維數較少，局部最優(yōu)值較少，并且不允許維數調整，用于測試算法的優(yōu)化精度?；鶞屎瘮岛吞囟ㄐ畔⑷绫?所示。

表1 基準測試函數及詳細信息

3.2 仿真平臺及參數設置

本文的仿真實驗操作系統(tǒng)為Microsoft Windows 10，CPU為Intel Core i7，主頻為2.4 GHz，內存為8 GB。實驗編程軟件為MATLAB R2017b。

算法參數設置:算法種群規(guī)模設置為30，最大迭代次數為500，維度為30，各基本算法內部參數設置如表2所示。

表2 算法參數設置

3.3 與不同改進EO算法對比

使用10個不同的基準測試函數分別對EO、SMEO、AEO[14]以及m-EO[15]進行求解，通過對4種算法的平均值和標準差的統(tǒng)計來對比驗證SMEO算法的有效性。算法獨立運行30次，實驗的平均值反映了算法在給定迭代次數下的收斂精度，標準差反映了算法的穩(wěn)定性。實驗結果如表3所示，其中加粗的部分為最優(yōu)結果。

從表3可以看出，本文提出的SMEO算法在10個基準測試函數上均取得了不錯的尋優(yōu)效果。對于函數f1、f2、f3、f4、f7、f9，SMEO算法相對于其他三種算法，算法準確度顯著提高的同時，且收斂到理論最優(yōu)值0，說明搜索效果得到了很好的提升。對比函數f7，四個算法均收斂到理論最優(yōu)值。m-EO算法在函數f5上取得最好的效果，更加的接近理論最優(yōu)值。對于在10個基準函數上的表現效果，SMEO算法在9個函數上優(yōu)于EO算法，在8個函數上優(yōu)于AEO，在8個函數上優(yōu)于m-EO算法。綜合上述比較結果來說，與EO算法、AEO算法以及m-EO算法相比，SMEO算法達到了更高的求解精度和取得了更好的穩(wěn)定性。

表3 不同EO算法對10個測試函數的實驗結果

3.4 與其他智能優(yōu)化算法對比

為了進一步評估改進SMEO的性能，將本文的SMEO算法與鯨魚優(yōu)化算法(WOA)、灰狼優(yōu)化算法(GWO)、麻雀搜索算法(SSA)、蝴蝶優(yōu)化算法(BOA)進行比較，實驗結果如表4所示，在10個基準測試函數上的收斂曲線如圖3所示。

表4 不同智能算法對10個測試函數的實驗結果

圖3 各測試函數下的收斂曲線

從圖3可以看出，本文SMEO算法在10個測試函數中的收斂曲線明顯優(yōu)于其他的算法函數，特別是在f1、f2、f3、f4、f6函數中，在適應度值達到最低的同時收斂速度也遠優(yōu)于EO算法、GWO算法、SSA算法、BOA算法，說明本文提出的改進策略可以有效地提高EO的局部開發(fā)能力和收斂速度。對于多峰函數f7、f8、f9，SMEO在200次迭代內找到最優(yōu)值并退出迭代，收斂曲線表明，SMEO算法可以避免算法陷入局部最優(yōu)，并具有強大的全局搜索能力。

從表4可以看出，SMEO算法在f1、f2、f3、f4、f6、f7、f8與f9等8個基準測試函數上均取得了最優(yōu)的最優(yōu)值、平均值以及標準差EO在f5與f10上取得最優(yōu)的效果。

為了進一步地驗證SMEO數據的可靠性和有效性，本文采用Wilcoxon秩和檢驗[18]對實驗結果進行進一步分析。Wilcoxon秩和檢測常用來對比兩組數據之間的差異，以確定它們是否在統(tǒng)計上存在顯著不同。本文將EO算法、GWO算法、SSA算法、BOA算法與SMEO算法在10個基準測試函數上進行Wilcoxon秩和檢驗對比分析，驗證SMEO算法尋優(yōu)結果在統(tǒng)計學上的優(yōu)勢。若計算出P＜5%，可以認為是拒絕零假設的有利依據，即兩個樣本數據的差別顯著。表5所示為不同測試函數下秩和檢驗的P值，表中的＋、－與＝分別表示SMEO算法的秩和統(tǒng)計結果優(yōu)于、次于和等于對比算法，NAN表示檢驗的所有樣本數據相同，即算法的性能相當。

由表5結果可知，除了算法性能相當的以外，SMEO算法相較于其他算法的Wilcoxon秩和檢測結果P值基本上都小于5%，說明SMEO算法對于基準測試函數的優(yōu)化結果在統(tǒng)計學上的具有很大的優(yōu)勢，驗證了SMEO算法的魯棒性。

表5 測試函數下秩和檢驗的P值

3.5 CEC2014測試函數尋優(yōu)對比

為了進一步驗證SMEO算法處理具有復雜特征的問題時的魯棒性，本文選取部分具有復雜特征的CEC2014單目標優(yōu)化函數進行尋優(yōu)對比分析，其中包括單峰(UF)、多峰(MF)、混合(HF)和復合(CF)類型函數，函數相關信息如表6所示。本文將SMEO與標準EO算法、GWO算法、L-SHADE算法、SSA算法、WOA算法進行對比。其中，L-SHADE算法在CEC2014測試函數中表現卓越，常用做于對比實驗。實驗參數取種群規(guī)模為N＝50，維度d＝30，最大迭代次數為2 000，每個函數獨立運行50次取平均值和標準差。其中L-SHADE算法的數據來源于文獻[19]，SMEO算法運行結果及與其他算法對比如表7所示。

表6 部分CEC2014函數

表7 CEC2014函數優(yōu)化對比

從表6可以看出，SMEO算法在CEC2014測試函數上的優(yōu)秀表現，除了單峰CEC03函數，SMEO算法在其他8個測試函數上都取得了最優(yōu)精度。對于CEC12、CEC13、CEC16以及CEC19測試函數，SMEO算法基本收斂到了理論最優(yōu)值；對于復合特征CEC23、CEC24和CEC24函數，SMEO算法尋優(yōu)標準差為0，說明其對于復合特征函數尋優(yōu)穩(wěn)定性很高。上述CEC2014測試函數尋優(yōu)結果分析說明，本文提出的SMEO算法對于具有復雜特征的函數尋優(yōu)上同樣具有很大優(yōu)勢，驗證了SMEO算法的魯棒性。

3.6 SMEO算法時間復雜度分析

SMEO算法的計算復雜度主要有兩部分:第一部分是基本EO的復雜度為:

式中:d為變量維數；第二部分單純形搜索的計算復雜度為O(d×g(d)×tmax)，其中g(d)為計算適應度值的次數。因此，整個SMEO算法的復雜度為:

雖然SMEO算法的復雜度比基本EO算法大，且都在同一數量級，但是所提算法的求解精度和穩(wěn)定性都要比基本EO算法好。

4 結論

本文為了進一步解決EO收斂速度慢，易陷入局部最優(yōu)的問題，提出了三種改進策略，即Sin混沌初始化、非線性自適應慣性權重以及單純形法。利用10個基準函數和部分CEC2014測試函數進行實驗比對，提出的策略對收斂速度和精度得到有效提高。同時，為了驗證SMEO的可靠性和有效性，對已給出的數據進行統(tǒng)計檢驗作出性能評價分析。校驗表明，改進的算法在搜索精度、誤差分析和成功率整體都要優(yōu)于其他算法，魯棒性也得到提高。下一步工作考慮將SMEO應用于實際工程設計問題，進一步驗證SMEO算法相對于其他算法的優(yōu)越性。