遺傳算法的matlab通用程序

1、已知 n 個城市之間的相互距離，現(xiàn)有一個推銷員必須遍訪這n 個城市，并且每個城市只能訪問一次，最后又必須返回出發(fā)城市。如何安排他對這些城市的訪問次序，可使其旅行路線的總長度最短？用圖論的術語來說，假設有一個圖g=(v,e) ，其中 v 是頂點集，e 是邊集，設d=(dij)是由頂點i 和頂點 j 之間的距離所組成的距離矩陣，旅行商問題就是求出一條通過所有頂點且每個頂點只通過一次的具有最短距離的回路。這個問題可分為對稱旅行商問題(dij=dji,任意i,j=1,2,3,n)和非對稱旅行商問題(dij wdji,任意 i,j=1,2,3,n)。若對于城市v=v1,v2,v3,vn的一個訪問順序為t

2、=(t1,t2,t3,ti,tn),其中ti Cv(i=1,2,3,n),且記tn+1= t1 ,則旅行商問題的數(shù)學模型為：min l= o- 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ù)，并且隨機產生pop-size 個初始染色體，每個染色體為1 到 18 的整數(shù)組成的隨機序列。適應度f的計算：對種群中的每個染色體 vi

3、 ,計算其適應度，f= bd(t(i),t(i+1).評價函數(shù)eval(vi) ：用來對種群中的每個染色體vi 設定一個概率，以使該染色體被選中的可能性與其種群中其它染色體的適應性成比例，既通過輪盤賭，適應性強的染色體被選擇產生后臺的機會要大，設alpha C (0,1),本文定義基于序的評價函數(shù)為 eval(vi)=alpha*(1-alpha)A(i-1)。隨機規(guī)劃與模糊規(guī)劃選擇過程：選擇過程是以旋轉賭輪pop-size 次為基礎，每次旋轉都為新的種群選擇一個染色體。賭輪是按每個染色體的適應度進行選擇染色體的。stepl 、對每個染色體 vi,計算累計概率 qi , q0=0;qi= o-

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

5、2 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 中產生一個隨機數(shù)r ，如果 r 將所選的父代兩兩組隊，隨機產生一個位置進行交叉，如：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 3 7 3 4 3 2 4 2

6、 2 1變異過程：本文采用均勻多點變異。類似交叉操作中選擇父代的過程，在r 選擇多個染色體 vi 作為父代。對每一個選擇的父代，隨機選擇多個位置，使其在每位置按均勻變異(該變異點xk 的取值范圍為ukmin,ukmax, 產生一個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 編碼：交叉和變異都是在grefenstette 編碼之后進行的，為了循環(huán)操作和

7、返回最終結果，必須逆grefenstette 編碼過程，將編碼恢復到自然編碼。循環(huán)操作：判斷是否滿足設定的帶數(shù)xzome ，否，則跳入適應度f 的計算；是，結束遺傳操作，跳出。matlab 代碼distTSP.txt0 6 18 4 87 0 17 3 74 4 0 4 520 19 24 0 228 8 16 6 0%GATSP.mfunction gatsp1()clear;load distTSP.txt;distance=distTSP;N=5;ngen=100;ngpool=10;%ngen=input('# of generations to evolve = ')

8、;%ngpool=input('# of chromosoms in the gene pool = ');% size of genepoolgpool=zeros(ngpool,N+1); % gene poolfor i=1:ngpool, % intialize gene poolgpool(i,:)=1 randomize(2:N')' 1;for j=1:i-1while gpool(i,:)=gpool(j,:)gpool(i,:)=1 randomize(2:N')' 1;endendend costmin=100000;tour

9、min=zeros(1,N);cost=zeros(1,ngpool);increase=1;resultincrease=1;for i=1:ngpool,cost(i)=sum(diag(distance(gpool(i,:)',rshift(gpool(i,:)'); end% record current best solutioncostmin,idx=min(cost);tourmin=gpool(idx,:);disp(num2str(increase) 'minmum trip length = ' num2str(costmin)costmin

10、old2=200000;costminold1=150000;resultcost=100000;tourminold2=zeros(1,N);tourminold1=zeros(1,N);resulttour=zeros(1,N);while;10(abs(costminold2-costminold1);100)&(abs(costminold1-costmin)0)&(increase ;500)costminold2=costminold1; tourminold2=tourminold1;costminold1=costmin;tourminold1=tourmin;

11、increase=increase+1;if resultcost>costminresultcost=costmin;resulttour=tourmin;resultincrease=increase-1;endfor i=1:ngpool,cost(i)=sum(diag(distance(gpool(i,:)',rshift(gpool(i,:)'); end% record current best solutioncostmin,idx=min(cost);tourmin=gpool(idx,:);%=% copy gens in th gpool accor

12、ding to the probility ratio% >1.1 copy twice% >=0.9 copy once% ;0.9 removecsort,ridx=sort(cost);% sort from small to big.csum=sum(csort);caverage=csum/ngpool;cprobilities=caverage./csort;copynumbers=0;removenumbers=0;for i=1:ngpool,if cprobilities(i) >1.1copynumbers=copynumbers+1;endif cpro

13、bilities(i) <0.9removenumbers=removenumbers+1;endendcopygpool=min(copynumbers,removenumbers);for i=1:copygpoolfor j=ngpool:-1:2*i+2 gpool(j,:)=gpool(j-1,:);endgpool(2*i+1,:)=gpool(i,:);endif copygpool=0gpool(ngpool,:)=gpool(1,:);end%=%when genaration is more than 50,or the patterns in a couple ar

14、e too close,do mutationfor i=1:ngpool/2%sameidx=gpool(2*i-1,:)=gpool(2*i,:);diffidx=find(sameidx=0);if length(diffidx)<=2gpool(2*i,:)=1 randomize(2:12')' 1;endend%=%cross gens in couplesfor i=1:ngpool/2gpool(2*i-1,:),gpool(2*i,:)=crossgens(gpool(2*i-1,:),gpool(2*i,:);endfor i=1:ngpool,cos

15、t(i)=sum(diag(distance(gpool(i,:)',rshift(gpool(i,:)');end% record current best solutioncostmin,idx=min(cost);tourmin=gpool(idx,:);disp(num2str(increase) 'minmum trip length = ' num2str(costmin) end disp('cost function evaluation: ' int2str(increase) ' times!')disp(&#

16、39;n:' int2str(resultincrease)disp('minmum trip length = ' num2str(resultcost)disp('optimum tour =')disp(num2str(resulttour)%= function B=randomize(A,rowcol)% Usage: B=randomize(A,rowcol)% randomize row orders or column orders of A matrix% rowcol: if =0 or omitted, row order (def

17、ault)% if = 1, column orderrand('state',sum(100*clock)if nargin = 1,rowcol=0;endif rowcol=0,m,n=size(A);p=rand(m,1);p1,I=sort(p);B=A(I,:);elseif rowcol=1,Ap=A'm,n=size(Ap);p=rand(m,1);p1,I=sort(p);B=Ap(I,:)'end%= function y=rshift(x,dir)% Usage: y=rshift(x,dir)% rotate x vector to ri

18、ght (down) by 1 if dir = 0 (default)% or rotate x to left (up) by 1 if dir = 1if nargin ;2, dir=0; endm,n=size(x);if m>1,if n = 1,col=1;elseif n>1,error('x must be a vector! break');end % x is a column vectorelseif m = 1,if n = 1, y=x;returnelseif n>1,col=0; % x is a row vector endendif dir=1, % rotate left or upif col=0, % row vecto