TSP問題的遺傳算法

1、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=

2、v1,v2,v3,vn的一個訪問順序為 t=(t1,t2,t3,ti,tn),其中ti v(i=1,2,3,n),且記tn+1= t1 ,那么旅行商問題的數(shù)學模型為：min l= (T d(t(i),t(i+1) (i=1,n)旅行商問題是一個典型的組合優(yōu)化問題,并且是一個 np 難問題,其可能的路徑數(shù)目與城市數(shù)目 n 是成指數(shù)型增長的,所以一般很難精確地求出其最優(yōu)解, 本文采用遺傳算法求其近似解.遺傳算法：初始化過程：用v1,v2,v3,vn代表所選n個城市.定義整數(shù)pop-size作為染色 體的個數(shù),并且隨機產(chǎn)生 pop-size 個初始染色體,每個染色體為 1到 18的整數(shù) 組成的隨機序

3、列.適應度f的計算：對種群中的每個染色體 vi,計算其適應度,f=(7 d(t(i),t(i+1). 評價函數(shù) eval(vi) ：用來對種群中的每個染色體 vi 設定一個概率,以使該染色體 被選中的可能性與其種群中其它染色體的適應性成比例, 既通過輪盤賭, 適應性價函數(shù)為eval(vi)=alpha*(1-alpha)4(i-1).隨機規(guī)劃與模糊規(guī)劃選擇過程：選擇過程是以旋轉(zhuǎn)賭輪 pop-size 次為根底,每次旋轉(zhuǎn)都為新的種群選擇一個染色體.賭輪是按每個染色體的適應度進行選擇染色體的.stepl、對每個染色體 vi,計算累計概率 qi , q0=0;qi= c eval(vj) j=1,i

4、;i=1,pop-size.step2、從區(qū)間(0,pop-size)中產(chǎn)生一個隨機數(shù)r;step3、假設qi-1<r<qi,那么選擇第i個染色體；step4、重復step2和step3共pop-size次,這樣可以得到 pop-size個復制的 染色體.grefenstette 編碼：由于常規(guī)的交叉運算和變異運算會使種群中產(chǎn)生一些無實際意義的染色體,本文采用 grefenstette 編碼?遺傳算法原理及應用?可以防止這種情況的出現(xiàn).所謂的 grefenstette 編碼就是用所選隊員在未選(不含淘汰)隊 員中的位置,如：8 15 2 16 10 7 4 3 11 14 6 12

5、 9 5 18 13 17 1對應：8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1 .交叉過程：本文采用常規(guī)單點交叉.為確定交叉操作的父代,從 到 pop-size 重 復以下過程：從0 , 1沖產(chǎn)生一個隨機數(shù)r,如果rvpc,那么選擇vi作為一個父 代.將所選的父代兩兩組隊,隨機產(chǎn)生一個位置進行交叉,如：8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 16 12 3 5 6 8 5 6 3 1 8 5 6 3 3 2 1 1交叉后為：8 14 2 13 8 6 3 2 5 1 8 5 6 3 3 2 1 16 12 3 5 6 8 5 6

6、3 7 3 4 3 2 4 2 2 1 變異過程：本文采用均勻多點變異.類似交叉操作中選擇父代的過程,在 r<pm 的標準下選擇多個染色體 vi 作為父代.對每一個選擇的父代,隨機選擇多個位 置,使其在每位置按均勻變異(該變異點 xk 的取值范圍為 ukmin,ukmax, 產(chǎn)生一個0 , 1中隨機數(shù)r,該點變異為x'k=ukmin+r(ukmax-ukmin)操作.如：8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1變異后：8 14 2 13 10 6 3 2 2 7 3 4 5 2 4 1 2 1反 grefenstette 編碼：交叉和變異都是在

7、grefenstette 編碼之后進行的,為了循 環(huán)操作和返回最終結(jié)果, 必須逆 grefenstette 編碼過程,將編碼恢復到自然編碼.循環(huán)操作：判斷是否滿足設定的帶數(shù) xzome,否,貝U跳入適應度f的計算；是, 結(jié)束遺傳操作,跳出.function bestpop,trace=ga(d,termops,num,pc,cxops,pm,alpha)% %bestpop,trace=ga(d,termops,num,pc,cxops,pm,alpha) %d: 距離矩陣%termops: 種群帶數(shù)%num: 每帶染色體的個數(shù)%pc: 交叉概率%cxops: 由于本程序采用單點交叉,交叉點的

8、設置在本程序中沒有很好的解決, 所以本文了采用定點,即第 cxops ,可以隨機產(chǎn)生.%pm: 變異概率%alpha:評價函數(shù) eval(vi)=alpha*(1-alpha)4(i-1).%bestpop: 返回的最優(yōu)種群%trace: 進化軌跡%citynum=size(d,2);n=nargin;if n<2disp('缺少變量！ ！)endif n<2termops=500;num=50;pc=0.25;cxops=3;alpha=0.10;endif n<3num=50;pc=0.25;cxops=3;pm=0.30;alpha=0.10;endif n&l

9、t;4pc=0.25;cxops=3;pm=0.30;alpha=0.10;endif n<5cxops=3;pm=0.30;alpha=0.10;endif n<6pm=0.30;alpha=0.10;endif n<7alpha=0.10;endif isempty(cxops)cxops=3;endt=initializega(num,citynum);for i=1:termopsl=f(d,t);x,y=find(l=max(l);trace(i)=-l(y(1);bestpop=t(y(1),:);t=select(t,l,alpha);g=grefenstett

10、e(t);g1=crossover(g,pc,cxops);g=mutation(g1,pm);% 均勻變異t=congrefenstette(g);endfunction t=initializega(num,citynum)for i=1:num t(i,:)=randperm(citynum);end function l=f(d,t)m,n=size(t);for k=1:mfor i=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,a

11、lpha)m,n=size(l);t1=t;beforesort,aftersort1=sort(l,2);%fsort from l to ufor i=1:naftersort(i)=aftersort1(n+1-i); %changeend for k=1:n;t(k,:)=t1(aftersort(k),:);l1(k)=l(aftersort(k);endt1=t;l=l1;for i=1:size(aftersort,2)evalv(i)=alpha*(1-alpha)4(i-1);endm=size(t,1);q=cumsum(evalv);qmax=max(q);for k=1

12、:mr=qmax*rand(1);for j=1:mif j=1&r<=q(1)t(k,:)=t1(1,:);elseif j=1&r>q(j-1)&r<=q(j)t(k,:)=t1(j,:);endendend function g=grefenstette(t)m,n=size(t);for k=1:mt0=1:n;for i=1:nfor j=1:length(t0)if t(k,i)=t0(j) g(k,i)=j; t0(j)=; breakendendendend function g=crossover(g,pc,cxops)m,n=siz

13、e(g);ran=rand(1,m);r=cxops;x,ru=find(ran<pc);if ru>=2for k=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); %dai gai jin rr=floor(n*rand(1,3)+1);x,mu=find(ran<pm);for k=1: