一些解決TSP問題算法源代碼

個人資料整理 僅限學習使用模擬退火算法模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內部粒子隨溫升變?yōu)闊o序狀，內能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態(tài)，最后在常溫時達到基態(tài)，內能減為最小。根據Metropolis準則，粒子在溫度T時趨于平衡的概率為e-E/(kT>，其中E為溫度T時的內能，ΔE為其改變量，k為Boltzmann常數。用固體退b5E2RGbCAP火模擬組合優(yōu)化問題，將內能 E模擬為目標函數值 f，溫度T演化成控制參數t，即得到解組合優(yōu)化問題的模擬退火算法：由初始p1EanqFDPw解i和控制參數初值t開始，對當前解重復“產生新解→計算目標函數差→接受或舍棄”的迭代，并逐步衰減t值，算法終止時的DXDiTa9E3d當前解即為所得近似最優(yōu)解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機搜索過程。退火過程由冷卻進度表(CoolingRTCrpUDGiTSchedule>控制，包括控制參數的初值t及其衰減因子Δt、每個t值時的迭代次數L和停止條件S。3.5.1模擬退火算法的模型模擬退火算法可以分解為解空間、目標函數和初始解三部分。模擬退火的基本思想:(1>初始化：初始溫度T(充分大>，初始解狀態(tài)S(是算法迭代的起點>，每個T值的迭代次數L(2>對k=1，，L做第(3>至第6步：(3>產生新解S′(4>計算增量t′=C(S′>-C(S>，其中C(S>為評價函數(5>若t′<0則接受S′作為新的當前解，否則以概率exp(-t′/T>接受S′作為新的當前解.(6>如果滿足終止條件則輸出當前解作為最優(yōu)解，結束程序。終止條件通常取為連續(xù)若干個新解都沒有被接受時終止算法。(7>T逐漸減少，且T->0，然后轉第2步。算法對應動態(tài)演示圖：模擬退火算法新解的產生和接受可分為如下四個步驟：第一步是由一個產生函數從當前解產生一個位于解空間的新解；為便于后續(xù)的計算和接受，減少算法耗時，通常選擇由當5PCzVD7HxA前新解經過簡單地變換即可產生新解的方法，如對構成新解的全部或部分元素進行置換、互換等，注意到產生新解的變換方法jLBHrnAILg決定了當前新解的鄰域結構，因而對冷卻進度表的選取有一定的影響。第二步是計算與新解所對應的目標函數差。因為目標函數差僅由變換部分產生，所以目標函數差的計算最好按增量計算。xHAQX74J0X1/67個人資料整理 僅限學習使用事實表明，對大多數應用而言，這是計算目標函數差的最快方法。第三步是判斷新解是否被接受,判斷的依據是一個接受準則，最常用的接受準則是Metropo1is準則:若t′<0則接受S′作LDAYtRyKfE為新的當前解S，否則以概率exp(-t′/T>接受S′作為新的當前解S。第四步是當新解被確定接受時，用新解代替當前解，這只需將當前解中對應于產生新解時的變換部分予以實現(xiàn)，同時修正 Zzz6ZB2Ltk目標函數值即可。此時，當前解實現(xiàn)了一次迭代。可在此基礎上開始下一輪實驗。而當新解被判定為舍棄時，則在原當前解的dvzfvkwMI1基礎上繼續(xù)下一輪實驗。模擬退火算法與初始值無關，算法求得的解與初始解狀態(tài)S(是算法迭代的起點>無關；模擬退火算法具有漸近收斂性，已在rqyn14ZNXI理論上被證明是一種以概率l收斂于全局最優(yōu)解的全局優(yōu)化算法；模擬退火算法具有并行性。3.5.2模擬退火算法的簡單應用作為模擬退火算法應用，討論貨郎擔問題 (TravellingSalesmanProblem，簡記為TSP>：設有n個城市，用數碼 1, ,n代表EmxvxOtOco。城市i和城市j之間的距離為d(i，j>i,j=1,．,nTSP問題是要找遍訪每個域市恰好一次的一條回路，且其路徑總長度為最SixE2yXPq5短.。求解TSP的模擬退火算法模型可描述如下：解空間解空間S是遍訪每個城市恰好一次的所有回路，是{1，，n}的所有循環(huán)排列的集合，S中的成員記為(w1,w2,6ewMyirQFL，wn>，并記wn+1=w1。初始解可選為(1，，n>目標函數此時的目標函數即為訪問所有城市的路徑總長度或稱為代價函數：kavU42VRUs我們要求此代價函數的最小值。新解的產生隨機產生1和n之間的兩相異數 k和m，若k<m，則將(w1,w2, ，wk,wk+1, ，wm, ，wn>變?yōu)椋?w1,w2, ，wm,wm-1,，wk+1,wk, ，wn>.如果是k>m，則將(w1,w2, ，wk,wk+1, ，wm, ，wn>變?yōu)椋?wm,wm-1,，w1,wm+1,，wk-1,wn,wn-1,，wk>.上述變換方法可簡單說成是 “逆轉中間或者逆轉兩端”。也可以采用其他的變換方法，有些變換有獨特的優(yōu)越性，有時也將它們交2/67個人資料整理 僅限學習使用替使用，得到一種更好方法。代價函數差設將(w1,w2, ，wn>變換為(u1,u2, ，un>,則代價函數差為： y6v3ALoS89根據上述分析，可寫出用模擬退火算法求解 TSP問題的偽程序：ProcedureTSPSA:begininit-of-T。{T為初始溫度}S={1，，n}。{S為初始值}termination=false。whiletermination=falsebeginfori=1toLdobegingenerate(S′formS>。{從當前回路S產生新回路S′}t:=f(S′>>-f(S>。{f(S>為路徑總長}IF( t<0>OR(EXP(- t/T>>Random-of-[0,1]>S=S′。IFthe-halt-condition-is-TRUETHENtermination=true 。End。T_lower。End。End模擬退火算法的應用很廣泛，可以較高的效率求解最大截問題 (MaxCutProblem>、0-1背包問題(ZeroOneKnapsackM2ub6vSTnPProblem>、圖著色問題(GraphColouringProblem> 、調度問題(SchedulingProblem>等等。0YujCfmUCw3.5.3模擬退火算法的參數控制問題模擬退火算法的應用很廣泛，可以求解NP完全問題，但其參數難以控制，其主要問題有以下三點：(1>溫度T的初始值設置問題。溫度T的初始值設置是影響模擬退火算法全局搜索性能的重要因素之一、初始溫度高，則搜索到全局最優(yōu)解的可能性大，但eUts8ZQVRd因此要花費大量的計算時間；反之，則可節(jié)約計算時間，但全局搜索性能可能受到影響。實際應用過程中，初始溫度一般需要sQsAEJkW5T依據實驗結果進行若干次調整。(2>退火速度問題。模擬退火算法的全局搜索性能也與退火速度密切相關。一般來說，同一溫度下的“充分”搜索(退火>是相當必要的，但這GMsIasNXkA3/67個人資料整理 僅限學習使用需要計算時間。實際應用中，要針對具體問題的性質和特征設置合理的退火平衡條件。(3>溫度管理問題。溫度管理問題也是模擬退火算法難以處理的問題之一。實際應用中，由于必須考慮計算復雜度的切實可行性等問題，常采TIrRGchYzg用如下所示的降溫方式：T(t+1>＝k×T(t>式中k為正的略小于1.00的常數，t為降溫的次數使用SA解決TSP問題的Matlab程序：functionout=tsp(loc>TSPTravelingsalesmanproblem(TSP>usingSA(simulatedannealing>.TSPbyitselfwillgenerate20citieswithinaunitcubeandthenuseSAtoslovethisproblem.%TSP(LOC>solvethetravelingsalesmanproblemwithcities'coordinatesgivenbyLOC,whichisanMby2matrixandMisthenumberofcities.%Forexample:%loc=rand(50,2> 。%tsp(loc>。ifnargin==0,ThefollowingdataisfromthepostbyJenniferMyers(jmyers@>edu>tocomp.ai.neural-nets.It'sobtainedfromthefigureinHopfield&Tank's1985paperinBiologicalCybernetics(Vol52,pp.141-152>.loc=[0.3663,0.9076 。0.7459,0.8713。0.4521,0.8465。0.7624,0.7459。0.7096,0.7228。0.0710,0.7426。0.4224,0.7129。0.5908,0.6931。0.3201,0.6403。0.5974,0.6436。0.3630,0.5908。0.6700,0.5908。0.6172,0.5495。0.6667,0.5446。0.1980,0.4686。0.3498,0.4488。0.2673,0.4274。0.9439,0.4208。0.8218,0.3795。0.3729,0.2690。0.6073,0.2640。0.4158,0.2475。0.5990,0.2261。0.3927,0.1947。0.5347,0.1898。0.3960,0.1320。0.6287,0.0842。0.5000,0.0396。0.9802,0.0182。0.6832,0.8515]。endNumCity=length(loc> 。%Numberofcities4/67個人資料整理 僅限學習使用distance=zeros(NumCity> 。%Initializeadistancematrix%Fillthedistancematrixfori=1:NumCity,forj=1:NumCity,distance(i,j>=norm(loc(i,-loc(j,> 。distance(i,j>=norm(loc(i,-loc(j,> 。endend%Togenerateenergy(objectivefunction>frompath%path=randperm(NumCity>。%energy=sum(distance((path-1>*NumCity+[path(2:NumCity>path(1>]>>。FindtypicalvaluesofdEcount=20。all_dE=zeros(count,1> 。fori=1:countpath=randperm(NumCity> 。energy=sum(distance((path-1>*NumCity+[path(2:NumCity>path(1>]>> 。new_path=path。index=round(rand(2,1>*NumCity+.5> 。inversion_index=(min(index>:max(index>> 。new_path(inversion_index>=fliplr(path(inversion_index>> 。all_dE(i>=abs(energy-...sum(sum(diff(loc([new_pathnew_path(1>],>'.^2>>> 。enddE=max(all_dE>。dE=max(all_dE>。temp=10*dE。%Choosethetemperaturetobelargeenoughfprintf('Initialenergy=%f\n\n',energy> 。%Initialplotsout=[pathpath(1>] 。plot(loc(out(,1>,loc(out(,2>,'r.','Markersize',20> 。axissquare。holdonh=plot(loc(out(,1>,loc(out(,2>> 。holdoffMaxTrialN=NumCity*100。%Max.#oftrialsatatemperatureMaxAcceptN=NumCity*10。%Max.#ofacceptancesatatemperatureStopTolerance=0.005。%StoppingtoleranceTempRatio=0.5。%TemperaturedecreaseratiominE=inf。%Initialvalueformin.energymaxE=-1。%Initialvalueformax.energy%Majorannealingloop5/67個人資料整理 僅限學習使用while(maxE-minE>/maxE>StopTolerance,minE=inf。minE=inf。maxE=0。TrialN=0。%NumberoftrialmovesAcceptN=0。%NumberofactualmoveswhileTrialN<MaxTrialN&AcceptN<MaxAcceptN,new_path=path。index=round(rand(2,1>*NumCity+.5>。inversion_index=(min(index>:max(index>>。new_path(inversion_index>=fliplr(path(inversion_index>>。new_energy=sum(distance(...(new_path-1>*NumCity+[new_path(2:NumCity>new_path(1>]>>。ifrand<exp((energy-new_energy>/temp>,%acceptit!energy=new_energy。path=new_path。minE=min(minE,energy>。maxE=max(maxE,energy>。AcceptN=AcceptN+1。endTrialN=TrialN+1。endend%Updateplotout=[pathpath(1>] 。set(h,'xdata',loc(out(,1>,'ydata',loc(out(,2>> 。drawnow。%Printinformationincommandwindowfprintf('temp.=%f\n',temp> 。tmp=sprintf('%d',path> 。fprintf('path=%s\n',tmp> 。fprintf('energy=%f\n',energy> 。fprintf('[minEmaxE]=[%f%f]\n',minE,maxE> 。fprintf('[AcceptNTrialN]=[%d%d]\n\n',AcceptN,TrialN> 。%Lowerthetemperaturetemp=temp*TempRatio 。endPrintsequentialnumbersinthegraphicwindowfori=1:NumCity,text(loc(path(i>,1>+0.01,loc(path(i>,2>+0.01,int2str(i>,...6/67個人資料整理 僅限學習使用'fontsize',8>。end7EqZcWLZNX又一個相關的Matlab程序function[X,P]=zkp(w,c,M,t0,tf>[m,n]=size(w> 。L=100*n。t=t0。clearm。x=zeros(1,n>xmax=x。fmax=0。whilet>tffork=1:Lxr=change(x>gx=g_0_1(w,x> 。gxr=g_0_1(w,xr> 。ifgxr<=Mfr=f_0_1(xr,c> 。f=f_0_1(x,c> 。df=fr-f。ifdf>0x=xr。iffr>fmaxfmax=fr。xmax=xr。endelsep=rand。ifp<exp(df/t>x=xr。endendendendt=0.87*tendP=fmax。X=xmax。下面的函數產生新解function[d_f,pi_r]=exchange_2(pi0,d>[m,n]=size(d> 。clearm。7/67個人資料整理 僅限學習使用u=rand。u=u*(n-2> 。u=round(u> 。ifu<2u=2。endifu>n-2u=n-2。endv=rand。v=v*(n-u+1> 。v=round(v>。ifv<1v=1。endv=v+u。ifv>nv=n。endpi_1(u>=pi0(v> 。pi_1(u>=pi0(u> 。ifu>1fork=1:(u-1>pi_1(k>=pi0(k> 。endendifv>(u+1>fork=1:(v-u-1>pi_1(u+k>=pi0(v-k> 。endendifv<nfork=(v+1>:npi_1(k>=pi0(k> 。endendd_f=0。ifv<nd_f=d(pi0(u-1>,pi0(v>>+d(pi0(u>,pi0(v+1>> 。fork=(u+1>:nd_f=d_f+d(pi0(k>,pi0(k-1>>-d(pi0(v>,pi0(v+1>> 。endd_f=d_f-d(pi0(u-1>,pi0(u>> 。fork=(u+1>:n8/67個人資料整理 僅限學習使用d_f=d_f-d(pi0(k-1>,pi0(k>> 。endelsed_f=d(pi0(u-1>,pi0(v>>+d(pi0(u>,pi0(1>>-d(pi0(u-1>,pi0(u>>-d(pi0(v>,pi0(1>>。fork=(u+1>:nd_f=d_f-d(pi0(k>,pi0(k-1>> 。endfork=(u+1>:nd_f=d_f-d(pi0(k-1>,pi0(k>> 。endendpi_r=pi_1。lzq7IGf02E遺傳算法

GA遺傳算法：旅行商問題(travelingsalemanproblem, 簡稱tsp>：已知n個城市之間的相互距離，現(xiàn)有一個推銷員必須遍訪這 n個城市，并且每個城市只能訪問一次，最后又必須返回出發(fā)城市。如何安排他對這些城市的訪問次序，可使其旅行路線的總長度最短？用圖論的術語來說，假設有一個圖g=(v,e>，其中v是頂點集，e是邊集，設d=(dij>是由頂點i和頂點j之間的距離所組成的距離矩陣，旅行商問題就是求出一條通過所有頂點且每個頂點只通過一次的具有最短距離的回路。這個問題可分為對稱旅行商問題(dij=dji,,任意i,j=1,2,3，,n>和非對稱旅行商問題(dij≠dji,,任意i,j=1,2,3，,n>。若對于城市v={v1,v2,v3,,vn}的一個訪問順序為t=(t1,t2,t3,,ti,,tn>,其中ti∈v(i=1,2,3,，,n>且記tn+1=t1，則旅行商問題的數學模型為：minl=σd(t(i>,t(i+1>><i=1,）,n旅行商問題是一個典型的組合優(yōu)化問題，并且是一個np難問題，其可能的路徑數目與城市數目n是成指數型增長的，所以一般很難精確地求出其最優(yōu)解，本文采用遺傳算法求其近似解。遺傳算法：初始化過程：用v1,v2,v3,,vn代表所選n個城市。定義整數pop-size作為染色體的個數，并且隨機產生pop-size個初始染色體，每個染色體為1到18的整數組成的隨機序列。適應度f的計算：對種群中的每個染色體vi，計算其適應度，f=σd(t(i>,t(i+1>>.評價函數eval(vi>：用來對種群中的每個染色體vi設定一個概率，以使該染色體被選中的可能性與其種群中其它染色體的適應性成比例，既通過輪盤賭，適應性強的染色體被選擇產生后臺的機會要大，設alpha∈(0,1>，本文定義基于序的評價函數為eval(vi>=alpha*(1-alpha>.^(i-1>。[隨機規(guī)劃與模糊規(guī)劃]選擇過程：選擇過程是以旋轉賭輪pop-size次為基礎，每次旋轉都為新的種群選擇一個染色體。賭輪是按每個染色體的適應度進行選擇染色體的。9/67意義的染色體，本文采用這種情況的出現(xiàn)。所謂的隊員中的位置，如：個人資料整理 僅限學習使用step1、對每個染色體vi,計算累計概率qi，q0=0。qi=σeval(vj>j=1,。i=,i1,pop-size.step2、從區(qū)間(0,pop-size>中產生一個隨機數r；step3、若qi-1<r<qi,則選擇第i個染色體；step4、重復step2和step3共pop-size次，這樣可以得到 pop-size個復制的染色體。grefenstette編碼：由于常規(guī)的交叉運算和變異運算會使種群中產生一些無實際grefenstette編碼《遺傳算法原理及應用》可以避免grefenstette編碼就是用所選隊員在未選<不含淘汰）815216107431114612951813171對應：81421386325734324221 。交叉過程：本文采用常規(guī)單點交叉。為確定交叉操作的父代，從 到pop-size重復以下過程：從[0，1]中產生一個隨機數r，如果r<pc，則選擇vi作為一個父代。將所選的父代兩兩組隊，隨機產生一個位置進行交叉，如：814213863257343242216123568563185633211交叉后為：814213863251856332116123568563734324221變異過程：本文采用均勻多點變異。類似交叉操作中選擇父代的過程，在 r<pm的標準下選擇多個染色體vi作為父代。對每一個選擇的父代，隨機選擇多個位置，使其在每位置按均勻變異<該變異點xk的取值范圍為[ukmin,ukmax],產生一個[0，1]中隨機數r，該點變異為x'k=ukmin+r(ukmax-ukmin>）操作。如：81421386325734324221變異后：814213106322734524121反grefenstette編碼：交叉和變異都是在grefenstette編碼之后進行的，為了循環(huán)操作和返回最終結果，必須逆grefenstette編碼過程，將編碼恢復到自然編碼。循環(huán)操作：判斷是否滿足設定的帶數xzome，否，則跳入適應度f的計算；是，結束遺傳操作，跳出。zvpgeqJ1hkMatlab程序：function[bestpop,trace]=ga(d,termops,num,pc,cxops,pm,alpha>%————————————————————————%[bestpop,trace]=ga(d,termops,num,pc,cxops,pm,alpha>%d:距離矩陣%termops:種群代數10/67個人資料整理 僅限學習使用%num:每代染色體的個數%pc:交叉概率%cxops:由于本程序采用單點交叉，交叉點的設置在本程序中沒有很好的解決，所以本文了采用定點，即第cxops，可以隨機產生。%pm:變異概率%alpha:評價函數eval(vi>=alpha*(1-alpha>.^(i-1>.%bestpop:返回的最優(yōu)種群%trace:進化軌跡%------------------------------------------------%####@@@##版權所有！歡迎廣大網友改正，改進！##@@@####%e-mail:tobysidney33@%####################################################%citynum=size(d,2> 。n=nargin。ifn<2disp('缺少變量??！'>disp('^_^ 開個玩笑^_^'>endifn<2termops=500。num=50。pc=0.25。cxops=3。pm=0.30。alpha=0.10。endifn<3num=50。pc=0.25。cxops=3。pm=0.30。alpha=0.10。endifn<4pc=0.25。cxops=3。pm=0.30。alpha=0.10。endifn<5cxops=3。pm=0.30。11/67個人資料整理 僅限學習使用alpha=0.10。endifn<6pm=0.30。alpha=0.10。endifn<7alpha=0.10。endifisempty(cxops>cxops=3。endNrpoJac3v1[t]=initializega(num,citynum>。fori=1:termops[l]=f(d,t>。[x,y]=find(l==max(l>>。trace(i>=-l(y(1>>。bestpop=t(y(1>,:>。[t]=select(t,l,alpha>。[g]=grefenstette(t>。[g1]=crossover(g,pc,cxops>。[g]=mutation(g1,pm>。%均勻變異[t]=congrefenstette(g>。end1nowfTG4KI---------------------------------------------------------function[t]=initializega(num,citynum>fori=1:numt(i,:>=randperm(citynum> 。end-----------------------------------------------------------function[l]=f(d,t>[m,n]=size(t> 。fork=1:mfori=1:n-1l(k,i>=d(t(k,i>,t(k,i+1>> 。endl(k,n>=d(t(k,n>,t(k,1>> 。l(k>=-sum(l(k,:>> 。end-----------------------------------------------------------function[t]=select(t,l,alpha>[m,n]=size(l> 。12/67個人資料整理 僅限學習使用t1=t。[beforesort,aftersort1]=sort(l,2> 。%fsortfromltoufori=1:naftersort(i>=aftersort1(n+1-i> 。%changeendfork=1:n。t(k,:>=t1(aftersort(k>,:> 。l1(k>=l(aftersort(k>> 。endt1=t。l=l1。fori=1:size(aftersort,2>evalv(i>=alpha*(1-alpha>.^(i-1> 。endm=size(t,1>。q=cumsum(evalv> 。qmax=max(q>。fork=1:mr=qmax*rand(1> 。forj=1:mifj==1&r<=q(1>t(k,:>=t1(1,:> 。elseifj~=1&r>q(j-1>&r<=q(j>t(k,:>=t1(j,:> 。endendend--------------------------------------------------function[g]=grefenstette(t>[m,n]=size(t> 。fork=1:mt0=1:n。fori=1:nforj=1:length(t0>ift(k,i>==t0(j>g(k,i>=j。t0(j>=[] 。breakendendendend-------------------------------------------function[g]=crossover(g,pc,cxops>13/67個人資料整理 僅限學習使用[m,n]=size(g> 。ran=rand(1,m> 。r=cxops。[x,ru]=find(ran<pc> 。ifru>=2fork=1:2:length(ru>-1g1(ru(k>,:>=[g(ru(k>,[1:r]>,g(ru(k+1>,[(r+1>:n]>] 。g(ru(k+1>,:>=[g(ru(k+1>,[1:r]>,g(ru(k>,[(r+1>:n]>] 。g(ru(k>,:>=g1(ru(k>,:> 。endend--------------------------------------------function[g]=mutation(g,pm>% 均勻變異[m,n]=size(g> 。ran=rand(1,m> 。r=rand(1,3> 。%daigaijinrr=floor(n*rand(1,3>+1> 。[x,mu]=find(ran<pm> 。fork=1:length(mu>fori=1:length(r>umax(i>=n+1-rr(i> 。umin(i>=1。g(mu(k>,rr(i>>=umin(i>+floor((umax(i>-umin(i>>*r(i>> 。endend---------------------------------------------------function[t]=congrefenstette(g>[m,n]=size(g> 。fork=1:mt0=1:n。fori=1:nt(k,i>=t0(g(k,i>> 。t0(g(k,i>>=[] 。endend------------------------------------------------- fjnFLDa5Zo又一個Matlab程序，其中交叉算法采用的是由 Goldberg和Lingle于1985年提出的PMX(部分匹配交叉>，淘汰保護指數alpha是我自己設計的，起到了加速優(yōu)勝劣汰的作用。tfnNhnE6e5%TSP問題<又名：旅行商問題，貨郎擔問題）遺傳算法通用 matlab程序%D是距離矩陣，n為種群個數,建議取為城市個數的 1~2倍，%C為停止代數，遺傳到第 C代時程序停止,C的具體取值視問題的規(guī)模和耗費14/67個人資料整理 僅限學習使用的時間而定%m為適應值歸一化淘汰加速指數 ,最好取為1,2,3,4,不宜太大%alpha為淘汰保護指數,可取為0~1之間任意小數,取1時關閉保護功能,最好取為0.8~1.0%R為最短路徑,Rlength為路徑長度function[R,Rlength]=geneticTSP(D,n,C,m,alpha> HbmVN777sL[N,NN]=size(D> 。farm=zeros(n,N> 。%用于存儲種群fori=1:nfarm(i,:>=randperm(N> 。%隨機生成初始種群endR=farm(1,:> 。%存儲最優(yōu)種群len=zeros(n,1>。%存儲路徑長度fitness=zeros(n,1> 。%存儲歸一化適應值counter=0。V7l4jRB8Hswhilecounter<Cfori=1:nlen(i,1>=myLength(D,farm(i,:>>。%計算路徑長度endmaxlen=max(len> 。minlen=min(len> 。fitness=fit(len,m,maxlen,minlen> 。%計算歸一化適應值rr=find(len==minlen> 。R=farm(rr(1,1>,:> 。%更新最短路徑 83lcPA59W9FARM=farm。%優(yōu)勝劣汰，nn記錄了復制的個數nn=0。fori=1:niffitness(i,1>>=alpha*randnn=nn+1。FARM(nn,:>=farm(i,:> 。endendFARM=FARM(1:nn,:>。mZkklkzaaP[aa,bb]=size(FARM>。%交叉和變異whileaa<nifnn<=2nnper=randperm(2> 。elsennper=randperm(nn> 。end15/67個人資料整理 僅限學習使用A=FARM(nnper(1>,:> 。B=FARM(nnper(2>,:> 。[A,B]=intercross(A,B> 。FARM=[FARM。A。B]。[aa,bb]=size(FARM>。endifaa>nFARM=FARM(1:n,:>。%保持種群規(guī)模為nendAVktR43bpwfarm=FARM。clearFARMcounter=counter+1endRlength=myLength(D,R> 。function[a,b]=intercross(a,b>L=length(a>。ifL<=10% 確定交叉寬度W=1。elseif((L/10>-floor(L/10>>>=rand&&L>10W=ceil(L/10>。elseW=floor(L/10> 。endp=unidrnd(L-W+1>。%隨機選擇交叉范圍，從p到p+Wfori=1:W%交叉x=find(a==b(1,p+i-1>> 。y=find(b==a(1,p+i-1>> 。[a(1,p+i-1>,b(1,p+i-1>]=exchange(a(1,p+i-1>,b(1,p+i-1>> 。[a(1,x>,b(1,y>]=exchange(a(1,x>,b(1,y>> 。endfunction[x,y]=exchange(x,y>temp=x。x=y。y=temp。ORjBnOwcEd計算路徑的子程序functionlen=myLength(D,p>[N,NN]=size(D> 。len=D(p(1,N>,p(1,1>> 。fori=1:(N-1>16/67個人資料整理 僅限學習使用len=len+D(p(1,i>,p(1,i+1>> 。end2MiJTy0dTT計算歸一化適應值子程序functionfitness=fit(len,m,maxlen,minlen>fitness=len。fori=1:length(len>fitness(i,1>=(1-((len(i,1>-minlen>/(maxlen-minlen+0.000001>>>.^m 。endgIiSpiue7A一個

C++

的程序：//c++的程序#include<iostream.h>#include<stdlib.h>template<classT>classGraph{public:Graph(intvertices=10>{n=vertices

。e=0

。}~Graph(>{}virtualboolAdd(intu,intv,constT&w>=0virtualboolDelete(intu,intv>=0 。virtualboolExist(intu,intv>const=0 。intVertices(>const{returnn 。}intEdges(>const{returne 。}protected:

。e。}。template<classT>classMGraph:publicGraph<T>{public:MGraph(intVertices=10,TnoEdge=0> 。~MGraph(> 。boolAdd(intu,intv,constT&w>boolDelete(intu,intv> 。boolExist(intu,intv>const 。voidFloyd(T**&d,int**&path>voidprint(intVertices> 。

。。17/67個人資料整理 僅限學習使用private:TNoEdge。T**a。}。template<classT>MGraph<T>::MGraph(intVertices,TnoEdge>{n=Vertices。NoEdge=noEdge。a=newT*[n] 。for(inti=0。i<n。i++>{a[i]=newT[n] 。a[i][i]=0 。for(intj=0 。j<n。j++>if(i!=j>a[i][j]=NoEdge 。}}template<classT>MGraph<T>::~MGraph(>{for(inti=0。i<n。i++>delete[]a[i] 。delete[]a。}template<classT>boolMGraph<T>::Exist(intu,intv>const{if(u<0||v<0||u>n-1||v>n-1||u==v||a[u][v]==NoEdge>returnfalse 。returntrue。}template<classT>boolMGraph<T>::Add(intu,intv,constT&w>{if(u<0||v<0||u>n-1||v>n-1||u==v||a[u][v]!=NoEdge>{cerr<<"BadInput!"<<endl 。returnfalse。}a[u][v]=w 。e++。returntrue。}template<classT>boolMGraph<T>:delete(intu,intv>{if(u<0||v<0||u>n-1||v>n-1||u==v||a[u][v]==NoEdge>{cerr<<"BadInput!"<<endl 。18/67個人資料整理 僅限學習使用returnfalse。}a[u][v]=NoEdge 。e--。returntrue。}template<classT>voidMGraph<T>::Floyd(T**&d,int**&path>{d=newT*[n] 。path=newint*[n] 。for(inti=0。i<n。i++>{d[i]=newT[n] 。path[i]=newint[n] 。for(intj=0 。j<n。j++>{d[i][j]=a[i][j] 。if(i!=j&&a[i][j]<NoEdge>path[i][j]=i 。elsepath[i][j]=-1 。}}for(intk=0。k<n。k++>{for(i=0。i<n。i++>for(intj=0 。j<n。j++>if(d[i][k]+d[k][j]<d[i][j]>{d[i][j]=d[i][k]+d[k][j] 。path[i][j]=path[k][j] 。}}}template<classT>voidMGraph<T>::print(intVertices>{for(inti=0。i<Vertices。i++>for(intj=0 。j<Vertices。j++>{cout<<a[i][j]<<'' 。if(j==Vertices-1>cout<<endl 。}}#definenoEdge10000#include<iostream.h>voidmain(>{cout<<"請輸入該圖的節(jié)點數："<<endl。19/67個人資料整理 僅限學習使用intvertices。cin>>vertices。MGraph<float>b(vertices,noEdge> 。cout<<"請輸入u,v,w:"<<endl 。intu,v。floatw。cin>>u>>v>>w 。while(w!=noEdge>{//u=u-1 。b.Add(u-1,v-1,w> 。b.Add(v-1,u-1,w> 。cout<<" 請輸入u,v,w:"<<endl 。cin>>u>>v>>w 。}b.print(vertices> 。int**Path 。int**&path=Path 。float**D。float**&d=D 。b.Floyd(d,path>。for(inti=0。i<vertices。i++>{for(intj=0 。j<vertices。j++>{cout<<Path[i][j]<<'' 。if(j==vertices-1>cout<<endl 。}}int*V。V=newint[vertices+1] 。cout<<"請輸入任意一個初始 H-圈："<<endl。for(intn=0。n<=vertices。n++>{cin>>V[n] 。}for(n=0。n<55。n++>{for(i=0。i<n-1。i++>{for(intj=0 。j<n-1。j++>{if(i+1>0&&j>i+1&&j<n-1>{if(D[V[i]][V[j]]+D[V[i+1]][V[j+1]]<D[V[i]][V[i+1]]+D[V[j]][V[j+1]]>{intl 。l=V[i+1] 。V[i+1]=V[j] 。V[j]=l。}}}20/67個人資料整理 僅限學習使用}}floattotal=0 。cout<<"最小回路："<<endl。for(i=0。i<=vertices。i++>{cout<<V[i]+1<<'' 。}cout<<endl 。for(i=0。i<vertices。i++>total+=D[V[i]][V[i+1]] 。cout<<"最短路徑長度："<<endl。cout<<total 。}uEh0U1Yfmh語言程序#include<stdio.h>#include<stdlib.h>#include<math.h>#include<alloc.h>#include<conio.h>#include<float.h>#include<time.h>#include<graphics.h>#include<bios.h> IAg9qLsgBX#define maxpop100#define maxstring100structpp{unsignedcharchrom[maxstring] 。floatx,fitness 。unsignedintparent1,parent2,xsite 。}。structpp*oldpop,*newpop,*p1 。unsignedintpopsize,lchrom,gem,maxgen,co_min,jrand 。unsignedintnmutation,ncross,jcross,maxpp,minpp,maxxy 。floatpcross,pmutation,sumfitness,avg,max,min,seed,maxold,oldrand[maxstring]。unsignedcharx[maxstring],y[maxstring]

。float*dd,ff,maxdd,refpd,fm[201]

。FILE*fp,*fp1

。floatobjfunc(float>

。voidstatistics(>

。21/67個人資料整理 僅限學習使用intselect(>。intflip(float> 。intcrossover(>。voidgeneration(> 。voidinitialize(>。voidreport(>。floatdecode(>。voidcrtinit(>。voidinversion(>。floatrandom1(> 。voidrandomize1(>。WwghWvVhPEmain(>{unsignedintgen,k,j,tt 。charfname[10]。floatttt。clrscr(>。co_min=0。if((oldpop=(structpp*>farmalloc(maxpop*sizeof(structpp>>>==NULL>{printf("memoryrequstfail!\n"> 。exit(0>。}if((dd=(float*>farmalloc(maxstring*maxstring*sizeof(float>>>==NULL>{printf("memoryrequstfail!\n"> 。exit(0>。}if((newpop=(structpp*>farmalloc(maxpop*sizeof(structpp>>>==NULL>{printf("memoryrequstfail!\n"> 。exit(0>。}if((p1=(structpp*>farmalloc(sizeof(structpp>>>==NULL>{printf("memoryrequstfail!\n"> 。exit(0>。}for(k=0。k<maxpop。k++>oldpop[k].chrom[0]='\0' 。for(k=0。k<maxpop。k++>newpop[k].chrom[0]='\0' 。printf("EnterResultDataFilename:"> 。gets(fname>。if((fp=fopen(fname,"w+">>==NULL>{printf("cannotopenfile\n">

。exit(0>

。}

asfpsfpi4kgen=0。randomize(>。initialize(>。fputs("thisisresultoftheTSPproblem:",fp> 。fprintf(fp,"city:%2dpsize:%3dRef.TSP_path:%f\n",lchrom,popsize,refpd>。fprintf(fp,"Pc:%fPm:%fSeed:%f\n",pcross,pmutation,seed>fprintf(fp,"Xsite:\n"> 。for(k=0。k<lchrom。k++>{if((k%16>==0>fprintf(fp,"\n"> 。

。22/67個人資料整理 僅限學習使用fprintf(fp,"%5d",x[k]> 。}fprintf(fp,"\nYsite:\n"> 。for(k=0。k<lchrom。k++>{if((k%16>==0>fprintf(fp,"\n"> 。fprintf(fp,"%5d",y[k]> 。}fprintf(fp,"\n"> 。ooeyYZTjj1crtinit(>。statistics(oldpop>。report(gen,oldpop> 。getch(>。maxold=min。fm[0]=100.0*oldpop[maxpp].x/ff 。do{gen=gen+1 。generation(> 。statistics(oldpop> 。if(max>maxold>{maxold=max 。co_min=0。}fm[gen%200]=100.0*oldpop[maxpp].x/ff 。report(gen,oldpop> 。gotoxy(30,25> 。ttt=clock(>/18.2 。tt=ttt/60 。printf("RunClock:%2d:%2d:%4.2f",tt/60,tt%60,ttt-tt*60.0> 。printf("Min=%6.4fNm:%d\n",min,co_min> 。}while((gen<100>&&!bioskey(1>> 。printf("\ngen=%d",gen> 。do{gen=gen+1 。generation(> 。statistics(oldpop> 。if(max>maxold>{maxold=max 。co_min=0。}fm[gen%200]=100.0*oldpop[maxpp].x/ff 。report(gen,oldpop> 。if((gen%100>==0>report(gen,oldpop> 。23/67個人資料整理 僅限學習使用gotoxy(30,25>。ttt=clock(>/18.2。tt=ttt/60。printf("RunClock:%2d:%2d:%4.2f",tt/60,tt%60,ttt-tt*60.0>。printf("Min=%6.4fNm:%d\n",min,co_min>。}while((gen<maxgen>&&!bioskey(1>>。BkeGuInkxIgetch(>。for(k=0。k<lchrom。k++>{if((k%16>==0>fprintf(fp,"\n">。fprintf(fp,"%5d",oldpop[maxpp].chrom[k]>。}fprintf(fp,"\n">。PgdO0sRlMofclose(fp>。farfree(dd>。farfree(p1>。farfree(oldpop>。farfree(newpop>。restorecrtmode(>。exit(0>。}3cdXwckm15/*%%%%%%%%%%%%%%%%*/floatobjfunc(floatx1>{floaty。y=100.0*ff/x1 。returny。}h8c52WOngM/*&&&&&&&&&&&&&&&&&&&*/voidstatistics(pop>structpp*pop。{intj。sumfitness=pop[0].fitness 。min=pop[0].fitness 。max=pop[0].fitness 。maxpp=0。minpp=0。for(j=1。j<popsize。j++>{sumfitness=sumfitness+pop[j].fitness 。if(pop[j].fitness>max>{max=pop[j].fitness 。24/67個人資料整理 僅限學習使用maxpp=j。}if(pop[j].fitness<min>{min=pop[j].fitness 。minpp=j。}}v4bdyGiousavg=sumfitness/(float>popsize 。}/*%%%%%%%%%%%%%%%%%%%%*/voidgeneration(>{unsignedintk,j,j1,j2,i1,i2,mate1,mate2 。floatf1,f2。j=0。do{mate1=select(> 。pp:mate2=select(> 。if(mate1==mate2>gotopp 。crossover(oldpop[mate1].chrom,oldpop[mate2].chrom,j> 。newpop[j].x=(float>decode(newpop[j].chrom> 。newpop[j].fitness=objfunc(newpop[j].x> 。newpop[j].parent1=mate1 。newpop[j].parent2=mate2 。newpop[j].xsite=jcross 。newpop[j+1].x=(float>decode(newpop[j+1].chrom> 。newpop[j+1].fitness=objfunc(newpop[j+1].x>。newpop[j+1].parent1=mate1。newpop[j+1].parent2=mate2。newpop[j+1].xsite=jcross。if(newpop[j].fitness>min>{for(k=0。k<lchrom。k++>oldpop[minpp].chrom[k]=newpop[j].chrom[k] 。oldpop[minpp].x=newpop[j].x 。oldpop[minpp].fitness=newpop[j].fitness 。co_min++。return。}J0bm4qMpJ9if(newpop[j+1].fitness>min>{for(k=0。k<lchrom。k++>oldpop[minpp].chrom[k]=newpop[j+1].chrom[k] 。oldpop[minpp].x=newpop[j+1].x 。25/67個人資料整理 僅限學習使用oldpop[minpp].fitness=newpop[j+1].fitness 。co_min++。return。}j=j+2 。}while(j<popsize> 。}XVauA9grYP/*%%%%%%%%%%%%%%%%%*/voidinitdata(>{unsignedintch,j。clrscr(>。printf("-----------------------\n">。printf("ASGA\n">。printf("------------------------\n">。/*pause(>。*/clrscr(>。printf("*******SGADATAENTRYANDINITILIZATION*******\n">。printf("\n">。printf("inputpopsize">。scanf("%d",&popsize>。printf("inputchromlength">。scanf("%d",&lchrom>。printf("inputmaxgenerations">。scanf("%d",&maxgen>。printf("inputcrossoverprobability">。scanf("%f",&pcross>。printf("inputmutationprob">。scanf("%f",&pmutation>。randomize1(>。clrscr(>。nmutation=0。ncross=0。}bR9C6TJscw/*%%%%%%%%%%%%%%%%%%%%*/voidinitreport(>{intj,k。printf("popsize=%d\n",popsize>。printf("chromosomelength=%d\n",lchrom>。printf("maxgen=%d\n",maxgen>。printf("pmutation=%f\n",pmutation>。printf("pcross=%f\n",pcross>。printf("initialgenerationstatistics\n">。printf("inipopmaxfitness=%f\n",max>。printf("inipopavrfitness=%f\n",avg>。printf("inipopminfitness=%f\n",min>。printf("inipopsumfit=%f\n",sumfitness>。}pN9LBDdtrd26/67個人資料整理 僅限學習使用voidinitpop(>{unsignedcharj1。unsignedintk5,i1,i2,j,i,k,j2,j3,j4,p5[maxstring] 。floatf1,f2。j=0。for(k=0。k<lchrom。k++>oldpop[j].chrom[k]=k 。for(k=0。k<lchrom。k++>p5[k]=oldpop[j].chrom[k] 。randomize(>。for(。j<popsize。j++>{j2=random(lchrom> 。for(k=0 。k<j2+20。k++>{j3=random(lchrom> 。j4=random(lchrom> 。j1=p5[j3] 。p5[j3]=p5[j4] 。p5[j4]=j1 。}for(k=0 。k<lchrom。k++>oldpop[j].chrom[k]=p5[k] 。}for(k=0。k<lchrom。k++>for(j=0。j<lchrom。j++>dd[k*lchrom+j]=hypot(x[k]-x[j],y[k]-y[j]> 。for(j=0。j<popsize。j++>{oldpop[j].x=(float>decode(oldpop[j].chrom> 。oldpop[j].fitness=objfunc(oldpop[j].x> 。oldpop[j].parent1=0 。oldpop[j].parent2=0 。oldpop[j].xsite=0 。}}DJ8T7nHuGT/*&&&&&&&&&&&&&&&&&*/voidinitialize(>{intk,j,minx,miny,maxx,maxy 。initdata(>。minx=0。miny=0。maxx=0。maxy=0。for(k=0。k<lchrom。k++>{x[k]=rand(> 。27/67個人資料整理 僅限學習使用if(x[k]>maxx>maxx=x[k] 。if(x[k]<minx>minx=x[k] 。y[k]=rand(> 。if(y[k]>maxy>maxy=y[k] 。if(y[k]<miny>miny=y[k] 。}if((maxx-minx>>(maxy-miny>>{maxxy=maxx-minx 。}else{maxxy=maxy-miny 。}maxdd=0.0。for(k=0。k<lchrom。k++>for(j=0。j<lchrom。j++>{dd[k*lchrom+j]=hypot(x[k]-x[j],y[k]-y[j]> 。if(maxdd<dd[k*lchrom+j]>maxdd=dd[k*lchrom+j] 。}refpd=dd[lchrom-1] 。for(k=0。k<lchrom。k++>refpd=refpd+dd[k*lchrom+k+2] 。for(j=0。j<lchrom。j++>dd[j*lchrom+j]=4.0*maxdd 。ff=(0.765*maxxy*pow(lchrom,0.5>> 。minpp=0。min=dd[lchrom-1] 。for(j=0。j<lchrom-1。j++>{if(dd[lchrom*j+lchrom-1]<min>{min=dd[lchrom*j+lchrom-1] 。minpp=j。}}initpop(>。statistics(oldpop>。initreport(>。}QF81D7bvUA/*&&&&&&&&&&&&&&&&&&*/voidreport(intl,structpp*pop>{intk,ix,iy,jx,jy 。unsignedinttt。floatttt。cleardevice(>。gotoxy(1,1>。printf("city:%4dpara_size:%4dmaxgen:%4dref_tour:%f\n",lchrom,popsize,maxgen,refpd> 。28/67個人資料整理 僅限學習使用n",ncross,nmutation,l,avg,min> 。printf("Rinpath:%6.4fMinpathlength:%10.4fRef_co_tour:%f\n",pop[maxpp].x/maxxy,pop[maxpp].x,ff> 。printf("Co_minpath:%6.4fMaxfit:%10.8f",100.0*pop[maxpp].x/ff,pop[maxpp].fitness> 。ttt=clock(>/18.2 。tt=ttt/60。printf("Runclock:%2d:%2d:%4d.2f\n",tt/60,tt%60,ttt-tt*60.0> 。setcolor(1%15+1> 。for(k=0。k<lchrom-1。k++>{ix=x[pop[maxpp].chrom[k]] 。iy=y[pop[maxpp].chrom[k]]+110 。jx=x[pop[maxpp].chrom[k+1]] 。jy=y[pop[maxpp].chrom[k+1]]+110 。line(ix,iy,jx,jy> 。putpixel(ix,iy,RED> 。}ix=x[pop[maxpp].chrom[0]] 。iy=y[pop[maxpp].chrom[0]]+110 。jx=x[pop[maxpp].chrom[lchrom-1]] 。jy=y[pop[maxpp].chrom[lchrom-1]]+110 。line(ix,iy,jx,jy> 。putpixel(jx,jy,RED> 。setcolor(11>。outtextxy(ix,iy,"*"> 。setcolor(12>。for(k=0。k<1%200。k++>{ix=k+280 。iy=366-fm[k]/3 。jx=ix+1 。jy=366-fm[k+1]/3 。line(ix,iy,jx,jy> 。putpixel(ix,iy,RED> 。}printf("GEN:%3d",l> 。printf("Minpath:%fMaxfit:%f",pop[maxpp].x,pop[maxpp].fitness> 。printf("Clock:%2d:%2d: