一種采用雙混沌搜索的類電磁機制算法

姜建國,劉夢楠,劉永青,蘇 仟,張麗媛

(西安電子科技大學計算機學院,陜西西安 710071)

一種采用雙混沌搜索的類電磁機制算法

姜建國,劉夢楠,劉永青,蘇 仟,張麗媛

(西安電子科技大學計算機學院,陜西西安 710071)

針對現有算法中初始種群隨機性強、局部搜索能力差、移動公式效率低等問題,提出了一種改進的類電磁機制算法.結合反向學習理論,引入帶擾動因子的反向學習機制構造初始種群;提出了一種雙混沌優化機制用于局部搜索;運用改進后的公式計算粒子之間的合力;設計了一種自適應移動算子來更新粒子.實驗結果表明,改進后的算法具有更好的收斂效果和更高的求解精度.

類電磁機制算法;反向學習機制;擾動;雙混沌;全局優化

在求解實際問題時,一般建立的數學模型要么維數高,要么沒有好的解析性質或難以獲知解析性質,因此確定全局優化算法很難或不能求解這些問題.隨機搜索算法的出現為這類問題的求解提供了新的思路.作為一種隨機搜索算法,類電磁機制(Electromagnetism-like Mechanism,EM)算法[1]模擬了電磁場中帶電粒子之間的吸引排斥機制,通過該機制使得粒子朝著最優粒子移動,已成功用于求解全局優化問題.該算法具有尋優機制簡單、搜索能力強、所需資源少、收斂速度快等優點.但是,標準類電磁機制算法中,初始種群是隨機產生的,多樣性不夠豐富;局部搜索范圍小,形式單一,易陷入早熟收斂;粒子間距離對其相互作用力影響較大,可能導致粒子尋優方向錯誤、計算溢出等問題;粒子的移動沒有考慮到進化代數的影響,使得算法效率偏低.

為此,筆者提出了一種改進的類電磁機制算法(Improved Electromagnetism-like Mechanism algorithm,IEM),即結合反向學習理論,引入帶擾動因子的反向學習機制[2]構造初始種群,既保證了初始群體含有較豐富的模式,又有利于提高整體的進化收斂速度;提出了基于雙混沌優化機制的局部搜索策略,運用兩種完全不同的混沌優化機制各自獨立搜索,不僅避免了算法過早陷入局部最優,而且在一定程度上提高了解的精度;運用改進后的公式[3]計算粒子間的作用力,同時加入擾動粒子避免因早熟收斂而陷入局部最優;設計了新的自適應移動算子來更新粒子.實驗結果表明,改進的類電磁機制算法在求解精度上有很大提高,對于經典的評價優化算法執行效果的測試函數,均取得了比較好的結果.

1 經典類電磁機制算法

類電磁機制算法的實現主要由4個階段完成,分別是初始化、局部搜索、電荷量及力的計算以及粒子移動.具體步驟見文獻[1].

2 改進的類電磁機制算法

2.1 帶擾動因子的反向學習機制的初始種群的構造

反向學習是由Tizhoosh[2]提出的,之后被應用于粒子群算法[4]等多種進化算法中,取得了較好的效果.其基本思想是比較候選個體的適應度與反向個體的適應度,保留數值較小者,從而獲得當前最優值.相關定義見文獻[2].

為了增加粒子的多樣性,提高粒子向新區域學習的能力,在反向學習算法中引入了擾動因子,即在計算xi的反向點時,隨機選擇一個粒子xj作為擾動粒子,給當前粒子一定的擾動,其中i≠j且i=1,2,…,n, j=1,2,…,n.帶擾動因子的反向點定義為

式中,λ為(0,1)中的隨機數.

筆者提出的改進算法是在進化過程中,選擇一些靠近最優個體的初始粒子,從而在一定程度上可以加快算法的收斂速度.具體方法為:利用經典類電磁機制算法的初始化,隨機選取n個點作為初始化粒子,在計算每個粒子的適應值的同時,計算該粒子對應的帶擾動因子的反向粒子的適應值,通過兩者相比較,挑選適應值更小的初始粒子作為初始種群.

2.2 采用雙混沌優化機制的局部搜索

在優化設計領域中,混沌現象的遍歷性特點可以作為搜索過程中避免早熟收斂的一種優化機制.雖然單個混沌優化算法能遍歷可行域中的所有狀態,但是需進行多次遍歷搜索,且搜索次數很難確定.為了提高混沌優化的效率,筆者提出了采用雙混沌優化機制的局部搜索策略,并給出了結束條件.即通過運用兩種完全不同的混沌優化機制進行各自獨立的搜索,豐富了搜索的動力學行為,提高了搜索的充分性.

筆者選取

和

共同作為產生混沌的機制進行優化搜索.其中,式(2)是Logistic映射,數學上已經證明μ=4時系統完全處于混沌狀態;式(3)為立方映射,當a∈[3.3,4]時為混沌映射[5],經實驗測試,選a=3.5.在(0,1)之間隨機取一個值,以該值為初始點,利用Logistic映射和立方映射分別進行混沌迭代20次,將迭代過程中產生的混沌變量值記錄下來,如圖1所示.從圖1中可以看出,在相同初始值、相同迭代次數的情況下,Logistic映射和立方映射的混沌變量值在絕大多數情況下都是不同的,這就為筆者提出的基于雙混沌優化的局部搜索能避免陷入局部最優并提高解的精度奠定了理論基礎.

基于雙混沌優化的局部搜索可分為粗搜索和細搜索兩個階段.其中,粗搜索階段可避免算法過早陷入局部最優,而細搜索階段對當前最優粒子附加隨機擾動,使得算法具有精細搜索的功能.粗搜索階段的結果可以為細搜索提供有效的初始點,避免搜索陷入局部極小;細搜索階段又可以彌補粗搜索在精細搜索能力方面的不足,在一定程度上提高解的精度.

筆者提出的算法只對當前最優粒子進行局部搜索操作.具體的步驟描述如下.

(1)粗搜索階段.

步驟1 令y1=xbest,y2=xbest,其中,y1是Logistic映射的搜索變量,y2是立方映射模型的搜索變量.

步驟2 將當前最優粒子的解空間映射到兩個混沌空間,即

并以此作為混沌搜索的初始解.其中,z1和z2是上述兩映射的混沌空間變量;k為遍歷粒子各維的變量,且k=1,2,…,m.

步驟3 在局部搜索迭代次數L內,對混沌變量z1和z2進行混沌迭代,即

其中,0＜zk1＜1,-1＜zk2＜1;t是混沌迭代次數,且t=1,2,…,L.

步驟4 將混沌空間映射回解空間,即

圖1 Logistic映射和立方映射混沌迭代取點效果對比

其中,δ為局部搜索參數,δ∈[0,1].

步驟5 計算目標函數值f(y1)和f(y2).如果f(y1)＜f(y2)＜f(xbest),則置xbest=y1;如果f(y2)＜f(y1)＜f(xbest),則置xbest=y2;如果僅f(y1)＜f(xbest),則置xbest=y1;如果僅f(y2)＜f(xbest),則置xbest=y2;否則,轉步驟3,直至滿足結束條件.

(2)細搜索階段.以粗搜索階段找到的最優值xbest為中心,對其施加隨機擾動,實施細搜索階段,其中變量的含義與粗搜索階段相同.該細搜索過程可描述為:

步驟1 令y1=xbest,y2=xbest.

步驟2 將當前最優粒子的解空間映射到兩個混沌空間,即

并以此作為混沌搜索的初始解.

步驟3 在局部搜索迭代次數L內,對混沌變量z1和z2進行混沌迭代,即

步驟4 由于z2混沌變量已處于(-1,1)區間,故此步只將z1映射到(-1,1)區間,即

步驟5 將混沌空間映射回解空間,即

步驟6 計算目標函數值f(y1)和f(y2).如果f(y1)＜f(y2)＜f(xbest),則置xbest=y1;如果f(y2)＜f(y1)＜f(xbest),則置xbest=y2;如果僅f(y1)＜f(xbest),則置xbest=y1;如果僅f(y2)＜f(xbest),則置xbest=y2;否則,轉步驟3,直至滿足結束條件.

至此,基于雙混沌優化的局部搜索已完成,細搜索階段得到的計算結果xbest即為雙混沌優化方法最終的計算結果.

2.3 電荷量及力的計算

在標準類電磁機制算法中,兩粒子間的距離可能不利于粒子朝更優方向移動或導致計算溢出等問題.為此,筆者采用文獻[3]中的方法,將目標函數值歸一化,運用修正后的合力計算公式,不但不會降低最優值的精度,反而提高了算法的運行速度.

2.4 粒子的更新

在經典類電磁機制算法中,粒子的移動步長沒有考慮到粒子進化代數對移動范圍的影響.針對該問題,文獻[6]提出了使用一個自適應的移動算子來控制移動步長的方法,但其適應度函數的下降速度偏快,使粒子容易陷入局部最優,進而無法搜索到全局最優解.

在綜合考慮提高算法搜索效率并改善早熟收斂現象的情況下,筆者設計了一個自適應的移動算子,即

其中,t表示當前迭代次數,Rmax表示最大迭代次數.對當前迭代次數t進行開方操作的主要原因是為了避免上述余弦函數的值下降過快,進而導致算法陷入局部最優而無法跳出.

圖2顯示了改進的類電磁機制移動算子和文獻[6]的收斂曲線對比.從圖中可以看出,文獻[6]中的自適應函數值下降速度較快,可能會導致算法過早陷入局部最優,進而無法搜索到問題的全局最優解.而筆者設計的移動算子的下降則相對平緩,符合粒子移動的規律.

圖2 改進的類電磁機制移動算子與文獻[6]收斂效果對比

3 實驗結果及分析

為了驗證改進的類電磁機制算法的優越性,將其與文獻[7]的改進算法(Electromagnetism-like Mechanism algorithm based on the Good point set,GEM)、基本類電磁機制算法進行對比.

選取了4個簡單測試函數[8]、3個復雜測試函數[8]進行試驗,分別運行25次,記錄算法運行的最優解并計算平均值和標準差.類電磁機制算法(EM)、GEM和改進的類電磁機制算法(IEM)的仿真結果對比如表1所示.

表1 仿真結果

從表1可以看出,對于Levy函數和可行域較大的Davis函數,改進的類電磁機制算法用比標準類電磁機制算法和GEM較小的種群規模和較少的迭代次數就能找到更優的全局最優值;對于Levy函數,改進的類電磁機制算法得到的解的值更加穩定;對于Trid(5)函數,改進的類電磁機制算法用較少的迭代次數求得了比標準類電磁機制算法和GEM更好的解;對于Step函數,改進的類電磁機制算法找到了不劣于標準類電磁機制算法的全局最優值;對于有多個局部極小點的Branin函數和Shekel[S10]函數,改進的類電磁機制算法均能較有效地找到它們的全局最優值;對于Hartman[H6]函數,改進的類電磁機制算法求得了比標準類電磁機制算法和GEM更好的全局最優解.

為了驗證該算法能成功地用于高維函數,選取了5個典型的函數[9],分別使用標準類電磁機制算法(EM)、GEM和改進的類電磁機制算法(IEM)進行了仿真,并對仿真結果進行了比較.其中,5個函數的維度均為30,種群規模分別為40、10、10、10、10,最大迭代次數分別為500、1 000、1 000、1 000、1 000,分別運行20次,測試結果如表2所示.

表2 高維函數測試結果

表2驗證了改進的類電磁機制算法可成功用于不可微、高維、多峰甚至是病態的函數,不僅求得了這些函數的全局最優值,也明顯地提高了解的精度.

4 結束語

從類電磁機制算法的機理出發,分析了其優化原理.針對原算法中存在的隨機生成初始種群多樣性差、局部搜索隨機性強、移動公式效率低等問題,提出了一種改進的類電磁機制算法.通過引入帶擾動因子的反向學習機制構造初始種群,提高了算法的搜索性能;采用雙混沌優化機制作為局部搜索策略,有效地避免了算法的早熟收斂,并使算法能得到更精確的全局最優解;最后,考慮了進化代數影響,設計了新的自適應移動算子,提高了算法的尋優效率.仿真結果表明,改進的類電磁機制算法在求解無約束優化問題時,在解的精度上取得了比標準類電磁機制算法和GEM算法更好的效果,平均提升20%～30%.針對高維復雜函數,該算法在尋優速度方面還有待改進.

[1]Birbil S,Fang S C.An Electromagnetism-like Mechanism for Global Optimization[J].Journal of Global Optimization, 2003,25(3):263-282.

[2]Tizhoosh H R.Opposition-based Learning:a New Scheme for Machine Intelligence[C]//Proceedings of International Conference on Computational Intelligence for Modeling,Control and Automation.Piscataway:IEEE,2005:695-701.

[3]王雙記.類電磁機制算法的改進與應用[D].西安:西安電子科技大學,2012.

[4]Wang H,Liu H,Liu Y,et al.Opposition-based Particle Swarm Algorithm with Cauchy Mutation[C]//IEEE Congress on Evolutionary Computation.Piscataway:IEEE,2007:4750-4756.

[5]修春波,劉向東,張宇河.雙混沌機制優化方法及其應用[J].控制與決策,2003,18(6):724-726. Xiu Chunbo,Liu Xiangdong,Zhang Yuhe.Optimization Algorithm Using Two Kinds of Chaos and Its Application[J]. Control and Decision,2003,18(6):724-726.

[6]龍秀萍.類電磁機制算法研究[D].西安:西安電子科技大學,2012.

[7]姜建國,龍秀萍,田旻,等.一種基于佳點集的類電磁機制算法[J].西安電子科技大學學報,2011,38(6):167-172. Jiang Jianguo,Long Xiuping,Tian Min,et al.Electromagnetism-like Mechanism Algorithm Based on the Good Point Set [J].Journal of Xidian University,2011,38(6):167-172.

[8]韓麗霞.自然啟發的優化算法及其應用研究[D].西安:西安電子科技大學,2009.

[9]Wang Yuping,Dang Chuangyin.An Evolutionary Algorithm for Global Optimization Based on Level-set Evolution and Latin Squares[J].IEEE Transactions on Evolutionary Computation,2007,11(5):579-595.

(編輯:郭 華)

Electromagnetism-like mechanism algorithm via dual chaotic search

JIANG Jianguo,LIU Mengnan,LIU Yongqing, SU Qian,ZHANG Liyuan
(School of Computer Science and Technology,Xidian Univ.,Xi’an 710071,China)

An improved Electromagnetism-like mechanism algorithm is proposed to overcome the drawbacks of the original EM algorithm,such as strong randomness of the initial population,low ability for local search and low efficiency in the movement according to the total force.The new algorithm generates the initial population with the disturbance factor and opposite learning mechanism,improves the local search algorithm with the double chaotic search method,and calculates the total force between particles with the modified equation.Besides,the algorithm is used to design an adaptive move operator for updating the locations of those particles.Experimental results indicate that the proposed algorithm has a better convergence effect and a higher solution accuracy.

electromagnetism-like mechanism algorithm;opposite learning mechanism;disturbance;dual chaotic search;global optimization

TP301.6

A

1001-2400(2014)05-0079-05

2013-03-12< class="emphasis_bold">網絡出版時間:

時間:2014-01-12

國家部委基礎科研計劃資助項目(A1120132007)

姜建國(1956-),男,教授,E-mail:jgjiang@mail.xidian.edu.cn.

http://www.cnki.net/kcms/doi/10.3969/j.issn.1001-2400.2014.05.014.html

10.3969/j.issn.1001-2400.2014.05.014