indextribalga.m

遗传算法解决vrp问题

function [x,endPop,bPop,traceInfo] = indexTribalGA(bounds,evalFN,evalOps,startPop,...
termFN,termOps,selectFN,selectOps,xOverFNs,xOverOps,mutFNs,mutOps)
% GA run a genetic algorithm for rount problems                             
% Output Arguments:
%   x            - the best solution found during the course of the run
%   endPop       - the final population 
%   bPop         - a trace of the best population
%   traceInfo    - a matrix of best and means of the ga for each generation
%
% Input Arguments:
%   evalFN       - the name of the evaluation .m function
%   evalOps      - options to pass to the evaluation function ([NULL])
%   startPop     - a matrix of solutions that can be initialized
%                  from initialize.m
%   termFN       - name of the .m termination function (['maxGenTerm'])
%   termOps      - options string to be passed to the termination function
%                  ([100]).
%   selectFN     - name of the .m selection function (['normGeomSelect'])
%   selectOpts   - options string to be passed to select after
%                  select(pop,#,opts) ([0.08])
%   xOverFNS     - a string containing blank seperated names of Xover.m
%                  files (['arithXover heuristicXover simpleXover']) 
%   xOverOps     - A matrix of options to pass to Xover.m files with the
%                  first column being the number of that xOver to perform
%                  similiarly for mutation ([2 0;2 3;2 0])
%   mutFNs       - a string containing blank seperated names of mutation.m 
%                  files (['boundaryMutation multiNonUnifMutation ...
%                           nonUnifMutation unifMutation'])
%   mutOps       - A matrix of options to pass to Xover.m files with the
%                  first column being the number of that xOver to perform
%                  similiarly for mutation ([4 0 0;6 100 3;4 100 3;4 0 0])

% Binary and Real-Valued Simulation Evolution for Matlab 
% Copyright (C) 1996 C.R. Houck, J.A. Joines, M.G. Kay 
%
% C.R. Houck, J.Joines, and M.Kay. A genetic algorithm for function
% optimization: A Matlab implementation. ACM Transactions on Mathmatical
% Software, Submitted 1996.
%
% This program is modified from ga by zhuhui

%now I don't use the below args
n=nargin;
bPop=[];
traceInfo=[];

%the define of var
xZomeLength  = size(startPop,2); 	%Length of the xzome=numVars+fittness
numVar       = xZomeLength-1; 		%Number of variables
popSize      = size(startPop,1); 	%Number of individuals in the pop
endPop       = zeros(popSize,xZomeLength); %A secondary population matrix
c1           = zeros(1,xZomeLength); 	%An individual
c2           = zeros(1,xZomeLength); 	%An individual
numXOvers    = size(xOverFNs,1); 	%Number of Crossover operators
numMuts      = size(mutFNs,1); 		%Number of Mutation operators
epsilon      =1e-6;
oval         = max(startPop(:,xZomeLength)); %Best value in start pop
bFoundIn     = 1; 			%Number of times best has changed
done         = 0;                       %Done with simulated evolution
gen          = 1; 			%Current Generation Number
collectTrace = (nargout>3); 		%Should we collect info every gen


while(~done)
	
	[bval,bindx] = max(startPop(:,xZomeLength)); %Best of current pop
	best =  startPop(bindx,:);
    
    %view the pop
    %printPop(gen,startPop);
    
    if collectTrace
        traceInfo(gen,1)=gen; 		          %current generation
        traceInfo(gen,2)=startPop(bindx,xZomeLength);       %Best fittness
        traceInfo(gen,3)=mean(startPop(:,xZomeLength));     %Avg fittness
        traceInfo(gen,4)=std(startPop(:,xZomeLength)); 
    end
	
	if ( (abs(bval - oval)>epsilon) | (gen==1)) %If we have a new best sol
	    bPop(bFoundIn,:)=[gen startPop(bindx,:)]; %Update bPop Matrix
	    bFoundIn=bFoundIn+1;                      %Update number of changes
	    oval=bval;                                %Update the best val
	end
    
	%endPop = feval(selectFN,startPop,[gen selectOps]); %Select
    endPop=startPop;
    
    %x='after select'
    %printPop(gen,endPop);
    %keyboard;
    
    for i=1:numXOvers,
        for j=1:xOverOps(i,1),
	        a = round(rand*(popSize-1)+1); 	%Pick a parent
	        b = round(rand*(popSize-1)+1); 	%Pick another parent
	        xN=deblank(xOverFNs(i,:)); 	%Get the name of crossover function
	        [c1 c2] = feval(xN,endPop(a,:),endPop(b,:),bounds,[xOverOps(i,:)]);
	
	        if c1(1:numVar)==endPop(a,(1:numVar)) %Make sure we created a new 
	            c1(xZomeLength)=endPop(a,xZomeLength); %solution before evaluating
	        elseif c1(1:numVar)==endPop(b,(1:numVar))
	            c1(xZomeLength)=endPop(b,xZomeLength);
    	    else 
	            [c1 c1(xZomeLength)] = feval(evalFN,c1,evalOps);	           
    	    end
        
	        if c2(1:numVar)==endPop(a,(1:numVar))
	            c2(xZomeLength)=endPop(a,xZomeLength);
    	    elseif c2(1:numVar)==endPop(b,(1:numVar))
	            c2(xZomeLength)=endPop(b,xZomeLength);
            else 
	            [c2 c2(xZomeLength)] = feval(evalFN,c2,evalOps);	           
    	    end      
	
	        endPop(a,:)=c1;
    	    endPop(b,:)=c2;
        end
    end
  
	for i=1:numMuts,
	    for j=1:mutOps(i,1), %the times of update
	        a = round(rand*(popSize-1)+1);
	        c1 = feval(deblank(mutFNs(i,:)),endPop(a,:),bounds,mutOps(i,2));
	        if c1(1:numVar)==endPop(a,(1:numVar)) 
	            c1(xZomeLength)=endPop(a,xZomeLength);
	        else
	            [c1 c1(xZomeLength)] = feval(evalFN,c1,evalOps);	            
	        end
	        endPop(a,:)=c1;
        end
	end  
  
	gen=gen+1;
    
    if gen>termOps
        done=1;
    end
    
    % this is the only one different from indexGA
    %no need to evolve
    if  std(startPop(:,xZomeLength)) < 0.0001
        done=1;
    end
	
	startPop=endPop; 			%Swap the populations
	
	[bval,bindx] = min(startPop(:,xZomeLength)); %Keep the best solution
	startPop(bindx,:) = best; 		%replace it with the worst
end

[bval,bindx] = max(startPop(:,xZomeLength));

x=startPop(bindx,:);

if collectTrace
  traceInfo(gen,1)=gen; 		%current generation
  traceInfo(gen,2)=startPop(bindx,xZomeLength); %Best fittness
  traceInfo(gen,3)=mean(startPop(:,xZomeLength)); %Avg fittness
end