基于遺傳算法求解TSP問(wèn)題實(shí)驗(yàn)報(bào)告

1、人工智能課程項(xiàng)目報(bào)告基于遺傳算法求解TSP問(wèn)題班級(jí)，學(xué)號(hào)，姓名摘要：巡回旅行商問(wèn)題（TSP）是一個(gè)組合優(yōu)化方面的問(wèn)題，從理論上講，使用窮舉法不但可以求解TSP問(wèn)題，而且還可以得到最優(yōu)解。但是，利用窮舉法所耗費(fèi)的時(shí)間巨大的，當(dāng)問(wèn)題的規(guī)模很大時(shí)，窮舉法的執(zhí)行效率較低，不能滿足及時(shí)的需要。 遺傳算法是計(jì)算機(jī)科學(xué)人工智能領(lǐng)域中用于解決最優(yōu)化的一種搜索啟發(fā)式算法，是進(jìn)化算法的一種。該算法通過(guò)模擬生物學(xué)交叉、變異等方式，是當(dāng)前向最優(yōu)解的方向進(jìn)化，因此使用于TSP問(wèn)題的求解。關(guān)鍵詞：人工智能；TSP問(wèn)題；遺傳算法本組成員：林志青，韓會(huì)雯，趙昊罡本人分工：掌握遺傳算法的基本原理，編寫(xiě)遺傳算法中部分匹配交叉、循

2、環(huán)交叉和循序交叉的具體實(shí)現(xiàn)過(guò)程。1 引言旅行商問(wèn)題，即TSP問(wèn)題，是一個(gè)最優(yōu)解的求解問(wèn)題。假設(shè)有n個(gè)城市，并且每個(gè)城市之間的距離已知，則如何只走一遍并獲得最短路徑為該問(wèn)題的具體解釋。對(duì)于TSP問(wèn)題的解決，有窮舉法、分支限界法等求解方式，該文章主要介紹遺傳算法求解過(guò)程。遺傳算法簡(jiǎn)稱GA，在本質(zhì)上是一種求解問(wèn)題的高效并行全局搜索方法。遺傳算法從任意一個(gè)初始化的群體出發(fā)，通過(guò)隨機(jī)選擇、交叉和變異等遺傳操作，使群體一代一代的進(jìn)化到搜索空間中越來(lái)越好的區(qū)域，直至抵達(dá)最優(yōu)解。在遺傳算法中，交叉操作為主要操作之一，包括部分匹配交叉、循環(huán)交叉和順序交叉等。2 算法原理與系統(tǒng)設(shè)計(jì)執(zhí)行遺傳算法，根據(jù)需要設(shè)定相應(yīng)的

3、交叉因子、變異因子和迭代次數(shù)，并選擇相應(yīng)的交叉算法，當(dāng)程序圖形顯示并運(yùn)算時(shí)會(huì)得到當(dāng)前的最優(yōu)解，判斷是否獲得最終的最優(yōu)解，若已得到所需結(jié)果，則停止運(yùn)行，否則繼續(xù)執(zhí)行。具體流程圖如下所示：部分匹配交叉（PMX）：先隨機(jī)生成兩個(gè)交叉點(diǎn)，定義這兩點(diǎn)間的區(qū)域?yàn)槠ヅ鋮^(qū)域，并交換兩個(gè)父代的匹配區(qū)域。如下圖所示：父代A：872 | 130 | 9546 父代B：983 | 567 | 1420 交換后變?yōu)椋?#160;temp A: 872 | 567 |

4、60;9546 temp B: 983 | 130 | 1420 對(duì)于 temp A、tempB中匹配區(qū)域以外出現(xiàn)的數(shù)碼重復(fù)，要依據(jù)匹配區(qū)域內(nèi)的位置逐一進(jìn)行替換。匹配關(guān)系：1<>5 3<>6 7<>0 子代A：802 | 567 | 9143 子代B：986 | 130 | 5427 順序交叉法（OX）：從父代隨機(jī)選一個(gè)編碼子串，放

5、到子代的對(duì)應(yīng)位置；子代空余的位置從父代B中按B的順序選?。ㄅc己有編碼不重復(fù)）。同理可得子代B，如下所示：父代A: 872 | 139 | 0546 父代B: 983 | 567 | 1420 交叉過(guò)程：對(duì)于父代A，選擇139進(jìn)行遺傳到下一代，其余部分從父代B中按照順序隨機(jī)選取，且不能和1、3、9數(shù)字相同，放到子代的對(duì)應(yīng)位置，得到下一代。交叉后： 子代A: 856 | 139 | 7420 子代B: 

6、;821 | 567 | 3904 循環(huán)交叉法（CX）：根據(jù)父代中的相應(yīng)位置的基因得到相應(yīng)的循環(huán)因子，該循環(huán)因子為子代的一部分，其余的因子從另一個(gè)父代中查找，找到不同于循環(huán)因子的基因并放到子代的對(duì)應(yīng)位置，形成新的子代。父代A：1 2 3 4 5 6 7 8 9 父代B：5 4 6 9 2 3 7 8 1 交叉過(guò)程：隨機(jī)選擇一個(gè)城市，如1，找到在父代B中對(duì)應(yīng)的城市為5，

7、再再返回到父代A中的城市5，對(duì)應(yīng)的父代B中的城市為2，依次查找，直達(dá)最終的城市為1為止。因此父代A的循環(huán)因子為1à5à2à4à9à1，另一子代的處理過(guò)程相似。交叉后：用循環(huán)的基因構(gòu)成子代A，順序與父代A一樣 1 2 4 5 9 ，用父代B剩余的基因填滿子代A： 1 2 6 4 5 3 7 8 9 3 系統(tǒng)實(shí)現(xiàn)部分匹配交叉：/先隨機(jī)產(chǎn)生兩個(gè)交叉點(diǎn)，定義這兩點(diǎn)間的區(qū)域?yàn)槠ヅ鋮^(qū)域，并用交換兩個(gè)

8、父代的匹配區(qū)域。double rand = Math.random();if(rand<pc)int m = (int)(Math.random()*cityNum);int n = (int)(Math.random()*cityNum);while(m=n)n = (int)(Math.random()*cityNum);if(m>n)int temp = m;m = n;n = temp;int tempA = new intn-m;int tempB = new intn-m;for(int e=m;e<n;e+)tempAe-m = populationa.gene

9、e;tempBe-m = populationb.genee;for(int e=m;e<n;e+)populationa.genee = tempBe-m;populationb.genee = tempAe-m;/對(duì)于tempA、tempB中匹配區(qū)域以外出現(xiàn)的數(shù)碼重復(fù)，要依據(jù)匹配區(qū)域內(nèi)的位置逐一進(jìn)行替換for(int e=0;e<m;e+)int p;while(p = Search(populationa.genee, tempB)!=-1) populationa.genee = tempAp;while(p = Search(populationb.genee, temp

10、A)!=-1)populationb.genee = tempBp;for(int e=n;e<cityNum;e+)int p;while(p = Search(populationa.genee, tempB)!=-1)populationa.genee = tempAp;while(p = Search(populationb.genee, tempA)!=-1)populationb.genee = tempBp;順序交叉：/選擇一定長(zhǎng)度的基因段進(jìn)行交換double rand = Math.random();if(rand<pc)int m = (int)(Math.ran

11、dom()*cityNum);int n = (int)(Math.random()*cityNum);while(m=n) n = (int)(Math.random()*cityNum);if(m>n)int temp = m;m = n;n = temp; int tempA = new intn-m;int tempB = new intn-m;for(int e=m;e<n;e+)tempAe-m = populationa.genee;tempBe-m = populationb.genee;int temp = new intcityNum;for(int e=0;e

12、<cityNum;e+) tempe = populationa.genee; /剩余部分從另一個(gè)父代中按照順序進(jìn)行選取，并隨機(jī)選取未在上述交換序列中的數(shù)字按位置/存放到子代中if(m=0)int q = n;for(int e=0;e<cityNum;e+)if(Search(populationb.genee, tempA)=-1)populationa.geneq = populationb.genee; q+; q=n;for(int e=0;e<cityNum;e+)if(Search(tempe, tempB)=-1)populationb.geneq = tem

13、pe; q+; elseint q=0;for(int e=0;e<cityNum;e+)if(Search(populationb.genee, tempA)=-1)populationa.geneq = populationb.genee;if(q=m-1) q = q+1+(n-m); else q+; q=0;for(int e=0;e<cityNum;e+)if(Search(tempe, tempB)=-1)populationb.geneq = tempe;if(q=m-1) q = q+1+(n-m); else q+; 循環(huán)交叉：/從當(dāng)前染色體A中隨機(jī)找到基因位置

14、，對(duì)應(yīng)得到另一染色體B中相應(yīng)位置的基因，/找到新基因在染色體A中的位置，繼續(xù)尋找下一基因，直到和最開(kāi)始的基因相同int q = (int)(Math.random()*cityNum);int v = populationa.geneq;tempAq = 1;int t=0;while(t=populationb.geneq)!=v)q = Search(t, populationa.gene);tempAq = 1; /將染色體B中不屬于循環(huán)因子的基因按位置填充到下一代染色體中for(int e=0;e<cityNum;e+)if(tempAe=0) populationa.genee

15、 = populationb.genee; q = (int)(Math.random()*cityNum);v = populationb.geneq;tempBq = 1;t = 0;while(t=tempq)!=v)q = Search(t, populationb.gene);tempBq = 1;for(int e=0;e<cityNum;e+)if(tempBe=0) populationb.genee = tempe; 4 實(shí)驗(yàn)或測(cè)試結(jié)果部分匹配算法： 當(dāng)前迭代次數(shù)：102539 當(dāng)前路徑長(zhǎng)度：144283順序交叉法： 當(dāng)前迭代次數(shù)：111974 當(dāng)前路徑長(zhǎng)度：153466循環(huán)交叉法： 當(dāng)前迭代次數(shù)：71302 當(dāng)前路徑長(zhǎng)度：1397145 結(jié)論從上面的三個(gè)算法的實(shí)現(xiàn)效果來(lái)看，當(dāng)?shù)拇螖?shù)有限時(shí)并沒(méi)有得到最終的最優(yōu)解，只是獲得了當(dāng)前情況下花費(fèi)最短和適應(yīng)度最高的路徑。從中可以了解到，遺傳算法能夠向最優(yōu)解的方向進(jìn)行進(jìn)化，但是進(jìn)化的方向是隨機(jī)的，即不一定在最開(kāi)始迭代中就得到最優(yōu)解的方向，而且不同的搜索算法所得到的最優(yōu)解盡管不是最終的解，但是各算法的當(dāng)前最優(yōu)解是相近的，因此遺傳算法不同方向的進(jìn)化程度是相似的，并有達(dá)到最優(yōu)解的可能性。該次求解過(guò)程中，主要考慮了交叉操作對(duì)問(wèn)題求解的影響