TSP問題的遺傳算法求解摘要：遺傳算法是模擬生物進化過程的一種新的全局優化搜索算法，本文簡單介紹了遺傳算法，并應用標準遺傳算法對旅行包問題進行求解。關鍵詞：遺傳算法、旅行包問題旅行包問題描述：旅行商問題，即TSP問題（TravelingSalemanProblem）是數學領域的一個著名問題，也稱作貨郎擔問題，簡單描述為：一個旅行商需要拜訪n個城市（1，2，…，n），他必須選擇所走的路徑，每個城市只能拜訪一次，最后回到原來出發的城市，使得所走的路徑最短。其最早的描述是1759年歐拉研究的騎士周游問題，對于國際象棋棋盤中的64個方格，走訪64個方格一次且最終返回起始點。用圖論解釋為有一個圖G=（V,E），其中V是頂點集，E是邊集，設D=（dij）是有頂點i和頂點j之間的距離所組成的距離矩陣，旅行商問題就是求出一條通過所有頂點且每個頂點只能通過一次的具有最短距離的回路。若對于城市V={v1，v2，v3，...，vn}的一個訪問順序為T=(t1，t2，t3，…，ti，…，tn)，其中ti∈V(i=1，2，3，…，n)，且記tn+1=

t1，則旅行商問題的數學模型為：min

L=Σd(t(i),t(i+1))

（i=1，…，n）旅行商問題是一個典型組合優化的問題，是一個NP難問題，其可能的路徑數為（n-1）！，隨著城市數目的增加，路徑數急劇增加，對與小規模的旅行商問題，可以采取窮舉法得到最優路徑，但對于大型旅行商問題，則很難采用窮舉法進行計算。在生活中TSP有著廣泛的應用，在交通方面，如何規劃合理高效的道路交通，以減少擁堵；在物流方面，更好的規劃物流，減少運營成本；在互聯網中，如何設置節點，更好的讓信息流動。許多實際工程問題屬于大規模TSP，Korte于1988年提出的VLSI芯片加工問題可以對應于1.2e6的城市TSP，Bland于1989年提出X-ray衍射問題對應于14000城市TSP，Litke于1984年提出電路板設計中鉆孔問題對應于17000城市TSP，以及Grotschel1991年提出的對應于442城市TSP的PCB442問題。遺傳算法簡介遺傳算法（GeneticAlgorithm，GA）是借鑒生物界自然選擇和自然遺傳機制“適者生存”的一種高度并行、隨機化和自適應的全局優化算法，其首先由Holland與1975年提出。其將問題的求解表示成“染色體”的適者生存過程，通過“染色體“群的一代代不斷進化，包括復制、交叉和變異等操作，最終收斂到”最適應環境“的個體，從而得到問體的最優解。標準的遺傳算法的只要步驟可描述為為：隨機產生一組初始個體構成初始種群，并評價每一個體的適配值；判斷算法的收斂準則是否滿足。若滿足則輸出搜索結果，否則執行下面步驟；根據適配值大小以一定的方式執行復制操作；按交叉概率pc執行交叉操作；按變異概率pm執行變異操作。返回2執行新一輪的復制、交叉、變異。在算法中，適配值是對染色體進行評價的一種指標，是遺傳算法進行優化所用的主要信息，與個體的目標值存在一種對應關系；復制操作通常采用比例復制，即復制概率正比于個體適配值，適配值高的個體在下一代中復制自身的概率大，從而提高種群的平均適配值；交叉操作通過交換兩父代個體的部分信息構成后代個體，使得后代繼承父代的有效模式，從而有助于產生優良個體；變異操作通過隨機改變個體的某些基因而產生新個體，有助于增加種群的多樣性，避免早熟收斂。遺傳算法利用生物進化和遺傳的思想實現優化過程，區別與傳統優化算法算法進行全空間并行搜索，并將搜索重點集中于性能高的部分，從而能夠提高效率并且不易陷入局部最小。算法具有固有并行性，通過對種群的遺傳處理可以處理大量的模式，并且容易并行實現；其主要設計如下：1、確定問題的編碼方案。2、確定適配值函數。3、遺傳算子的設計。4、算法參數（種群數目、交叉與變異概率和進化代數等）的選取。5、確定函數終止條件。對TSP問題的遺傳算法實現設計思路：1、初始化城市距離采用一個city_xy函數獲取n個城市的TSP問題的坐標，保存在city矩陣中，并且用city_dis矩陣表示任意兩個城市之間的距離，矩陣中的元素city_dis（i，j)代表第i個城市與第j個城市間的距離。2、初始化種群通過randperm函數，生成一個一維隨機向量（是整數1，2，3，4，5的任意排列），然后將其賦給二維數組group的第一列，作為一個個體。如此循環N次，生成了第一代種群，種群的每個個體代表一條路徑。3、計算適應度采用的適應度函數為個體巡回路徑的總長度的函數。具體為adapt(1,i)=(n*maxdis-dis)(1)在式（1）中，adapt(1,i)表示第i個個體的適應度函數，maxdis為城市間的最大距離，dis為個體巡回路徑的總長度，這樣定義的適應度，當路經越短時適應度值越大。在適應度值的基礎上，給出的計算個體期望復制數的表達式為adaptnum(1,i)=(N*adapt(1,i)/sumadapt)(2)其中，sumadapt為種群適應度之和。4、復制采用優秀個體的大比例保護基礎上的隨機數復制法。具體做法為在生成下一代個體時，先將最大適應度對應的路徑個體以較大的比例復制到下一代，然后再用隨機數復制法生成下一代的其他個體。其中，有一個問題必須考慮，即若某一次生成的隨機數過大，結果能復制一個或極少個樣本。為了避免這一情況，采用了限制措施，即壓低了隨機數的上限。5、交叉采用的方法為按步長的單點交叉，為隨機選擇一對樣本，再隨機選擇一個交叉點位置，按一定的步長進行交叉點的選擇。選擇一個步長而不是將其設為1，是因為若某一位置處的城市代碼因為進行了交叉而發生了改變，則其經過該處的兩個距離都會改變。這種交叉兼有遺傳和變異兩方面的作用，因為若交叉點處的城市編號都相同，則對兩個個體而言交叉后樣本無變化，否則樣本有變化。6、變異方法為隨機兩點I，J的交互位置法。對于A=[12345678910]，若I=3,J=8，則變異后B=[12845673910]雖然是簡單的隨機兩點交互，但實際上已經有40%的距離發生了改變。若用dij表示城市i與j之間的距離，則變異后與變異前樣本路徑的距離差為B23十B34+B78十B89一A23十A34+A78+A89可見，隨機兩點交互足以產生新的模式樣本。較大地提高變異率就會產生大量的新樣本，全局最優樣本出現的概率隨之提高。為了收斂到最優解，借鑒模擬退火算法的思想，采取了變異率由很大逐漸衰減到較小的數量，這樣做也利于找到全局最優解。7、將復制，交叉，變異后得到的種群group1重新賦給group,然后重復3，4，5，6步操作。直至滿足循環停止條件，即找到最優路徑。仿真實驗：TSP實驗數據點取為：10城市TSP（自己隨機選取10個點）：0，0；12，32；5，25;8,45;33,17;25,7;15,15;15,25;25,15;41,1230城市TSP問題（d=423.741byD.B.Fogel）：41,94;37,84;54,67;25,62;7,64;2,99;68,58;71,44;54,62;83,69;64,60;18,54;22,60;83,46;91,38;25,38;24,42;58,69;71,71;74,78;87,76;18,40;13,40;82,7;62,32;58,35;45,21;41,26;44,35;4,5050城市TSP問題（d=427.855byD.B.Fogel）：31，32；32，39；40，30；37，69；27，68；37，52；38，46；31，62；30，48；21，47；25，55；16，57；17，63；42，41；17，33；25，32；5，64；8，52；12，42；7，38；5，25；10，17；45，35；42，57；32，22；27，23；56，37；52，41；49，49；58，48；57，58；39，10；46，10；59，15；51，21；48，28；52，33；58，27；61，33；62，63；20，26；5，6；13，13；21，10；30，15；36，16；62，42；63，69；52，64；43，67對與10點TSP問題，城市數比較少，每一代個體數目為200，進化代數取為1000代，算法執行結果為：最優路徑為：95106713428每一代的最小距離收斂圖為：最后得到的最優路徑為：對于30城市TSP問題，每一代個體數目為200，將其遺傳代數取為10000，算法執行結果為：最優路徑為：621202110151839117814192425262728291617222330121345其每一代的最小距離的收斂圖為：得到的最優路徑為：對于50城市TSP問題，每一代的個體數目選取為200，遺傳代數為20000，則算法執行結果為：最優路徑為：3516131479118513171812101920212242434426244504948403130292823363839472737153433324645252641每一代最小距離收斂圖如下：最后得到的優化路徑為：在30城市TSP問題中，得到的最終的優化距離為425.3，與實際的最小值423.471相差很少，在50城市TSP問題中，得到的最終優化解為474.1，與實際的最優路線的最小距離427.855相差較大。這是由于標準遺傳算法的缺點所確定的，標準遺傳算法在前期搜索的效果比較良好，算法后期搜索比較緩慢，從收斂圖中可以驗證這一點。在50城市TSP問題中，遺傳代數范圍內一個優化解的最小距離開始出現之后經過5000代才繼續下降尋找更好的解。此外，遺傳算法實現的效果很大程度上取決與問題的多種參數，如交叉率，變異率，每一代的個體數目，如果這些參數設置不好，遺傳算法將類似隨機搜索方法，出現“早熟收斂”。在50城市TSP中，如果增加每一代個體數目、遺傳總代數、優化變異率和交叉率，會更靠近最優化解。鑒于標準遺傳算法的缺點，現階段出現了許多遺傳算法的改進。在交叉操作方面，有部分匹配交叉算子、增強邊緣重組算子、序號交叉算子、均勻排序交叉算子、循環交叉算子以及單點交叉算子等。在變異方面還有自適應變異、多級變異等。此外，一些高級的基因操作如雙倍體、顯性遺傳、倒位操作、靜態繁殖等被應用于遺傳算法之中，以改進和優化遺傳算法。參考文獻：王凌，智能優化算法及其應用[D]，清華大學出版社曾憲釗，軍事最優化新方法[D]，軍事科學出版社蔣騰旭，智能優化算法概述[J]，人工智能及識別技術鄭偉、孫文生，遺傳算法及其在求解TSP問題中的應用，中國科技論文在線符一平、陳光喜，一種求解TSP問題的改進遺傳算法，桂林電子科技大學學報/downloads76/sourcecode/math/288006/travelsale.doc/math/shumo/news.asp?id=212/view/46e9db2e453610661ed9f4c9.html附：MATLAB程序functionyichaung_TSP2clc,closeallclearalln=50;city=city_xy(n);%獲取城市坐標信息city_dis=zeros(n,n);fori=1:nforj=1:ncity_dis(i,j)=sqrt((city(i,1)-city(j,1)).^2+(city(i,2)-city(j,2)).^2);endend%初始化城市距離maxdis=max(max(city_dis));%城市間最大距離N=200;%每一代種群中的個體數maxlun=20000;%迭代次數fori=1:Nttemp=randperm(n);%初始化種群，即隨機產生N種路徑，放在n行，N列的矩陣group中forj=1:ngroup(j,i)=ttemp(j);endendforlun=1:maxlun%迭代循環maxlun次sumadapt=0;%適度值之和maxadapt(1,lun)=0;%最大適度值初值minadapt(1,lun)=100;%最小適度值初值viprate=0.1;%最優個體復制率copyrate=0.02;%復制率參數maxadaptloc=0;%最大適應值對應的個體號碼初值mindisiii(1,lun)=100000;%每一代的最憂路徑對應的旅行距離總和初值fori=1:Ndis(1,i)=0;forj=1:n-1dis(1,i)=dis(1,i)+city_dis(group(j,i),group(j+1,i));enddis(1,i)=dis(1,i)+city_dis(group(1,i),group(n,i));%求一次旅行個體的總長度adapt(1,i)=n*maxdis-dis(1,i);%第i個個體的適應度函數sumadapt=sumadapt+adapt(1,i);%適應度函數總和ifdis(1,i)<mindisiii(1,lun)mindisiii(1,lun)=dis(1,i);endendfori=1:Nadaptnum(1,i)=(N*adapt(1,i)/sumadapt);%第i個個體的期望復制數ifadaptnum(1,i)>maxadapt(1,lun)maxadapt(1,lun)=adaptnum(1,i);%求本代最大適應值maxadaptloc=i;%求最大適應值對應的個體號碼endifadaptnum(1,i)<minadapt(1,lun)minadapt(1,lun)=adaptnum(1,i);%求本代最小適應值endend%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%.%復制操作tcopyN=0;%復制個數初值num=(maxadapt(1,lun)-copyrate-minadapt(1,lun))*rand(1)+minadapt(1,lun);%生成隨機數vipnum=viprate*N;%確定最優個體復制個數fortcopyN=1:vipnum%先復制vipnum個最優個體至中間矩陣group1fori=1:ngroup1(i,tcopyN)=group(i,maxadaptloc);endendwhiletcopyN<N%再復制其余N-vipnum個fori=1:Nifadaptnum(1,i)>num&&tcopyN<NtcopyN=tcopyN+1;fork=1:n%由于針對n個城市，故每個個體有n個元素group1(k,tcopyN)=group(k,i);endendendend%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%交叉操作pc=0.5-(0.5-0.4)*(lun-1)/(maxlun-1);%交叉率pair=pc*N/2;%最多交叉對數step=2;%交叉步長取為2pairno=0;%當前交叉過的個體數whilepairno<paira=floor(N*rand(1)+1);%隨機產生兩個交叉個體，floor為向負無窮取整函數b=floor(N*rand(1)+1);marri(1,a)=2;%參與交叉的個體標記初值marri(1,b)=3;ifmarri(1,a)~=1&&marri(1,b)~=1&&a~=bmarri(1,a)~=1;marri(1,b)~=1;%參與交叉的個體標記為1pairno=pairno+1;location=floor(n*rand(1)+1);%用隨機數確定個體中單交叉點位置l1=0;l2=0;fori=location:step:n%以下按步長step進行交叉forj=1:n%用for確定交叉位置ifgroup1(i,a)==group1(j,b)l1=j;endendforj=1:nifgroup1(i,b)==group1(j,a)l2=j;endendtemp=group1(i,a);group1(i,a)=group1(l2,a);group1(l2,a)=temp;temp=group1(i,b);group1(i,b)=group1(l1,b);group1(l1,b)=temp;endendend%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%變異操作pb=0.1;%個體變異率bnum=pb*N;%變異個體數fori=1:bnum%逐個取個體，隨機選擇位置進行變異a1=floor(n*rand(1)+1);a2=floor(n*rand(1)+1);b=floor(N*rand(1)+1);temp=group1(a1,b);group1(a1,b)=group1(a2,b);group1(a2,b)=temp;end%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%fori=1:Nforj=1:ngroup(j,i)=group1(j,i);%構造經過復制，交叉，變異后的矩陣，group,準備下次循環endendenddisp('最優路徑為：');fori=1:nfprintf('%.d',group(i,1));ifrem(i,10)==0fprintf('\n');endendfigure(1);lun=1:1:maxlun;mindis=mindisiii(1,lun);plot(lun,mindis);title('每一代種群最短距離的收斂過程');xlabel('遺傳代數');ylabel('每一代種群最短距離');x=zeros(1,n+1);y=zeros(1,n+1);fori=1:nk=group(i,1);x(1,i)=city(k,1);y(1,i)=city(k,2);endx(1,n+1)=x(1,1);y(1,n+1)=y(1,1);figure,plot(x,y,'-*g');title('閉合曲線即為最優路徑');xlabel('x')ylabel('y');functionC=city_xy(n)ifn==10C=[0,0;12,32;5,25;8,45;33,17;25,7;15,15;15,25;25,15;41,12];elseifn==30C=[41,94;37,84;54,67;25,62;7,64;2,99;68,58;71,44;54,62;83,69;64,60;18,54;...22,60;83,46;91,38;25,38;24,42;58,69;71,71;74,78;87,76;18,40;13,40;...82,7;62,32;58,35;45,21;41,26;44,35;4,50];elseifn==50C=[31,32;32,39;40,30;37,69;27,68;37,52;38,46;31,62;30,48;21,47;25,55;...16,57;17,63;42,41;17,33;25,32;5,64;8,52;12,42;7,38;5,25;10,17;...45,35;42,57;32,22;27,23;56,37;52,41;49,49;58,48;57,58;39,10;...46,10;59,15;51,21;48,28;52,33;58,27;61,33;62,63;20,26;5,6;13,13;...21,10;30,15;36,16;62,42;63,69;52,64;43,67];end基于單片機和DSP的卷繞控制器數據采集和通訊設計基于MSP430單片機的柴油發電機監控器的設計基于CPLD/FPGA和單片機的爆速儀設計基于單片機控制的晶閘管中頻感應電源的研制基于十六位單片機的電力設備故障在線監測裝置的設計與算法研究基于SPCE061A單片機的語音識別系統的研究基于PIC單片機的生物機能實驗裝置的研究基于MotorolaMC68HC08系列單片機演示系統的設計與實現基于TCP/IP協議的單片機與INTERNET互連的設計與實現基于嵌入式實時操作系統和TCP/IP協議的單片機測控系統AVR8位嵌入式單片機在車載全球定位系統顯示終端中的應用基于AVR單片機的250WHID燈電子鎮流器的研究基于單片機的TCP/IP技術研究及應用基于P87C591單片機的CAN總線應用層協議的研究基于單片機實現對二級倒立擺的控制C8051FXXX系列單片機仿真器的研制基于80C196MC單片機控制的變頻調速及配料控制系統的應用研究基于單片機的膠印機控制系統開發研究基于凌陽單片機的二次壓降全自動測量儀的研制基于單片機的超聲測距系統基于MOTOROLA單片機的專用電池組智能充電儀全站儀動態測量的研究以及其與單片機在軌道式龍門吊實時檢測中的應用一種基于80C196KC單片機的新型電子負載的設計基于單片機的對講系統的研究開發基于單片機的微波加熱瀝青路面再生修復機溫度控制器的開發與研究基于單片機ATmega128的嵌入式工業控制器設計基于單片機的壓電閉環微位移控制系統的研究基于單片機的高壓靜電除塵整流設備的自動監控系統設計采用W78E58單片機的酸堿濃度檢測技術基于單片機的糧庫溫度監控系統設計基于單片機控制的微型軸流式血泵外磁驅動系統研究基于AVR單片機的電動自行車控制系統研究基于PIC單片機的配電網綜