李松芳，劉 偉

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

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

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

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

1 GSGA算法思想

1.1 改進的交叉算子

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

本文對交叉算子改進為

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

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

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

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

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

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

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

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

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

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

ai表示個體Xi受到個體Xj作用后的加速度，計算如下:

1.2 改進的變異算子

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

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

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

本文對變異算子改進為

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

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

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

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

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

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

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

由圖1可知:

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

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

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

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

本文在變異運算過程中，讓當代最優(yōu)個體Xbest進行變異，變異運算按下式計算:

式中Ak由式(19)得到

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

1.4 改進的交叉算子和變異算子特點

改進后的交叉算子和變異算子主要有以下幾個特點:

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

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

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

1.5 最優(yōu)個體與隨機選取個體交叉與隨機兩個個體交叉的對比

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

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

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

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

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

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

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

2 算法流程

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

GSGA算法流程為:

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

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

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

Step4:按式(2)定義的交叉算子進行交叉運算.

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

Step6:錦標賽選擇新種群，競賽規(guī)模設置為2.

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

3 數(shù)值實驗

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

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

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

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

圖4 各函數(shù)3種遺傳算法的進化曲線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)定性要強于RGA和GSA.

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

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

4 結(jié)論

本文提出一種基于萬有引力搜索的改進遺傳算法(GSGA)，改進了交叉和變異算子.改進后的算子吸收了萬有引力搜索優(yōu)點，使之具有較強的全局及局部尋優(yōu)能力，同時較好地利用了每代中最優(yōu)個體的信息，從而保證了新算子具有較高的全局尋優(yōu)能力.通過8個測試函數(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］張軍，詹志輝.計算智能［M］.北京:清華大學出版社，2009.

［4］周明，孫樹棟.遺傳算法原理及其應用［M］.北京:國防工業(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］涂井先，劉偉.基于爬山算子和適應值共享的改進遺傳算法［J］.廣東工業(yè)大學學報，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］.軟件學報，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］.科學通報，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］譚躍，譚冠政，胡塞純，等.自適應策略的混沌局部搜索遺傳算法［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］唐煥文，秦學志.實用最優(yōu)化方法［M］.3版.大連:大連理工大學出版社，1999.

［20］董文永，張文生，于瑞國.求解組合優(yōu)化問題伊藤算法的收斂性和期望收斂速度分析［J］.計算機學報，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.