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

姜建國,劉夢(mèng)楠,劉永青,蘇 仟,張麗媛

(西安電子科技大學(xué)計(jì)算機(jī)學(xué)院,陜西西安 710071)

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

姜建國,劉夢(mèng)楠,劉永青,蘇 仟,張麗媛

(西安電子科技大學(xué)計(jì)算機(jī)學(xué)院,陜西西安 710071)

針對(duì)現(xiàn)有算法中初始種群隨機(jī)性強(qiáng)、局部搜索能力差、移動(dòng)公式效率低等問題,提出了一種改進(jìn)的類電磁機(jī)制算法.結(jié)合反向?qū)W習(xí)理論,引入帶擾動(dòng)因子的反向?qū)W習(xí)機(jī)制構(gòu)造初始種群;提出了一種雙混沌優(yōu)化機(jī)制用于局部搜索;運(yùn)用改進(jìn)后的公式計(jì)算粒子之間的合力;設(shè)計(jì)了一種自適應(yīng)移動(dòng)算子來更新粒子.實(shí)驗(yàn)結(jié)果表明,改進(jìn)后的算法具有更好的收斂效果和更高的求解精度.

類電磁機(jī)制算法;反向?qū)W習(xí)機(jī)制;擾動(dòng);雙混沌;全局優(yōu)化

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

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

1 經(jīng)典類電磁機(jī)制算法

類電磁機(jī)制算法的實(shí)現(xiàn)主要由4個(gè)階段完成,分別是初始化、局部搜索、電荷量及力的計(jì)算以及粒子移動(dòng).具體步驟見文獻(xiàn)[1].

2 改進(jìn)的類電磁機(jī)制算法

2.1 帶擾動(dòng)因子的反向?qū)W習(xí)機(jī)制的初始種群的構(gòu)造

反向?qū)W習(xí)是由Tizhoosh[2]提出的,之后被應(yīng)用于粒子群算法[4]等多種進(jìn)化算法中,取得了較好的效果.其基本思想是比較候選個(gè)體的適應(yīng)度與反向個(gè)體的適應(yīng)度,保留數(shù)值較小者,從而獲得當(dāng)前最優(yōu)值.相關(guān)定義見文獻(xiàn)[2].

為了增加粒子的多樣性,提高粒子向新區(qū)域?qū)W習(xí)的能力,在反向?qū)W習(xí)算法中引入了擾動(dòng)因子,即在計(jì)算xi的反向點(diǎn)時(shí),隨機(jī)選擇一個(gè)粒子xj作為擾動(dòng)粒子,給當(dāng)前粒子一定的擾動(dòng),其中i≠j且i=1,2,…,n, j=1,2,…,n.帶擾動(dòng)因子的反向點(diǎn)定義為

式中,λ為(0,1)中的隨機(jī)數(shù).

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

2.2 采用雙混沌優(yōu)化機(jī)制的局部搜索

在優(yōu)化設(shè)計(jì)領(lǐng)域中,混沌現(xiàn)象的遍歷性特點(diǎn)可以作為搜索過程中避免早熟收斂的一種優(yōu)化機(jī)制.雖然單個(gè)混沌優(yōu)化算法能遍歷可行域中的所有狀態(tài),但是需進(jìn)行多次遍歷搜索,且搜索次數(shù)很難確定.為了提高混沌優(yōu)化的效率,筆者提出了采用雙混沌優(yōu)化機(jī)制的局部搜索策略,并給出了結(jié)束條件.即通過運(yùn)用兩種完全不同的混沌優(yōu)化機(jī)制進(jìn)行各自獨(dú)立的搜索,豐富了搜索的動(dòng)力學(xué)行為,提高了搜索的充分性.

筆者選取

和

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

基于雙混沌優(yōu)化的局部搜索可分為粗搜索和細(xì)搜索兩個(gè)階段.其中,粗搜索階段可避免算法過早陷入局部最優(yōu),而細(xì)搜索階段對(duì)當(dāng)前最優(yōu)粒子附加隨機(jī)擾動(dòng),使得算法具有精細(xì)搜索的功能.粗搜索階段的結(jié)果可以為細(xì)搜索提供有效的初始點(diǎn),避免搜索陷入局部極小;細(xì)搜索階段又可以彌補(bǔ)粗搜索在精細(xì)搜索能力方面的不足,在一定程度上提高解的精度.

筆者提出的算法只對(duì)當(dāng)前最優(yōu)粒子進(jìn)行局部搜索操作.具體的步驟描述如下.

(1)粗搜索階段.

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

步驟2 將當(dāng)前最優(yōu)粒子的解空間映射到兩個(gè)混沌空間,即

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

步驟3 在局部搜索迭代次數(shù)L內(nèi),對(duì)混沌變量z1和z2進(jìn)行混沌迭代,即

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

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

圖1 Logistic映射和立方映射混沌迭代取點(diǎn)效果對(duì)比

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

步驟5 計(jì)算目標(biāo)函數(shù)值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;否則,轉(zhuǎn)步驟3,直至滿足結(jié)束條件.

(2)細(xì)搜索階段.以粗搜索階段找到的最優(yōu)值xbest為中心,對(duì)其施加隨機(jī)擾動(dòng),實(shí)施細(xì)搜索階段,其中變量的含義與粗搜索階段相同.該細(xì)搜索過程可描述為:

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

步驟2 將當(dāng)前最優(yōu)粒子的解空間映射到兩個(gè)混沌空間,即

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

步驟3 在局部搜索迭代次數(shù)L內(nèi),對(duì)混沌變量z1和z2進(jìn)行混沌迭代,即

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

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

步驟6 計(jì)算目標(biāo)函數(shù)值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;否則,轉(zhuǎn)步驟3,直至滿足結(jié)束條件.

至此,基于雙混沌優(yōu)化的局部搜索已完成,細(xì)搜索階段得到的計(jì)算結(jié)果xbest即為雙混沌優(yōu)化方法最終的計(jì)算結(jié)果.

2.3 電荷量及力的計(jì)算

在標(biāo)準(zhǔn)類電磁機(jī)制算法中,兩粒子間的距離可能不利于粒子朝更優(yōu)方向移動(dòng)或?qū)е掠?jì)算溢出等問題.為此,筆者采用文獻(xiàn)[3]中的方法,將目標(biāo)函數(shù)值歸一化,運(yùn)用修正后的合力計(jì)算公式,不但不會(huì)降低最優(yōu)值的精度,反而提高了算法的運(yùn)行速度.

2.4 粒子的更新

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

在綜合考慮提高算法搜索效率并改善早熟收斂現(xiàn)象的情況下,筆者設(shè)計(jì)了一個(gè)自適應(yīng)的移動(dòng)算子,即

其中,t表示當(dāng)前迭代次數(shù),Rmax表示最大迭代次數(shù).對(duì)當(dāng)前迭代次數(shù)t進(jìn)行開方操作的主要原因是為了避免上述余弦函數(shù)的值下降過快,進(jìn)而導(dǎo)致算法陷入局部最優(yōu)而無法跳出.

圖2顯示了改進(jìn)的類電磁機(jī)制移動(dòng)算子和文獻(xiàn)[6]的收斂曲線對(duì)比.從圖中可以看出,文獻(xiàn)[6]中的自適應(yīng)函數(shù)值下降速度較快,可能會(huì)導(dǎo)致算法過早陷入局部最優(yōu),進(jìn)而無法搜索到問題的全局最優(yōu)解.而筆者設(shè)計(jì)的移動(dòng)算子的下降則相對(duì)平緩,符合粒子移動(dòng)的規(guī)律.

圖2 改進(jìn)的類電磁機(jī)制移動(dòng)算子與文獻(xiàn)[6]收斂效果對(duì)比

3 實(shí)驗(yàn)結(jié)果及分析

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

選取了4個(gè)簡單測試函數(shù)[8]、3個(gè)復(fù)雜測試函數(shù)[8]進(jìn)行試驗(yàn),分別運(yùn)行25次,記錄算法運(yùn)行的最優(yōu)解并計(jì)算平均值和標(biāo)準(zhǔn)差.類電磁機(jī)制算法(EM)、GEM和改進(jìn)的類電磁機(jī)制算法(IEM)的仿真結(jié)果對(duì)比如表1所示.

表1 仿真結(jié)果

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

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

表2 高維函數(shù)測試結(jié)果

表2驗(yàn)證了改進(jìn)的類電磁機(jī)制算法可成功用于不可微、高維、多峰甚至是病態(tài)的函數(shù),不僅求得了這些函數(shù)的全局最優(yōu)值,也明顯地提高了解的精度.

4 結(jié)束語

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

[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]王雙記.類電磁機(jī)制算法的改進(jìn)與應(yīng)用[D].西安:西安電子科技大學(xué),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ī)制優(yōu)化方法及其應(yīng)用[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]龍秀萍.類電磁機(jī)制算法研究[D].西安:西安電子科技大學(xué),2012.

[7]姜建國,龍秀萍,田旻,等.一種基于佳點(diǎn)集的類電磁機(jī)制算法[J].西安電子科技大學(xué)學(xué)報(bào),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]韓麗霞.自然啟發(fā)的優(yōu)化算法及其應(yīng)用研究[D].西安:西安電子科技大學(xué),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">網(wǎng)絡(luò)出版時(shí)間:

時(shí)間:2014-01-12

國家部委基礎(chǔ)科研計(jì)劃資助項(xiàng)目(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