結(jié)合變尺度法的改進(jìn)類電磁機(jī)制算法

印 峰，王耀南，楊易旻，曹文明

(湖南大學(xué)電氣與信息工程學(xué)院，湖南長沙410082)

在求解函數(shù)優(yōu)化問題過程中，如果待優(yōu)化問題的目標(biāo)函數(shù)較為復(fù)雜，或其一、二階信息難以獲取時，一般傳統(tǒng)的優(yōu)化方法不再適合求解這類問題.而啟發(fā)式的隨機(jī)搜索方法是求解此類全局優(yōu)化問題的有效途徑之一，至今已得到廣泛應(yīng)用的模擬退火算法、遺傳算法及蟻群算法等都采用了隨機(jī)搜索的思想［1-2］.近年來，Birbil等學(xué)者受電磁學(xué)中帶電粒子間“排斥－吸引”力的啟發(fā)，提出一種新的用于求解含有界變量約束問題的全局收斂算法——類電磁算法［3］，通過選取15個函數(shù)組成的綜合測試函數(shù)集對EM(electromagnetism-like mechanism)算法性能進(jìn)行了測試，并與經(jīng)典優(yōu)化方法進(jìn)行了比較，測試結(jié)果表明EM算法可收斂到問題的最優(yōu)解，并且顯示出更好的優(yōu)化性能.文獻(xiàn)［4］進(jìn)一步從理論上證明了EM算法依分布全局收斂于問題的ε-最優(yōu)解.目前，EM算法在函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、TSP以及項目調(diào)度問題上已得到了初步的應(yīng)用，并取得了很好的優(yōu)化結(jié)果［3，5-6］.

雖然對EM算法的研究在理論和工程應(yīng)用上已取得了一定的進(jìn)展，但和遺傳算法、蟻群算法等傳統(tǒng)優(yōu)化方法相比，目前對于EM算法的研究還非常有限.本文所做的工作是:圍繞算法初值敏感性問題、種群規(guī)模選取及其對算法的收斂速度影響、算法收斂速度及停滯等問題對EM法開展了深入的研究.結(jié)合本文的研究結(jié)果提出了一種優(yōu)化的計算框架，采用該混合優(yōu)化策略可將EM法和DFP法二者的優(yōu)勢相結(jié)合，保證計算的有效性和實時性.

1 類電磁機(jī)制算法的原理

EM法首先隨機(jī)地從可行域中產(chǎn)生一組初始解，并將每一個解想象成空間中的一個帶電粒子;通過模擬電磁理論中帶電粒子間吸引－排斥機(jī)制使得粒子種群朝最優(yōu)解區(qū)域移動，每個粒子下一步的移動方向通過計算其他粒子施加給當(dāng)前粒子的合力方向來確定，同電磁力的計算方式一樣，該合力是通過將來自其他粒子的力進(jìn)行矢量疊加得到的.這樣，每完成一次迭代計算就產(chǎn)生一組新的更優(yōu)解.一個n維變量約束優(yōu)化問題可用如下方程描述:

采用EM算法求解上述優(yōu)化問題主要包括以下4個基本步驟:初始化、局部搜索、電荷量和合力計算以及移動粒子的過程.

1.1 初始化

在進(jìn)行迭代計算前，需要進(jìn)行初始化，即從可行域內(nèi)均勻地隨機(jī)抽取m個樣本點{x1，x2，…，xm}作為初始解，其中，i=1，2，…，m.隨機(jī)抽樣過程可采用式(1)實現(xiàn):

抽取到所有樣本點后，計算出每個樣本點對應(yīng)的目標(biāo)函數(shù)值，并將目標(biāo)函數(shù)值最優(yōu)的樣本點記為xbest.

1.2 局部搜索

局部搜索過程用來改進(jìn)當(dāng)前樣本點，即搜索樣本點鄰域范圍內(nèi)的更優(yōu)解，如果這樣的更優(yōu)樣本點存在，則用更優(yōu)樣本點代替當(dāng)前已搜索到的樣本點.局部搜索的對象可以是整個樣本點，也可以只對當(dāng)前最優(yōu)樣本點進(jìn)行局部搜索.

1.3 電荷量及合力矢量計算

EM算法通過計算施加到每個粒子上的合力獲取下一步的搜索信息.首先需要確定每個粒子的電荷量，構(gòu)造公式如下:

根據(jù)式(2)，目標(biāo)函數(shù)較優(yōu)的粒子將擁有較大的電荷量.同時規(guī)定:兩粒子之間使目標(biāo)函數(shù)更優(yōu)的粒子對另一個粒子保持更強的吸引力.仿照電磁理論中帶電粒子間電磁力計算公式得:

根據(jù)式(3)，每2個粒子間使目標(biāo)函數(shù)較優(yōu)的粒子將吸引另一個粒子，由于當(dāng)前最優(yōu)粒子xbest的目標(biāo)函數(shù)值最小，因此充當(dāng)著一個絕對吸引粒子，吸引著粒子群中其他所有粒子朝當(dāng)前最優(yōu)粒子位置移動.

1.4 移動粒子

計算合力矢量后，按在［0，1］區(qū)間內(nèi)隨機(jī)分布的步長λ沿合力的方向移動粒子i，計算公式如下:

式中:R為一個向量，對于第i個粒子，其分量表示對應(yīng)的向上邊界uk或下邊界lk移動的可行步長.

計算完以上4個步驟，每個粒子的位置得到了更新，也就完成了一次EM算法的迭代過程.

2 EM算法的收斂速度分析

已有研究證明［4］，當(dāng)?shù)螖?shù)趨于極限時，種群中至少有一個粒子以概率1移動到全局最優(yōu)解附近.然而現(xiàn)在還未見有文獻(xiàn)對EM法的收斂速度開展專門的研究，圍繞著EM法的收斂速度問題，有以下3個方面需要關(guān)注:

1)種群規(guī)模的設(shè)置.對于粒子算法，種群數(shù)m設(shè)置大雖然可以提高搜索過程中發(fā)現(xiàn)最優(yōu)解的概率，但同時又會增加算法的計算耗時.特別地，對于高維函數(shù)優(yōu)化問題，單純的增加搜索種群數(shù)目反而有可能影響計算效率.對于搜索的粒子數(shù)目m取何值時既能保證算法搜索效率，同時計算耗時較小?這一問題值得研究.

2)算法初值敏感性EM算法在每一次迭代過程中，通過吸引其他粒子向當(dāng)前最優(yōu)位置移動來搜索更優(yōu)解.如果在移動過程中找到一個更優(yōu)位置，則以該粒子為下一次迭代計算的吸引粒子，如此反復(fù)直至找到全局最優(yōu)解.這樣就提出一個問題，如果在初始化過程中隨機(jī)確定的起始搜索粒子偏離最優(yōu)解位置會否影響算法的搜索效率，特別當(dāng)搜索空間較大時，這一問題顯得更為重要.

3)算法停滯問題.遺傳算法存在“早熟”問題，由于局部信息素過多會引起蟻群算法停滯.雖然現(xiàn)有文獻(xiàn)證明了EM法必然收斂，但并沒有對EM法的停滯問題開展專門的研究.EM法是否存在停滯問題，如果存在，可能的原因是什么，如何解決，這一問題也值得重點研究.

圍繞上述3個問題，本節(jié)通過2個典型的測試函數(shù)對EM法的收斂特性展開了深入的研究.所選取的測試函數(shù)及其全局最優(yōu)解如下［7］:

測試函數(shù)1:Six-Hump Camel-back function.

已知最優(yōu)解為

測試函數(shù)2:Sphere function.

最優(yōu)解為

式中:測試函數(shù)1為六峰值駝背函數(shù)，該函數(shù)共有6個局部極小點，其中2個為全局最小點;測試函數(shù)2為球函數(shù)，該函數(shù)是一個典型的高維單峰值函數(shù).

2.1 EM算法求解

EM算法的初始化過程即首先選取粒子數(shù)m，并在問題的可行域內(nèi)隨機(jī)指定粒子的初始位置，同時找到使得函數(shù)值最小的當(dāng)前最優(yōu)粒子，使它充當(dāng)算法第一次迭代計算中的初始“吸引粒子”.為了測試種群數(shù)目及初始最優(yōu)粒子位置對于EM算法收斂速度的影響，本文對測試函數(shù)1取不同粒子數(shù)下的收斂性進(jìn)行了仿真研究，計算結(jié)果見圖1.

圖1 測試函數(shù)1取不同粒子數(shù)時最優(yōu)解的進(jìn)化曲線Fig.1 The solution curves of the best evolution with different particle numbers for test function 1

由圖1可知，當(dāng)所取粒子數(shù)較大時(m=50)，經(jīng)初始化過程確定的起始“吸引粒子”位置較接近于最優(yōu)解位置.當(dāng)粒子數(shù)種群數(shù)較少時，起始“吸引粒子”位置具有隨機(jī)性.即由初始化過程確定的起始搜索位置有可能接近于最優(yōu)解空間，也有可能遠(yuǎn)離最優(yōu)解空間范圍.這一結(jié)論也可根據(jù)算法初始化含義很容易得出.

對于一般迭代算法，其收斂速度受搜索的起始位置影響較大，為提高算法收斂速度，一般要求設(shè)置的起始點盡可能地接近于最優(yōu)解位置.而對于EM法其收斂速度幾乎不受起始“吸引粒子”位置的影響，由圖1可知，即使起始“吸引粒子”位置遠(yuǎn)離最優(yōu)解空間，EM算法也可以在極短的迭代步數(shù)內(nèi)收斂到最優(yōu)解鄰近空間.這說明EM算法具有非常強的全局搜索能力.以變量區(qū)間長度為10的測試函數(shù)1為例，經(jīng)本文多次測試，在最多不超過10次迭代步數(shù)內(nèi)，問題的搜索解空間都將收斂到距離最優(yōu)解非常小的區(qū)間內(nèi)，這里將搜索解空間大小定義為

式中:f*為當(dāng)前最優(yōu)解，fglob為全局最優(yōu)解.另外，從本文對測試函數(shù)2的實驗結(jié)果(圖2所示)可以得出與前述測試函數(shù)1相似的結(jié)論，這說明當(dāng)目標(biāo)函數(shù)變量區(qū)間取值范圍較大時，EM算法同樣保持了非常強的全局搜索能力.

由圖1和圖2可知，當(dāng)EM算法搜索到最優(yōu)解鄰近區(qū)域時，算法的搜索速度明顯減慢甚至出現(xiàn)停滯.原因之一是當(dāng)前最優(yōu)解已接近于全局最優(yōu)解，其收斂幅度相應(yīng)會減小.另外，從算法本身構(gòu)造分析不難發(fā)現(xiàn)，粒子群向最優(yōu)解區(qū)域聚積過程也可能影響算法的收斂速度.圖3所示為測試函數(shù)1經(jīng)30次EM算法迭代計算前種群(m=10)初始位置和更新后的位置分布.因為在最優(yōu)解的“吸引”下，粒子群將逐漸向最優(yōu)解區(qū)域聚積，隨著最優(yōu)解鄰近區(qū)域內(nèi)粒子密度的增大，粒子之間極易達(dá)成一種動態(tài)力平衡狀態(tài)，此時加載在粒子上的“合力”將趨于0.由于EM算法是通過計算“合力”獲取下一步的搜索信息，合力趨于0時顯然不利于最優(yōu)解的搜索.

圖2 測試函數(shù)2取不同粒子數(shù)時最好解的進(jìn)化曲線Fig.2 The solution curves of the best evolution with different particle numbers for test function 2

圖3 EM迭代計算前后粒子位置的分布Fig.3 The distribution of particle positions before and after the iterative calculation

2.2 基于EM算法和變步長法組合計算

由上述分析可知，在EM算法搜索后期，由于粒子聚集有可能造成算法收斂速度下降甚至出現(xiàn)停滯.雖然在EM算法中引入局部搜索機(jī)制可改善這一情況，但由于計算所得合力非常小，從而造成全局搜索信息的丟失，此時EM算法主要依靠局部搜索過程尋優(yōu)，這勢必會影響算法的求解效率.

注意到EM算法前期收斂速度非?？?，并且可確保收斂到問題的近似最優(yōu)解.而對于一般迭代算法，如果設(shè)置的搜索起始點已接近于最優(yōu)，則可極大地提高其優(yōu)化速度.為解決算法后期搜索停滯問題，一種可行的策略是摒棄EM算法的后期搜索過程，通過其他優(yōu)化方法對EM算法前期優(yōu)化結(jié)果進(jìn)行二次優(yōu)化搜索問題的最優(yōu)解.

假設(shè)目標(biāo)函數(shù)一階信息可求，為實時求出問題的精確解，采用變尺度法對EM算法前期優(yōu)化結(jié)果進(jìn)行二次優(yōu)化.即首先采用EM算法快速搜索問題真實解的鄰域解，如果該解滿足問題求解的精度要求，則停止計算;否則，以該近似解為初始值，采用變尺度法進(jìn)一步搜索問題的精確解.測試函數(shù)仍選取測試函數(shù)1，程序流程見圖4.其中，種群數(shù)m取10，EM算法計算程序最大迭代步數(shù)取30，計算中矩陣H采用如下公式計算［8］:

圖4 EM-DFP算法計算流程Fig.4 The flow chart of EM-DFP algorithm

在實際計算中，本文只進(jìn)行了1次二次搜索過程，即變尺度法計算的最大迭代步長取1.對測試函數(shù)1連續(xù)測試15次，每個計算序列經(jīng)EM算法一次優(yōu)化和變尺度法二次優(yōu)化所得的函數(shù)最小值見圖5.由圖5所示結(jié)果可知，經(jīng)二次優(yōu)化后的求解精度得到較大的提高;并且與EM算法后期搜索過程相比(見圖1、圖2)，二次優(yōu)化的尋優(yōu)效率大大超過了EM算法.在本文的計算實例中，即使只進(jìn)行1次二次搜索過程，也可以迅速地逼進(jìn)問題的最優(yōu)解.

圖5 對連續(xù)15次計算結(jié)果進(jìn)行二次優(yōu)化的結(jié)果Fig.5 Quadratic optimization results for the results of continuous 15

3 優(yōu)化參數(shù)選取及EM算法改進(jìn)

根據(jù)實驗結(jié)果，可得如下結(jié)論:

1)種群數(shù)的選擇應(yīng)綜合考慮搜索效率和計算耗時.由前述分析可知，種群數(shù)目m取值較大時，雖然起始搜索位置相對較接近最優(yōu)解位置，但增加種群數(shù)m會增加計算量，特別地，對于高維優(yōu)化問題，單純增加種群數(shù)m反而可能降低算法的計算效率.另外，如果初始粒子數(shù)過多，在粒子向最優(yōu)區(qū)域聚積過程中，粒子之間達(dá)成動態(tài)力平衡狀態(tài)的機(jī)率大大增加，由前文分析可知，這一狀態(tài)不利于最優(yōu)解的搜索.

根據(jù)前文結(jié)果可知，EM算法對于起始搜索位置并不敏感，即EM算法具有較強的全局搜索能力.以圖1結(jié)果為例，雖然不同粒子數(shù)目收斂到近似最優(yōu)解的迭代步數(shù)約15步，但m取50時計算耗時要遠(yuǎn)遠(yuǎn)大于其他m取值較小的情況.對于種群數(shù)m的選擇目前還沒有一個固定的標(biāo)準(zhǔn).基于以上的結(jié)果，筆者認(rèn)為對于一般的連續(xù)函數(shù)優(yōu)化問題，采用EM算法計算的搜索種群數(shù)目在［2，10］整數(shù)區(qū)間上取值即可滿足計算效率和精度的要求.在計算過程中，考慮到問題的維數(shù)及方程的復(fù)雜度等因素可適當(dāng)?shù)卦黾铀阉髁Ｗ訑?shù)量m.

2)EM算法搜索過程具有隨機(jī)性且算法搜索后期可能出現(xiàn)停滯.EM算法的前期收斂速度非?？?，在粒子移動過程中，如果某個粒子更新后的位置剛好落到最優(yōu)解位置，則此時可以迅速地確定問題的最優(yōu)解.但更一般的情況是各個粒子向最優(yōu)解區(qū)域聚積的過程中，由于粒子間相互排斥和吸引，使得計算合力F可能等于0或趨近于0，此時EM算法法的收斂機(jī)制基本失效，粒子位置的更新完全依賴于局部信息，從而造成算法收斂非常緩慢甚至出現(xiàn)停滯，從近似最優(yōu)解逼近于全局最優(yōu)解所需的迭代步數(shù)大大增加，算法搜索效率較低.

3)結(jié)合二次搜索策略可顯著提高算法的收斂速度和精度.在粒子聚積過程中，合力F為0的情況難以避免，因此依靠EM算法本身的收斂機(jī)制無法解決這一問題.一種有效的解決方式是將EM算法和其他優(yōu)化方法相結(jié)合，采取組合的計算方式.由于此時只需要EM算法計算問題的近似最優(yōu)解，因此可只保留EM算法前期搜索計算過程，從而進(jìn)一步地提高了計算效率.

從EM算法本身構(gòu)造考慮，可從以下2個方面對算法進(jìn)行改進(jìn):

1)局部搜索.在實際優(yōu)化問題中，如果只需要知道其近似最優(yōu)解，為了提高計算效率，在計算過程中可考慮忽略局部搜索過程，必要時候只對當(dāng)前最優(yōu)粒子進(jìn)行局部搜索，另外也可從改進(jìn)局部搜索性能角度加快算法的收斂速度.

2)合力計算和粒子的移動方向.標(biāo)準(zhǔn)EM算法采用式(3)計算合力F，顯然，只要保證粒子在力的作用下朝更優(yōu)粒子區(qū)域移動，該力的構(gòu)造公式并不是惟一的，同時式(3)也不是最優(yōu)的.考慮這樣一種情況:對于當(dāng)前粒子，當(dāng)另外2個粒子同時吸引該粒子時，如果較優(yōu)粒子距離當(dāng)前粒子相對較遠(yuǎn)，根據(jù)式(3)，其對當(dāng)前粒子的“吸引力”將被減弱，此時當(dāng)前粒子就有可能朝較劣粒子區(qū)域移動.這一過程可以用圖6來說明.如圖6所示，拉大粒子之間的距離雖然不改變兩者之間作用力的方向，但力大小將降低，此時將使得合力方向偏向另一個粒子(F1偏向F2)，圖6(b)顯然不利于最優(yōu)解的搜索，解決辦法之一是弱化或忽略計算公式中粒子間的距離項，即式(3)的分母項;或者通過其他強化較優(yōu)粒子作用力的方式使得合力的方向偏向較優(yōu)粒子區(qū)域以提高算法的收斂速度.

圖6 力矢量合成及粒子移動方向Fig.6 Composition of forces and particle direction of movement

4 結(jié)束語

利用EM算法前期收斂速度快，且易于與其他優(yōu)化方法相結(jié)合的特點，將EM算法與其他局部優(yōu)化方法混合，或與其他性能強大的搜索方法相結(jié)合，可從根本上解決算法搜索后期收斂速度緩慢問題.另外，對于算法中力的計算方式及參數(shù)進(jìn)行優(yōu)化調(diào)整，可進(jìn)一步提高算法的優(yōu)化性能.目前，通過一些實驗和比較已經(jīng)顯示出了EM算法的強大性和優(yōu)越性，對EM算法及其應(yīng)用開展深入的研究是一個非常有意義的研究方向.

［1］趙云豐，尹怡欣，付冬梅，等.禁忌免疫網(wǎng)絡(luò)算法及其在函數(shù)優(yōu)化中的應(yīng)用［J］.智能系統(tǒng)學(xué)報，2008，3(5):394-400.ZHAO Yunfeng，YIN Yixin，F(xiàn)U Dongmei，et al.Application of a Tabu immune network algorithm in function optimizations［J］.CAAI Transactions on Intelligent Systems，2008，3(5):394-400.

［2］周建新，楊衛(wèi)東，李擎.求解連續(xù)函數(shù)優(yōu)化問題的改進(jìn)蟻群算法及仿真［J］.系統(tǒng)仿真學(xué)報，2009，21(6):1685-1688.ZHOU Jianxin，YANG Weidong，LI Qing.Improved ant colony algorithm and simulation for continuous function optimization［J］.Journal of System Simulation，2009，21(6):1685-1688.

［3］BIRBIL S I，F(xiàn)ANG S C.An electromagnetism-like mechanism for global optimization［J］.Journal of Global Optimization，2003，23(3):263-282.

［4］BIRBIL S L，F(xiàn)ANG S C，SHEU R L.On the convergence of a population-based global optimization algorithm ［J］.Journal of Global Optimization，2004，30(2):301-318.

［5］WANG Xiaojuan，GAO Liang，ZHANG Chaoyong.Electromagnetism-like mechanism based algorithm for neural network training［J］.Lecture Notes in Computer Science，2008，5227:45-47.

［6］DIETER D，De REYCK B，LEUS R，et al.A hybrid scatter search/electromagnetism meta-heuristic for project scheduling［J］.European Journal of Operational Research，2006，169(2):638-653.

［7］YAO Xin，LIU Yong，LIN Guangming.Evolutionary programming made faster［J］.IEEE Transactions on Evolutionary Computation，1999，3(2):82-102.

［8］陳寶林.最優(yōu)化理論與算法［M］.北京:清華大學(xué)出版社，2005:372-375.