【文章內(nèi)容簡介】 用其對等基因替換的現(xiàn)象，在TSP中位點(diǎn)變異可用于基于順序編碼的染色體。順序編碼下表示的路徑是基于順序表的，每個基因值可以重復(fù)出現(xiàn)，所以執(zhí)行位點(diǎn)變異操作后仍能表示一條合法的路徑，只是對等基因的值只能從一定范圍中取值。（2）逆轉(zhuǎn)變異逆轉(zhuǎn)變異是指在染色體上隨機(jī)選擇兩個變異點(diǎn)，將兩個變異點(diǎn)之間的基因按原來相反的次序進(jìn)行排列從而產(chǎn)生一條新的染色體。比如在選擇第二和第六個基因座為變異點(diǎn)后產(chǎn)生的新個體為。（3）對換變異對換變異是指在染色體上隨機(jī)選擇兩個變異點(diǎn)，然后將這兩個基因進(jìn)行對換從而產(chǎn)生新個體。比如在選擇第二和第六個基因座為變異點(diǎn)后產(chǎn)生的新個體為。（4）隨機(jī)插入變異隨機(jī)插入變異是指在染色體上隨機(jī)選擇兩個變異點(diǎn)，將其中一個基因插入到另一個基因座后，從而產(chǎn)生新的個體。比如在選擇第二和第六個基因座為變異點(diǎn)后將第六個基因插入到第二個基因之后產(chǎn)生的新個體為。 基于遺傳算法對TSP實(shí)現(xiàn)的方法實(shí)現(xiàn)TSP的算法可表述為：第一步：定義基因、染色體、個體、最佳個體群、最差個體群和種群的變量類型，打開城市坐標(biāo)文件和統(tǒng)計(jì)結(jié)果輸出的磁盤文件；第二步：初始化。包括輸入控制參數(shù)（種群大小、染色體長度、交叉概率、變異概率、最大進(jìn)化代數(shù)、隨機(jī)數(shù)種子），對各種變量類型分配內(nèi)存，初始化種群；第三步：統(tǒng)計(jì)并輸出當(dāng)前種群中的最佳個體群和最差個體群，即最佳路徑和最差路徑；第四步：遺傳操作，包括從當(dāng)前種群選擇個體，進(jìn)行交叉和變異操作，產(chǎn)生新一代種群；第五步：用新一代種群替代當(dāng)前種群，返回第三步，直到達(dá)到最大進(jìn)化代數(shù)為止停止搜索。 數(shù)據(jù)結(jié)構(gòu)本文的程序用C語言實(shí)現(xiàn)。程序中用自然編碼法對路徑進(jìn)行編碼，即用城市序號的全排列編碼為染色體，染色體上的每一個基因?qū)?yīng)于一個城市的信息，包括城市的序號和二維坐標(biāo)值，染色體的長度即為所求城市的個數(shù)。個體的適應(yīng)度是基于排序的，第個個體的適應(yīng)度為，為個體在種群中排序后的序號，是介于的整數(shù)，為排序后第個個體的路徑長度。選擇操作用輪盤賭選擇法實(shí)現(xiàn)。在程序中基因（gene）是由城市序號和二維實(shí)數(shù)坐標(biāo)值構(gòu)成的結(jié)構(gòu)體，染色體是由基因構(gòu)成的數(shù)組，個體（individual）定義為由染色體、適應(yīng)度、路徑總距離、交叉位置、變異位置和兩個父個體構(gòu)成的結(jié)構(gòu)體，當(dāng)前種群（old population）和新產(chǎn)生的種群（new population）是由個體構(gòu)成的數(shù)組，數(shù)組長度即為種群規(guī)模（population size），在程序的統(tǒng)計(jì)輸出中記錄由最佳個體構(gòu)成的最佳個體群和由最差個體構(gòu)成的最差個體群，最佳個體和最差個體是由染色體、適應(yīng)度、路徑總距離和當(dāng)前進(jìn)化代數(shù)構(gòu)成的結(jié)構(gòu)體，最佳個體群和最差個體群分別是由最佳個體和最差個體構(gòu)成的數(shù)組。它們之間的構(gòu)成關(guān)系為圖九 數(shù)據(jù)結(jié)構(gòu)關(guān)系圖數(shù)據(jù)結(jié)構(gòu)定義為struct gene /*基因*/{ int cityno。 /*城市序號*/ double xcoordinate,ycoordinate。 /*城市位置坐標(biāo)*/}。struct individual /*個體*/{ struct gene *chrom。 /*染色體*/ double fitness。 /*個體適應(yīng)度*/ double totaldistance。 /*路徑總長度*/ int xcross,ycross。 /*交叉位置*/ int xmutation,ymutation。 /*變異位置*/ int parent[2]。 /*父個體*/}。struct bestever /*最佳個體*/{ struct gene *chrom。 /*最佳個體染色體*/ double fitness。 /*最佳個體適應(yīng)度*/ double totaldistance。 /*最佳個體的路徑總長度*/ int generation。 /*最佳個體生成代*/}。struct worstever /*最差個體*/{ struct gene *chrom。 /*最差個體染色體*/ double fitness。 /*最差個體適應(yīng)度*/ double totaldistance。 /*最差個體的路徑總長度*/ int generation。 /*最差個體生成代*/}。 實(shí)現(xiàn)方法程序中我們著重設(shè)計(jì)了不同的交叉算子和變異算子來實(shí)現(xiàn)TSP，主要有四組實(shí)現(xiàn)方法，分別為部分匹配交叉法+對換變異法（PMX+EM）、部分匹配交叉法+逆轉(zhuǎn)變異法（PMX+RM）、類貪婪交叉法+對換變異法(SGX+EM)和類貪婪交叉法+逆轉(zhuǎn)變異法(SGX+RM)。在隨機(jī)選擇兩個交叉點(diǎn)后，兩條父染色體上在由兩個交叉點(diǎn)確定的交叉區(qū)域之間基因的映射關(guān)系可能存在一對多的情形，即一個基因可能對應(yīng)多個其他的等位基因。這時在交換兩個父染色體的交叉區(qū)域之后形成的兩個初始子染色體中，在將交叉區(qū)域外的基因和交叉區(qū)域內(nèi)的基因進(jìn)行比較并用映射的基因替換相同基因的過程中，需要多次比較替換。當(dāng)比較替換一次后，由于是一對多的映射關(guān)系，一次替換后在交叉區(qū)域外仍然會有重復(fù)的基因，因此需要進(jìn)行第二次比較替換過程，如此下去直到整條染色體中沒有重復(fù)的基因?yàn)橹?。具體的部分匹配交叉算法C源程序見附錄A。我們從下面的兩個例子中可以歸納出需要進(jìn)行比較替換的次數(shù)。圖十所示為有五個基因的染色體，兩條父染色體分別為和，交叉點(diǎn)選在第二個和第四個基因座之后，交叉區(qū)域中有兩個基因，存在的映射關(guān)系有和。在交換交叉區(qū)域形成兩個初始子染色體后需要進(jìn)行兩次比較替換操作才能保證每條子染色體上沒有重復(fù)的基因。圖十 交叉點(diǎn)之間有兩個基因的情況圖十一所示為兩個交叉點(diǎn)之間有三個基因的部分匹配交叉操作，兩個父染色體分別為和，交叉點(diǎn)選在第一個和第四個基因座之后，存在的映射關(guān)系有、和，在交換兩條父染色體的交叉區(qū)域后形成初始子染色體后需要進(jìn)行三次比較替換操作。圖十一 交叉點(diǎn)之間有三個基因的情況通過歸納我們得出結(jié)論：定理：在進(jìn)行部分匹配交叉時，在交換兩條父染色體的交叉區(qū)域后產(chǎn)生的初始子染色體需要將交叉區(qū)域外與交叉區(qū)域內(nèi)的基因比較替換n次后才能保證得到的子染色體上不會再有重復(fù)的基因，n指交叉區(qū)域中的基因個數(shù)。證明：在隨機(jī)選擇了兩個交叉點(diǎn)之后兩條父染色體的交叉區(qū)域之間最多存在n組映射關(guān)系。若n組映射關(guān)系中均為一對一，則在將交叉區(qū)域外與交叉區(qū)域中的基因比較替換一次后則可以將所有交叉區(qū)域外與交叉區(qū)域中相同的基因替換掉。若n組映射關(guān)系中有k(k=n)組一對多的映射關(guān)系，則最多需要比較替換k次后可以將所有交叉區(qū)域外與交叉區(qū)域中相同的基因替換掉，這時會執(zhí)行nk次無用的比較替換操作。因此在進(jìn)行部分匹配交叉時進(jìn)行n次比較替換操作后就可以將所有交叉區(qū)域外與交叉區(qū)域中相同的基因替換掉。 類貪婪交叉法通常的交叉算法是兩個父個體產(chǎn)生兩個子個體，而類貪婪交叉法是兩個父個體只產(chǎn)生一個子個體的交叉算法，產(chǎn)生子個體時基因的產(chǎn)生類似于貪婪算法，因此這里我們把此種交叉算法命名為類貪婪交叉算法。為了和部分匹配交叉法能夠產(chǎn)生兩個子個體相統(tǒng)一，我們在程序中連續(xù)進(jìn)行兩次類貪婪交叉操作，函數(shù)最終返回兩個子個體。算法的基本思想是：假設(shè)兩條父染色體為和，子染色體設(shè)置為空，首先在基因中隨機(jī)選擇一個基因t，然后找到該基因分別在兩條父染色體上的位置x和y，則有，即基因、和相同，將該基因t加入到子染色體中，此時的子染色體為。然后取出父染色體自基因開始的上一個基因，將之與子染色體中現(xiàn)有的基因逐個比較，若子染色體中所有基因都與不同，則將向前加入到子染色體中，即，若基因和子染色體中的某一個基因相同，則不再對父染色體繼續(xù)執(zhí)行以上操作，接著取出父染色體自開始的下一個基因，將之與子染色體中現(xiàn)有的基因逐個比較，若子染色體中所有的基因都與不同，則將向后加入到子染色體中，此時，若基因與子染色體的某一個基因相同，則不再對父染色體繼續(xù)執(zhí)行以上操作，需要注意的是在對父染色體讀取基因時，若讀取到的第一個基因時下一次讀取的基因是從最后一個基因開始向前逐個讀取直到，同樣在對父染色體讀取基因時，若讀取到的最后一個基因時下一次讀取的基因是從第一個基因開始向后讀取直到。間隔地對父染色體、重復(fù)以上操作，直到從兩條父染色體中讀取的基因都分別與子染色體中的某一個基因相同，則停止貪婪操作。最后將剩余未讀取出的基因按隨機(jī)排列的順序補(bǔ)充到子染色體現(xiàn)有基因的末尾。這樣就得到了完整的子代染色體。圖十二說明了類貪婪交叉法的基本思想。類貪婪交叉法的C源程序見附錄B。圖十二 類貪婪交叉算法比如有兩個父染色體為、選擇基因3為起始基因，子染色體為，在父染色體和中找到基因3的位置分別為5和2。開始貪婪操作：讀取中第四個基因1，將之與中現(xiàn)有的基因比較，發(fā)現(xiàn)與中的基因都不同，則將1向前加入到中，得到，接著讀取中第三個基因4，將之與中的基因比較，發(fā)現(xiàn)與中現(xiàn)有的基因都不同，則將4向后加入到中，得到，重復(fù)上述操作得到，然后找出剩余的基因5和6并將基因5和6以隨機(jī)的排列順序補(bǔ)充到的末尾得到。 對TSP各組實(shí)現(xiàn)方法的比較在程序運(yùn)行時，我們將最大進(jìn)化代數(shù)設(shè)置為3000，，種群規(guī)模設(shè)置為2倍的城市的個數(shù)。文中對TSPLIB中經(jīng)典的Oliver Eil 51和中國旅行商問題CTSP 31進(jìn)行了求解，它們的坐標(biāo)文件見附錄C。程序運(yùn)行時將初始種群設(shè)置成相同的種群，這樣可以更好地比較四組方法。為了比較四組實(shí)現(xiàn)方法的優(yōu)劣我們需要用到以下幾個衡量指標(biāo)：最佳個體的路徑長度、程序中最佳個體得到的最早代數(shù)和平均路徑隨進(jìn)化代數(shù)的變化情況。 最佳個體路徑長度的比較最佳個體是指程序運(yùn)行到最大進(jìn)化代數(shù)時搜索到的最優(yōu)個體，也正是問題所需要的求解結(jié)果。因此我們認(rèn)為若某個算法運(yùn)行到最后一代后得到的最佳個體它的路徑長度較其他算法運(yùn)行到最后一代后得到的最佳個體的路徑長度越小則此算法較好，但是前提是必須保證最佳個體是全局最優(yōu)的或滿意的。分別對Oliver Eil 51和CTSP 31求解后我們得到如下對最佳個體路徑長度的統(tǒng)計(jì)數(shù)據(jù)以及最佳個體的路徑圖。最佳個體路徑長度Oliver 30Eil 51CTSP 31PMX+EMPMX+RMSGX+EMSGX+RM表二 最佳個體路徑長度的統(tǒng)計(jì)數(shù)據(jù)圖十三 四組方法下Oliver 30最佳個體的路徑圖從圖十三和表二的對照中可以看出路徑之間的交叉點(diǎn)越多得到的路徑越長。對于Oliver 30 SGX+RM 得到的最佳路徑最短，最佳個體路徑圖中路徑之間沒有交叉點(diǎn)，而PMX+RM得到的最佳路徑最長，對應(yīng)的最佳個體路徑圖中路徑之間的交叉點(diǎn)最多。圖十四 四組方法下Eil 51最佳個體的路徑圖對于Eil 51同樣SGX+RM得到了最短的路徑，最佳個體路徑圖中沒有交叉點(diǎn)，而PMX+EM得