parents.m

一些用matlab编写的经典遗传算法算例。可以用于解决许多优化问题

function par = parents(pop,method,varargin)
% PARENTS - Selects parents from a given population.
%
% par=parents(population,'method',option1,option2,etc..)
% There are several different methods that parents can be selected
% from a population. Given the population, method and options the
% function will return an even number of parents in an Nx2 matrix.
% If the population is an odd number X then N=(X-1)/2
%
% [parent1_XX parent1_XY
%  parent2_XX parent2_XY
%     .          . 
%     .          .
%  parentN_XX parentN_XY];
% 
% The following methods and options are supported
%
% 'rand'   - random selection
%   options:
%   'elim'  - prevent a member from being selected twice (default)
%   'keep'  - keep the member in the parent pool
%
% 'lin'    - linear fitness 
%   options:
%   'elim'  - prevent a member from being selected twice (default)
%   'keep'  - keep the member in the parent pool
%
% 'quad'   - quadratic fitness
%   options:
%   'elim'  - prevent a member from being selected twice (default)
%   'keep'  - keep the member in the parent pool
%
% 'best'   - best members allways selected NOT IMPLEMENTED YET
%   options:
%   top    - use this number of best members (default 4)
%   'rand' - select from remaining parent pool using 'rand' (default)
%   'lin'  - select from remaining parent pool using 'lin'
%   'quad' - select from remaining parent pool using 'quad'
%
% The number of desired parents can also be
% selected this argument when specified should be the last in the
% function call, if omitted the entire population will be paired.
%
% Examples:
%
% par=parents(pop,'quad') pair up the population with quadratic fitness.
%
% par=parents(pop,'lin',6) create 6 parents i.e. 3 pairs using
% linear fitness and preventing a member from being selected twice.
%
% par=parents(pop,'best',4,'rand,'keep') will give parents where
% the top 4 best members are randomly matched with the rest of the
% members in the poplation.  
%
% par=parents(pop,'best','rand',6) same as above, 3 pairs will be
% selected from the top 4 best members, in this case however the top 3
% best member will be randomly paired with a member from the rest of
% the parent pool, again preventing any member from being selected
% twice.
%
% See also CHILDREN,MUTATE

%------------------------------------------------------------
pop=tagem(pop);
%------------------------------------------------------------
if strcmp(method,'best')
  nmbr_par=0;
  bmethod=find_boption(pop,varargin);
  for k=1:length(varargin)
    if isa(varargin{k},'double')
      nmbr_par=varargin{k};
      repeat=length(pop)/(2*nmbr_par);
      break
    end
  end
  if ~nmbr_par
    nmbr_par=1;				% this should be default
    repeat=length(pop)/2;                % not good though
  end
else
  nmbr_par=number_of_par(pop,varargin);
  repeat=length(pop)/nmbr_par;
end
opt=find_option(pop,varargin);

cp=[];
if mod(length(pop),nmbr_par)
  error('Bad number of parents')
end

for l=1:repeat
  
  switch method				

   case 'rand'				
    par=pair_pop(pop,method,opt,nmbr_par);
   case 'lin'
    par=pair_pop(pop,method,opt,nmbr_par);
   case 'quad'
    par=pair_pop(pop,method,opt,nmbr_par);
   
   case 'best'
    
    pop=fliplr(sort(pop));
    bpar=pop(1:nmbr_par);
    
    for k=1:nmbr_par
      pop=del_chrom(pop,bpar(k));
    end
    
    for k=1:nmbr_par;
      w=make_wheel(pop,bmethod);
      tmp(k)=spin_wheel(pop,w);
      if strcmp(opt,'elim')
	pop=del_chrom(pop,tmp(k));
      elseif strcmp(opt,'keep')
	pop=pop;
      else
	error('wrong option')
      end
    end
    par(:,1)=bpar;
    par(:,2)=tmp;
   
   otherwise
    error('wrong method')
  end
  cp=[cp
      par];

end
par=cp;

%==============END MAIN=============================================

function par = pair_pop(pop,method,opt,nmbr_par)
% PAIR_POP - 
%   
for k=1:nmbr_par;
  w=make_wheel(pop,method);
  tmp(k)=spin_wheel(pop,w);
  if strcmp(opt,'elim')
    pop=del_chrom(pop,tmp(k));
  elseif strcmp(opt,'keep')
    pop=pop;
  else
    error('wrong option')
  end
end
par(1:nmbr_par/2,1)=tmp(1:2:end-1); 
par(1:nmbr_par/2,2)=tmp(2:2:end);
%=============END PAIR_POP===============================================

function w = make_wheel(c,method)
% MAKE_WHEEL - This function makes the roulette wheel. 
%   
switch method
 case 'rand'
  n=length(c);
  w=linspace(0,1,n+1);
  w=w(2:end);
 case 'lin'
  pol=rand(1,2);
  for k=1:length(c)
    fit(k)=polyval(pol,get(c(k),'fitness'));
  end
  for k=1:length(c)
    w(k)=sum(fit(1:k))/sum(fit);
  end
 case  'quad'
  pol=rand(1,3);
  for k=1:length(c)
    fit(k)=polyval(pol,get(c(k),'fitness'));
  end
  for k=1:length(c)
    w(k)=sum(fit(1:k))/sum(fit);
  end
end
%================END MAKE_WHEEL==============================

function winner = spin_wheel(pop,w)
% SPIN_WHEEL - This function spins the roulette wheel and returns
% the winner.
win=rand;
for k=1:length(w)
  if win<=w(k)
    winner=pop(k);
    break
  end
end
%===============END SPIN_WHEEL===============================

function pop = del_chrom(pop,dchrom)
% DEL_CHROM - Deletes a chromosome from a vector of
% chromosomes.

id=get(dchrom,'id');
ind=find_id(pop,id);

if ~ind
  pop=pop;
  return
end

n=length(pop);

if and(ind==1,n==1)
  pop=chrom;
elseif ind==1
  pop=pop(2:end);
  return;
elseif ind==n;
  pop=pop(1:end-1);
  return;
else
  pop=[pop(1:ind-1) pop(ind+1:end)];
end
%===============END DEL_CHROM================================


function ind=find_id(chr,id)
ind=0;
for k=1:length(chr)
  if strcmp(get(chr(k),'id'),deblank(id));
    ind=k;
    break
  end
end
  
function nmbr=number_of_par(pop,options);
n=length(pop);
if mod(n,2)
  error('There must be an even number of members in the population')
end

if ~length(options)
  nmbr=n/2;
  break
else
  for k=1:length(options)
    if isa(options{k},'double')
      tst_nmbr=options{k};
      if tst_nmbr>n | mod(tst_nmbr,2)
	error('Wrong number of parents, read the help')
      else
	nmbr=tst_nmbr;
	break
      end
    else
      nmbr=n/2;
    end
  end
end
   

function opt=find_option(pop,options)
if isempty(options)
  opt='elim';
  break;
end
for k=1:length(options)
  if isa(options{k},'char')
    if strcmp(options{k},'elim')|strcmp(options{k},'keep')
      opt=options{k};
      break
    else
      opt='elim';
    end
  else
    opt='elim';
  end
end


function opt=find_boption(pop,options)
if isempty(options)
  opt='rand';
  break;
end
opt='';
for k=1:length(options)
  if isa(options{k},'char')
    if ~strcmp(options{k},'elim')|strcmp(options{k},'keep')
      switch options{k}
       case 'lin'
	opt='lin';
	break
       case 'quad'
	opt='quad';
	break;
       case 'rand'
	opt='rand';
	break;
       otherwise
	error('wrong option')
      end
    end
  end
end
if isempty(opt)
  opt='rand';
end