基于萬(wàn)有引力思想的遺傳算子

李松芳，劉 偉

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

遺傳算法是一種有效的智能優(yōu)化算法，它主要借鑒生物學(xué)中的生物進(jìn)化理論.經(jīng)過(guò)幾十年的發(fā)展，遺傳算法以其簡(jiǎn)單、可操作性強(qiáng)、魯棒性強(qiáng)和潛在的并行性特點(diǎn)，被應(yīng)用于工業(yè)工程的諸多領(lǐng)域［1-4］.同時(shí)，傳統(tǒng)遺傳算法也暴露出易進(jìn)入局部最優(yōu)和隨機(jī)波動(dòng)等現(xiàn)象，導(dǎo)致算法的性能較差.一般情況下，算法要達(dá)到更高的收斂精度，需要增加較長(zhǎng)的搜索時(shí)間，這些因素影響了遺傳算法的發(fā)展和實(shí)際應(yīng)用［4-7］.

如何克服遺傳算法的不足，一直都是研究的熱點(diǎn).其中，遺傳算子的改進(jìn)是一個(gè)重要方面:Jong De K A［7］針對(duì)單點(diǎn)交叉提出了多點(diǎn)交叉.Kusum Deep和Manoj Thakur［8-9］成功把高斯分布引入交叉算子，以及把指數(shù)分布引入變異算子.Eshelman L J等［10］人提出了混合雜交，混合雜交在由父代構(gòu)成的超三角內(nèi)隨機(jī)得到后代.Janilow和Michalewicz Z［11］提出了非均勻變異，提高了算法的搜索精度和微調(diào)能力.Gen等［12］提出了有向變異，有效避免了個(gè)體陷入局部最優(yōu).另一個(gè)人們關(guān)注的研究方向是混合遺傳算法:文獻(xiàn)［13］將爬山算子引入遺傳算法，提出了基于爬山算子和適應(yīng)值共享的改進(jìn)遺傳算法，有效地提高了遺傳算法的局部搜索能力.文獻(xiàn)［14］將局部搜索算子嵌入遺傳算法形成局部搜索塊，為解決遺傳算法局部搜索能力差，提供了一種有效的方法.上述文獻(xiàn)從不同的方向出發(fā)對(duì)遺傳算法做出了有效改進(jìn)，增強(qiáng)了算法的收斂速度和提高了解的精度.

在種群進(jìn)化過(guò)程中，最優(yōu)個(gè)體往往代表著算法的迭代方向，能否挖掘并充分利用最優(yōu)個(gè)體的特征信息，對(duì)算法的搜索性能具有至關(guān)重要的影響［15-20］.為此，本文借鑒萬(wàn)有引力搜索算法［21-23］和混沌搜索對(duì)算術(shù)交叉和非均勻變異算子進(jìn)行了改進(jìn)，得到了一種改進(jìn)的遺傳算法(Gravitational Search Genetic Algorithm，GSGA).改進(jìn)交叉算子對(duì)進(jìn)入交叉運(yùn)算的每?jī)蓚€(gè)個(gè)體利用萬(wàn)有引力搜索算法中個(gè)體的運(yùn)動(dòng)法則，在兩個(gè)個(gè)體互相的引力作用下，質(zhì)量較大的個(gè)體運(yùn)動(dòng)速度較慢，質(zhì)量較小的個(gè)體運(yùn)動(dòng)速度較快，從而質(zhì)量較小的個(gè)體向質(zhì)量大的個(gè)體靠攏，同時(shí)本文將進(jìn)入交叉運(yùn)算的個(gè)體和最優(yōu)個(gè)體進(jìn)行交叉，這樣在一定程度上有效利用了最優(yōu)個(gè)體信息，達(dá)到提高收斂速度的效果;在改進(jìn)的變異算子中，在種群每個(gè)個(gè)體的引力作用下，進(jìn)入變異的個(gè)體以及最優(yōu)個(gè)體在合力作用下在一定范圍內(nèi)搜索，有利于算法在探索新區(qū)域的同時(shí)，也增強(qiáng)了算法的收斂精度.

1 GSGA算法思想

1.1 改進(jìn)的交叉算子

算術(shù)交叉算子是由凸集理論得來(lái).一般，兩個(gè)個(gè)體X1和X2經(jīng)過(guò)算術(shù)交叉得到的個(gè)體X′1和X′2為

本文對(duì)交叉算子改進(jìn)為

其中Xbest為種群最優(yōu)個(gè)體，a1為X1在Xbest作用下的加速度.

計(jì)算主要依據(jù)萬(wàn)有引力搜索算法，該算法根據(jù)牛頓萬(wàn)有引力定律——宇宙內(nèi)隨機(jī)兩個(gè)質(zhì)點(diǎn)之間存在吸引力F，該引力的大小與它們的質(zhì)量M1和M2的乘積成正比，與它們之間的距離R的平方成反比(其中G為引力常數(shù))

以及牛頓運(yùn)動(dòng)定律——質(zhì)點(diǎn)的運(yùn)動(dòng)加速度a等于該質(zhì)點(diǎn)所受的力F和其質(zhì)量M的比值

由N個(gè)個(gè)體構(gòu)成的種群表示為

X={X1，X2，…，Xi…，XN}，其 中Xi=

其中G(t)是第t代下的萬(wàn)有引力常量，Maj(t)是個(gè)體Xj的主動(dòng)引力質(zhì)量，Mpi(t)是個(gè)體Xi的被動(dòng)引力質(zhì)量.Rij(t)表示個(gè)體Xi和Xj之間的距離(i和j為個(gè)體排序后的位置序號(hào))，定義如下:

Rij(t)由個(gè)體Xi和Xj在種群的位置進(jìn)行定義，當(dāng)個(gè)體Xi和Xj的適應(yīng)值相差越小，即|j-i|越小，則Rij(t)越小.

萬(wàn)有引力常量初始值為G0(本文G0=1)，隨著t的增加，G會(huì)逐漸減小來(lái)控制搜索的精確度.G是關(guān)于G0和t的函數(shù)(T為迭代次數(shù)).

引力質(zhì)量和慣性質(zhì)量通過(guò)適應(yīng)值函數(shù)計(jì)算得到，假設(shè)引力質(zhì)量和慣性質(zhì)量相等，新個(gè)體的引力質(zhì)量和慣性質(zhì)量定義為

其中，fiti(t)表示個(gè)體Xi在第t代的適應(yīng)值，best(t)和worst(t)定義為

ai表示個(gè)體Xi受到個(gè)體Xj作用后的加速度，計(jì)算如下:

1.2 改進(jìn)的變異算子

非均勻變異算子是由Michalewicz［24］提出的.該算子可以得到較高的計(jì)算精度而且具有微調(diào)能力.

其中［L，U］表示Xi的可行區(qū)間，Δ為進(jìn)化代數(shù)t和y的函數(shù)，

其中b是確定的非均勻程度的參數(shù)，T為進(jìn)化的最大代數(shù).

本文對(duì)變異算子改進(jìn)為

其中Ai為Xi在種群中合力作用下的加速度，由(13)式得到.［L′，U′］定義如下:

其中N為種群規(guī)模，n為個(gè)體維數(shù)，［L′，U′］為集合{［L，L1］，［L1，U1］，［U1，U］}中任意一個(gè)元素.

個(gè)體Xi在第t代受到其他個(gè)體的合力Fi(t)表示為

其中，rand∈［0，1］為隨機(jī)數(shù)，增加算法的隨機(jī)性.

Ai表示個(gè)體Xi受種群合力產(chǎn)生的加速度:

以Ackley＇s Function為例，1000代內(nèi)X1和X2作用力變化和X1受種群合力變化如圖1所示.

圖1 個(gè)體Xi受個(gè)體Xj作用的加速度ai和受種群作用的加速度Ai的變化曲線Fig.1 Curves of aiacceleratied by Xiunder the action of Xjand Aiaccelerated by Xiunder the action of the population

由圖1可知:

(1)個(gè)體的兩種加速度都是在區(qū)間［0，1］內(nèi)變化的.而且加速度都隨著代數(shù)的增加，總體趨向于0.

(2)a∈(0，1)滿足算術(shù)交叉的條件;A的變化趨勢(shì)和非均勻變異參數(shù)的變化趨勢(shì)相似.

(3)兩個(gè)個(gè)體之間的作用力和個(gè)體在種群中受到的合力在進(jìn)化前期數(shù)值較大，而且波動(dòng)較大，這樣有助于算法進(jìn)行全局搜索，防止算法陷入局部最優(yōu);后期數(shù)值較小，有利于算法進(jìn)行局部搜索，提高算法的收斂精度.

1.3 最優(yōu)個(gè)體搜索策略

本文在變異運(yùn)算過(guò)程中，讓當(dāng)代最優(yōu)個(gè)體Xbest進(jìn)行變異，變異運(yùn)算按下式計(jì)算:

式中Ak由式(19)得到

其中Abest為個(gè)體Xbest在種群中所受的合力，k為進(jìn)入變異運(yùn)算個(gè)體的數(shù)目，Ak利用混沌策略進(jìn)行更新.在變異運(yùn)算過(guò)程中Xbest將產(chǎn)生k個(gè)后代.

1.4 改進(jìn)的交叉算子和變異算子特點(diǎn)

改進(jìn)后的交叉算子和變異算子主要有以下幾個(gè)特點(diǎn):

(1)進(jìn)入交叉運(yùn)算的個(gè)體都會(huì)和當(dāng)代最優(yōu)個(gè)體進(jìn)行交叉.依據(jù)交叉算子的特點(diǎn)可以得到，后代個(gè)體有較大概率向最優(yōu)個(gè)體運(yùn)動(dòng)，有利于加快種群的收斂速度.與傳統(tǒng)算術(shù)交叉算子相比，改進(jìn)的交叉算子在保持傳統(tǒng)算術(shù)交叉的隨機(jī)性的同時(shí)引入了兩個(gè)父代的自身信息，使得進(jìn)化更具有目的性.

(2)改進(jìn)后的變異算子，繼續(xù)保持了非均勻變異算子的特性，在進(jìn)化前期能夠進(jìn)行全局搜索，后期能夠進(jìn)行局部搜索.在進(jìn)化過(guò)程中，進(jìn)入變異的個(gè)體的搜索區(qū)間給細(xì)分為3個(gè)部分，目的在于使搜索區(qū)間隨著種群進(jìn)化的過(guò)程，也同時(shí)進(jìn)化;同時(shí)最優(yōu)個(gè)體也會(huì)在變異過(guò)程中進(jìn)行混沌搜索，利用混沌的遍歷性、隨機(jī)性的特點(diǎn)以及最優(yōu)個(gè)體信息，從而加強(qiáng)的算法的局部搜索能力以及跳出局部最優(yōu)解的能力.

(3)交叉變異過(guò)程中，個(gè)體的適應(yīng)值越好，個(gè)體的質(zhì)量就越大.在萬(wàn)有引力作用下，質(zhì)量小的個(gè)體以大概率事件向質(zhì)量大的個(gè)體靠攏.

1.5 最優(yōu)個(gè)體與隨機(jī)選取個(gè)體交叉與隨機(jī)兩個(gè)個(gè)體交叉的對(duì)比

為了說(shuō)明本文提出算子的有效性，通過(guò)下面實(shí)驗(yàn)結(jié)果說(shuō)明最優(yōu)個(gè)體進(jìn)入交叉運(yùn)算對(duì)種群進(jìn)化過(guò)程的影響.以RGA為例，在1000代內(nèi)種群進(jìn)化結(jié)果對(duì)比，解空間分布情況如圖2和圖3所示:

圖2 1000代內(nèi)最優(yōu)個(gè)體不參與遺傳運(yùn)算得到的解分布Fig.2 Distribution of 1 000 intragenerational solutions of the Genetic Algorithm without best individuals

圖3 1000代內(nèi)最優(yōu)個(gè)體參與遺傳運(yùn)算得到的解分布Fig.3 Distribution of 1000 intragenerational solutions of the Genetic Algorithm with best individuals

由圖2和圖3的對(duì)比可以得到下面結(jié)論:

(1)在最優(yōu)個(gè)體不參與遺傳運(yùn)算的圖2中，解很長(zhǎng)時(shí)間無(wú)法集中到一個(gè)固定區(qū)域，即無(wú)法快速收斂到最優(yōu)解.

(2)在最優(yōu)個(gè)體參與遺傳運(yùn)算的圖3中，解能夠在較短時(shí)間集中到一個(gè)固定區(qū)域，而且匯聚到一個(gè)較小的區(qū)域，即可以快速收斂到最優(yōu)解.

(3)在最優(yōu)個(gè)體參與下，傳統(tǒng)的RGA算法，可以以更快的速度收斂到最優(yōu)解，而且解的精度也進(jìn)一步得到提高.由此得到，最優(yōu)個(gè)體在遺傳算法收斂效果方面起到至關(guān)重要的作用.

2 算法流程

優(yōu)化問(wèn)題一般描述為:

GSGA算法流程為:

Step1:參數(shù)初始化.設(shè)定種群規(guī)模N、問(wèn)題的維數(shù)n、進(jìn)化代數(shù)t、最大進(jìn)化代數(shù)T、變量的范圍［L，U］、雜交概率Pc和變異概率Pm.

Step2:種群初始化P(0):P(0)=L+rand(N，n)(U-L).其中rand∈(0，1)之間的隨機(jī)數(shù).

Step3:計(jì)算種群個(gè)體的適應(yīng)值，依據(jù)適應(yīng)值對(duì)個(gè)體進(jìn)行排序，把最優(yōu)個(gè)體記為Xbest，計(jì)算個(gè)體的質(zhì)量Mi，任兩個(gè)個(gè)體間的距離Rij和作用力Fij，個(gè)體受種群中所有個(gè)體的作用力的合力Fi.

Step4:按式(2)定義的交叉算子進(jìn)行交叉運(yùn)算.

Step5:按式(14)和(17)定義的變異算子進(jìn)行變異運(yùn)算.

Step6:錦標(biāo)賽選擇新種群，競(jìng)賽規(guī)模設(shè)置為2.

Step7:如果t≤T，t=t+1，返回Step3，否則運(yùn)算結(jié)束.

3 數(shù)值實(shí)驗(yàn)

本文選擇了8個(gè)經(jīng)典的測(cè)試函數(shù)優(yōu)化問(wèn)題測(cè)試了3種算法的性能.

以上8個(gè)函數(shù)中，F(xiàn)1、F2、F6、F7為多峰獨(dú)立函數(shù)，F(xiàn)3、F5、F8為單峰函數(shù)，F(xiàn)4都為多峰非獨(dú)立函數(shù).分別用文獻(xiàn)［6］標(biāo)準(zhǔn)遺傳算法(RGA)和文獻(xiàn)［17］的萬(wàn)有引力搜索算法(GSA)與本文的算法(GSGA)進(jìn)行比較.為了比較更有針對(duì)性，RGA采用算術(shù)交叉，非均勻變異，競(jìng)賽法選擇.設(shè)置參數(shù)為:最大代數(shù)為1 000代，交叉率為0.8，變異率為0.1，種群規(guī)模為50，染色體長(zhǎng)度為30.試驗(yàn)結(jié)果見(jiàn)表1.

表1 RGA GSA GSGA分別對(duì)F1-F8單獨(dú)優(yōu)化50次的結(jié)果Tab.1 RGA GSA GSGA Respectively on F1-F8to separate the result of optimization of 50 times

為了比較這些算法的收斂速度，以一次測(cè)試結(jié)果作為收斂結(jié)果，得到的收斂曲線如圖4所示.

圖4 各函數(shù)3種遺傳算法的進(jìn)化曲線Fig.4 Evolution curve of three genetic algorithm of F1～F8

從表1可以看出在相同代數(shù)內(nèi)，GSGA得到的最優(yōu)解要比RGA和GSA得到的最優(yōu)解要好，從平均值和方差方面可以看出GSGA的穩(wěn)定性要強(qiáng)于RGA和GSA.

從圖4可以得到GSGA不僅能以比RGA和GSA更快的速度逼近最優(yōu)解，而且逼近最優(yōu)解的程度也是3種算法中最高的.

GSGA算法的進(jìn)化曲線能夠在100代內(nèi)快速逼近最優(yōu)解，說(shuō)明算法有較強(qiáng)的全局搜索能力.從函數(shù)F5和函數(shù)F8后期的進(jìn)化曲線可以看出GSGA算法有跳出局部最優(yōu)解的能力.

4 結(jié)論

本文提出一種基于萬(wàn)有引力搜索的改進(jìn)遺傳算法(GSGA)，改進(jìn)了交叉和變異算子.改進(jìn)后的算子吸收了萬(wàn)有引力搜索優(yōu)點(diǎn)，使之具有較強(qiáng)的全局及局部尋優(yōu)能力，同時(shí)較好地利用了每代中最優(yōu)個(gè)體的信息，從而保證了新算子具有較高的全局尋優(yōu)能力.通過(guò)8個(gè)測(cè)試函數(shù)優(yōu)化結(jié)果表明GSGA比GSA和RGA的尋優(yōu)效果好，收斂速度快.

［1］Tu C Y，Zeng Y J.A new genetic algorithm based upon globally-optimal choosing and its practices［J］.Engineering Science，2003，5(2):28-29.

［2］Zhao C X，Ji Y M.Particle swarm optimization for 0/1 knaps problem［J］.MicrocomputerDevelepment，2005(10):23-25.

［3］張軍，詹志輝.計(jì)算智能［M］.北京:清華大學(xué)出版社，2009.

［4］周明，孫樹(shù)棟.遺傳算法原理及其應(yīng)用［M］.北京:國(guó)防工業(yè)出版社，1999.

［5］Brindel A.Genetic algorithms for function optimization［D］.Edmonton University of Alberta，Department of Computing Science，1981.

［6］Back T.The interaction of mutation rate，selection and selfadaption within a genetic algorithm［C］∥Parallel Problem Solving from Nature 2.Amsterdam［S.l.］:Elseriver Science Publisher，1992:85-94.

［7］Jong De K A.An analysis of the behavior of a class of genetic adaptive systems［D］.Ann Arbor:University of Michign，College of Literature，Science，and the Arts Computer and Communication Sciences Department，1975.

［8］Deep K，Thakur M.A new mutation operator for real coded genetic algorithms［J］.Applied Mathematics and Computation，2007(193):211-230.

［9］Deep K，Thakur M.A new crossover operator for real coded genetic algorithms［J］.Applied Mathematics and Computations，2007(188):895-911.

［10］Eshelman L J，Schaffer J D.Real-coded genetic algorithms and intervalschemata［J］.Foundation of Genetic Algorithns，1993(2):187-202.

［11］Michalewicz Z.Genetic algorithm+data structure=evolution programs［M］.New York:Springer-Verlag，1996.

［12］Gen M，liu B，Ida K.Evolution Program for deterministic and stochastic optimization［J］.European Journal of Operational Research，1996，3(94):618-625.

［13］涂井先，劉偉.基于爬山算子和適應(yīng)值共享的改進(jìn)遺傳算法［J］.廣東工業(yè)大學(xué)學(xué)報(bào)，2011，28(1):78-81.Tu J X，Liu W.An improved genetic algorithm based on mountain-climbing operators and fitness sharing［J］.Journal of Guangdong University of Technology，2011，28(1):78-81.

［14］彭偉，盧錫城.一種函數(shù)優(yōu)化的混合遺傳算法［J］.軟件學(xué)報(bào)，1999，8(10):819-823.Peng W，Lu X C.A hybrid genetic algorithm for function optimization［J］.Journal of Software，1999，8(10):819-823.

［15］Rudoph G.Convergence analysis of canonical genetic algorithms［J］.IEEE Transaction Neural Netwoks，1994，5(1):96-101.

［16］Dinabandhu B，Murthy C A.Genetic algorithm with elitist model and its convergence［J］.International Journal of Pattern Recognition and Artificial Intelligence，1996，10(6):990-995.

［17］彭宏，王興華.具有Elitist選擇的遺傳算法的收斂速度估計(jì)［J］.科學(xué)通報(bào)，1997，42(2):144-147.Peng H，Wang X H.Convergence speed estimate of genetic algorithm with elitist selection［J］.Chinese Science Bulletin，1997，42(2):14-147.

［18］譚躍，譚冠政，胡塞純，等.自適應(yīng)策略的混沌局部搜索遺傳算法［J］.計(jì)算機(jī)與數(shù)字工程，2010，38(5):19-21.Tan Y，Tan G Z，Hu S C，et al.Chaotic local search genetic algorithm with adaptive strategy［J］.Computer＆Digital Engineering，2010，38(5):19-21.

［19］唐煥文，秦學(xué)志.實(shí)用最優(yōu)化方法［M］.3版.大連:大連理工大學(xué)出版社，1999.

［20］董文永，張文生，于瑞國(guó).求解組合優(yōu)化問(wèn)題伊藤算法的收斂性和期望收斂速度分析［J］.計(jì)算機(jī)學(xué)報(bào)，2011，34(4):636-646.Dong W Y，Zhang W S，Yu R.Convergence and runtime analysis of ITO algorithm for one class of combinatorial optimization［J］.Chinese Journal of Computers，2011，34(4):636-646.

［21］Rashedi E，Nezamabadi-Pour H，Saryazdi S.GSA:a gravitational search algorithm［J］.Information Sciences，2009，13(179):2232-2248.

［22］Sarafrazi S，Nezamabadi-Pour H，Saryazdi S.Disruption:a new operator in gravitational search algorithm［J］.Scientia Iranica，2011，3(18):539-548.

［23］Naji H R，Sohrabi M，Rashedi E.A high speed and performance optimization algorithm based on gravitational approach［J］.Computing in Science＆Engineering，2012，5(14):56-62.

［24］Michalewicz Z，Janikow C Z，Krawczyk J B.A modified genetic algorithm for optimal control problems［J］.Computers and Mathematics with Applications，1992，23(12):83-94.