羅　萍，劉　偉，周述波

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

?

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

羅萍，劉偉，周述波

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

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

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

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

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

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

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

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

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

(1)

(2)

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

萬有引力常量定義為

(3)

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

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

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

(4)

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

(5)

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

(6)

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

然后根據(jù)牛頓運(yùn)動規(guī)律，計算出在時間t時物質(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)行過程中，如果某物質(zhì)找到了一個當(dāng)前最優(yōu)位置，則其他物質(zhì)會迅速向這個最優(yōu)位置聚集. 如果這個最優(yōu)位置是一個局部最優(yōu)點(diǎn)，萬有引力算法就無法在解空間內(nèi)重新搜索，出現(xiàn)停滯或早熟收斂現(xiàn)象.

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

(9)

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

1.3混沌變異

混沌指在一個確定的系統(tǒng)中發(fā)生的不規(guī)則的運(yùn)動，行為主要表現(xiàn)為隨機(jī)性、規(guī)律性、 遍歷性.由于執(zhí)行簡單并且能夠有效避免陷入局部極值，因此混沌搜索已成為一種新的局部搜索技術(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)平均粒距小于或等于給定值時，算法陷入早熟收斂狀態(tài),對最優(yōu)物質(zhì)進(jìn)行混沌搜索，引導(dǎo)物質(zhì)快速跳出局部最優(yōu)，避免陷入早熟收斂.當(dāng)物質(zhì)的平均粒距大于給定值時，對最差物質(zhì)進(jìn)行混沌搜索，產(chǎn)生一個優(yōu)于最差物質(zhì)的位置,來替換最差物質(zhì)，加快算法收斂速度.

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

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

(11)

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

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

(12)

1.4越界處理

考慮到本文中的變異方法可能產(chǎn)生一些越界的物質(zhì)，對越界物質(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個物質(zhì)的位置和速度.

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

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

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

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

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

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

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

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

為驗證改進(jìn)后算法的有效性，本文選擇了5個標(biāo)準(zhǔn)的測試函數(shù)與標(biāo)準(zhǔn)萬有引力算法(SGSA)和混沌萬有引力算法(CGSA)作比較，如表1所示.本文改進(jìn)后的算法簡稱ACGSA.5個測試函數(shù)中f1～f3為單模測試函數(shù),f4～f5為多模測試函數(shù).在實(shí)驗中,種群規(guī)模N=30,最大迭代次數(shù)T=50,平均粒距給定值d0=0.003,萬有引力常量初值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　測試函數(shù)

表2　計算結(jié)果

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

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

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

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

3結(jié)語

本文給出一種自適應(yīng)的混沌變異萬有引力優(yōu)化算法(ACGSA算法).該算法在運(yùn)行的前期可以經(jīng)過變異，加快算法收斂速度；在算法運(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)變異的萬有引力算法[J].廣東工業(yè)大學(xué)學(xué)報, 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)度問題的萬有引力收索算法[J].智能系統(tǒng)學(xué)報,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] 劉勇,馬良.非線性極大極小問題的混沌萬有引力搜索算法求解[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] 蔣悅,沈冬梅,趙彥,等.基于引力搜索和分布估計的混合離散優(yōu)化算法[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] 徐耀群,王長舉.一種萬有引力算法及其收斂性分析[J].哈爾濱商業(yè)大學(xué)學(xué)報(自然版).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-均值算法和萬有引力算法求解模糊聚類問題[J].智能系統(tǒng)學(xué)報，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ī)科學(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] 張維平,任雪飛,李國強(qiáng),等.改進(jìn)的萬有引力搜索算法在函數(shù)優(yōu)化中的應(yīng)用[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é)報,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

中圖分類號:TP301.6

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

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

doi:10.3969/j.issn.1007- 7162.2016.01.011

作者簡介:羅萍(1987-)，女，碩士研究生，主要研究方向為智能計算及其應(yīng)用.

基金項目:國家自然科學(xué)基金資助項目(60974077)

收稿日期:2014- 09- 23