遗传算法求解tsp问题的matlab代码

遗传算法求解tsp问题的matlab代码 ï?? ä??ã?‚æ?‡ç? æ?,自 ç??æ??æº ç •å??(www.sfcode.cn) Matlabçš„GAç?‹åº? é•?ä? ç??æ??æ?‚TSP for i=1:ngpool, cost(i)=sum(diag(distance(gpool(i,:)',rshift(gpool(i,:))'))); end % record current best solution [costmin,idx]=min(cost); tourmin=gpool(idx,:); %============== % copy gens in th gpool according to the probility ratio % >1.1 copy twice % >=0.9 copy once % <0.9 remove [csort,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.1 copynumbers=copynumbers+1; end if cprobilities(i)<0.9 removenumbers=removenumbers+1; end end copygpool=min(copynumbers,removenumbers); for i=1:copygpool for j=ngpool:-1:2*i+2 gpool(j,:)=gpool(j-1,:); end gpool(2*i+1,:)=gpool(i,:); end if copygpool==0 gpool(ngpool,:)=gpool(1,:); end %========= %when genaration is more than 50,or the patterns in a couple are too close,do mutation for i=1:ngpool/2 % sameidx=[gpool(2*i-1,:)==gpool(2*i,:)]; diffidx=find(sameidx==0); if length(diffidx)<=2 gpool(2*i,:)=[1 randomize([2:12]')' 1]; end end %=========== %cross gens in couples for i=1:ngpool/2 [gpool(2*i-1,:),gpool(2*i,:)]=crossgens(gpool(2*i-1,:),gpool(2*i,:)); end for i=1:ngpool, cost(i)=sum(diag(distance(gpool(i,:)',rshift(gpool(i,:))'))); end % record current best solution [costmin,idx]=min(cost); tourmin=gpool(idx,:); disp([num2str(increase) 'minmum trip length = ' num2str(costmin)]) end disp(['cost function evaluation: ' int2str(increase) ' times!']) disp(['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 (default) % if = 1, column order rand('state',sum(100*clock)) if nargin == 1, rowcol=0; end if 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 right (down) by 1 if dir = 0 (default) % or rotate x to left (up) by 1 if dir = 1 if nargin<2, dir=0; end [m,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 vector elseif m == 1, if n == 1, y=x; return elseif n > 1, col=0; % x is a row vector end end if dir==1, % rotate left or up if col==0, % row vector, rotate left y = [x(2:n) x(1)]; elseif col==1, y = [x(2:n); x(1)]; % rotate up end elseif dir==0, % default rotate right or down if col==0, y = [x(n) x(1:n-1)]; elseif col==1 % column vector y = [x(n); x(1:n-1)]; end end %================================================== function [L1,L2]=crossgens(X1,X2) % Usage:[L1,L2]=crossgens(X1,X2) s=randomize([2:12]')'; n1=min(s(1),s(11));n2=max(s(1),s(11)); X3=X1;X4=X2; for i=n1:n2, for j=1:13, if X2(i)==X3(j), X3(j)=0; end if X1(i)==X4(j), X4(j)=0; end end end j=13;k=13; for i=12:-1:2, if X3(i)~=0, j=j-1; t=X3(j);X3(j)=X3(i);X3(i)=t; end if X4(i)~=0, k=k-1; t=X4(k);X4(k)=X4(i);X4(i)=t; end end for i=n1:n2 X3(2+i-n1)=X2(i); X4(2+i-n1)=X1(i); end L1=X3;L2=X4; %======================= å…?ä?-distTSP.txtä?º10ä?ªåŸ?å?‚è??ç,?çŸ?é?µã?‚ 0 622 1042 776 2236 2496 1821 636 825 1130 2005 1953 622 0 1608 1342 2802 3063 2387 972 1161 1166 2623 2519 1042 1608 0 1336 2544 2805 2129 1622 1811 2116 2313 2261 776 1342 1336 0 1451 1721 1045 1356 1545 1229 1229 1177 2236 2802 2544 1451 0 1172 842 2542 2353 2048 2048 1439 2496 3063 2805 1721 1172 0 676 2376 2187 1882 1813 1327 1821 2387 2129 1045 842 676 0 1700 1511 1206 1165 651 636 972 1622 1356 2542 2376 1700 0 189 494 1651 1686 825 1161 1811 1545 2353 2187 1511 189 0 305 1462 1497 1130 1166 2116 1229 2048 1882 1206 494 305 0 1157 1192 2005 2623 2313 1229 2048 1813 1165 1651 1462 1157 0 514 1953 2519 2261 1177 1439 1327 651 1686 1497 1192 514 0 二ã?‚%TSPé??é??ï?ˆå?ˆå??ï?šæ?…è?Œå?†é??é??ï?Œè??éƒ?æ‹…é??é??ï?‰é•?ä? ç??æ??é?šç??matlabç?‹åº %Dæ??è??ç,?çŸ?é?µï?Œnä?ºç??ç?,ä?ªæ??,å?ºè??å??ä?ºåŸ?å?‚ä?ªæ??çš„1~2å??ï?Œ %Cä?ºå?œæ-?ä??æ??ï?Œé??ä? åˆ?ç?? Cä??æ??ç?‹åº?å?œæ-?,Cçš„å…?ä??å??å??è?†é??é??çš„è?„æ??å’Œè??è??çš„æ??é??è?Œå?š %mä?ºé?‚åº?å??å?’ä??åŒ?æ??æ??åŠ é?ŸæŒ‡æ?? ,æœ?å,?å ?ä?º1,2,3,4 ,ä??å?œå,ªå,? %alphaä?ºæ??æ??ä??æŠ,指æ??,å??å??ä?º0~1ä?‹é??ä??æ„?å??æ??,å??1æ??å…?é?,ä??æŠ,功èƒ?,æœ?å,?å ?ä?º0.8~1.0 %Rä?ºæœ?çŸ-è??å?„,Rlengthä?ºè??å?„é??åº, function [R,Rlength]=geneticTSP(D,n,C,m,alpha) [N,NN]=size(D); farm=zeros(n,N);%ç??äº?å-?å‚?ç? ç?? for i=1:n farm(i,:)=randperm(N);%éš?机ç?Ÿæˆ?åˆ?å?‹ç??ç?, end R=farm(1,:);%å-?å‚?æœ?ä??ç? ç?? len=zeros(n,1);%å-?å‚?è??å?„é??åº, fitness=zeros(n,1);%å-?å‚?å?’ä??åŒ?é?‚åº?å?? counter=0; while counter=alpha*rand nn=nn+1; FARM(nn,:)=farm(i,:); end end FARM=FARM(1:nn,:); [aa,bb]=size(FARM);%äº?å?‰å’Œå??å?‚ while aan FARM=FARM(1:n,:);%ä??æŒ?ç??ç?,è?„æ??ä?ºn end farm=FARM; clear FARM counter=counter+1 end Rlength=myLength(D,R); function [a,b]=intercross(a,b) L=length(a); if L<=10%ç??å?šäº,å?‰å??åº, W=1; elseif ((L/10)-floor(L/10))>=rand&&L>10 W=ceil(L/10); else W=floor(L/10); end p=unidrnd(L-W+1);%éš?机é?‰æ‹?äº,å?‰èŒƒå›?ï?Œä??påˆ?p+W for 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 function [x,y]=exchange(x,y) temp=x; x=y; y=temp; % è??ç??è??å?„çš„å-?ç?‹åº? function len=myLength(D,p) [N,NN]=size(D); len=D(p(1,N),p(1,1)); for i=1:(N-1) len=len+D(p(1,i),p(1,i+1)); end %è??ç??å?’ä??åŒ?é?‚åº?å??å-?ç?‹åº? 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))).^m; end