遺傳算法及其應(yīng)用實(shí)例

1、Page of20遺傳算法及其應(yīng)用實(shí)例遺傳算法(GeneticAlgorithm)是由美國(guó)Michigan大學(xué)的Holland教授(1969)提出，后經(jīng)由DeJong(1975),Goldberg(1989)等歸納總結(jié)所形成的一類(lèi)模擬進(jìn)化算法。遺傳算法搜索最優(yōu)解的方法是模仿生物的進(jìn)化過(guò)程，即通過(guò)選擇與染色體之間的交叉和變異來(lái)完成的。遺傳算法主要使用選擇算子、交叉算子與變異算子來(lái)模擬生物進(jìn)化，從而產(chǎn)生一代又一代的種群X(t)。選擇算子：是模擬自然選擇的操作，反映“優(yōu)勝劣汰”原理。它根據(jù)每一個(gè)個(gè)體的適應(yīng)度，按照一定規(guī)則或方法，從t代種群X(t)中選擇出一些優(yōu)良的個(gè)體(或作為母體，或讓其遺傳到下一代

2、種群X(t1)。彳(2)交叉算子：是模擬有性繁殖的基因重組操作，它將從種群X的所選擇的每一對(duì)母體，以一定的交叉概率交換它們之間的部分基因。呻(3)變異算子：是模擬基因突變的遺傳操作，它對(duì)種群X(t)中的每一個(gè)個(gè)體，以一定的變異概率改變某一個(gè)或某一些基因座上的基因值為其他的等位基因。呻交叉算子與變異算子的作用都在于重組染色體基因，以生成新的個(gè)體。遺傳算法的運(yùn)算過(guò)程如下：步1（初始化）確定種群規(guī)模N，交叉概率P,變異概率P和終止進(jìn)化準(zhǔn)則；隨cm機(jī)生成N個(gè)個(gè)體作為初始種群X（0）；置t0。步2（個(gè)體評(píng)價(jià)）計(jì)算評(píng)估X（t）中各個(gè)體的適應(yīng)度。步3（種群進(jìn)化）選擇（母體）從X（t）中運(yùn)用選擇算子選擇出M/

3、2對(duì)母體（MN）。交叉對(duì)所選擇的M/2對(duì)母體，以概率P執(zhí)行交叉，形成Mc個(gè)中間個(gè)體。變異對(duì)m個(gè)中間個(gè)體分別獨(dú)立以概率P執(zhí)行變異，形成Mm個(gè)候選個(gè)體。選擇（子代）從上述所形成的M個(gè)候選個(gè)體中依據(jù)適應(yīng)度選擇出N個(gè)個(gè)體組成新一代種群X（t1）。步4（終止檢驗(yàn)）如已滿(mǎn)足終止準(zhǔn)則，則輸出Xtt1）中具有最大適應(yīng)度的個(gè)體作為最優(yōu)解，終止計(jì)算，否則置tt!并轉(zhuǎn)步2。以上運(yùn)算過(guò)程只是遺傳算法的多種實(shí)現(xiàn)方式中的一種，根據(jù)實(shí)際問(wèn)題的不同，遺傳算法的實(shí)現(xiàn)也是多種多樣的。遺傳算法具有通用、并行、穩(wěn)健、簡(jiǎn)單與全局優(yōu)化能力強(qiáng)等突出優(yōu)點(diǎn)，適用于解決復(fù)雜、困難的全局優(yōu)化問(wèn)題。一個(gè)優(yōu)化問(wèn)題被稱(chēng)為是復(fù)雜的，通常指它具有下述特征之

4、一：（1）目標(biāo)函數(shù)沒(méi)有明確解析表達(dá)（如非數(shù)值優(yōu)化問(wèn)題）。（2）目標(biāo)函數(shù)雖有明確表達(dá)，但不可能恰好估值（如大部分最優(yōu)控制問(wèn)題、金融優(yōu)化問(wèn)題）。（3）目標(biāo)函數(shù)有極多的峰值（如DNA計(jì)算、組合優(yōu)化問(wèn)題）。（4）多目標(biāo)優(yōu)化，即目標(biāo)函數(shù)是向量值。一個(gè)優(yōu)化問(wèn)題被稱(chēng)為是困難的，則通常是指：或者目標(biāo)函數(shù)f不連續(xù)、不可微、高度非線(xiàn)性，或者優(yōu)化問(wèn)題是困難的組合問(wèn)題。對(duì)于這些復(fù)雜、困難的優(yōu)化問(wèn)題，已知的優(yōu)化方法或者根本不可用，或者可用但不有效。相比之下，遺傳算法不但保證可用，而且常常顯得更為有效。但是，我們必須注意到，一個(gè)通用而又較少依賴(lài)于目標(biāo)函數(shù)值與其他輔助信息的算法不可能比專(zhuān)用且充分利用目標(biāo)函數(shù)值與相關(guān)輔助信息

5、的算法更為有效，而當(dāng)一個(gè)問(wèn)題有某些輔助信息可供使用時(shí)舍棄應(yīng)用本來(lái)可供應(yīng)用的信息而去應(yīng)用于這些信息無(wú)關(guān)的算法也不是一個(gè)聰明的選擇。所以，遺傳算法一般來(lái)說(shuō)并不適宜應(yīng)用于通常的數(shù)值優(yōu)化問(wèn)題（例如連續(xù)可微的數(shù)學(xué)規(guī)劃問(wèn)題），或者說(shuō)，當(dāng)應(yīng)用于這樣的問(wèn)題時(shí)，遺傳算法并不總能顯示其優(yōu)越性。接下來(lái)，我們通過(guò)一個(gè)求解簡(jiǎn)單函數(shù)的最小值點(diǎn)的問(wèn)題來(lái)初步展示遺傳算法的具體實(shí)現(xiàn)方法：?jiǎn)栴}1：求函數(shù)f(X)Ilsin(6x)7cos(5x)在x0,2區(qū)間上的最小值點(diǎn)。20151050-5-10-15上圖為函數(shù)f(x)Ilsin(6x)7cos(5x)在x0,2闔區(qū)間上的曲線(xiàn)圖像,可以看出，該函數(shù)有多個(gè)極值點(diǎn)，如果使用其他的搜

6、尋方法，很容易陷入局部最小點(diǎn)，而不能搜尋到真正的全局最小點(diǎn)，但遺傳算法可以較好地彌補(bǔ)這個(gè)缺陷。遺傳算法的具體實(shí)現(xiàn)如下：1問(wèn)題分析。對(duì)于本問(wèn)題，自變量x可以抽象為個(gè)體的基因組，即用二進(jìn)制編碼表示x；函數(shù)值f(x)可以抽象為個(gè)體的適應(yīng)度，函數(shù)值越小，適應(yīng)度越高。關(guān)于二進(jìn)制編碼方式，在精度允許的范圍下，可以將區(qū)間內(nèi)的無(wú)窮多點(diǎn)用間隔足夠小的有限點(diǎn)來(lái)代替，以降低計(jì)算量同時(shí)保證精度損失不大。如用16位二進(jìn)制數(shù)來(lái)表示該區(qū)間的點(diǎn)，相鄰點(diǎn)的間隔僅為2丄09.5875110-5，相鄰點(diǎn)的函數(shù)值的變化幅度已經(jīng)很小，由此帶來(lái)216-1的精度損失完全可以接受。另一個(gè)問(wèn)題是普通的二進(jìn)制編碼方式可能具有較大的漢明(Hamm

7、ing距離，例如15和16的二進(jìn)制表示為01111和10000,從15到16必須改變所有位，這種缺陷將降低遺傳算法的搜索效率。采用格雷編碼(GrayEncoding)可以避免這一缺陷。格雷碼的特點(diǎn)是任意兩個(gè)連續(xù)的兩個(gè)整數(shù)的編碼值之間只有一個(gè)位是不同的，其他位都完全相同。格雷編碼的原理如下：設(shè)有二進(jìn)制串bb12b，對(duì)應(yīng)的格雷串a(chǎn)aa，則從二進(jìn)制編碼n12n到格雷編碼的變換為ab,i-1啟-b.，i-1川從格雷編碼到二進(jìn)制編碼的變換為b(-a)mod2。ijj例如，0-15的格雷碼如下表所示：01234567000000010011001001100111010101008910111213141

8、5110011011111111010101011100110002.根據(jù)遺傳算法的運(yùn)算過(guò)程編寫(xiě)程序。%f(x)=11sin(6x)+7cos(5x),0=x=2*piL=16；N=32；M=48；T=100；Pc=0.8；Pm=0.03；fori=1:1:Nx1(1,i)=rand()*2*pi；x2(1,i)=uint16(x1(1,i)/(2*pi)*65535)；grayCode(i,:)=num2gray(x2(1,i),L)；endfort=1:1:Ty1=11*sin(6*x1)+7*cos(5*x1)；fori=1:1:M/2a,b=min(y1)；grayCodeNew(i,

9、:)=grayCode(b,:)；grayCodeNew(i+M/2,:)=grayCode(b,:)；y1(1,b)=inf；endfori=1:1:M/2p=unidrnd(L)；ifrand()Pcforj=p:1:Ltemp=grayCodeNew(i,j)；grayCodeNew(i,j)=grayCodeNew(M-i+1,j)；grayCodeNew(M-i+1,j)=temp；endendendfori=1:1:Mforj=1:1:Lifrand()PmgrayCodeNew(i,j)=1-grayCodeNew(i,j)；endendendfori=1:1:Mx4(1,i)=

10、gray2num(grayCodeNew(i,:)；endx3=double(x4)*2*pi/65535；y3=11*sin(6*x3)+7*cos(5*x3)；fori=1:1:Na,b=min(y3)；x1(1,i)=x3(1,b)；grayCodei,:)=grayCodeNew(b,:)；y3(1,b)=inf；endendx1y1=11*sin(6*x1)+7*cos(5*xl)3.結(jié)論分析。程序運(yùn)行結(jié)果為：最小值點(diǎn)為x1.8486,f（x）17.8340。下面針對(duì)上面的問(wèn)題，討論遺傳算法中一些初始化參數(shù)的設(shè)定方法及其影響。（1）編碼長(zhǎng)度L。使用二進(jìn)制編碼時(shí)，L通常由對(duì)問(wèn)題的求解精

11、度決定，編碼長(zhǎng)度L越長(zhǎng)，可期望的最優(yōu)解的精度也就越高，但應(yīng)注意過(guò)大的L會(huì)增大運(yùn)算量。（2）種群規(guī)模N。種群規(guī)模N表示每一代種群中所含個(gè)體數(shù)目。當(dāng)N取值較小時(shí)，可提高遺傳算法的運(yùn)算速度，但卻降低種群的多樣性，容易引起遺傳算法早熟，出現(xiàn)假收斂；而當(dāng)N取值較大時(shí)，又會(huì)使得遺傳算法效率降低。一般建議的取值范圍是20100。（3）交叉概率P。在遺傳算法中交叉算子被認(rèn)為是主要搜索算c子，因而一般取較大值。一般說(shuō)，較大的P容易破壞群體中已形成的c優(yōu)良模式，是搜索的隨機(jī)性太大，而較小的P使發(fā)現(xiàn)新個(gè)體（特別是c優(yōu)良新個(gè)體）的速度太慢。一般建議的取值范圍是0.40.99。另外，比較理想的的方式是非一致地使用交叉概

12、率，例如在遺傳算法的前期使用較大的P，后期降低P以保留優(yōu)良個(gè)體。cc（4）變異概率p。較大的變異概率P使遺傳算法在整個(gè)搜索空mm間中大步跳躍，而小的變異概率使遺傳算法聚焦于特別區(qū)域作局部搜索。一般在不使用交叉算子的情形(演化策略(EvolutionStrategy)算法，進(jìn)化程序(EvolutionProgramming)算法)，變異算子作主要搜索算子，P取較大值(0.41)；而在與交叉算子聯(lián)合使用的情形(遺m傳算法)，P通常取較小值(0.00010.5)。m終止進(jìn)化代數(shù)t。遺傳算法不同于傳統(tǒng)優(yōu)化算法，它很難有明確的搜索終止準(zhǔn)則(特別是對(duì)于非數(shù)值優(yōu)化問(wèn)題)，于是通常需指定一個(gè)終止進(jìn)化代數(shù)來(lái)終止

13、算法，一般設(shè)T100,1000。一般來(lái)說(shuō)，事先指定T通常只能找到給定問(wèn)題的在給定時(shí)限內(nèi)所能尋求的相對(duì)滿(mǎn)意解，但不一定是問(wèn)題的最優(yōu)解或較高精度的近似解。為了獲得較高精度解，通?？梢罁?jù)種群適應(yīng)度的穩(wěn)定情況來(lái)實(shí)時(shí)調(diào)整T的設(shè)置?？傮w來(lái)說(shuō)，以上參數(shù)的確定并沒(méi)有明確的準(zhǔn)則可依據(jù)，需要根據(jù)實(shí)際問(wèn)題的特點(diǎn)以及算法的運(yùn)行情況進(jìn)行實(shí)時(shí)的調(diào)整，以搜索獲得更為滿(mǎn)意的最優(yōu)解。Page of20L=32；N=60；M=80；T=100；Pc:=0.6；Pm:=0.02；fori=1:1:Nx10(1,i)=unidrnd(2人Lx10(2,i)=unidrnd(2人Lx11(1,i)=double(x10(1,x11(2

14、,i)=double(x10(2,-1);-1);i)/(2人L-1)*10-5；i)/(2人L-1)*10-5；接下來(lái)，我們用遺傳算法來(lái)求解一個(gè)更為復(fù)雜的函數(shù)最值問(wèn)題。問(wèn)題2：求Schaffer函數(shù)的最大值點(diǎn)：sin2Jx2x20.5:,x)0.5丄2,Sx5,i1,212l0.001(x2x2)2i丄20.8-0.4-0.2-5-5根據(jù)遺傳算法的一般運(yùn)算過(guò)程編寫(xiě)MATLAB程序如下：Page #of20endfortPage of20foritemp1(1,i)=x11(1,i)人2+x11(2,i)人2；y1(1,i)=0.5-(sin(sqrt(temp1(1,i)*temp1(1,i

15、)；grayCode1(1,grayCode1(2,endi,：)i,：)=num2gray(x10(1,=num2gray(x10(2,i),i),fori=1:1:a,b=max(y1)；grayCode2(1,i,grayCode2(2,i,y1(1,b)=-inf；end：）：）=grayCode1(1,b,=grayCode1(2,b,：）；：）；人2-0.5)/(1+.001L)；L)；fori=1:1:M/p=unidrnd(L)；ifrand()Pcforj=p:1:temp=grayCode2(1,i,j)；grayCode2(1,i,j)=grayCode2(1,grayC

16、ode2(1,M-i+1,j)=temp；temp=grayCode2(2,i,j)；grayCode2(2,grayCode2(2,endM-i+1,j)；endendfori=1:1:Mforj=1:1:Lfork=1:1:ifrand()grayCode2endendendendfori=1:1:Mx20(1,x20(2,x21(1,x21(2,i)i)i)i)i,j)M-iPm=grayCode2(2,M-i+1,j)；+1,j)=temp；j)=1-grayCode2(k,i,j)；=gray2num(grayCode2(1,i,=gray2num(grayCode2(2,i,=do

17、uble(x20(1,i)/(2人=double(x20(2,i)/(2人：)；：)；L-1)*L-1)*i)人2；10-5；10-5；temp2(1,i)=x21(1,i)人2+x21(2,y2(1,i)=0.5-(sin(sqrt(temp2(1,i)人2-*temp2(1,i)；0.5)/(1+.001endPage of20fori=1:1:Na,b=max(y2)；x10(1,i)=x20(1,b)；x10(2,i)=x20(2,b)；x11(1,i)=x21(1,b)；x11(2,i)=x21(2,b)；y21,b)=-inf；endendxl1運(yùn)行結(jié)果顯示，遺傳算法常常在x2X2

18、2附近陷入局部最大，12而難以達(dá)到(x,x).(0,0)的全局最大點(diǎn)。為此，應(yīng)對(duì)遺傳算法加以改進(jìn)。12之前的遺傳算法存在的一個(gè)缺陷是不能保證搜尋到的最佳個(gè)體可以被遺傳到下一代，因此可能會(huì)錯(cuò)過(guò)全局最優(yōu)點(diǎn)。父子混合選擇遺傳算法(Father-OffspringCombinedSelectionGeneticAlgorithm)對(duì)此加以改進(jìn)，該算法要求上一代的最佳個(gè)體必須被無(wú)條件地遺傳到下一代，因此記錄了到目前為止算法所發(fā)現(xiàn)的最佳個(gè)體，因而適應(yīng)度序列必然具有單調(diào)性，即關(guān)于進(jìn)化代數(shù)是單調(diào)不減的?？梢宰C明的是，該算法是遺傳算法保證收斂的執(zhí)行策略。父子混合選擇遺傳算法的執(zhí)行過(guò)程如下：步1(初始化)隨機(jī)產(chǎn)生

19、M對(duì)母體組成初始種群X(0)，置t0。步2(種群進(jìn)化)獨(dú)立地對(duì)X(t)中的N對(duì)母體執(zhí)行交叉,生成中間種群Y(t(由N個(gè)中間個(gè)體組成)。獨(dú)立地對(duì)Y(t)中的每一個(gè)中間個(gè)體執(zhí)行變異，生成子代種群Z(t)。2.3.在父代種群x(t)與子代種群Z(t)的并集X(t)Z(t)中選擇N對(duì)母體作為新一代父代種群x(t.1)。步3(終止檢驗(yàn))4+4如果終止準(zhǔn)則滿(mǎn)足，停機(jī)并輸出X(t.1)中的最佳個(gè)體作為問(wèn)題的近似解，否則置tt.1并轉(zhuǎn)步2。根據(jù)這一算法重新編寫(xiě)程序。+L=32；N=60；T=100；Pc=0.6；Pm=0.02；fori=1:1:Nx0(1,i)=unidrnd(2人L-1)；x0(2,i)=

20、unidrnd(2人L-1)；endfort=1:1:Tfori=1:1:NgrayCode(1,i,:)=num2gray(x0(1,i),L)；grayCode(2,i,:)=num2gray(x0(2,i),L)；endfori=1:1:N/2ifrand()Pcp=unidrnd(L)；forj=1:1:p-1grayCode(1,i+N,j)=grayCode(1,i,j)；grayCode(2,i+N,j)=grayCode(2,i,j)；grayCode(1,N-i+1+N,j)=grayCode(1,N-i+1,j)；grayCode(2,N-i+1+N,j)=grayCode

21、(2,N-i+1,j)；endforj=p:1:LgrayCode(1,i+N,j)=grayCode(1,N-i+1,j)；grayCode(2,i+N,j)=grayCode(2,N-i+1,j)；grayCode(1,N-i+1+N,j)=grayCode(1,i,j)；grayCode(2,N-i+1+N,j)=grayCode(2,i,j)；endendendfori=N+1:1:2*Nforj=1:1:Lfork=1:1:2ifrand()PmgrayCode(k,i,j)=1-grayCode(k,i,j)；endendendendfori=N+1:1:2*Nx0(1,i)=gr

22、ay2num(grayCode(1,i,:)；x0(2,i)=gray2num(grayCode(2,i,:)；endfori=1:1:2*Nx1(1,i)=double(x0(1,i)/(2人L-1)*10-5；x1(2,i)=double(x0(2,i)/(2人L-1)*10-5；temp1,i)=x1(1,i)人2+x1(2,i)人2；y(1,i)=0.5-(sin(sqrt(temp(1,i)人2-0.5)/(1+0.001*temp(1,i)；endfori=1:1:Na,b=max(y)；x2(:,i)=x0(:,b)；y(1,b)=-inf；endfori=1:1:Nx0(:,i

23、)=x2(:,i)；endend運(yùn)行結(jié)果顯示，該算法已經(jīng)搜索到了近似最優(yōu)解(x,x)(0,0)12關(guān)于遺傳算法的收斂性問(wèn)題，這里可以給出幾個(gè)結(jié)論供參考。經(jīng)典遺傳算法并不保證全局最優(yōu)收斂，而只能在一定的約束條件下，實(shí)現(xiàn)全局最優(yōu)收斂。經(jīng)典遺傳算法可能出現(xiàn)未成熟收斂問(wèn)題，主要表現(xiàn)在以下兩個(gè)方面：一是群體中所有的個(gè)體都陷于同一適應(yīng)度而停止進(jìn)化；二是接近最優(yōu)解的個(gè)體總是被淘汰，進(jìn)化過(guò)程不收斂。抑制未成熟收斂的對(duì)策有：提高變異概率；調(diào)整選擇概率；維持群體中個(gè)體的多樣性等等。但這些方式都不能確保全局最優(yōu)收斂。但是，如果在每次迭代過(guò)程中保留最優(yōu)個(gè)體，那么就能夠保證其收斂。不過(guò)，保留最優(yōu)個(gè)體的遺傳算法在概率意義

24、下的收斂，并不表明該方法一定具有很快的收斂速度，也不意味著該方法具有更佳的性能，因?yàn)樗赡苄枰L(zhǎng)的時(shí)間，其計(jì)算代價(jià)可能是無(wú)法接受的。在設(shè)計(jì)遺傳算法的編碼方式時(shí)，應(yīng)考慮以下問(wèn)題：（1）對(duì)于問(wèn)題空間的任何一個(gè)點(diǎn)有表達(dá)空間的一個(gè)點(diǎn)與之對(duì)應(yīng)，即問(wèn)題空間的所有可能解都能表示為所設(shè)計(jì)得染色體形式。（2）對(duì)于表達(dá)空間中的任何一個(gè)點(diǎn)都有問(wèn)題空間中的一個(gè)點(diǎn)與之對(duì)應(yīng)，即任何一個(gè)染色體都對(duì)應(yīng)于一個(gè)可能解。（3）問(wèn)題空間和表達(dá)空間一一對(duì)應(yīng)。這三點(diǎn)是編碼方式或策略應(yīng)遵守的普遍準(zhǔn)則，但是，在實(shí)際應(yīng)用中，對(duì)于很多問(wèn)題，很難設(shè)計(jì)出同時(shí)滿(mǎn)足上述三個(gè)性質(zhì)的編碼方案。此時(shí)，首先必須滿(mǎn)足第一個(gè)要求，即在保證所有可能解均可以被表示為

25、染色體形式的前提下，是允許生成無(wú)用解的。最后，我們使用遺傳算法來(lái)解決一個(gè)更為貼近實(shí)際的問(wèn)題旅行商問(wèn)題（TravellingSalesmanProblem）。問(wèn)題的具體表述如下：一個(gè)旅行商需要訪(fǎng)問(wèn)個(gè)城市，在任意路線(xiàn)的兩個(gè)城市之間有一個(gè)關(guān)聯(lián)的費(fèi)用（例如公里數(shù)、航空費(fèi)用等）。找出一個(gè)費(fèi)用最少的路徑：從一個(gè)城市出發(fā)，經(jīng)過(guò)所有其他的城市一次且僅一次，然后回到出發(fā)點(diǎn)。這個(gè)問(wèn)題已被證明是NP難題，當(dāng)城市數(shù)量較大時(shí)，使用普通算法將耗費(fèi)大量的時(shí)間，因此我們嘗試使用遺傳算法來(lái)求解。適應(yīng)度評(píng)價(jià)函數(shù)的很直觀：我們要做的是評(píng)估路徑的長(zhǎng)度，然后按照長(zhǎng)度對(duì)路徑進(jìn)行排序，最短的就是最好的。因此，對(duì)于本問(wèn)題的求解，最重要的部分

26、在于編碼方式的確定。假設(shè)我們有9個(gè)城市要訪(fǎng)問(wèn)，編號(hào)為1,2,9。加入簡(jiǎn)單的用一個(gè)四位二進(jìn)制數(shù)(0001,0010,1001)來(lái)代表每一個(gè)城市，二進(jìn)制串0001001000110100010101100111B1000聊卩01代表按照序號(hào)順序進(jìn)行訪(fǎng)問(wèn)。但問(wèn)題在于，交叉算子與變異算子很難應(yīng)用到這種編碼方式上，一般的交叉算子和變異算子會(huì)產(chǎn)生大量的不可行解，從而影響搜索速度。另一種方式是使用一個(gè)數(shù)字(例如1,2,9)代表一個(gè)城市，通過(guò)對(duì)這9個(gè)數(shù)字排序構(gòu)造路徑，選擇合適的遺傳算子產(chǎn)生路徑。Davis(1985)提出了有序交叉(OrderCrossover)算子，較好地解決了這個(gè)問(wèn)題，具體方式如下：有序交

27、叉通過(guò)在一個(gè)雙親的路徑中選擇城市子序列創(chuàng)建子代。首先，選擇兩個(gè)劃分點(diǎn)，用|標(biāo)志，劃分點(diǎn)任意插入到雙親路徑中的相同位置，如：p1(19214657183)p2(459|1876|23)兩個(gè)子代和按下面的方法產(chǎn)生。首先，雙親中劃分點(diǎn)中間的部分復(fù)制到后代中：c1(|4657|)c2(118761)然后，從一個(gè)雙親路徑的第二個(gè)劃分點(diǎn)開(kāi)始，從另外一個(gè)雙親路徑中來(lái)的城市按相同的順序復(fù)制。當(dāng)字符串的結(jié)尾到達(dá)時(shí)，轉(zhuǎn)從字符串的開(kāi)始處繼續(xù)，最終得到兩個(gè)子代：cl(23914657118)c2(39211876145)一般來(lái)說(shuō)，對(duì)于TSP問(wèn)題，城市的順序在生成最少花費(fèi)路徑時(shí)非常重要，于是雙親路徑中的順序信息片段傳遞

28、到子代路徑中去時(shí)很關(guān)鍵的。根據(jù)該思路編寫(xiě)程序如下：(測(cè)試數(shù)據(jù)來(lái)自TSPLIB95：rd100.tsp)rd100=importdata(rd10O.tsp)；cityAmount=100；fori=1:1:cityAmountforj=1:1:cityAmountdistancei,j)=sqrt(rd100(i,2)-rd100(j,2)人2+(rd100(i,3)-rd100(j,3)人2)；endendL=100；N=200；T=10000；Pc=0.8；Pm=0.15；fori=1:1:Nx(i,:)=randperm(L)；endfort=1:1:Tfori=1:1:N/2ifran

29、d()p2temp=pl；pl=p2；p2=temp；endflagl=zeros(1,L)；flag2=zeros(1,L)；forj=pl:1:p2x(i+N,j)=x(i,j)；flagl(1,x(i,j)=1；x(N-i+1+N,j)=x(N-i+1,j)；flag2(1,x(N-i+1,j)=1；endj=p2+1；k=1；while1ifjLj=1；endifk=p1k=p2+1；endifkLbreak；endifflag1(1,x(N-i+1,j)=0 x(i+N,k)=x(N-i+1,j)；j=j+1；k=k+1；elsej=j+1；endendj=p2+1；k=1；while1ifjLj=1；endifk=p1k=p2+1；endifkLbreak；endifflag2(1,x(i,j)=0 x(N-i+1+N,k)=x(i,j)；j=j+1；k=k+1；elsej=j+1；endendelsex(i+N,:)=x(i,:)；x(N-i+1+N,:)=x(N-i+1,:)；endendf