王福林,付曉明,朱會霞,趙勝雪(.東北農(nóng)業(yè)大學工程學院,哈爾濱 50030;.遼寧工業(yè)大學管理學院,遼寧 錦州 00)
?
基于兩點交叉多子代遺傳算法
王福林1,付曉明1,朱會霞2,趙勝雪1
(1.東北農(nóng)業(yè)大學工程學院,哈爾濱150030;2.遼寧工業(yè)大學管理學院,遼寧錦州121001)
摘要:針對目前遺傳算法局部搜索能力差、收斂精度低問題,提出基于兩點交叉多子代遺傳算法(TPCMCGA),闡明該算法優(yōu)越性,并給出多子代個體產(chǎn)生方法。該方法可增加優(yōu)秀個體概率及算法在當前最優(yōu)解周圍搜索精度,提高算法局部搜索能力。在進化策略中引入種群內(nèi)部競爭操作,使種群在有限生存空間內(nèi)加速進化,提高算法運算速度。結果表明,與傳統(tǒng)遺傳算法相比,TPC-MCGA平均計算時間減少31%~36%,平均迭代次數(shù)減少50.2%~51.6%,TPC-MCGA運算速度與最優(yōu)解精度均明顯提高。
關鍵詞:多子代遺傳算法;兩點交叉;子代數(shù)量;進化策略
王福林,付曉明,朱會霞,等.基于兩點交叉多子代遺傳算法[J].東北農(nóng)業(yè)大學學報,2016,47(3):72-79.
Wang Fulin,Fu Xiaoming,Zhu Huixia,et al.Multi-child genetic algorithm based on two-point crossover[J].Journal of Northeast Agricultural University,2016,47(3):72-79.(in Chinese with English abstract)
遺傳算法(Genetic algorithm,GA)是借鑒生物界自然選擇和進化機制發(fā)展起來的高度并行、隨機、自適應智能優(yōu)化算法[1-3],由John H.Holland教授于1975年首次提出[4]。與傳統(tǒng)優(yōu)化算法相比,遺傳算法具有良好魯棒性、靈活性、通用性及較強全局搜索能力[5-7],受到廣泛關注。但遺傳算法局部搜索能力較差,算法進化后期搜索效率較低、收斂精度和運算速度均難提高[8-9]。針對遺傳算法不足,近年研究者不斷改進。Zhang等在遺傳算法中引入模擬退火機制,將模擬退火與遺傳算法結合,提高算法局部搜索能力[10]。Chen和Wang等為提高遺傳算法尋優(yōu)性能,將個體通過堿基編碼成生物分子,借鑒生物分子操作提高遺傳算法搜索效率和尋優(yōu)性能[11-12]。徐梅等提出一種改進遺傳算法初始種群產(chǎn)生方法,提高遺傳算法求解有約束問題搜索能力[13]。Saitoh等設計一種新量子遺傳算法,在每代所有染色體上根據(jù)量子交叉法交叉,實現(xiàn)二次加速,提高遺傳算法搜索能力[14]。王福林等提出一種改進進化策略遺傳算法,避免變異過程對交叉產(chǎn)生優(yōu)秀個體破壞,提高遺傳算法運算速度[15]。本研究以生物學原理為基礎,針對目前遺傳算法局部搜索能力差,運算速度慢、收斂精度低問題,將生物學中“多子代”思想和“種群內(nèi)部競爭”機制引入遺傳算法中,提出基于兩點交叉多子代遺傳算法(Two-point crossover multichild genetic algorithm,TPC-MCGA)。旨在解決目前遺傳算法局部搜索能力差、運算效率低問題,為充分發(fā)揮遺傳算法性能、提高算法求解能力提供有效途徑,為多子代遺傳算法應用提供理論基礎。
遺傳算法中存在如下基本假設①存在由多個生物個體組成種群;②生物個體之間存在差異,或群體具有多樣性;③生物能夠自我繁殖;④不同個體具有不同環(huán)境生存能力,具有良好基因結構個體繁殖能力強,反之則弱[16]。在遺傳算法實際應用中,假定種群規(guī)模始終保持不變,實際是隱含種群容量已飽和、種群容量受限假設。
多子代遺傳算法對多子代遺傳算法定義如下:
父代個體交叉產(chǎn)生子代個體數(shù)量多于其父代個體數(shù)量遺傳算法,稱為多子代遺傳算法(Multichild genetic algorithm,MCGA)。
在多子代遺傳算法中,子代個體數(shù)量一般是父代個體數(shù)量整數(shù)倍。令父代個體數(shù)量為N0,子代個體數(shù)量為N1時,有
其中,α-子代個體數(shù)量與其父代個體數(shù)量比例系數(shù)。
由式(1)可知,MCGA子代數(shù)量較多,在有限生存空間條件下,種群個體生存壓力增大,種群個體相互競爭。在競爭過程中,依據(jù)優(yōu)勝劣汰原則[18],競爭獲勝優(yōu)秀個體生存,競爭失敗個體淘汰。因此,與傳統(tǒng)GA相比,MCGA種群個體間競爭加劇,優(yōu)勝劣汰速度和種群進化速度加快。
3.1生物學基礎
達爾文進化論中生物進化論自然選擇學說[17]包括高度生育率、生存斗爭、不定變異、最適者生存和受惠種族等因素。生物界中一對父代個體繁殖子代個體數(shù)量多于兩個,物種在進化過程中不但能繼承父代個體特征,有利于在復雜變化自然環(huán)境中生存,生物物種不斷進化,得到更優(yōu)良個體。而由父代個體產(chǎn)生子代個體數(shù)量小于或等于父代個體數(shù)量種群并不存在,即便存在,產(chǎn)生后代個體數(shù)量較少,導致有利生存基因在進化中受外界環(huán)境因素影響而消失。
動植物父代產(chǎn)生子代數(shù)量大多大于父代數(shù)量,多子代遺傳算法正是基于生物學原理而提出。
3.2數(shù)學生態(tài)學基礎
對種群規(guī)模增長和下降研究,是數(shù)學生態(tài)學最古老分支[18-19]。為說明一個種群能夠持續(xù)生存條件,需先討論種群滅絕概率,假設一個種群開始只有一個個體,在某一時間t其規(guī)模將為0概率是
式中,i-初始種群數(shù)量,μ-死亡率,λ-生殖率。
關于式(2)推導過程請詳見文獻[18],如果初始大小為i種群變到滅種,可見i個獨立家系均不存在,即對于任意i,這種事件概率是
要求出種群最終滅種概率,須使t趨于無窮。故對式(3)分三種情況討論:
a.當生殖率小于死亡率時,即λ<μ時
顯然,在式(3)中指數(shù)項隨t→∞而變?yōu)?,因
此可得:
概率為1,顯然該種群無法延續(xù)。
b.當生殖率大于死亡率時,即λ>μ時
則當t→∞時,式(3)可化為
仍有可能滅種,但生殖率超過死亡率越多,生物滅種概率越小。
c.當生殖率等于死亡率時,即λ=μ時
將式(3)中指數(shù)項展開成級數(shù)形式,并令λ-μ= r,來求tl→im∞p(0t),因此
當r→0時,r2項忽略,并且因為λ-μ=r,μ→λ,所以
顯然,
由此可見,即使生殖率等于死亡率,也會最終滅種。僅當λ>μ時,即種群有正增加率,種群才有可能(并非必然)保持。數(shù)學生態(tài)學證明了當生物初始種群數(shù)量已知時,生物種群規(guī)模取值概率分布只取決于每個個體增加率與時間乘積,所以高生殖率保持較短時間,和低生殖率保持較長時間,只要每個個體增加率與時間乘積相等,就會得到相同結果,因此為在最短時間內(nèi)得到更加優(yōu)良個體,需要提高物種生殖率。
傳統(tǒng)遺傳算法交叉操作是兩個父代生成兩個子代,而TPC-MCGA是兩個父代個體交叉產(chǎn)生兩個以上子代個體。假設有被選擇參與交叉兩個父代個體P1和P2,其編碼長度均為l,隨機產(chǎn)生n(2< n≤l-1)個交叉點,則P1和P2染色體被分成n+1段,即P1=A1A2A3…Ak…An- 1AnAn + 1,P2=B1B2B3…Bk…Bn-1BnBn+1。TPC-MCGA子代產(chǎn)生方法是:首先在n個交叉點中任意選擇2個交叉點,把這兩個交叉點間所包括等位基因看作子串,交換兩個父代P1和P2子串形成兩個子代個體Child1和Child2;再在n個交叉點中任意選擇與之前非重復2個交叉點,交換兩個父代P1和P2子串形成兩個子代個體Child3和Child4;以此類推,兩個父代P1和P2可經(jīng)過Cn2次非重復交叉,最多可產(chǎn)生2Cn2個不同新子代個體。有如下定義:
一對父代染色體在隨機產(chǎn)生n(2 TPC-MCGA多子代個體產(chǎn)生方法見圖1。 由圖1可知,Child(ii=1,2,…,2Cn2)為交叉所產(chǎn)生第i個子個體。顯然,在TPC-MCGA中,一對父代能夠產(chǎn)生2Cn2個新子代個體,其子代個體數(shù)量是傳統(tǒng)GACn2倍。例如,有被選擇參與交叉兩個父代個體P1和P2,采用二進制編碼,其分別為P1= 1011001000和P2=1100110110,設產(chǎn)生隨機交叉點個數(shù)n為3,假設這3個交叉點分別位于第3、6、8位,則有 交叉點:1 2 3 P1=101 100 10 00, P2=110 011 01 10 因此,父代個體P1和P2按圖1所示兩點交叉多子代產(chǎn)生方法得到子代個體分別為: C1=101 011 10 00, C2=110 100 01 10, C3=101 011 01 00, C4=110 100 10 10, C5=101 100 01 00, C6=110 011 10 10, 顯然,TPC-MCGA中子代個體數(shù)量明顯增加,子代中優(yōu)秀個體產(chǎn)生概率升高,同時一對父代個體交叉產(chǎn)生了更多具有相同父代特征子代個體,增加了算法最優(yōu)解周圍搜索精度,提高算法局部搜索能力。因此與傳統(tǒng)GA相比,TPC-MCGA具有更快收斂速度和更強尋優(yōu)能力。但子代個體數(shù)量過多必然導致每迭代一次運算量增加,因此應該選取合適子代數(shù)量。關于TPC-MCGA算法最佳子代數(shù)量確定需進一步理論分析和試驗研究,為驗證TPC-MCGA優(yōu)越性,本文將以兩個父代交叉產(chǎn)生最少多子代個體為例(即兩個父代交叉產(chǎn)生4個多子代個體)進行算法比較測試試驗與分析。 圖1 兩點交叉多子代遺傳算法子代產(chǎn)生方法Fig.1 Method of producing multi-child offspring in TPC-MCGA TPC-MCGA進化策略是:首先產(chǎn)生種群規(guī)模為N0初始種群,計算種群個體適應度;第二通過輪盤賭方式隨機選擇參與交叉?zhèn)€體,將被選中每對個體按兩點交叉產(chǎn)生多子代方法交叉,并從交叉產(chǎn)生N1個多子代個體和N0個父代個體中選擇m個具有最高適應度個體作精英保留;第三對交叉產(chǎn)生N1個多子代個體變異,并將m個精英個體與變異后N1個子代個體進行種群內(nèi)部競爭,競爭過程中淘汰(N1+m-N0)個低適應度個體以保持種群規(guī)模不變,形成新種群;最后計算新種群個體適應度,判斷是否滿足迭代終止條件,如果滿足,則停止迭代,如果不滿足,則循環(huán)以上過程使種群繼續(xù)進化,到滿足終止條件為止。其進化策略如圖2所示。 6.1試驗方法與測試函數(shù)選取 為驗證本文提出TPC-MCGA性能,選取6個常用典型測試函數(shù)[21-22],將TPC-MCGA與傳統(tǒng)遺傳算法(Traditional genetic algorithm,TGA)進行算法搜索性能對比試驗。試驗擬采用兩種方法:固定搜索精度運算速度比較法和固定迭代次數(shù)求解精度比較法。 TPC-MCGA與TGA均采用二進制編碼,初始種群隨機產(chǎn)生,試驗參數(shù)設置如下:種群規(guī)模N0= 100,子代個體數(shù)量與其父代個體數(shù)量比例系數(shù)α= 2,交叉概率Pc=0.9,變異概率Pm=0.1,保留精英個體數(shù)m=10,TPC-MCGA與TGA迭代終止條件為: 式中,fi*-第i個函數(shù)理論最優(yōu)解;fi-算法搜索到第i個函數(shù)最優(yōu)解;εi-第i個函數(shù)搜索停止精度。 6個測試函數(shù)搜索停止精度εi均為10-4。兩種算法對每個測試函數(shù)在相同測試環(huán)境下分別獨立運行1 000次。 所用6個測試函數(shù)包含多個已知極值點,有連續(xù)、非連續(xù)、單峰,多峰、病態(tài)等不同數(shù)學特征。 測試函數(shù)1: 圖2 多子代遺傳算法進化策略Fig.2 Evolution strategy ofTPC-MCGA 6.2試驗結果與分析 由表1可知,TPC-MCGA與TGA算法對測試函數(shù)f1~f6固定搜索停止精度為10-4獨立對比試驗結果,其中平均迭代次數(shù)和平均計算時間是指算法運行1 000次對各測試函數(shù)符合迭代停止條件,即達到搜索停止精度平均迭代次數(shù)和平均計算時間。圖3~8分別給出固定迭代次數(shù)為500時,兩種算法對6個測試函數(shù)獨立運行1 000次平均適應度收斂曲線。由表1可知,6個測試函數(shù)取得最優(yōu)解時,TPC-MCGA平均計算時間0.3813~1.1250 s,平均迭代次數(shù)11.1185~39.2031次;TGA平均計算時間為0.5963~1.6231 s,平均迭代次數(shù)22.9530~ 78.7100次。與TGA相比,TPC-MCGA平均計算時間減少31%~36%,平均迭代次數(shù)減少50.2%~ 51.6%。顯然,TPC-MCGA平均計算時間與平均迭代次數(shù)均明顯優(yōu)于TGA。這是由于在函數(shù)優(yōu)化時,TPC-MCGA每次迭代產(chǎn)生子代個體數(shù)量多于TGA,因此子代種群規(guī)模要明顯大于TGA,增加了子代中高適應度優(yōu)秀個體概率。子代個體經(jīng)過變異后,在種群競爭過程中大部分低適應度個體被淘汰,使在TPC-MCGA中生存子代個體平均適應度高于TGA,同時在進化策略中引入種群內(nèi)部競爭操作,使子代種群規(guī)模與初始種群保持規(guī)模一致,保證種群在有限生存空間內(nèi)加速進化。因此,TPCMCGA求解運算速度明顯優(yōu)于TGA。 由圖3~8可知,與TGA算法相比,TPC-MCGA收斂精度明顯提高。尤其對于測試函數(shù)f3和f6,經(jīng)過少量次數(shù)迭代,TPC-MCGA即可達到理論最優(yōu)值。這是由于一對父代產(chǎn)生了更多具有相同父代特征子代個體,增加算法在當前最優(yōu)解周圍搜索精度,提高算法局部搜索能力。 表1 TPC-MCGA與TGA算法測試結果Table 1 Testing results of TPC-MCGA and TGA 圖3 函數(shù)f1平均適應度收斂曲線Fig.3 Convergence curve of average fitness for f1 圖5 函數(shù)f3平均適應度收斂曲線Fig.5 Convergence curve of average fitness for f3 圖7 函數(shù)f5平均適應度收斂曲線Fig.7 Convergence curve of average fitness for f5 圖4 函數(shù)f2平均適應度收斂曲線Fig.4 Convergence curve of average fitness for f2 圖6 函數(shù)f4平均適應度收斂曲線Fig.6 Convergence curve of average fitness for f4 圖8 函數(shù)f6平均適應度收斂曲線Fig.8 Convergence curve of average fitness for f6 本試驗結果表明,遺傳算法子代數(shù)量增加提高了算法求解運算速度和收斂精度,與Hsieh等研究結果一致[23]。但在Hsieh研究中,將隨機產(chǎn)生個體加入子代種群中提高子代數(shù)量,因此搜索效率提高依靠隨機產(chǎn)生個體中出現(xiàn)優(yōu)秀個體概率,本文采用兩點交叉產(chǎn)生多子代個體方法,使產(chǎn)生多子代個體繼承父代特征,保留父代個體優(yōu)秀模式,提高子代出現(xiàn)優(yōu)秀個體概率,結果表明,采用本文提出方法,搜索效率和收斂精度均明顯提高。Shi等研究提出遺傳算法個體生存概率概念,使每代個體均有一定概率生存到下一(幾)代,因此子代數(shù)量增加,算法收斂加快,但后期過大種群規(guī)模導致運算效率降低,不適于處理復雜優(yōu)化問題[24]。Koljonen等研究認為,種群規(guī)模增加提高遺傳算法穩(wěn)定性,但降低收斂速度[25]。本試驗研究表明,通過引入種群內(nèi)部競爭機制,增加子代群體通過競爭淘汰低適應度個體,保證種群在有限生存空間內(nèi)加速進化,提高算法收斂速度。 本試驗中選取子代個體數(shù)量與其父代個體數(shù)量比例系數(shù)α=2,即兩個父代交叉產(chǎn)生4個多子代個體。結果顯示,與TGA相比,TPC-MCGA平均計算時間與平均迭代次數(shù)均明顯減少,證明TPCMCGA優(yōu)越性,為解決目前遺傳算法局部搜索能力差,運算速度慢,收斂精度低問題提供有效方法。由本試驗結果可知,當取α=3時,TPC-MCGA平均計算時間與迭代次數(shù)進一步減少,但減少量小于α= 2時計算時間和迭代次數(shù)減少量,這表明α=2并不非最佳子代與父代個體數(shù)量比。顯然,子代個體數(shù)量變化對TPC-MCGA性能有顯著影響。雖然本試驗證明TPC-MCGA求解精度與運算時間均優(yōu)于TGA,但不能確定TPC-MCGA最佳子代數(shù)量,對TPC-MCGA子代個體數(shù)量對算法性能影響及變化規(guī)律需深入研究。針對如不同編碼條件下TPCMCGA子代產(chǎn)生方法研究,TPC-MCGA子代數(shù)量與運算速度關系研究,種群規(guī)模對TPC-MCGA算法收斂精度影響等有待進一步探討。 本文在研究傳統(tǒng)遺傳算法基礎上,依據(jù)生物學和數(shù)學生態(tài)學理論,針對目前遺傳算法局部搜索能力差、運算效率低問題提出兩點交叉多子代遺傳算法(TPC-MCGA),該算法利用兩點交叉方式產(chǎn)生多于父代個體子代種群,使子代種群中出現(xiàn)優(yōu)秀個體概率明顯增加,提高算法尋優(yōu)能力。該算法在進化策略中引入種群內(nèi)部競爭操作,使多子代種群在有限生存空間內(nèi)競爭,加快算法求解運算速度。本研究結果表明,TPC-MCGA在運算速度與求得最優(yōu)解精度上均明顯優(yōu)于TGA算法。 [參考文獻] [1]Sivanandam S N,Deepa S N.Introduction to Genetic Algorithm[M].New York:Springer-verlag Berlin Heidelberg,2008. [2]劉大蓮,徐尚文.求解約束優(yōu)化問題內(nèi)外交叉遺傳算法[J].系統(tǒng)工程理論與實踐,2012,32(1):189-195. [3]Velkatraman S,Yen G G.A genetic framework for constrained optimization using genetic algorithms[J].IEEE Transactions on Evolutionary Computation,2005,9(4):424-435. [4]Holland J H.Adaptation in natural and artificial systems[M].Ann Arbor:University of Michigan Press,1975. [5]Tutkun N.Optimization of multimodal continuous functions using anew crossover for the real-coded genetic algorithms[J].Expert Systems with Applications,2010,36(4):8172-8177. [6]趙紅杰,柏繼云,馬力.遺傳擴展蟻群算法用于馬斯京根模型參數(shù)估計[J].東北農(nóng)業(yè)大學學報,2014,45(8):118-123. [7]Cheng T M,Yan R Z.Integrating messy genetic algorithms and simulation to optimize resource utilization[J].Computer- Aided Civil and Infrastructure Engineering,2009,24(6):401-415. [8]Liu C Y.An improved adaptive genetic algorithm for the multidepot vehicle routing problem with time window[J].Journal of Networks,2013,8(5):1035-1042. [9]楊世達,單志勇,李慶華.基于親緣選擇遺傳算法[J].計算機工程,2009,35(15):10-12. [10]Zhang L,Cai L B,Li M,et al.A method for least- cost QoS multicast routing based on genetic simulated annealing algorithm[J].Computer Communications,2009,32(1):105-110. [11]Chen X,Wang N.Optimization of short-time gasoline blending scheduling problem with a DNA based hybrid genetic algorithm[J].Chemical Engineering and Processing,2011,49(10):1076-1083. [12]Wang K,Wang N.A protein inspired RNA genetic algorithm for parameter estimation in hydrocracking of heavy oil[J].Chemical Engineering Journal,2011,167(1):228-239. [13]徐梅,文士發(fā),王福林,等.遺傳算法求解約束優(yōu)化問題時產(chǎn)生初始種群改進方法[J].東北農(nóng)業(yè)大學學報,2014,45(7):104-107. [14]Saitoh A,Rahimi R,Nakahara M.A quantum genetic algorithm with quantum crossover and mutation operations[J].Quantum Information Processing.2014,13(3):737-755. [15]王福林,朱會霞,王吉權等.遺傳算法一種改進進化策略[J].生物數(shù)學學報,2015,30(1):69-74. [16]李敏強,寇紀淞,林丹,等.遺傳算法基本理論與應用[M].北京:科學出版社,2002:2-3. [17]Darwin C.On the Origin of Species by Means of Natural Selection[M].London:John Murry,1859. [18]Pielou E C.Mathematical Ecology[M].New York:John Wiley and Sons,1987:4-8. [19]Bailey N T.The Elements of Stochastic Procedures with Applications to the Natural Science[M].New York:John Wiley and Sons,1964. [21]王福林,朱會霞,王吉權.遺傳算法一種改進進化策略[J].生物數(shù)學學報,2015,30(1):69-74. [22]王小平,曹立明.遺傳算法-理論應用與軟件實現(xiàn)[M].西安:西安交通大學出版社,2002:32-34. [23]Hsieh S T,Sun T Y,Liu C C.Potential offspring production strategies:An improved genetic algorithm for global numerical optimization[J].Expert Systems with Applications,2009,36(8):11088-11098. [24]Shi X H,Wan L M,Lee H P,et al.An improved genetic algorithm with variable population- size and a PSO- GA based hybrid evolutionary algorithm[C].International Conference on Machine Learningand Cybernetics,2003:1735-1740. [25]Koljonen J,Alander J T.Effects of population size and relative elitism on optimization speed and reliability of genetic algorithms[C].In Proceedings of the 12th Finnish Artificial Intelligence Conference,2006:26-27. Multi-child genetic algorithm based on two-point crossover WANG Fulin1,FU Xiaoming1,ZHU Huixia2,ZHAO Shengxue1(1.School of Engineering,Northeast Agricultural University,Harbin 150030,China; 2.School of Management,Liaoning University of Technology,Jinzhou Liaoning 121001,China) Abstract:Considering that current genetic algorithm had low efficiency in local extreme searching and low convergence accuracy,the two-point crossover multi-child genetic algorithm(TPC-MCGA)was proposed.The superiority of this algorithm was illustrated in theory.On this basis,the method of producing multi-child offspring was presented.This method not only improved the probability of creating excellent individuals with higher fitness,but increased searching accuracy around the current optimal solution so as to improve the local search ability of GA.In addition,since the internal competition operation was adopted in the evolution strategy,the population evolve increasingly in the limited living space which improved the convergence speed of GA.The results showed that the average computational time of TPC-MCGA was reduced 31% to 36% and the average iteration steps of TPC-MCGA was reduced 50.2% to 51.6% compared with TGA.The computational speed and the searched optimal solution accuracy of TPC-MCGA were increased obviously compared with traditional GA. Key words:multi-child genetic algorithm; two-point crossover; the quantity of children; evolution strategy 作者簡介:王福林(1959-),男,教授,博士,研究方向為農(nóng)業(yè)系統(tǒng)工程與管理科學與工程。E-mail:fulinwang1462@126.com 基金項目:國家自然科學基金(31071331);國家社會科學基金(13BJY098) 收稿日期:2015-12-06 中圖分類號:TP301.6 文獻標志碼:A 文章編號:1005-9369(2016)03-0072-085 TPC- MCGA進化策略
6 試驗與分析
7 討 論
8 結 論