羅　萍，劉　偉，周述波

(廣東工業(yè)大學(xué) 應(yīng)用數(shù)學(xué)學(xué)院，廣東 廣州 510520)

?

自適應(yīng)混沌變異的萬(wàn)有引力搜索算法

羅萍，劉偉，周述波

(廣東工業(yè)大學(xué) 應(yīng)用數(shù)學(xué)學(xué)院，廣東 廣州 510520)

摘要:通過(guò)引入平均粒距和混沌搜索變異，提高萬(wàn)有引力算法的局部搜索能力,增加物質(zhì)種群的多樣性.并且對(duì)變異后不可行的物質(zhì)采用邊界變異約束處理.實(shí)驗(yàn)結(jié)果表明,新算法收斂精度較高,收斂速度較快,能比較有效地避免早熟收斂問(wèn)題.

關(guān)鍵詞:萬(wàn)有引力算法； 混沌； 平均粒距； 邊界變異

萬(wàn)有引力算法(GSA)[1]在2009年首次由Rashedi等人提出，其思想是基于物理學(xué)中宇宙間的萬(wàn)有引力定律和運(yùn)動(dòng)規(guī)律而得出的.基于萬(wàn)有引力算法的優(yōu)化算法得到廣泛關(guān)注.受“分裂”思想的啟發(fā), S.Sarafrazi等[2]提出一種具有分裂功能的萬(wàn)有引力算法.徐懷祥等[3]引入一個(gè)變異算子使算法跳出局部最優(yōu)，給出了一種改進(jìn)的萬(wàn)有引力算法.谷文祥等[4]將萬(wàn)有引力算法運(yùn)用于解決流水線的調(diào)度問(wèn)題. 為解決非線性的極大極小值問(wèn)題，馬良等[5]提出一種新的混沌萬(wàn)有引力算法，對(duì)當(dāng)前的最優(yōu)位置利用混沌優(yōu)化進(jìn)行比較細(xì)密的搜索. Nihan Kazak和Alpaslan Duysak針對(duì)標(biāo)準(zhǔn)引力算法的收斂速度比較慢的缺點(diǎn)，提出了成員衛(wèi)星算法[6]，每個(gè)物質(zhì)都有各自的幾個(gè)衛(wèi)星，衛(wèi)星和成員的同步進(jìn)化，保證了此算法在當(dāng)代最優(yōu)值周圍的更為精細(xì)的搜索. 為提高引力算法的局部收斂能力，一些學(xué)者將引力算法與其他算法結(jié)合，提出了許多的混合引力算法[7-10]. Zahir[11]提出的模糊萬(wàn)有引力算法 ，給出了數(shù)據(jù)挖掘的新途徑.許多學(xué)者通過(guò)引入各種變異算子[12-15]，增加物質(zhì)種群的多樣性，提高算法的搜索效率.

上述算法都存在收斂速度慢,求解精度低等問(wèn)題.針對(duì)這些問(wèn)題,本文提出了一種根據(jù)平均粒距大小來(lái)判斷算法收斂程度,對(duì)物質(zhì)群中的最優(yōu)位置和最差位置進(jìn)行自適應(yīng)混沌變異的萬(wàn)有引力算法，保持和提高函數(shù)求解精度，同時(shí)提高算法的收斂速度.該算法的主要思想是在進(jìn)化的過(guò)程中引入平均粒距，如果平均粒距大于給定值，說(shuō)明算法處于初期，則對(duì)最差物質(zhì)的位置進(jìn)行混沌變異，加快算法收斂速度.如果平均粒距小于或者等于給定值，即算法處于中后期，陷入局部最優(yōu)時(shí)，則在最優(yōu)物質(zhì)的附近進(jìn)行混沌變異，增加物質(zhì)種群的多樣性，跳出局部收斂.如果變異產(chǎn)生出來(lái)的新的物質(zhì)優(yōu)于當(dāng)前的最優(yōu)物質(zhì)，則替換原有的最優(yōu)物質(zhì)繼續(xù)進(jìn)化.測(cè)試函數(shù)的實(shí)驗(yàn)結(jié)果表明了該算法的有效性.

1改進(jìn)的引力算法

1.1標(biāo)準(zhǔn)萬(wàn)有引力算法

在GSA算法模型中，優(yōu)化問(wèn)題的每個(gè)解與搜索空間中的一個(gè)物質(zhì)相對(duì)應(yīng)，每個(gè)物質(zhì)都有4個(gè)特點(diǎn)：位置、施力物、受力物、慣性質(zhì)量，而物質(zhì)的位置就是優(yōu)化問(wèn)題的解.標(biāo)準(zhǔn)GSA的算法過(guò)程如下：

首先利用式(1)和式(2)計(jì)算出每個(gè)物質(zhì)的慣性質(zhì)量Mi(t).

(1)

(2)

其中valuei(t)表示物質(zhì)i在第t代的適應(yīng)值，xbest(t)(t)，xworst(t)分別表示第t代種群中最好和最壞的適應(yīng)值.

萬(wàn)有引力常量定義為

(3)

其中，G0是一個(gè)初始值，α為一個(gè)常數(shù)，t是當(dāng)前代數(shù)，T是最大的迭代次數(shù).對(duì)于求最小值問(wèn)題xbest(t),xworst(t)的定義為

xbest(t)=minj={1,2,3,…,N}valuej(t)，

xworst(t)=maxj={1,2,3…,N}valuej(t).

(4)

其次，計(jì)算各個(gè)物質(zhì)在每一維間上相互之間的引力.物質(zhì)j對(duì)物質(zhì)i作用的第d維萬(wàn)有引力定義為

(5)

其中，ε是一個(gè)極小的值，Rij(t)表示物質(zhì)i和物質(zhì)j之間的歐氏距離，由此可得出物質(zhì)i在第d維所受到的合力為

(6)

Randj為介于0和1之間的隨機(jī)數(shù)，Kbest從K0到1隨著時(shí)間線性減小，使得算法到最后在搜索空間中只有最好的解的那個(gè)物質(zhì)去作用于其他的物質(zhì).

然后根據(jù)牛頓運(yùn)動(dòng)規(guī)律，計(jì)算出在時(shí)間t時(shí)物質(zhì)i在第d維的加速度為

(7)

最后物質(zhì)的速度和位置更新為

(8)

其中，randi為0和1之間的隨機(jī)數(shù)，它可使搜索變得隨機(jī)化.

1.2群體的平均粒距

由于在標(biāo)準(zhǔn)GSA算法進(jìn)程中，物質(zhì)種群是根據(jù)追隨種群最優(yōu)位置進(jìn)行更新的，所以這種算法在運(yùn)行過(guò)程中，如果某物質(zhì)找到了一個(gè)當(dāng)前最優(yōu)位置，則其他物質(zhì)會(huì)迅速向這個(gè)最優(yōu)位置聚集. 如果這個(gè)最優(yōu)位置是一個(gè)局部最優(yōu)點(diǎn)，萬(wàn)有引力算法就無(wú)法在解空間內(nèi)重新搜索，出現(xiàn)停滯或早熟收斂現(xiàn)象.

試驗(yàn)證明，GSA中無(wú)論是全局收斂還是早熟收斂，萬(wàn)有引力算法中的物質(zhì)都會(huì)有 “聚集”的現(xiàn)象，此時(shí)非常缺乏種群的多樣性.種群多樣性的缺乏是導(dǎo)致過(guò)早收斂以及停滯現(xiàn)象的重要原因.

(9)

平均粒距說(shuō)明了在單位搜索空間上物質(zhì)的分布情況，描述了種群中各個(gè)物質(zhì)間彼此相互分布的離散程度，D(t)越小，表示種群越集中.即可能陷入局部收斂.

1.3混沌變異

混沌指在一個(gè)確定的系統(tǒng)中發(fā)生的不規(guī)則的運(yùn)動(dòng)，行為主要表現(xiàn)為隨機(jī)性、規(guī)律性、 遍歷性.由于執(zhí)行簡(jiǎn)單并且能夠有效避免陷入局部極值，因此混沌搜索已成為一種新的局部搜索技術(shù).

本文引入Logistic混沌方程，其表達(dá)式為

xi+1=αxi(1-xi)，i=1,2…N，α=4.0.

(10)

由于GSA算法本身的局限性使得標(biāo)準(zhǔn)的引力算法比較容易陷入局部最優(yōu)，而混沌的遍歷性、不重復(fù)性，可以在一定的搜索空間內(nèi)跳出局部收斂，因此在GSA算法中引入混沌搜索，獲得全局最優(yōu)解就成為可能.自適應(yīng)混沌變異GSA算法的主要思想是在標(biāo)準(zhǔn)GSA算法的基礎(chǔ)上，引入平均粒矩，當(dāng)平均粒距小于或等于給定值時(shí)，算法陷入早熟收斂狀態(tài),對(duì)最優(yōu)物質(zhì)進(jìn)行混沌搜索，引導(dǎo)物質(zhì)快速跳出局部最優(yōu)，避免陷入早熟收斂.當(dāng)物質(zhì)的平均粒距大于給定值時(shí)，對(duì)最差物質(zhì)進(jìn)行混沌搜索，產(chǎn)生一個(gè)優(yōu)于最差物質(zhì)的位置,來(lái)替換最差物質(zhì)，加快算法收斂速度.

當(dāng)算法的平均粒距大于給定值d0時(shí)，即在算法初期,對(duì)最差物質(zhì)的位置由下式變異更新.

xi(t)=αxworst(t)(1-xworst(t)),

(11)

當(dāng)算法的平均粒距小于或等于給定值d0時(shí)，此時(shí)算法出現(xiàn)早熟收斂，對(duì)最優(yōu)物質(zhì)的位置由下式變異更新.

xj(t)=αxbest(t)(1-xbest(t)),

(12)

1.4越界處理

考慮到本文中的變異方法可能產(chǎn)生一些越界的物質(zhì)，對(duì)越界物質(zhì)采用邊界變異的方式進(jìn)行處理.

ifx(p)

x(p)=x_min

endif

ifx(p)>x_max

x(p)=x_max

endif

其中x_max和x_min為物質(zhì)在第p維位置的上下界，x(p)為變異后物質(zhì)第p維的位置.

1.5算法步驟

本文算法主要步驟如下.

步驟1：設(shè)定算法參數(shù),包括種群平均粒距給定值d0等,在解空間隨機(jī)初始化N個(gè)物質(zhì)的位置和速度.

步驟2：計(jì)算物質(zhì)的函數(shù)適應(yīng)值valuei(t).

步驟3：利用式(3)～(4)計(jì)算更新每個(gè)物質(zhì)的xworst(t)和xbest(t).

步驟4：利用式(9)計(jì)算群體的平均粒距D(t).

步驟7：利用式(1)、(2)計(jì)算每個(gè)物質(zhì)的質(zhì)量Mi(t).

步驟9：根據(jù)式(7)、(8)計(jì)算物質(zhì)的加速度，速度以及更新種群中物質(zhì)的位置.

步驟10：如果達(dá)到了結(jié)束的條件,最大迭代次數(shù)或者更新的位置足夠好，則迭代結(jié)束，否則返回步驟2.

2數(shù)值實(shí)驗(yàn)結(jié)果及分析

2.1測(cè)試函數(shù)與條件

為驗(yàn)證改進(jìn)后算法的有效性，本文選擇了5個(gè)標(biāo)準(zhǔn)的測(cè)試函數(shù)與標(biāo)準(zhǔn)萬(wàn)有引力算法(SGSA)和混沌萬(wàn)有引力算法(CGSA)作比較，如表1所示.本文改進(jìn)后的算法簡(jiǎn)稱ACGSA.5個(gè)測(cè)試函數(shù)中f1～f3為單模測(cè)試函數(shù),f4～f5為多模測(cè)試函數(shù).在實(shí)驗(yàn)中,種群規(guī)模N=30,最大迭代次數(shù)T=50,平均粒距給定值d0=0.003,萬(wàn)有引力常量初值G0=100,最大速度v_max=[3,3,3],最小速度v_min=[-3,-3,-3],K0=100.表2為3種算法獨(dú)立運(yùn)行50次,得到的最優(yōu)值(BSF),最優(yōu)值的平均值(ABSF)以及最優(yōu)值的標(biāo)準(zhǔn)方差(STDBSF)的比較結(jié)果.

表1　測(cè)試函數(shù)

表2　計(jì)算結(jié)果

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

對(duì)于單峰函數(shù)f1～f3,由圖1可以發(fā)現(xiàn)在這3種算法中ACGSA均能準(zhǔn)確且快速地找到函數(shù)的最優(yōu)解.同時(shí)從表2的數(shù)據(jù)結(jié)果來(lái)看,ACGSA算法搜索到的最優(yōu)值精度都比SGSA和CGSA高.由標(biāo)準(zhǔn)方差來(lái)看,ACGSA算法的穩(wěn)定性也是最好的.

圖1　f1～f5的進(jìn)化曲線

對(duì)于多峰函數(shù)f4～f5,其他兩種算法都快速地陷入局部最優(yōu),出現(xiàn)停滯現(xiàn)象，而ACGSA由于引入混沌搜索,算法的局部和全局搜索能力的調(diào)整更為靈活，提高了搜索過(guò)程的效率，又增加了種群的多樣性,使算法繼續(xù)在解空間搜索，逐步收斂到精度更高的全局最優(yōu)值.同時(shí)表2中3種算法的標(biāo)準(zhǔn)方差的比較結(jié)果也反映出該算法在處理多峰問(wèn)題時(shí)具有較好的穩(wěn)定性.這說(shuō)明隨著問(wèn)題復(fù)雜程度的增加,ACGSA的優(yōu)化效果沒有減弱.

3結(jié)語(yǔ)

本文給出一種自適應(yīng)的混沌變異萬(wàn)有引力優(yōu)化算法(ACGSA算法).該算法在運(yùn)行的前期可以經(jīng)過(guò)變異，加快算法收斂速度；在算法運(yùn)行的后期可以跳出局部收斂，增加種群的多樣性，并在全局最優(yōu)區(qū)域進(jìn)行較為細(xì)密的搜索.本文算法搜索速度和收斂精度比標(biāo)準(zhǔn) GSA 算法及CGSA算法有較大提高，并且能夠以更快的速度找到全局最優(yōu)解.

參考文獻(xiàn)：

[1]RASHEDI E,NEZAMABADI-POUR H, SARYAZDI S.GSA:a gravitational search algoritm[J].Information Sciences, 2009, 179(13):2232-2248.

[2] SARAFRAZI S, NEZAMABADI-POUR H, SARYAZDI S.Disruption: a new operator in gravitational search algorithm[J].Scientia Iranica D, 2011, 18(3):539-548.

[3] 徐懷祥，劉偉.基于最優(yōu)變異的萬(wàn)有引力算法[J].廣東工業(yè)大學(xué)學(xué)報(bào), 2014, 31(1):46-50.

XU H X, LIU W.The gravitational algorithm based on the optimal mutation[J].Journal of Guangdong University of Technology, 2014, 31(1):46-50.

[4] 谷文祥，李向濤，朱磊，等.求解求解流水線調(diào)度問(wèn)題的萬(wàn)有引力收索算法[J].智能系統(tǒng)學(xué)報(bào),2010,5(5):411-418.

GU W X,LI X T,ZHU L,et al.A gravitationnal search algorithm for slow shop scheduling[J].CAAI Transactions on Intelligent System,2010,5(5):411-418.

[5] 劉勇,馬良.非線性極大極小問(wèn)題的混沌萬(wàn)有引力搜索算法求解[J].計(jì)算機(jī)應(yīng)用研究,2012, 29(1):47-48.

LIU Y, MA L.Solving nonlinear minimax problems based on chaos gravitional search algorithm[J].Application Research of Computers, 2012, 29(1):47-48.

[6] KAZAK N, DUYSAK A.Modified gravitational search algorithm[C]∥ Innovations in Intelligent Systems and Applications, International Symposium on. Turkey:IEEE,2012:1589-1597.

[7] MIRJALILI S,HASHIM S Z M.A New Hybrid PSOGSA Algorithm for Function Optimization[C]∥ Computer and Information Application (ICCIA), 2010 International Conference on.Tianjin:IEEE,2010:374-377.

[8] 蔣悅,沈冬梅,趙彥,等.基于引力搜索和分布估計(jì)的混合離散優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用.2014,34(7):2074-2079.

JIANG Y,SHEN D M,ZHAO Y,et al.Hybrid discrete optimization algorithm based on gravity search and estimate of distribution[J].Journal of Computer Application，2014,34(7):2074-2079.

[9] 徐耀群,王長(zhǎng)舉.一種萬(wàn)有引力算法及其收斂性分析[J].哈爾濱商業(yè)大學(xué)學(xué)報(bào)(自然版).2013,29(1):63-67.

XU Y Q,WANG C J.Universal gravitation optimization and its convergence analysis[J].Journal of Harbin University of Commerce(Natural Sciences Edition)，2013,29(1):63-67.

[10]谷文祥,郭麗萍,殷明浩.模糊c-均值算法和萬(wàn)有引力算法求解模糊聚類問(wèn)題[J].智能系統(tǒng)學(xué)報(bào)，2011,6(6):520-524.

GU W X,GUO L P,YIN M H.A solution for a fuzzy clustering problem by applying fuzzy c-means algorithm and gravitational search algorithm[J].CAAI Transactions on Intelligent Systems,2011,6(6):520-524.

[11] ZAHIRI S H.Fuzzy gravitational search algorithm an approch for data mining[J].Iranian Journal of Fuzzy Systems,2012,9(1),21-37.

[12] 徐遙,安亞靜,王士同.基于三角范數(shù)的引力搜索算法分析[J].計(jì)算機(jī)科學(xué),2011,38(11):225-229.

Xu Y, AN Y J,WANG S T.Analyzing of gravitational search algorithm based on triangular norms[J].Computer Science,2011,38(11):225-229.

[13] SOLEIMANPOUR-MOGHADAM M, NEZAMABADI-POUR H.An improved quantum behaved gravitational search algorithm[C]∥ Electrical Engineering (ICEE), 2012 20th Iranian Conference on. Tehran:IEEE,2012:711-714.

[14] 張維平,任雪飛,李國(guó)強(qiáng),等.改進(jìn)的萬(wàn)有引力搜索算法在函數(shù)優(yōu)化中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用,2013,33(5):1317-1320.

ZHANG W P, REN X F,LI G Q,et al.Improved gravitation search algorithm and its application to function optimization[J].Journal of Computer Application,2013,33(5):1317-1320.

[15] 袁建濤,周慧,郭陳江,等.基于改進(jìn)引力搜索算法的陣列天線波束賦形[J].微波學(xué)報(bào),2014,30(3):50-53.

YUAN J T,ZHOU H,GUO C J,et al.Beam shaping for antenna based on improved gravitational search algorithm[J].Journal of Microwaves,2014,30(3):50-53.

Gravitational Search Algorithm of Adaptive Chaos Mutation

Luo Ping, Liu Wei, Zhou Shu-bo

(School of Applied Mathematics, Guangdong University of Technology, Guangzhou 510520, China)

Abstract:This paper proposes a gravitational search algorithm of adaptive chaos mutation. By introducing the average distance and the chaotic search variation, this paper improves local search ability of gravity algorithm, increases the diversity of substance population and treats the unfeasible materials after mutation by boundary variation constraint. The results show that the new algorithm has the advantages of high precision and fast rate in convergence which can effectively avoid premature convergence. And the variation of the material after not feasible material treated by boundary variationconstraint.

Key words:gravitational search algorithm; chaos; average particle distance; boundary mutation

中圖分類號(hào):TP301.6

文獻(xiàn)標(biāo)志碼:A

文章編號(hào):1007-7162(2016)01- 0057- 05

doi:10.3969/j.issn.1007- 7162.2016.01.011

作者簡(jiǎn)介:羅萍(1987-)，女，碩士研究生，主要研究方向?yàn)橹悄苡?jì)算及其應(yīng)用.

基金項(xiàng)目:國(guó)家自然科學(xué)基金資助項(xiàng)目(60974077)

收稿日期:2014- 09- 23