tsp.m

matlab的遗传算法的一个工具箱

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
NIND=100;		% Number of individuals
MAXGEN=100;		% Maximum no. of generations
NVAR=15;		% No. of variables
PRECI=1;		% Precision of variables
ELITIST=0.1;    % percentage of the elite population
GGAP=1-ELITIST;		% Generation gap
STOP_PERCENTAGE=.80;    % percentage of equal fitness individuals for stopping


% 1 -- to use the input file specified by the filename
% 0 -- click the cities yourself, which will be saved in the file called
% filename
USE_FILE=1;
FILENAME='data/cities.xy';



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



if (USE_FILE==0)

    % get the input cities
    figure(1);clf;
    axis([0 1 0 1]);
    title(NVAR);
    hold on;
    x=zeros(NVAR,1);y=zeros(NVAR,1);
    for v=1:NVAR
        [xi,yi]=ginput(1);
        x(v)=xi;
        y(v)=yi;
        plot(xi,yi, 'ko','MarkerFaceColor','Black');
        title(NVAR-v);
    end
    hold off;
    
    dlmwrite(FILENAME,[x y],'\t');

else
    XY=dlmread(FILENAME,'\t');
    x=XY(:,1);
    y=XY(:,2);
end



% calculate distance matrix between each pair of cities
Dist=zeros(NVAR,NVAR);
for i=1:size(x,1)
	for j=1:size(y,1)
		Dist(i,j)=sqrt((x(i)-x(j))^2+(y(i)-y(j))^2);
	end
end


		
% initialize population
Chrom=zeros(NIND,NVAR);
for row=1:NIND
	Chrom(row,:)=path2adj(randperm(NVAR));
end

gen=0;

% number of individuals of equal fitness needed to stop
stopN=ceil(STOP_PERCENTAGE*NIND);


% evaluate initial population
ObjV = tspfun(Chrom,Dist);

best=zeros(1,MAXGEN);

% generational loop

while gen<MAXGEN
    
    %%% stop if the amount of equal fitness indiv. is reached
    sObjV=sort(ObjV);
    if (sObjV(stopN)==sObjV(1))
        break;
    end
    %%%
    
	best(gen+1)=min(ObjV);
	minimum=best(gen+1);

	for t=1:size(ObjV,1)
		if (ObjV(t)==minimum)
			break;
		end
	end
	
	visualizeTSP(x,y,adj2path(Chrom(t,:)), minimum, 2);
		
	figure(1);
	semilogy([0:gen],best(1:gen+1),'ro');
	
	figure(3);
	plot(sort(ObjV),'kx-');
	drawnow;

	%assign fitness values to entire population
	FitnV=ranking(ObjV);
	
	%select individuals for breeding
	SelCh=select('sus', Chrom, FitnV, GGAP);
	
	%recombine individuals (crossover)
	SelCh=recombin('xalt_edges',SelCh,0.9);
	
	%apply mutation
	SelCh=mutateTSP('reciprocal_exchange',SelCh,0.1);
	
	%evaluate offspring, call objective function
	ObjVSel = tspfun(SelCh,Dist);
	
	%reinsert offspring into population
	[Chrom ObjV]=reins(Chrom,SelCh,1,1,ObjV,ObjVSel);
	
	%increment generation counter
	gen=gen+1;
end


figure(3);
plot(sort(ObjV),'kx-');