用模擬退火算法或者遺傳算法解決TSP問(wèn)題程序.docx

《用模擬退火算法或者遺傳算法解決TSP問(wèn)題程序.docx》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、用模擬退火算法、遺傳算法（或蟻群算法）求解10城市的TSP（旅行商）問(wèn)題，計(jì)算旅行封閉的最短旅行距離。解：用遺傳算法解決TSP問(wèn)題，首先需要確定城市個(gè)數(shù)及城市間的距離，隨機(jī)產(chǎn)生城市序列作為一個(gè)個(gè)體，確定目標(biāo)函數(shù)，通過(guò)遺傳算法的復(fù)制、交叉、變異求出最優(yōu)解。目標(biāo)函數(shù)fx=i=0ndi,i+1+d(n,0)適應(yīng)度函數(shù)Fx=-fx+Cmaxfx

2、5117739471574118012532511163320771369115739611518127212530146238014908218563660385256725111462092223351562216539959331653163338092201700104111353870456209720771490233517000231192021701920142513698211562104123110142042906261177115785621651135920142002870129039473961366039953870217

3、04290287004090157415183859934561920626129040900];D=size(ZQ,1);EE=CSHZQ(ZQDX,D);disp('初始種群中的一個(gè)隨機(jī)值:')SCXL(EE(1,:));RTH=XLCD(ZQ,EE(1,:));disp('總距離:');disp(num2str(RTH));Q=0;OV=XLCD(ZQ,EE);POV=min(OV);while(Q

4、(XZ,Pc);XZ=BY(XZ,Pm);XZ=NZ(XZ,ZQ);EE=CCZ(EE,XZ,OV);Q=Q+1;endOV=XLCD(ZQ,EE);[minOV,minInd]=min(OV);disp('最優(yōu)解:')p=SCXL(EE(minInd(1),:));disp('總距離：');disp(num2str(OV(minInd(1))));初始化全局變量：functionEE=CSHZQ(ZQDX,D)EE=zeros(ZQDX,D);for(i=1:ZQDX)EE(i,:)=randperm(D);end適應(yīng)度函數(shù)：functionSYD=S

5、HYD(len)SYD=1./len;選擇程序：functionXZ=XUANZE(EE,SYD,DG)ZQDX=size(EE,1);NSel=max(floor(ZQDX*DG+.5),2);ChrIx=sus(SYD,NSel);XZ=EE(ChrIx,:);functionNewChrIx=sus(SYD,Nsel)[Nind,ans]=size(SYD);cumfit=cumsum(SYD);trials=cumfit(Nind)/Nsel*(rand+(0:Nsel-1)');Mf=cumfit(:,ones(1,Nsel));Mt=tria

6、ls(:,ones(1,Nind))';[NewChrIx,ans]=find(Mt=rand)[XZ(i,:),XZ(i+1,:)]=ICS(XZ(i,:),XZ(i+1,:));endendICS函數(shù)function[

7、a,b]=ICS(a,b)L=length(a);r1=randsrc(1,1,[1:L]);r2=randsrc(1,1,[1:L]);ifr1~=r2a0=a;b0=b;s=min([r1,r2]);e=max([r1,r2]);fori=s:ea1=a;b1=b;a(i)=b0(i);b(i)=a0(i);x=find(a==a(i));y=find(b==b(i));i1=x(x~=i);i2=y(y~=i);if~isempty(i1)a(i1)=a1(i);endif~isempty(i2)b(i2)=b1(i);endendend變異：fu

8、nctionXZ=BY(XZ,Pm)[NSel,L]=size(XZ);for(