結合變尺度法的改進類電磁機制算法

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

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

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

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

1 類電磁機制算法的原理

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

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

1.1 初始化

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

抽取到所有樣本點后，計算出每個樣本點對應的目標函數值，并將目標函數值最優的樣本點記為xbest.

1.2 局部搜索

局部搜索過程用來改進當前樣本點，即搜索樣本點鄰域范圍內的更優解，如果這樣的更優樣本點存在，則用更優樣本點代替當前已搜索到的樣本點.局部搜索的對象可以是整個樣本點，也可以只對當前最優樣本點進行局部搜索.

1.3 電荷量及合力矢量計算

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

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

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

1.4 移動粒子

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

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

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

2 EM算法的收斂速度分析

已有研究證明［4］，當迭代次數趨于極限時，種群中至少有一個粒子以概率1移動到全局最優解附近.然而現在還未見有文獻對EM法的收斂速度開展專門的研究，圍繞著EM法的收斂速度問題，有以下3個方面需要關注:

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

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

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

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

測試函數1:Six-Hump Camel-back function.

已知最優解為

測試函數2:Sphere function.

最優解為

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

2.1 EM算法求解

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

圖1 測試函數1取不同粒子數時最優解的進化曲線Fig.1 The solution curves of the best evolution with different particle numbers for test function 1

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

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

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

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

圖2 測試函數2取不同粒子數時最好解的進化曲線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算法搜索后期，由于粒子聚集有可能造成算法收斂速度下降甚至出現停滯.雖然在EM算法中引入局部搜索機制可改善這一情況，但由于計算所得合力非常小，從而造成全局搜索信息的丟失，此時EM算法主要依靠局部搜索過程尋優，這勢必會影響算法的求解效率.

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

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

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

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

圖5 對連續15次計算結果進行二次優化的結果Fig.5 Quadratic optimization results for the results of continuous 15

3 優化參數選取及EM算法改進

根據實驗結果，可得如下結論:

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

根據前文結果可知，EM算法對于起始搜索位置并不敏感，即EM算法具有較強的全局搜索能力.以圖1結果為例，雖然不同粒子數目收斂到近似最優解的迭代步數約15步，但m取50時計算耗時要遠遠大于其他m取值較小的情況.對于種群數m的選擇目前還沒有一個固定的標準.基于以上的結果，筆者認為對于一般的連續函數優化問題，采用EM算法計算的搜索種群數目在［2，10］整數區間上取值即可滿足計算效率和精度的要求.在計算過程中，考慮到問題的維數及方程的復雜度等因素可適當地增加搜索粒子數量m.

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

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

從EM算法本身構造考慮，可從以下2個方面對算法進行改進:

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

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

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

4 結束語

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

［1］趙云豐，尹怡欣，付冬梅，等.禁忌免疫網絡算法及其在函數優化中的應用［J］.智能系統學報，2008，3(5):394-400.ZHAO Yunfeng，YIN Yixin，FU 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］周建新，楊衛東，李擎.求解連續函數優化問題的改進蟻群算法及仿真［J］.系統仿真學報，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，FANG S C.An electromagnetism-like mechanism for global optimization［J］.Journal of Global Optimization，2003，23(3):263-282.

［4］BIRBIL S L，FANG 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］陳寶林.最優化理論與算法［M］.北京:清華大學出版社，2005:372-375.