王福林，付曉明，朱會(huì)霞，趙勝雪（.東北農(nóng)業(yè)大學(xué)工程學(xué)院，哈爾濱　50030；.遼寧工業(yè)大學(xué)管理學(xué)院，遼寧　錦州　00）

?

基于兩點(diǎn)交叉多子代遺傳算法

王福林1，付曉明1，朱會(huì)霞2，趙勝雪1
（1.東北農(nóng)業(yè)大學(xué)工程學(xué)院，哈爾濱150030；2.遼寧工業(yè)大學(xué)管理學(xué)院，遼寧錦州121001）

摘要：針對(duì)目前遺傳算法局部搜索能力差、收斂精度低問(wèn)題，提出基于兩點(diǎn)交叉多子代遺傳算法（TPCMCGA），闡明該算法優(yōu)越性，并給出多子代個(gè)體產(chǎn)生方法。該方法可增加優(yōu)秀個(gè)體概率及算法在當(dāng)前最優(yōu)解周圍搜索精度，提高算法局部搜索能力。在進(jìn)化策略中引入種群內(nèi)部競(jìng)爭(zhēng)操作，使種群在有限生存空間內(nèi)加速進(jìn)化，提高算法運(yùn)算速度。結(jié)果表明，與傳統(tǒng)遺傳算法相比，TPC-MCGA平均計(jì)算時(shí)間減少31%～36%，平均迭代次數(shù)減少50.2%～51.6%，TPC-MCGA運(yùn)算速度與最優(yōu)解精度均明顯提高。

關(guān)鍵詞：多子代遺傳算法；兩點(diǎn)交叉；子代數(shù)量；進(jìn)化策略

王福林,付曉明,朱會(huì)霞,等.基于兩點(diǎn)交叉多子代遺傳算法[J].東北農(nóng)業(yè)大學(xué)學(xué)報(bào),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）是借鑒生物界自然選擇和進(jìn)化機(jī)制發(fā)展起來(lái)的高度并行、隨機(jī)、自適應(yīng)智能優(yōu)化算法[1-3]，由John H.Holland教授于1975年首次提出[4]。與傳統(tǒng)優(yōu)化算法相比，遺傳算法具有良好魯棒性、靈活性、通用性及較強(qiáng)全局搜索能力[5-7]，受到廣泛關(guān)注。但遺傳算法局部搜索能力較差，算法進(jìn)化后期搜索效率較低、收斂精度和運(yùn)算速度均難提高[8-9]。針對(duì)遺傳算法不足，近年研究者不斷改進(jìn)。Zhang等在遺傳算法中引入模擬退火機(jī)制，將模擬退火與遺傳算法結(jié)合，提高算法局部搜索能力[10]。Chen和Wang等為提高遺傳算法尋優(yōu)性能，將個(gè)體通過(guò)堿基編碼成生物分子，借鑒生物分子操作提高遺傳算法搜索效率和尋優(yōu)性能[11-12]。徐梅等提出一種改進(jìn)遺傳算法初始種群產(chǎn)生方法，提高遺傳算法求解有約束問(wèn)題搜索能力[13]。Saitoh等設(shè)計(jì)一種新量子遺傳算法，在每代所有染色體上根據(jù)量子交叉法交叉，實(shí)現(xiàn)二次加速，提高遺傳算法搜索能力[14]。王福林等提出一種改進(jìn)進(jìn)化策略遺傳算法，避免變異過(guò)程對(duì)交叉產(chǎn)生優(yōu)秀個(gè)體破壞，提高遺傳算法運(yùn)算速度[15]。本研究以生物學(xué)原理為基礎(chǔ)，針對(duì)目前遺傳算法局部搜索能力差，運(yùn)算速度慢、收斂精度低問(wèn)題，將生物學(xué)中“多子代”思想和“種群內(nèi)部競(jìng)爭(zhēng)”機(jī)制引入遺傳算法中，提出基于兩點(diǎn)交叉多子代遺傳算法（Two-point crossover multichild genetic algorithm，TPC-MCGA）。旨在解決目前遺傳算法局部搜索能力差、運(yùn)算效率低問(wèn)題，為充分發(fā)揮遺傳算法性能、提高算法求解能力提供有效途徑，為多子代遺傳算法應(yīng)用提供理論基礎(chǔ)。

1　遺傳算法基本假設(shè)

遺傳算法中存在如下基本假設(shè)①存在由多個(gè)生物個(gè)體組成種群；②生物個(gè)體之間存在差異，或群體具有多樣性；③生物能夠自我繁殖；④不同個(gè)體具有不同環(huán)境生存能力，具有良好基因結(jié)構(gòu)個(gè)體繁殖能力強(qiáng)，反之則弱[16]。在遺傳算法實(shí)際應(yīng)用中，假定種群規(guī)模始終保持不變，實(shí)際是隱含種群容量已飽和、種群容量受限假設(shè)。

2　多子代遺傳算法概念及其分析

多子代遺傳算法對(duì)多子代遺傳算法定義如下：

父代個(gè)體交叉產(chǎn)生子代個(gè)體數(shù)量多于其父代個(gè)體數(shù)量遺傳算法，稱為多子代遺傳算法（Multichild genetic algorithm，MCGA）。

在多子代遺傳算法中，子代個(gè)體數(shù)量一般是父代個(gè)體數(shù)量整數(shù)倍。令父代個(gè)體數(shù)量為N0，子代個(gè)體數(shù)量為N1時(shí)，有

其中，α-子代個(gè)體數(shù)量與其父代個(gè)體數(shù)量比例系數(shù)。

由式（1）可知，MCGA子代數(shù)量較多，在有限生存空間條件下，種群個(gè)體生存壓力增大，種群個(gè)體相互競(jìng)爭(zhēng)。在競(jìng)爭(zhēng)過(guò)程中，依據(jù)優(yōu)勝劣汰原則[18]，競(jìng)爭(zhēng)獲勝優(yōu)秀個(gè)體生存，競(jìng)爭(zhēng)失敗個(gè)體淘汰。因此，與傳統(tǒng)GA相比，MCGA種群個(gè)體間競(jìng)爭(zhēng)加劇，優(yōu)勝劣汰速度和種群進(jìn)化速度加快。

3　多子代遺傳算法理論基礎(chǔ)

3.1生物學(xué)基礎(chǔ)

達(dá)爾文進(jìn)化論中生物進(jìn)化論自然選擇學(xué)說(shuō)[17]包括高度生育率、生存斗爭(zhēng)、不定變異、最適者生存和受惠種族等因素。生物界中一對(duì)父代個(gè)體繁殖子代個(gè)體數(shù)量多于兩個(gè)，物種在進(jìn)化過(guò)程中不但能繼承父代個(gè)體特征，有利于在復(fù)雜變化自然環(huán)境中生存，生物物種不斷進(jìn)化，得到更優(yōu)良個(gè)體。而由父代個(gè)體產(chǎn)生子代個(gè)體數(shù)量小于或等于父代個(gè)體數(shù)量種群并不存在，即便存在，產(chǎn)生后代個(gè)體數(shù)量較少，導(dǎo)致有利生存基因在進(jìn)化中受外界環(huán)境因素影響而消失。

動(dòng)植物父代產(chǎn)生子代數(shù)量大多大于父代數(shù)量，多子代遺傳算法正是基于生物學(xué)原理而提出。

3.2數(shù)學(xué)生態(tài)學(xué)基礎(chǔ)

對(duì)種群規(guī)模增長(zhǎng)和下降研究，是數(shù)學(xué)生態(tài)學(xué)最古老分支[18-19]。為說(shuō)明一個(gè)種群能夠持續(xù)生存條件，需先討論種群滅絕概率，假設(shè)一個(gè)種群開(kāi)始只有一個(gè)個(gè)體，在某一時(shí)間t其規(guī)模將為0概率是

式中，i-初始種群數(shù)量，μ-死亡率，λ-生殖率。

關(guān)于式（2）推導(dǎo)過(guò)程請(qǐng)?jiān)斠?jiàn)文獻(xiàn)[18]，如果初始大小為i種群變到滅種，可見(jiàn)i個(gè)獨(dú)立家系均不存在，即對(duì)于任意i，這種事件概率是

要求出種群最終滅種概率，須使t趨于無(wú)窮。故對(duì)式（3）分三種情況討論：

a.當(dāng)生殖率小于死亡率時(shí)，即λ<μ時(shí)

顯然，在式（3）中指數(shù)項(xiàng)隨t→∞而變?yōu)?，因

此可得：

概率為1，顯然該種群無(wú)法延續(xù)。

b.當(dāng)生殖率大于死亡率時(shí)，即λ>μ時(shí)

則當(dāng)t→∞時(shí)，式（3）可化為

仍有可能滅種，但生殖率超過(guò)死亡率越多，生物滅種概率越小。

c.當(dāng)生殖率等于死亡率時(shí)，即λ=μ時(shí)

將式（3）中指數(shù)項(xiàng)展開(kāi)成級(jí)數(shù)形式，并令λ-μ= r，來(lái)求tl→im∞p（0t），因此

當(dāng)r→0時(shí)，r2項(xiàng)忽略，并且因?yàn)棣?μ=r，μ→λ，所以

顯然，

由此可見(jiàn)，即使生殖率等于死亡率，也會(huì)最終滅種。僅當(dāng)λ>μ時(shí)，即種群有正增加率，種群才有可能（并非必然）保持。數(shù)學(xué)生態(tài)學(xué)證明了當(dāng)生物初始種群數(shù)量已知時(shí)，生物種群規(guī)模取值概率分布只取決于每個(gè)個(gè)體增加率與時(shí)間乘積，所以高生殖率保持較短時(shí)間，和低生殖率保持較長(zhǎng)時(shí)間，只要每個(gè)個(gè)體增加率與時(shí)間乘積相等，就會(huì)得到相同結(jié)果，因此為在最短時(shí)間內(nèi)得到更加優(yōu)良個(gè)體，需要提高物種生殖率。

4　TPC- MCGA子代產(chǎn)生方法

傳統(tǒng)遺傳算法交叉操作是兩個(gè)父代生成兩個(gè)子代，而TPC-MCGA是兩個(gè)父代個(gè)體交叉產(chǎn)生兩個(gè)以上子代個(gè)體。假設(shè)有被選擇參與交叉兩個(gè)父代個(gè)體P1和P2，其編碼長(zhǎng)度均為l，隨機(jī)產(chǎn)生n（2< n≤l-1）個(gè)交叉點(diǎn)，則P1和P2染色體被分成n+1段，即P1=A1A2A3…Ak…An- 1AnAn + 1，P2=B1B2B3…Bk…Bn-1BnBn+1。TPC-MCGA子代產(chǎn)生方法是：首先在n個(gè)交叉點(diǎn)中任意選擇2個(gè)交叉點(diǎn)，把這兩個(gè)交叉點(diǎn)間所包括等位基因看作子串，交換兩個(gè)父代P1和P2子串形成兩個(gè)子代個(gè)體Child1和Child2；再在n個(gè)交叉點(diǎn)中任意選擇與之前非重復(fù)2個(gè)交叉點(diǎn)，交換兩個(gè)父代P1和P2子串形成兩個(gè)子代個(gè)體Child3和Child4；以此類推，兩個(gè)父代P1和P2可經(jīng)過(guò)Cn2次非重復(fù)交叉，最多可產(chǎn)生2Cn2個(gè)不同新子代個(gè)體。有如下定義：

一對(duì)父代染色體在隨機(jī)產(chǎn)生n（2

TPC-MCGA多子代個(gè)體產(chǎn)生方法見(jiàn)圖1。

由圖1可知，Child（ii=1，2，…，2Cn2）為交叉所產(chǎn)生第i個(gè)子個(gè)體。顯然，在TPC-MCGA中，一對(duì)父代能夠產(chǎn)生2Cn2個(gè)新子代個(gè)體，其子代個(gè)體數(shù)量是傳統(tǒng)GACn2倍。例如，有被選擇參與交叉兩個(gè)父代個(gè)體P1和P2，采用二進(jìn)制編碼，其分別為P1= 1011001000和P2=1100110110，設(shè)產(chǎn)生隨機(jī)交叉點(diǎn)個(gè)數(shù)n為3，假設(shè)這3個(gè)交叉點(diǎn)分別位于第3、6、8位，則有

交叉點(diǎn)：1 2 3

P1=101 100 10 00，

P2=110 011 01 10

因此，父代個(gè)體P1和P2按圖1所示兩點(diǎn)交叉多子代產(chǎn)生方法得到子代個(gè)體分別為：

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中子代個(gè)體數(shù)量明顯增加，子代中優(yōu)秀個(gè)體產(chǎn)生概率升高，同時(shí)一對(duì)父代個(gè)體交叉產(chǎn)生了更多具有相同父代特征子代個(gè)體，增加了算法最優(yōu)解周圍搜索精度，提高算法局部搜索能力。因此與傳統(tǒng)GA相比，TPC-MCGA具有更快收斂速度和更強(qiáng)尋優(yōu)能力。但子代個(gè)體數(shù)量過(guò)多必然導(dǎo)致每迭代一次運(yùn)算量增加，因此應(yīng)該選取合適子代數(shù)量。關(guān)于TPC-MCGA算法最佳子代數(shù)量確定需進(jìn)一步理論分析和試驗(yàn)研究，為驗(yàn)證TPC-MCGA優(yōu)越性，本文將以兩個(gè)父代交叉產(chǎn)生最少多子代個(gè)體為例（即兩個(gè)父代交叉產(chǎn)生4個(gè)多子代個(gè)體）進(jìn)行算法比較測(cè)試試驗(yàn)與分析。

圖1　兩點(diǎn)交叉多子代遺傳算法子代產(chǎn)生方法Fig.1 Method of producing multi-child offspring in TPC-MCGA

5　TPC- MCGA進(jìn)化策略

TPC-MCGA進(jìn)化策略是：首先產(chǎn)生種群規(guī)模為N0初始種群，計(jì)算種群個(gè)體適應(yīng)度；第二通過(guò)輪盤(pán)賭方式隨機(jī)選擇參與交叉?zhèn)€體，將被選中每對(duì)個(gè)體按兩點(diǎn)交叉產(chǎn)生多子代方法交叉，并從交叉產(chǎn)生N1個(gè)多子代個(gè)體和N0個(gè)父代個(gè)體中選擇m個(gè)具有最高適應(yīng)度個(gè)體作精英保留；第三對(duì)交叉產(chǎn)生N1個(gè)多子代個(gè)體變異，并將m個(gè)精英個(gè)體與變異后N1個(gè)子代個(gè)體進(jìn)行種群內(nèi)部競(jìng)爭(zhēng)，競(jìng)爭(zhēng)過(guò)程中淘汰（N1+m-N0）個(gè)低適應(yīng)度個(gè)體以保持種群規(guī)模不變，形成新種群；最后計(jì)算新種群個(gè)體適應(yīng)度，判斷是否滿足迭代終止條件，如果滿足，則停止迭代，如果不滿足，則循環(huán)以上過(guò)程使種群繼續(xù)進(jìn)化，到滿足終止條件為止。其進(jìn)化策略如圖2所示。

6　試驗(yàn)與分析

6.1試驗(yàn)方法與測(cè)試函數(shù)選取

為驗(yàn)證本文提出TPC-MCGA性能，選取6個(gè)常用典型測(cè)試函數(shù)[21-22]，將TPC-MCGA與傳統(tǒng)遺傳算法（Traditional genetic algorithm，TGA）進(jìn)行算法搜索性能對(duì)比試驗(yàn)。試驗(yàn)擬采用兩種方法：固定搜索精度運(yùn)算速度比較法和固定迭代次數(shù)求解精度比較法。

TPC-MCGA與TGA均采用二進(jìn)制編碼，初始種群隨機(jī)產(chǎn)生，試驗(yàn)參數(shù)設(shè)置如下：種群規(guī)模N0= 100，子代個(gè)體數(shù)量與其父代個(gè)體數(shù)量比例系數(shù)α= 2，交叉概率Pc=0.9，變異概率Pm=0.1，保留精英個(gè)體數(shù)m=10，TPC-MCGA與TGA迭代終止條件為：

式中，fi*-第i個(gè)函數(shù)理論最優(yōu)解；fi-算法搜索到第i個(gè)函數(shù)最優(yōu)解；εi-第i個(gè)函數(shù)搜索停止精度。

6個(gè)測(cè)試函數(shù)搜索停止精度εi均為10-4。兩種算法對(duì)每個(gè)測(cè)試函數(shù)在相同測(cè)試環(huán)境下分別獨(dú)立運(yùn)行1 000次。

所用6個(gè)測(cè)試函數(shù)包含多個(gè)已知極值點(diǎn)，有連續(xù)、非連續(xù)、單峰，多峰、病態(tài)等不同數(shù)學(xué)特征。

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

圖2　多子代遺傳算法進(jìn)化策略Fig.2 Evolution strategy ofTPC-MCGA

6.2試驗(yàn)結(jié)果與分析

由表1可知，TPC-MCGA與TGA算法對(duì)測(cè)試函數(shù)f1～f6固定搜索停止精度為10-4獨(dú)立對(duì)比試驗(yàn)結(jié)果，其中平均迭代次數(shù)和平均計(jì)算時(shí)間是指算法運(yùn)行1 000次對(duì)各測(cè)試函數(shù)符合迭代停止條件，即達(dá)到搜索停止精度平均迭代次數(shù)和平均計(jì)算時(shí)間。圖3～8分別給出固定迭代次數(shù)為500時(shí)，兩種算法對(duì)6個(gè)測(cè)試函數(shù)獨(dú)立運(yùn)行1 000次平均適應(yīng)度收斂曲線。由表1可知，6個(gè)測(cè)試函數(shù)取得最優(yōu)解時(shí)，TPC-MCGA平均計(jì)算時(shí)間0.3813～1.1250 s，平均迭代次數(shù)11.1185～39.2031次；TGA平均計(jì)算時(shí)間為0.5963～1.6231 s，平均迭代次數(shù)22.9530～ 78.7100次。與TGA相比，TPC-MCGA平均計(jì)算時(shí)間減少31%～36%，平均迭代次數(shù)減少50.2%～ 51.6%。顯然，TPC-MCGA平均計(jì)算時(shí)間與平均迭代次數(shù)均明顯優(yōu)于TGA。這是由于在函數(shù)優(yōu)化時(shí)，TPC-MCGA每次迭代產(chǎn)生子代個(gè)體數(shù)量多于TGA，因此子代種群規(guī)模要明顯大于TGA，增加了子代中高適應(yīng)度優(yōu)秀個(gè)體概率。子代個(gè)體經(jīng)過(guò)變異后，在種群競(jìng)爭(zhēng)過(guò)程中大部分低適應(yīng)度個(gè)體被淘汰，使在TPC-MCGA中生存子代個(gè)體平均適應(yīng)度高于TGA，同時(shí)在進(jìn)化策略中引入種群內(nèi)部競(jìng)爭(zhēng)操作，使子代種群規(guī)模與初始種群保持規(guī)模一致，保證種群在有限生存空間內(nèi)加速進(jìn)化。因此，TPCMCGA求解運(yùn)算速度明顯優(yōu)于TGA。

由圖3～8可知，與TGA算法相比，TPC-MCGA收斂精度明顯提高。尤其對(duì)于測(cè)試函數(shù)f3和f6，經(jīng)過(guò)少量次數(shù)迭代，TPC-MCGA即可達(dá)到理論最優(yōu)值。這是由于一對(duì)父代產(chǎn)生了更多具有相同父代特征子代個(gè)體，增加算法在當(dāng)前最優(yōu)解周圍搜索精度，提高算法局部搜索能力。

7　討　論

表1　TPC-MCGA與TGA算法測(cè)試結(jié)果Table 1 Testing results of TPC-MCGA and TGA

圖3　函數(shù)f1平均適應(yīng)度收斂曲線Fig.3 Convergence curve of average fitness for f1

圖5　函數(shù)f3平均適應(yīng)度收斂曲線Fig.5 Convergence curve of average fitness for f3

圖7　函數(shù)f5平均適應(yīng)度收斂曲線Fig.7 Convergence curve of average fitness for f5

圖4　函數(shù)f2平均適應(yīng)度收斂曲線Fig.4 Convergence curve of average fitness for f2

圖6　函數(shù)f4平均適應(yīng)度收斂曲線Fig.6 Convergence curve of average fitness for f4

圖8　函數(shù)f6平均適應(yīng)度收斂曲線Fig.8 Convergence curve of average fitness for f6

本試驗(yàn)結(jié)果表明，遺傳算法子代數(shù)量增加提高了算法求解運(yùn)算速度和收斂精度，與Hsieh等研究結(jié)果一致[23]。但在Hsieh研究中，將隨機(jī)產(chǎn)生個(gè)體加入子代種群中提高子代數(shù)量，因此搜索效率提高依靠隨機(jī)產(chǎn)生個(gè)體中出現(xiàn)優(yōu)秀個(gè)體概率，本文采用兩點(diǎn)交叉產(chǎn)生多子代個(gè)體方法，使產(chǎn)生多子代個(gè)體繼承父代特征，保留父代個(gè)體優(yōu)秀模式，提高子代出現(xiàn)優(yōu)秀個(gè)體概率，結(jié)果表明，采用本文提出方法，搜索效率和收斂精度均明顯提高。Shi等研究提出遺傳算法個(gè)體生存概率概念，使每代個(gè)體均有一定概率生存到下一（幾）代，因此子代數(shù)量增加，算法收斂加快，但后期過(guò)大種群規(guī)模導(dǎo)致運(yùn)算效率降低，不適于處理復(fù)雜優(yōu)化問(wèn)題[24]。Koljonen等研究認(rèn)為，種群規(guī)模增加提高遺傳算法穩(wěn)定性，但降低收斂速度[25]。本試驗(yàn)研究表明，通過(guò)引入種群內(nèi)部競(jìng)爭(zhēng)機(jī)制，增加子代群體通過(guò)競(jìng)爭(zhēng)淘汰低適應(yīng)度個(gè)體，保證種群在有限生存空間內(nèi)加速進(jìn)化，提高算法收斂速度。

本試驗(yàn)中選取子代個(gè)體數(shù)量與其父代個(gè)體數(shù)量比例系數(shù)α=2，即兩個(gè)父代交叉產(chǎn)生4個(gè)多子代個(gè)體。結(jié)果顯示，與TGA相比，TPC-MCGA平均計(jì)算時(shí)間與平均迭代次數(shù)均明顯減少，證明TPCMCGA優(yōu)越性，為解決目前遺傳算法局部搜索能力差，運(yùn)算速度慢，收斂精度低問(wèn)題提供有效方法。由本試驗(yàn)結(jié)果可知，當(dāng)取α=3時(shí)，TPC-MCGA平均計(jì)算時(shí)間與迭代次數(shù)進(jìn)一步減少，但減少量小于α= 2時(shí)計(jì)算時(shí)間和迭代次數(shù)減少量，這表明α=2并不非最佳子代與父代個(gè)體數(shù)量比。顯然，子代個(gè)體數(shù)量變化對(duì)TPC-MCGA性能有顯著影響。雖然本試驗(yàn)證明TPC-MCGA求解精度與運(yùn)算時(shí)間均優(yōu)于TGA，但不能確定TPC-MCGA最佳子代數(shù)量，對(duì)TPC-MCGA子代個(gè)體數(shù)量對(duì)算法性能影響及變化規(guī)律需深入研究。針對(duì)如不同編碼條件下TPCMCGA子代產(chǎn)生方法研究，TPC-MCGA子代數(shù)量與運(yùn)算速度關(guān)系研究，種群規(guī)模對(duì)TPC-MCGA算法收斂精度影響等有待進(jìn)一步探討。

8　結(jié)　論

本文在研究傳統(tǒng)遺傳算法基礎(chǔ)上，依據(jù)生物學(xué)和數(shù)學(xué)生態(tài)學(xué)理論，針對(duì)目前遺傳算法局部搜索能力差、運(yùn)算效率低問(wèn)題提出兩點(diǎn)交叉多子代遺傳算法（TPC-MCGA），該算法利用兩點(diǎn)交叉方式產(chǎn)生多于父代個(gè)體子代種群，使子代種群中出現(xiàn)優(yōu)秀個(gè)體概率明顯增加，提高算法尋優(yōu)能力。該算法在進(jìn)化策略中引入種群內(nèi)部競(jìng)爭(zhēng)操作，使多子代種群在有限生存空間內(nèi)競(jìng)爭(zhēng)，加快算法求解運(yùn)算速度。本研究結(jié)果表明，TPC-MCGA在運(yùn)算速度與求得最優(yōu)解精度上均明顯優(yōu)于TGA算法。

[參考文獻(xiàn)]

[1]Sivanandam S N,Deepa S N.Introduction to Genetic Algorithm[M].New York:Springer-verlag Berlin Heidelberg,2008.

[2]劉大蓮,徐尚文.求解約束優(yōu)化問(wèn)題內(nèi)外交叉遺傳算法[J].系統(tǒng)工程理論與實(shí)踐,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]趙紅杰,柏繼云,馬力.遺傳擴(kuò)展蟻群算法用于馬斯京根模型參數(shù)估計(jì)[J].東北農(nóng)業(yè)大學(xué)學(xué)報(bào),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]楊世達(dá),單志勇,李慶華.基于親緣選擇遺傳算法[J].計(jì)算機(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)化問(wèn)題時(shí)產(chǎn)生初始種群改進(jìn)方法[J].東北農(nóng)業(yè)大學(xué)學(xué)報(bào),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]王福林,朱會(huì)霞,王吉權(quán)等.遺傳算法一種改進(jìn)進(jìn)化策略[J].生物數(shù)學(xué)學(xué)報(bào),2015,30(1):69-74.

[16]李敏強(qiáng),寇紀(jì)淞,林丹,等.遺傳算法基本理論與應(yīng)用[M].北京:科學(xué)出版社,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]王福林,朱會(huì)霞,王吉權(quán).遺傳算法一種改進(jìn)進(jìn)化策略[J].生物數(shù)學(xué)學(xué)報(bào),2015,30(1):69-74.

[22]王小平,曹立明.遺傳算法-理論應(yīng)用與軟件實(shí)現(xiàn)[M].西安:西安交通大學(xué)出版社,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

作者簡(jiǎn)介：王福林（1959-），男，教授，博士，研究方向?yàn)檗r(nóng)業(yè)系統(tǒng)工程與管理科學(xué)與工程。E-mail:fulinwang1462@126.com

基金項(xiàng)目：國(guó)家自然科學(xué)基金（31071331）；國(guó)家社會(huì)科學(xué)基金（13BJY098）

收稿日期：2015-12-06

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

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

文章編號(hào)：1005-9369（2016）03-0072-08