許 毅，馮 翔,2，虞慧群,2

（1.華東理工大學(xué)信息科學(xué)與工程學(xué)院，上海200237；2.上海智慧能源工程技術(shù)研究中心，上海200237）

全局優(yōu)化問題廣泛存在于工程、經(jīng)濟、生物、網(wǎng)絡(luò)交通等領(lǐng)域，目前主要有兩大類優(yōu)化算法用于解決全局優(yōu)化問題，一類是基于梯度的算法，一類是元啟發(fā)式優(yōu)化算法。然而許多基于梯度的算法，如拉格朗日乘子法、共軛方向法、投影罰函數(shù)法以及黃金分割法等，主要依賴于目標(biāo)函數(shù)的梯度信息，而實際問題中的目標(biāo)函數(shù)往往是不可導(dǎo)的，所以該類算法在解決實際問題時會受到很大的限制。

元啟發(fā)式算法的優(yōu)勢在于它的靈活性，由于它僅需要通過觀察輸入和輸出來解決優(yōu)化問題，而無需考慮搜索空間的梯度，所以在解決各式各樣的問題上具有高度的靈活性，同時，在算法中加入的隨機因子也有助于避免陷入局部最優(yōu)。基于這些優(yōu)勢，元啟發(fā)式算法可應(yīng)用于更廣泛的領(lǐng)域中。

元啟發(fā)式算法分為兩大類：群體智能算法[1]和進化算法[2]。群體智能算法的基礎(chǔ)主要來源于一些群體生物的集體智慧，將這些群體行為構(gòu)建而成的模型作為解決復(fù)雜現(xiàn)實問題的框架，其中最常用的算法是粒子群算法（PSO）[3-4]和蟻群算法（ACO）[5]。此外，還有其他群體智能算法，如：灰狼群算法(GWO)[6-8]、人工蜜蜂群算法(ABC)[9]、樽海鞘群算法(SSA)[10]等。進化算法模擬了自然進化的過程，最著名的是遺傳算法（GA）[11]，其他的進化算法有差分演化算法(DE)[12]、生物地理優(yōu)化算法(BBO)[13]等。

冬季湖水結(jié)冰是一種常見的自然現(xiàn)象。當(dāng)湖水溫度低至凝固點時，水分子就會凝結(jié)成冰晶。通常，影響湖水溫度的因素有湖水的深度、大氣的溫度、湖面風(fēng)的大小等。本文以找出湖水中心為目標(biāo)，通過模擬湖水結(jié)冰的過程實現(xiàn)對連續(xù)極值問題的求解，提出了冰晶連續(xù)優(yōu)化算法來解決全局優(yōu)化問題。

冰晶連續(xù)優(yōu)化算法在解決極值問題時會極度依賴于每次迭代時中心點的選取，這樣算法容易陷入局部最優(yōu)。受文獻[14]中參考向量的啟發(fā)，本文引入了角度懲罰距離策略來綜合考慮中心點位置的選取，以達到平衡收斂性和分布性的目的。同時在新生冰晶的位置選擇上，為了加速算法的收斂速度，受文獻[15]中組選擇策略的影響，引入了基于強化學(xué)習(xí)的概率更新策略，利用已有的先驗知識對新生冰晶的位置作出指導(dǎo)，有效地提高了收斂速度。

1 基于強化學(xué)習(xí)和角度懲罰距離的冰晶連續(xù)優(yōu)化算法

1.1 冰晶連續(xù)優(yōu)化算法

1.1.1 初始化 算法開始時，湖水中會分布S個維度為n的晶體，即c i=(ci1,ci2,···,cin)∈Rn，初始化每個晶體的能量值Ei0=f(x)，其中f(x) 為目標(biāo)函數(shù)。

1.1.2 冰晶殼的生成 第一次初始化后，能量值最低的NS個晶體將會鏈接在一起，形成一層冰晶殼，形成冰晶殼的晶體不再加入到沉淀過程中。同時為了保證湖水中未析出晶體個數(shù)不變，將會重新生成NS個晶體，以替代形成冰晶殼的晶體。

1.1.3 湖水晶體的能量變化 未形成冰晶殼的晶體會發(fā)生能量變化，其能量隨時間的變化公式為

1.1.4 冰晶殼的再生長 未結(jié)成冰晶殼的晶體在能量變化后，能量值最低的Np個晶體開始沉淀，沉淀過程中會被已結(jié)成冰晶殼的晶體吸收能量，從而加速沉淀并加入到已結(jié)成的冰晶殼中，這樣擴大了冰晶殼的范圍，而未沉淀的晶體將會參與到下次的能量變化和沉淀過程中。

圖1為冰晶連續(xù)優(yōu)化模型收斂示意圖，其偽代碼如下：

圖1 冰晶連續(xù)優(yōu)化模型收斂示意圖Fig.1 Convergence diagram of ice crystal continuous optimization model

1.2 基于角度懲罰距離的偏差策略

由于湖水中心位置的不確定性，所以選擇當(dāng)前位置最好的點作為臨時湖水中心，但這勢必會導(dǎo)致晶體能量的變化產(chǎn)生偏差，即不能準(zhǔn)確地計算出晶體從湖水中心獲得的能量值。本文采用角度懲罰距離策略來消除臨時湖水中心帶來的偏差值。

1.2.1 多樣性度量 受臨時湖水中心影響，晶體的沉淀過程和結(jié)冰結(jié)果易陷入局部最優(yōu)。本文采用角度信息來評價晶體的位置分布，從而消除臨時湖水中心帶來的收斂程度的影響。

對于晶體c i，多樣性度量是指其與未結(jié)冰晶體中其他晶體的最小夾角，計算公式為

1.2.2 角度懲罰距離 在算法前期，應(yīng)該使晶體的分布更為分散，即讓冰晶殼的形成總是從外圍向內(nèi)部擴展，使之與實際湖水中心帶來的能量變化的影響相符；而到了算法后期，在結(jié)冰范圍越來越靠近湖水中心時，減少晶體的多樣性，以期在較小的區(qū)域中更快地逼近湖水中心。為了消除湖水中心帶來的偏差以及滿足以上要求，針對1.1.3 節(jié)中晶體的能量變化公式，本文引入了角度懲罰距離策略。隨著晶體結(jié)冰的進程，動態(tài)地調(diào)整算法在前后期晶體的分布和消除臨時湖水中心帶來的能量偏差。角度懲罰距離公式為

圖2 基于角度懲罰距離的偏差策略示意圖Fig.2 Deviation strategy based on angle penalty distance

通過角度懲罰距離選擇出迭代過程中的臨時湖水中心，與原本從目標(biāo)函數(shù)得出的湖水中心相比，角度懲罰距離會考慮到多樣性的影響，且是一個隨迭代過程動態(tài)變化的值，能更好地體現(xiàn)實際湖水中心的位置。

1.3 基于強化學(xué)習(xí)的概率更新

經(jīng)過能量交互后，能量較低的晶體將會沉淀并析出，析出的晶體則會鏈接在一起形成冰晶殼，冰晶殼的結(jié)冰范圍為

為了保證湖水中的未析出晶體總數(shù)不變，在冰晶殼的范圍內(nèi)會生成新的晶體分子，以參與到下一次的迭代沉淀中。在[c j_min,c j_max] 范圍內(nèi)隨機生成新的晶體，旨在后續(xù)迭代中不斷形成冰晶殼，從而不斷地逼近湖水中心。對于整個湖水能量體系來說，冰晶殼總是位于遠離湖水中心的位置，隨機生成的晶體極有可能會同樣被分布到遠離湖水中心的位置，很大程度地降低了湖面結(jié)冰的速度。為了讓湖面盡快結(jié)冰，即加快冰晶算法的尋優(yōu)速度，本文提出了基于強化學(xué)習(xí)的概率更新來加快晶體的沉淀過程。

強化學(xué)習(xí)[16-17]被定義為一個智能體在未知環(huán)境中如何采取動作以期獲得最大的累計收益，每一步的選擇都不僅僅只是影響到當(dāng)前的收益。強化學(xué)習(xí)潛在的思想就是那些能使累計收益最大的動作有更大的可能被選擇。

晶體的生成依賴于未沉淀晶體的位置。每次沉淀后，會保留有S?Ns個晶體繼續(xù)參與下次迭代，新生的晶體會依概率Gt從保留的S?Ns個晶體中選擇一個，出現(xiàn)在其附近。初始時，保留的晶體被選擇的概率是相同的，但隨著迭代，上一次保留的晶體可能會在這一次迭代中依舊存在，這時將會獎勵這個晶體，并通過式（9）更新概率：

1.4 算法流程

為了盡量消除由于臨時湖水中心的位置引起的能量變化誤差和加快湖面結(jié)冰的速度，本文分別對臨時湖水中心的選擇和晶體的生成進行了改進，提出了基于強化學(xué)習(xí)和角度懲罰距離的冰晶優(yōu)化算法(APD-CEO)。算法的偽代碼如下：

輸入：冰晶群大小S，最大迭代次數(shù)Tmax輸出：湖水中心的位置

begin

（1）初始化S個冰晶，T= 0

（2）whileT

（3） 根據(jù)式（2）～式（5）計算角度懲罰距離，得出臨時湖水中心

（4） 根據(jù)式（1），晶體能量發(fā)生變化

（5） 對于每個晶體：

（6）if 晶體能量達到閾值

（7） 晶體開始沉淀，形成冰晶殼

（8） 根據(jù)式（9）計算晶體被選擇的概率Gt

（9） 根據(jù)式10 計算出新生晶體的位置

（10）輸出湖水中心的位置

end

2 算法收斂性證明

湖水能量體系可以看作是一個能量消耗系統(tǒng)，其整體的能量會隨著時間而減少。APD-CEO 算法中的每個晶體都會在空氣中散發(fā)能量，并且有可能會被冰晶吸收能量，因此構(gòu)成了一個能量衰減的動態(tài)系統(tǒng)。本文通過定義一個正定的Lyapunov 函數(shù)來判定該動態(tài)系統(tǒng)的穩(wěn)定性。

證明 對于APD-CEO 算法，會存在3種狀態(tài)的晶體，即湖水中心的晶體、處于湖水邊沿的晶體和已經(jīng)析出的晶體。對于已經(jīng)析出的晶體，其能量穩(wěn)定，狀態(tài)不再變化，已變?yōu)榉€(wěn)定的狀態(tài)。

代入相應(yīng)的計算公式，有

湖水中心晶體通過式（4）來判斷，湖水中心Lcenter由角度懲罰距離和初始能量共同決定。當(dāng)算法步入迭代后期，式（5）中Z(θ)的值趨近于0，此時的湖水中心總是選取當(dāng)前能量最大的湖水晶體，即湖水中心分子總是選取每次迭代中的最大值。而湖水體系是一個能量衰減的系統(tǒng)，所以湖水中心分子最終會收斂到一個穩(wěn)定的值。

由上述可知，基于Lyapunov 穩(wěn)定性定理，APDCEO算法將會收斂到一個平衡的狀態(tài)。

3 實驗與分析

實驗環(huán)境：Matlab R2014b on the HPCCof Lenovo Shenteng 6800，該集群擁有8 個計算節(jié)點和1 個總控節(jié)點。每一個計算節(jié)點是一臺高性能服務(wù)器，內(nèi)存為24 GB，四核2.4 GHz 中央處理器。

3.1 算法的有效性比較

12個基準(zhǔn)函數(shù)的描述如表1所示。將APD-CEO算法與RGA[18]、GSO[19]、SSO[20]和LAS[21]算法進行對比來驗證算法的性能。在所有的比較示例中，群體規(guī)模均為100，最大迭代次數(shù)均為1 000。每個算法的參數(shù)設(shè)置如表2所示。

表3示出了本文算法與其他4種算法在函數(shù)維度D為30維的比較結(jié)果，實驗運行次數(shù)為30次。性能評價指標(biāo)為平均最佳解(AB)、最佳解的標(biāo)準(zhǔn)差(SD)。從表中可以看出本文算法只有在f5、f6和f9函數(shù)上的AB指標(biāo)不理想；在f2和f3函數(shù)上，算法性能排第二；在其余的7個函數(shù)中都能取得最優(yōu)的AB和SD指標(biāo)。表4示出了算法在50維基準(zhǔn)函數(shù)下的實驗結(jié)果，與30維基準(zhǔn)函數(shù)相比，本文算法表現(xiàn)得更好，除了上述的7 個函數(shù)外，還在f2和f3函數(shù)上取得了最好的結(jié)果。

表1 基準(zhǔn)測試函數(shù)Table 1 Benchmark functions

表2 各個算法的參數(shù)設(shè)置Table2 Parameter settings of each algorithms

表3 APD-CEO、RGA、GSO、SSO和LSA 在基準(zhǔn)函數(shù)上的實驗結(jié)果(D=30)Table 3 Experimental resultsof APD-CEO,RGA,GSO,SSO and LSA on benchmark functions (D=30)

表4 APD-CEO、RGA、GSO、SSO和LSA 在基準(zhǔn)函數(shù)上的實驗結(jié)果(D=50)Table 4 Experimental resultsof APD-CEO,RGA,GSO,SSO and LSA on benchmark functions (D=50)

為了測試本文算法在高維度上的性能表現(xiàn)，提升基準(zhǔn)函數(shù)的維度到100維，實驗結(jié)果如表5所示。與50維的結(jié)果類似，本文算法在9個基準(zhǔn)函數(shù)上取得了最好的效果，同時在f8和f10函數(shù)中依舊取得了標(biāo)準(zhǔn)最小值0。

圖3為不同優(yōu)化算法在30維的基準(zhǔn)函數(shù)上的搜索演化曲線圖，可以更直觀地看出算法的優(yōu)劣性。基準(zhǔn)函數(shù)分別為f1、f3、f4、f7、f8、f10、f11、f12，從圖中可以看出，APD-CEO的收斂速度最快。

表5 APD-CEO、RGA、GSO、SSO和LSA 在基準(zhǔn)函數(shù)上的實驗結(jié)果(D=100)Table 5 Experimental resultsof APD-CEO,RGA, GSO,SSOand LSA on benchmark functions (D=100)

圖3 5種算法在8個30維基準(zhǔn)函數(shù)上的演化曲線Fig.3 Evolution curves of the five algorithms on eight benchmark functions with 30 dimensions

為了更進一步分析算法的有效性，以Friedman排名來進一步說明。圖4示出了不同算法100維下在12個基準(zhǔn)函數(shù)上的排名，可以看出，除了函數(shù)f5、f6和f9之外，APD-CEO在5種算法中表現(xiàn)最好。表6列出了不同維度下算法在基準(zhǔn)函數(shù)上的Friedman 平均排名?？梢钥闯?種算法的優(yōu)化性能表現(xiàn)排名為APD-CEO、LSA、RGA、SSO和GSO。

3.2 角度懲罰距離的有效性

為了驗證角度懲罰距離在冰晶連續(xù)優(yōu)化算法中的有效性，將加入角度懲罰距離策略后的冰晶連續(xù)優(yōu)化算法與未加入任何策略的冰晶連續(xù)優(yōu)化算法進行了性能比較。實驗結(jié)果如表7所示。

圖4 各算法的Friedman 排名Fig.4 Friedman ranksof each optimization algorithms

表6 各優(yōu)化算法在30、50 和100維下的平均排名Table 6 Average ranking of each optimization algorithms

表7 角度懲罰距離策略的有效性Table7 Effectiveness of angle penalty distancestrategy

3.3 基于強化學(xué)習(xí)的概率更新策略的有效性

本文對加入基于強化學(xué)習(xí)的概率更新策略前后的算法進行了比較，實驗結(jié)果如圖5所示。After 表示加入概率更新后的優(yōu)化曲線，Before表示加入之前的優(yōu)化曲線?？梢钥闯?，加入概率更新后，曲線下降得更快，優(yōu)化算法能更快地收斂，并且保持在1 000次迭代后擁有更好的結(jié)果。實驗表明基于強化學(xué)習(xí)的概率更新能給算法帶來優(yōu)勢。

4 結(jié)束語

通過模擬湖水結(jié)冰的過程來實現(xiàn)對連續(xù)極值問題的求解，提出了冰晶連續(xù)優(yōu)化算法以解決全局優(yōu)化問題，并在其基礎(chǔ)上加入了角度懲罰距離策略和基于強化學(xué)習(xí)的概率更新策略，使得中心點的選擇能同時考慮到收斂性和分布性，以及晶體的生成能借鑒已有的先驗知識，加速了算法的收斂速度和準(zhǔn)確度。將本文算法與其他4種對比算法在12個基準(zhǔn)函數(shù)上進行測試，并分別在30維、50維和100維上檢驗了算法性能。實驗結(jié)果表明，與其他4種算法相比，APD-CEO能表現(xiàn)出良好的性能，且在高維度上能表現(xiàn)得更好。為了更進一步測試算法性能，使用Friedman Test 非參數(shù)統(tǒng)計方法分析了本文算法的表現(xiàn)。本文主要探討的是算法在單目標(biāo)極值優(yōu)化問題上的性能表現(xiàn)，在接下來的工作中，我們將更多地研究算法在多目標(biāo)優(yōu)化問題中的表現(xiàn)。

圖5 加入概率更新策略前后算法的演化曲線Fig.5 Evolution curvesof thealgorithms before and after joining probabilistic update atrategy