Tsp問題的幾種算法的講解

1、摘要本文分析比較了 tsp 問題的動態(tài)規(guī)劃算法， 分支界限法，近似等算法。分析了旅行商問題的時間度特點(diǎn)，針對啟發(fā)式 算法求解旅行商問題中存在的一些問題提出了改進(jìn)算法。此 算法將群體分為若干小子集，并用啟發(fā)式交叉算子，以較好 利用父代個體的有效信息，達(dá)到快速收斂的效果，實(shí)驗(yàn)表明 此算法能提高尋優(yōu)速度，解得質(zhì)量也有所提高。關(guān)鍵詞：旅行商問題 TSPAbstractthis paper analyzed the time complexity of traveling salesman problem,then put forward some imprivement towards the gen

2、etic algorithm for solving this problen: divding the population into some small parent individual well.so it can quickly get into convergence, the experimental result indicates the impwoved algorithm can accelerate the apeed of finding solution and improve the precision.Keywords traveling salesman p

3、roblem; genetic algorithm; subset; henristic crossover operator目錄1、 摘要 -12、Abstract-13、Tsp 問題的提法 -24、回溯法求Tsp問題 -35、分支限界法求 Tsp 問題 -76、近似算法求解 Tsp 問題 -107、動態(tài)規(guī)劃算法解 Tsp 問題 -12引言tsp 問題剛提出時， 不少人都認(rèn)為很簡單。 后來，人們實(shí) 踐中才逐步認(rèn)識到，這個問題只是敘述簡單，易于為人所理 解而其計(jì)算復(fù)雜性卻是問題的輸入規(guī)模的指數(shù)函數(shù)，屬于 NP 完全問題。 Tsp 問題的實(shí)現(xiàn)思想已被應(yīng)用到交通， 管理等 很多領(lǐng)域所以有必要探討

4、Tsp 問題的算法。這里給出 Tsp 問 題的動態(tài)規(guī)劃算法，回溯算法，分支限界法，近似算法，和 改進(jìn)的啟發(fā)式算法，以及它們之間的分析比較。正文：旅行售貨員問題的提法是： 某售貨員要到若干城市去推銷商品，已知各城市之間的 路程（或旅費(fèi)） 。他要選定一條從駐地出發(fā)，經(jīng)過每個城市 一遍，最后回到駐地的路線，使總的路程（或旅費(fèi)）最小。設(shè) G=（V ,E） 是一個帶權(quán)圖。 圖中各邊的費(fèi)用 （權(quán)）為正數(shù)。 圖中的一條周游路線是包括 V 中的每個頂點(diǎn)在內(nèi)的一條回 路。周游路線的費(fèi)用是這條路線上所有邊的費(fèi)用之和。旅行 售貨員問題要在圖 G 中找到費(fèi)用最小的周游路線。圖 1-1:回溯法：(1 )回溯法的基本思想

5、：確定了解空間的組織結(jié)構(gòu)后， 回溯法從開始結(jié)點(diǎn)(根結(jié)點(diǎn))出發(fā)，以深度優(yōu)先方式搜索整 個解空間。這個開始結(jié)點(diǎn)成為活結(jié)點(diǎn)，同時也成為當(dāng)前的擴(kuò) 展結(jié)點(diǎn)處，搜索向縱深方向移至一個新結(jié)點(diǎn)。這個新結(jié)點(diǎn)即 成為新的活結(jié)點(diǎn)，并為當(dāng)前擴(kuò)展結(jié)點(diǎn)。如果在當(dāng)前的擴(kuò)展結(jié) 點(diǎn)處不能再向縱深方向移動，貝y當(dāng)前擴(kuò)展結(jié)點(diǎn)就成為死結(jié) 點(diǎn)。此時，應(yīng)往回移動(回溯)至最近的一個活結(jié)點(diǎn)處，并 使這個活結(jié)點(diǎn)成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)?；厮莘ㄒ赃@種工作方式 遞歸地在解空間中搜索，直至找到所要求的解或解空間中已 無活結(jié)點(diǎn)時為止。回溯法搜索解空間樹時，通常采用兩種則略避免無效搜 索，提高回溯法的搜索效率。其一是用約束函數(shù)在擴(kuò)展結(jié)點(diǎn) 處減去不滿足約束的

6、子數(shù)；其二是用界限函數(shù)剪去得不到最 優(yōu)解的子數(shù)。這兩類函數(shù)統(tǒng)稱為剪支函數(shù)。(2)回溯法解tsp問題：旅行售貨員問題的解空間可以 組織成一棵樹，從書的根結(jié)點(diǎn)到任一葉結(jié)點(diǎn)的路徑定義了圖 G的一條周游路線。圖 5-3是當(dāng)n=4時解空間樹的示例。其 中從根結(jié)點(diǎn)A到葉結(jié)點(diǎn)L的路徑上邊的標(biāo)號組成一條周游路 線1, 2, 3, 4, 1。而從根結(jié)點(diǎn)A到葉結(jié)點(diǎn)0的路徑則表示 周游路線1, 3, 4, 2, 1.圖G的每一條周游路線都恰好對應(yīng) 于解空間樹中一條從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的路徑。因此，解空間 樹中葉結(jié)點(diǎn)個數(shù)為【（n-1）!】。圖 1-2 :對于圖1-2的圖G,用回溯法找最小費(fèi)用路線時，從解空間 樹的根結(jié)點(diǎn)A

7、出發(fā)，搜索至B,C,F,L.在葉結(jié)點(diǎn)L處記錄找到 的周游路線1, 2, 3, 4, 1,該周游路線的費(fèi)用為 59.從葉結(jié) 點(diǎn)L返回至最近活結(jié)點(diǎn) F處。由于F處已沒有可擴(kuò)展結(jié)點(diǎn)。 算法又返回到結(jié)點(diǎn) C處。結(jié)點(diǎn)C成為新擴(kuò)展結(jié)點(diǎn)，由新擴(kuò)展 結(jié)點(diǎn)，算法再移至結(jié)點(diǎn) G后又移至結(jié)點(diǎn) M,得到周游路線1 ,2, 4, 3, 1，其費(fèi)用為66.這個費(fèi)用不比已有周游路線1, 2,3,4, 1的費(fèi)用更小。因此舍棄該結(jié)點(diǎn)。算法又依次返回至結(jié)點(diǎn)G , C, B。從結(jié)點(diǎn)B，算法繼續(xù)搜索至結(jié)點(diǎn)D , H , N。在葉結(jié)點(diǎn) N 處，相應(yīng)的周游路線 1，23， 2，4， 1 的費(fèi)用為25.它是當(dāng)前找到的最好的一條周游路線。從

8、結(jié)點(diǎn)N 算法返回至結(jié)點(diǎn) H ，D ，然后在從結(jié)點(diǎn) D 開始 D 開始繼續(xù)向縱深搜 索至結(jié)點(diǎn)0。以此方法算法繼續(xù)搜索遍整個解空間，最終得 到最小費(fèi)用周游路線 1，3， 2，4， 1.在遞歸算法 Backtrack 中，當(dāng) i=n 時，當(dāng)前擴(kuò)展結(jié)點(diǎn)是 排列數(shù)的葉結(jié)點(diǎn)的父結(jié)點(diǎn)。 此時算法檢測圖 G 是否存在一條 從頂點(diǎn) x【 n-1 到頂點(diǎn) xn 的邊和一條從頂點(diǎn) xn 到頂點(diǎn) 1 的 邊如果這兩條邊都存在，則找到一條旅行售貨員回路。此時 算法還需要判斷這條回路的費(fèi)用是否優(yōu)于已找到的當(dāng)前最 優(yōu)回路的費(fèi)用bustc。如果是則必須更新當(dāng)前最優(yōu)值bestc和當(dāng)前最優(yōu)解 bestx。當(dāng) in 時，當(dāng)前擴(kuò)展結(jié)

9、點(diǎn)位于排列樹的第 i-1 層。圖 G 中存在從頂點(diǎn) xi-1 到頂點(diǎn) xi 的邊時， xl,:i 構(gòu)成圖 G 的一條 路徑，且當(dāng) x;:i 的費(fèi)用小于當(dāng)前最優(yōu)值時算法進(jìn)入排列樹的 第i層，否則將剪去相應(yīng)的子數(shù)。算法中用變量cc記錄當(dāng)前路徑 x【l:i 的費(fèi)用。解旅行售貨員問題的回溯算法可描述如下：TemplateClass Travelingfriend Type tSP(int * *,int,int,Type);private:void Backtrack(int i); int n,*x, *bestx;Type* *a,cc, bestx;Type * *a,cc, bestc, No

10、Edge;TemplateVoid Traveling:Backtrack(int i)If(i=n)If(axn-1)xn!=NoEdge&axn1!=N0Edge&(cc+a xn-1xn+axn1best| bestc=NoEdge)for(int j=1;j=n;j+)bestxj=xj; bestc=cc+axn-1xn+axn1; elsefor(int j=i;j=n;j+) if(axi-1xj!=NoEdge&(cc+axi-1xjbestc|bestc =NoEdge)Swap(xi,xj; cc+=axi-1xi;Backtrack(i+10; cc-=axi-1xi;s

11、wap(xi,xj);分支界限法：(1)分支界限法的基本思想： 分支界限法以廣度優(yōu)先或 以最小耗費(fèi)(最大效益)優(yōu)勢的方式搜索問題的解空間樹。 問題的解空間樹是表示問題解空間的一棵有序樹，常見的有 子集樹和排列樹。在搜索問題的解空間樹時，分支界限法與 回溯法的主要區(qū)別在于他們對當(dāng)前擴(kuò)展結(jié)點(diǎn)所采用的擴(kuò)展 方式不同。在分支界限法中，每一個活結(jié)點(diǎn)只有一次機(jī)會成 為擴(kuò)展結(jié)點(diǎn)?；罱Y(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其所 有兒子結(jié)點(diǎn)。在這些兒子結(jié)點(diǎn)中，導(dǎo)致不可行解或?qū)е路亲?優(yōu)解得兒子結(jié)點(diǎn)被舍棄，其余兒子結(jié)點(diǎn)被加入活結(jié)點(diǎn)表中。此后，從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并重復(fù) 上述結(jié)點(diǎn)擴(kuò)展過程。這個過程一直

12、持續(xù)到找到所需的解或活 結(jié)點(diǎn)表為空時為止。（2）從活結(jié)點(diǎn)表中選擇下一個擴(kuò)展結(jié)點(diǎn)的不同方式導(dǎo)致 不同的分支界限法。最常用的有兩種方式1.方式隊(duì)列式（ FIFO ）分支界限法 隊(duì)列式分支界限法將活結(jié)點(diǎn)組織成一個隊(duì)列，并按隊(duì) 列的先進(jìn)先出原則選擇下一個結(jié)點(diǎn)為當(dāng)前擴(kuò)展結(jié)點(diǎn)。2優(yōu)先隊(duì)列式分支界限法 優(yōu)先隊(duì)列式的分支界限法將活結(jié)點(diǎn)表組織成一個優(yōu)先隊(duì) 列，并按優(yōu)先隊(duì)列中規(guī)定的結(jié)點(diǎn)優(yōu)先級選取優(yōu)先級最高的下 一個結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。（ 3）分支法解 tsp 問題：考察 4 城市旅行售貨員的例子， 如圖 5-3 所示，該問題的解空間樹是一棵排列樹。解次問題 的隊(duì)列式分支界限法以排列樹中結(jié)點(diǎn) B 作為初始擴(kuò)展結(jié)點(diǎn)

13、。 此時，活結(jié)點(diǎn)隊(duì)列為空。由于從圖 G 的頂點(diǎn) 1 到頂點(diǎn) 2， 3 和 4 均有邊相連，所以結(jié)點(diǎn) B 的兒子結(jié)點(diǎn) C，D， E 均為可 行結(jié)點(diǎn)，它們被加入到活結(jié)點(diǎn)隊(duì)列中，并舍去當(dāng)前擴(kuò)展結(jié)點(diǎn) B。當(dāng)前活結(jié)點(diǎn)隊(duì)列中的隊(duì)首結(jié)點(diǎn) C成為下一個擴(kuò)展結(jié)點(diǎn)。 由于圖 G 的頂點(diǎn) 2 到頂點(diǎn) 3 和 4 有邊相連，故結(jié)點(diǎn) C 的 2 個兒子結(jié)點(diǎn) F 和 G 均為可行結(jié)點(diǎn)， 從而被加入到活結(jié)點(diǎn)隊(duì)列 中。接下來，結(jié)點(diǎn) D 和結(jié)點(diǎn) E 相繼成為擴(kuò)展結(jié)點(diǎn)而被擴(kuò)展。F，G，H，I，J，K。用于表示活結(jié)點(diǎn)優(yōu)先隊(duì)列。 lcost 值是優(yōu)先隊(duì)列的優(yōu)先此時活結(jié)點(diǎn)隊(duì)列中的結(jié)點(diǎn)依次是算法描述： 算法開始時創(chuàng)建一個最小堆， 堆中每

14、個結(jié)點(diǎn)的子樹費(fèi)用的下界 級。接著算法計(jì)算出圖中每個頂點(diǎn)的最小費(fèi)用出邊并用minout 記錄。如果所給的有向圖中某個頂點(diǎn)沒有出邊，則該 圖不可能有回路，算法即告結(jié)束。如果每個頂點(diǎn)都有出邊， 則根據(jù)計(jì)算出的 minout 作算法初始化。算法的 while 循環(huán)體完成對排列樹內(nèi)部結(jié)點(diǎn)的擴(kuò)展。對 于當(dāng)前擴(kuò)展結(jié)點(diǎn)，算法分 2 種情況進(jìn)行處理：1、首先考慮 s=n-2 的情形，此時當(dāng)前擴(kuò)展結(jié)點(diǎn)是排列 樹中某個葉結(jié)點(diǎn)的父結(jié)點(diǎn)。如果該葉結(jié)點(diǎn)相應(yīng)一條可行回路 且費(fèi)用小于當(dāng)前最小費(fèi)用，則將該葉結(jié)點(diǎn)插入到優(yōu)先隊(duì)列 中，否則舍去該葉結(jié)點(diǎn)。2、當(dāng) sn-2 時，算法依次產(chǎn)生當(dāng)前擴(kuò)展結(jié)點(diǎn)的所有兒 子結(jié)點(diǎn)。由于當(dāng)前擴(kuò)展結(jié)點(diǎn)

15、所相應(yīng)的路徑是x0:s ，其可行兒子結(jié)點(diǎn)是從剩余頂點(diǎn) xs+1:n-1 中選取的頂點(diǎn) xi ，且 (xs ， xi) 是所給有向圖 G 中的一條邊。對于當(dāng)前擴(kuò)展結(jié)點(diǎn)的每一 個可行兒子結(jié)點(diǎn)，計(jì)算出其前綴 (x0:s ， xi) 的費(fèi)用 cc 和相 應(yīng)的下界 lcost 。當(dāng) lcostbestc 時，將這個可行兒子結(jié)點(diǎn)插入 到活結(jié)點(diǎn)優(yōu)先隊(duì)列中。算法中 while 循環(huán)的終止條件是排列樹的一個葉結(jié)點(diǎn)成 為當(dāng)前擴(kuò)展結(jié)點(diǎn)。 當(dāng) s=n-1 時，已找到的回路前綴是 x0:n-1 ， 它已包含圖 G 的所有 n 個頂點(diǎn)。因此，當(dāng) s=n-1 時，相應(yīng)的 擴(kuò)展結(jié)點(diǎn)表示一個葉結(jié)點(diǎn)。此時該葉結(jié)點(diǎn)所相應(yīng)的回路的費(fèi)

16、 用等于 cc 和 lcost 的值。 剩余的活結(jié)點(diǎn)的 lcost 值不小于已找 到的回路的費(fèi)用。它們都不可能導(dǎo)致費(fèi)用更小的回路。因此 已找到的葉結(jié)點(diǎn)所相應(yīng)的回路是一個最小費(fèi)用旅行售貨員 回路，算法可以結(jié)束。算法結(jié)束時返回找到的最小費(fèi)用，相應(yīng)的最優(yōu)解由數(shù)組v 給出。近似算法： 近似算法解旅行售貨員問題： 問題描述： 給定一個完全無向圖G=(V ,E) ，其每一邊 (u,v) E有一非負(fù)整數(shù)費(fèi)用 c(u,v)。要找出G的最小費(fèi)用哈密頓 回路。旅行售貨員問題的一些 特殊性質(zhì) ：比如，費(fèi)用函數(shù) c 往往具有 三角不等式性質(zhì) ，即對任意的 3 個頂點(diǎn) u,v,w V ,有：c(u,w) 1，不存 在性

17、能比為p的解旅行售貨員問題的多項(xiàng)式時間近似算法。2(d)(e)(b)表示找到的最小生成樹T; (c)表示對T作前序遍歷的次序；( (d)表示L產(chǎn)生的哈密頓回路 H ;(e)是G的一個最小費(fèi)用旅行售貨員回路動態(tài)規(guī)劃解tsp問題：由于貨郎擔(dān)問題經(jīng)過的路線是一條經(jīng)過所有城市的閉 合回路，因此從哪一點(diǎn)出發(fā)是無所謂的，因此不妨設(shè)從城市 1出發(fā)。問題的動態(tài)規(guī)劃模型構(gòu)造如下：階段k:已經(jīng)歷過的城市個數(shù)，包括當(dāng)前所在的城市。k=1,2,n , n+1 , k=1表示出發(fā)時位于起點(diǎn)，k=n+1表示結(jié) 束時回到終點(diǎn)。狀態(tài)變量：xk=(i, Sk)，其中i表示當(dāng)前所在的城市，Sk表示尚未訪問過的城市的集合。很明顯(

18、b)S仁2,3,n，Sn=Sn+1=F其中 F 表示空集。并且有xn=(i, F)i=2,3,n,xn+1=(1, F)決策變量： dk=( i , j ) ，其中 i 為當(dāng)前所在的城市， j 為下一站 將要到達(dá)的城市。狀態(tài)轉(zhuǎn)移方程：若當(dāng)前的狀態(tài)為xk=( i ,Sk)采取的決策為dk=( i , j )則下一步到達(dá)的狀態(tài)為xk+1=T(xk,dk)=( j ,Sk j)階段指標(biāo)：vk(xk,dk)=Cij最優(yōu)指標(biāo)函數(shù)：fk(xk)=fk(i,Sk)表示從城市 i 出發(fā)，經(jīng)過 Sk 中每個城市一次且僅一次，最后返回城市 1 的 最短距離。終端條件：fn+1(xn+1)=fn+1(1, F)=0

19、對于如圖 3.7.1 所示的一個五個城市的貨郎擔(dān)問題，求解步 驟如下： 對于 k=5 ，有f5(i,F)=minCij+f6(1,F)=Ci1i=2,3,4,5d5?(i,1)f5(I,F) 的值列表如下：if5(i, F)22374255對于 k=4 ，有f4(i, S4)=minCij+f5(j,S5)j?S4f4(i,S4) 的值列表如下：(i,S4) jCijS5Cij+f5(j,S5)f4(i,S4) j*(2,3)33F3+f5(3,F)=3+7=10103(2,4)45F5+f5(4,F)=5+2=774(2,5)51F1+f5(5,F)=1+5=665(3,2)23F3+f5(

20、2,F)=3+2=552(3,4)44F4+f5(4,F)=4+2=664(3,5)56F6+f5(5,F)=6+5=11115(4,2)25F5+f5(2,F)=5+2=772(4,3)34F4+f5(3,F)=4+7=11113(4,5)53F3+f5(5,F)=3+5=885(5,2)21F1+f5(2,F)=1+2=332(5,3)36F6+f5(3,F)=6+7=13133(5,4)43F3+f5(4,F)=3+2=554對于 k=3 ，有f3(i,S3)=minCij+f4(j,S4)j?S3f3(i,S3) 的值列表如下：(i,S3)j CijS4Cij+f4(j,S4)f3(i

21、,S3)j*(2,3,4)34354395314546 542105295411329526 5533+f4(3,4)=3+6=9*5+f4(4,3)=5+11=163(2,3,5) 35 31 3+f4(3,5)=3+11=14*1+f4(5,3)=1+13=14*3,5(2,4,5)45515+f4(4,5)=5+8=131+f4(5,4)=1+5=6*(3,2,4)24343+f4(2,4)=3+7=10*4+f4(4,2)=4+7=112(3,2,5) 25 363+f4(2,5)=3+6=9*6+f4(5,2)=6+3=9*2,5(3,4,5) 45 464+f4(4,5)=4+8=

22、126+f4(5,4)=6+5=11*5(4,2,3) 23 545+f4(2,3)=5+10=154+f4(3,2)=4+5=9*3(4,2,5)25535+f4(2,5)=5+6=113+f4(5,2)=3+3=6*(4,3,5)3543CM 寸1?二+(宀 2 寸)寸J+pzvg+g守弋co)寸J+9 宀寸 7CO9 E宀匕 (守(宙 P 寸)寸J+COSOH 卜 +v(守)7)寸J+ L 宀曼寸)COL5:0 (守 0LO)C07 二 * L LH9+9H (宀驚)E+9* L Luo L+ LM 柱 7)寸J+ L 0宀2 9L20 (宀0斜9) co9 L 9VCOL+e宀 Qgs

23、+rgVL L+寸M(宀 20)寸J+寸co寸 9 宀SSM (宀 90.斜寸)4 6 寸V8 +9守 0lo)2+9ov9+寸宀 90.寸)2+寸 *69+(宀 9i7)2+co9 寸co宀SE0 (宀 9寸 00)9COL *COV4L+L 守(宀 9寸弋C02+C0 宅99寸) L9CO宀S寸總 (宀9寸7)J (4S)Q 0S.DS2+0cosO- (4S)j*=2j*=5j*=43,52,52,3 5+f3(2,3,5)=5+14=194+f3(3,2,5)=4+9=13*3+f3(5,2,3)= 3+11=14 13 3(5,2,3,4) 234 163 3,42,42,31+f3

24、(2,3,4)=1+9=10*6+f3(3,2,4)=6+10=163+f3(4,2,3)= 3+9=12 10 2對于 k=1 ，有f1(1,S1)=minC1j+f2(j,S2)f1(1,S1)的值列表如下：(1,S1)jCijS2Cij+f2(j,S2)f1(1,S1)j*(1,2,3,4,5) 2345 2725 3,4,52,4,52,3,52,3,42+f2(2,3,4,5)=2+13=15*7+f2(3,2,4,5)=7+9=162+f2(4,2,3,5)=2+13=15*5+f2(5,2,3,4)=5+10=15*152,4,5由狀態(tài) x1=(1,2,3,4,5) 開始回朔，得

25、到(1,2,3,4,5)(2,3,4,5)(5,2,3,4)(42,3,5)j*=5j*=2j*=3(5,3,4)(2,3,4)(3,2,5)j*=3j*=3j*=2j*=5(3,4)(3,4)(2,5)(5,2)j*=4j*=4j*=4j*=2(4,)(4,)(5,)(2,)即得到以下四條回路：aaaaaaaaaaaaaaaaaaaa其中(1)和(4)是同一條回路， (2)和(3)是同一條回路。容易驗(yàn) 證，兩條回路的長度都是 15。動態(tài)規(guī)劃方法并不是解決 TSP 問題的一個好方法， 因其占用 空間和時間復(fù)雜度均較大。改進(jìn)的啟發(fā)式算法： 本算法將群體分成若干小子集，再進(jìn)行雜交變異操作，算法運(yùn)行

26、到一定階段，當(dāng)群體中最優(yōu)個體的適應(yīng)值之差小于 某個給定的初值時，表明解空間的搜索已經(jīng)基本完成，終止 遺傳迭代。算法采用最自然的路徑編碼表示方法，適應(yīng)值得 大小為個體所代表的路徑長度的倒數(shù)。1、分級對于給定規(guī)模的群體，按適應(yīng)值大小對個體進(jìn)行排序， 分成若干小子集，然后在各個小子集的后代個體按適應(yīng)值比 列選擇一定數(shù)目的個體組成新的群體，并且把父體也放在一 起競爭，避免最優(yōu)個體的遺失。這樣適應(yīng)值相似的個體進(jìn)行 交叉變異，優(yōu)秀的個體之間可以進(jìn)行局部最優(yōu)解的開采。而 且對每個小子集的后代以適應(yīng)值比列選擇，而不是把整個群 體放在一起進(jìn)行選擇，這樣可以讓群體保持一定得多樣性， 不易陷入早熟狀態(tài)。2、交叉算子 交叉算子的設(shè)計(jì)是遺產(chǎn)法的核心。一個好的交叉算子應(yīng) 該能從父體中繼承好的遺傳性狀，逐步提高子代的適應(yīng)度。 同時交叉算子應(yīng)能有效地搜索解空間，避免算法的過快收 斂。啟發(fā)式交叉算子如下：已知兩個父體，隨機(jī)選擇一個城 市 c 作為起點(diǎn)，在兩父體中分別找到 c 的右邊城市，并選取 兩個中距c較近的那個結(jié)點(diǎn)C作為子代中c的下一個結(jié)點(diǎn)， 且把城市結(jié)點(diǎn)C從父體中刪除，然后對 C再尋找離它較近的 下一個結(jié)點(diǎn)，直到完成整路徑為止，同理，另一子代產(chǎn)生方 法類似，只是相應(yīng)的選擇 c 的左邊城市，直到生成一個合法 個體.3、變異算子 遺產(chǎn)算法中，局部搜索能力和