TSP遺傳算法概要

1、實(shí)驗(yàn)二 基于遺傳算法的T S P求解一、實(shí)驗(yàn)?zāi)康恼莆者z傳算法求解TSP問題的實(shí)現(xiàn)過程。二、實(shí)驗(yàn)內(nèi)容用遺傳算法求解TSR由于其任一可能解一一 一個(gè)合法的城市序列，即 n個(gè)城市的一個(gè)排列，都可以事先構(gòu) 造出來。于是，我們就可以直接在解空間(所有合法的城市序列)中搜索最佳解。這正適合 用遺傳算法求解。三、實(shí)驗(yàn)步驟(1)編碼路徑表示是表示旅程對(duì)應(yīng)的基因編碼的最自然、最簡單的表示方法。例如，旅程(5 1 7894 623)可以直接表不'為(517894623),基于路徑表不'的編碼方法，要求個(gè)個(gè)體(即一條旅程)的染色體編碼中不允許有重復(fù)的基因碼，也就是說要滿足任一個(gè)城市必須而且只能訪問一

2、次的約束。(2)定義適應(yīng)度函數(shù)我們將一個(gè)合法的城市序列s= (c1, c2,，cn)作為一個(gè)個(gè)體。這個(gè)序列中相鄰兩城市之間的距離之和的倒數(shù)就可作為相應(yīng)個(gè)體s的適應(yīng)度，從而適應(yīng)度函數(shù)就是：1f (s) = Tj' d(G,Ci 1) i工例如，對(duì)于9個(gè)城市的TSP,我們用符號(hào)1、2、3、4、5、6、7、8、9代表相應(yīng)的城市， 用這9個(gè)符號(hào)的序列表示可能解即染色體。然后進(jìn)行遺傳操作用部分匹配交叉PMRT法：匹配操作要求隨機(jī)選取兩個(gè)交叉點(diǎn)，確定一個(gè)匹配段，根據(jù)兩個(gè)父個(gè)體中兩個(gè)交叉點(diǎn)之間的中間段給出的映射關(guān)系生成兩個(gè)子個(gè)體.例如，對(duì)下面兩個(gè)父個(gè)體的表示，隨機(jī)選擇兩個(gè)交義點(diǎn)P1: 1 2 3 4

3、 5 6 7 8 9o1:4 2 3 1 8 7 6 5 9P2: 4 5 2 1 8 7 6 9 302:1 8 2 4 5 6 7 9 3交叉方法：隨機(jī)選取染色體上兩個(gè)元，然后交換 它們的位置.例如：4 5 2 1 8 7 6 9 3交換后：4 5 6 1 8 7 2 9 3(3 )求解的Tsp問題的城市坐標(biāo)如下：38.24 20.4239.57 26.1540.56 25.3236.26 23.1233.48 10.5437.5612.1938.4213.1137.5220.4441.239.1041.1713.0536.08-5.2138.4715.1338.1515.3537.511

4、5.1735.4914.3239.3619.5638.0924.3636.0923.0040.4413.5740.3314.1540.3714.2337.5722.56四、程序?qū)崿F(xiàn)%基于遺傳算法的TSP問題求解%D是距離矩陣，n為種群個(gè)數(shù)，建議取為城市個(gè)數(shù)的12倍，%C為停止代數(shù)，遺傳到第C代時(shí)程序停止，C的具體取值視問題的規(guī)模和耗費(fèi)的時(shí)間而定%m為適應(yīng)值歸一化淘汰加速指數(shù)，最好取為1,2,3,4 ,不宜太大%alpha為淘汰保護(hù)指數(shù)，可取為01之間任意小數(shù)，取1時(shí)關(guān)閉保護(hù)功能，最好取為0.81.0%R為最短路徑，Rlength為路徑長度close all;clc;clear;%城市坐標(biāo)cit

5、y=38.2420.42;39.57 26.15;40.56 25.32;36.26 23.12;33.48 10.54;37.56 12.19;38.42 13.11;37.52 20.44;41.23 9.10;41.17 13.05;36.08 -5.21;38.47 15.13;38.15 15.35;37.5115.17;35.49 14.32;39.36 19.56;38.09 24.36;36.09 23.00;40.44 13.57;40.33 14.15;40.37 14.23;37.57 22.56;'D=dist(city,city);%城市間距離矩陣n=100;

6、C=100;m=2;alpha=0.9;N,NN=size(D);farm=zeros(n,N);%用于存儲(chǔ)種群for i=1:nfarm(i,:)=randperm(N);%隨機(jī)生成初始種群endR=farm(1,:);%存儲(chǔ)最優(yōu)種群len=zeros(n,1);%存儲(chǔ)路徑長度fitness=zeros(n,1);%存儲(chǔ)歸一化適應(yīng)值counter=0;%記錄迭代次數(shù)while counter<Cfor i=1:nlen(i,1)=myLength(D,farm(i,:);% 計(jì)算路徑長度 end maxlen=max(len);minlen=min(len);fitness=fit(l

7、en,m,maxlen,minlen);% 計(jì)算歸一化適應(yīng)值 rr=find(len=minlen);R=farm(rr(1,1),1);%更新最短路徑FARM=farm;%優(yōu)勝劣汰，nn記錄了復(fù)制的個(gè)數(shù) nn=0; for i=1:nnn=nn+1;FARM(nn,:)=farm(i,:);if fitness(i,1)>=alpha*randendaa,bb=size(FARM);% 交叉和變異 while aa<nif nn<=2nnper=randperm(2);elsennper=randperm(nn);endA=FARM(nnper(1),:);B=FARM(n

8、nper(2),:);A,B=intercross(A,B);FARM=FARM;A;B;aa,bb=size(FARM);endif aa>nFARM=FARM(1:n,:);%保持種群規(guī)模為 n endfarm=FARM;clear FARMcounter=counter+1;endRlength=len(16)% 最優(yōu)路徑farm(16,:)%城市訪問次序newcood=city(:,farm(16,:);newcood=newcood newcood(:,1);%路徑是封閉連續(xù)的分段曲線plot(newcood(1,:),newcood(2,:),'o-');ti

9、tle('最優(yōu)路徑圖')%計(jì)算歸一化適應(yīng)值子程序function fitness=fit(len,m,maxlen,minlen)fitness=len;for i=1:length(len)fitness(i,1)=(1-(len(i,1)-minlen)/(maxlen-minlen+0.000001).Am; end%計(jì)算路徑的子程序 function len=myLength(D,p) N,NN=size(D);len=D(p(1,N),p(1,1);for j=1:N-1len=len+D(p(1,j),p(1,j+1);function x,y=exchange(x

10、,y)temp=x;x=y;y=temp;function a,b=intercross(a,b)L=length(a);if L<=10%確定交叉寬度W=1;elseif (L/10)-floor(L/10)>=rand&&L>10W=ceil(L/10);elseW=floor(L/10);endp=unidrnd(L-W+1);%隨機(jī)選擇交叉范圍，從 p到p+Wfor i=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);End運(yùn)行結(jié)果：counter =%迭代100次100Rlength =%最優(yōu)路徑程度124.4678ans =%最優(yōu)路徑次序Columns 1 through 10141731841195610Columns 11 through 2020222816121921713Columns 21 through 22115五、問題思考比較用Hopfield求解TSP問題和遺傳算法求解TS