Exploration of fast convergence of Genetic Algorithms

weasels.m

%% Exploration of fast convergence of Genetic Algorithms
% This matlab script contains the code for the results presented in the
% above paper.
%%
function weasels()
   % Test main hypothesis, if crossover speeds up convergence
   experiment1()
   % Effect of smaller population
   experiment2()
   % Effect of range of mutation over range of crossover probabilities
   experiment3()
end

% Test main hypothesis, if crossover speeds up convergence
function experiment1()
   clear;
   startTime = cputime;

   popSize = 3000;
   maxGenCount= 1000;
   pMutation = 1.0/28;
   pCrossoverRange = 0:0.2:1.0;

   XO_Range = length(pCrossoverRange);
   AvgConvergenceGenCounts = zeros(1,XO_Range);
   fprintf(['------------------------\n', ...
            'GA Parameters used\n', ...
            '\tPopulationSize = %d\n', ...
            '\tMaxGenerationCount = %d\n', ...
            '\tpMutation = %0.3f\n\n'], ...
            popSize, maxGenCount, pMutation);

   for k = 1:XO_Range
      pCrossover = pCrossoverRange(k);
      avgGenCount = MicrobialGA(popSize,maxGenCount, ...
                                             pMutation,pCrossover);

      fprintf(['Avg generations for convergence = %d', ...
              ' pCrossover = %0.3f\n'], ...
               avgGenCount, pCrossover);
      AvgConvergenceGenCounts(k) = avgGenCount;
   end
   figure(1);
   title('Speed of Convergence vs pCrossover');
   plot(pCrossoverRange,AvgConvergenceGenCounts,'LineWidth',2);
   grid on;

   xlabel('Crossover');ylabel('Generations');
   fprintf('Execution time = %4.0f sec\n', cputime - startTime);

end

% Effect of smaller population
function experiment2()
   clear;
   startTime = cputime;

   popSizeRange = [100,300,1000,2000,3000];
   maxGenCount= 1000;
   pMutation = 1.0/28;
   pCrossover = 0.6;
   AvgConvergenceGenCounts = zeros(1,length(popSizeRange));

   
   for k = 1:length(popSizeRange)
      popSize = popSizeRange(k);
      AvgConvergenceGenCounts(k) = MicrobialGA(popSize,maxGenCount, ...
                                                      pMutation,pCrossover);
      fprintf(['Avg generations for convergence = %d', ...
              ' population = %3d\n'], ...
               AvgConvergenceGenCounts(k), popSize);
   end
   figure(2);
   title('Speed of Convergence vs Population Size');
   plot(popSizeRange,AvgConvergenceGenCounts,'LineWidth',2);
   grid on;

   xlabel('Populations Size');ylabel('Generations');
   fprintf('Execution time = %4.0f sec\n', cputime - startTime);
end
   
% Effect of range of mutation over range of crossover probabilities
function experiment3()
   clear;
   startTime = cputime;

   popSize = 3000;
   maxGenCount= 5000;
   pMutationRange = 0.0:0.005:0.05;
   pCrossoverRange = 0:0.2:1.0;

   AvgConvergenceGenCounts = zeros(length(pCrossoverRange),length(pMutationRange));
   fprintf(['------------------------\n', ...
            'GA Parameters used\n', ...
            '\tPopulationSize = %d\n', ...
            '\tMaxGenerationCount = %d\n', ...
            '\n'], ...
            popSize, maxGenCount);

   for mu = 1:length(pMutationRange)
      for xo = 1:length(pCrossoverRange)
         pCrossover = pCrossoverRange(xo);
         pMutation = pMutationRange(mu);
         AvgConvergenceGenCounts(xo,mu) = MicrobialGA(popSize, ...
                                        maxGenCount,pMutation,pCrossover);

         fprintf(['Avg generations for convergence = %d', ...
                 ' pCrossover = %0.3f pMutation = %0.3f\n'], ...
                  AvgConvergenceGenCounts(xo,mu), pCrossover, pMutation);
      end
   end
   
   figure(3);
   title('Speed of Convergence vs pCrossover vs pMutation');
   plot(pCrossoverRange,AvgConvergenceGenCounts,'LineWidth',2);
   xs = arrayfun(@num2str,pMutationRange,'UniformOutput',false);
   legend(xs,'Location','NorthEastOutside');
   grid on;

   xlabel('Crossover');ylabel('Generations');
   fprintf('Execution time = %4.0f sec\n', cputime - startTime);
 
end

% Microbial Genetic Algorithm
function gc = MicrobialGA(popSize,maxGenCount,pMutation,pCrossover)
% GA Parameters
GeneCount = 28;
PopulationSize = popSize;
GenerationCount= maxGenCount;
RepeatCount = 10;

% Objective is to evolve a random string to 
% the target 'methinks it is like a weasel'
T = repmat('methinks it is like a weasel',PopulationSize,1);

TotalGenCountForConvergence = 0;
%pre-allocate for performance
BestFitnessAtEachGen = zeros(RepeatCount,GenerationCount);
fprintf('Starting Experiment with pCrossover = %0.4f\n',pCrossover);
for r = 1:RepeatCount
   % Initialize population      
   Population = char(floor(94*rand(PopulationSize, GeneCount) + 32));
   OverallMaxFitness = intmin;

   % Evolve for GenerationCount number of generations or until
   % Target is reached   
   for n = 1:GenerationCount
      [Fitness,TargetFitness] = ComputeFitness(Population,T);

      % Keep stats
      [mf,] = max(Fitness); % Max fitness of this generation
      BestFitnessAtEachGen(r,n) = mf;
      if OverallMaxFitness < mf
         OverallMaxFitness = mf;
         %BestFitSoFar = Population(ii,:);
      end
      %fprintf('Generation = %d\t%d\t%s\n', n,mf,BestFitSoFar);

      % Check for early convergence
      if (OverallMaxFitness == TargetFitness)
         break
      end

      % Here we shuffle the indices and compare fitness of even and odd 
      % chromosomes. 
      idx = randperm(PopulationSize);
      for kk = 1:PopulationSize/2
         % Select Players
         I1 = idx(2 * kk - 1);
         I2 = idx(2 * kk);
         P1 = Population(I1,:);
         P2 = Population(I2,:);

         % Create offspring inplace
         if(Fitness(I1) > Fitness(I2))
            Population(I2,:) = XOMutate(P1,P2,GeneCount, ...
                                               pMutation,pCrossover);
         else
            Population(I1,:) = XOMutate(P2,P1,GeneCount, ...
                                               pMutation,pCrossover);
         end
      end%kk
   end%n generations
   TotalGenCountForConvergence = TotalGenCountForConvergence + n;
end% repeat
% return avg gen count for convergence
gc =int32(TotalGenCountForConvergence / RepeatCount);
end

% Crossover and Mutation operators
function g = XOMutate(winner, loser, geneCount, pMutation, pCrossover)
   g = loser; %ordinarily output is loser genes
   % Perform one-point crossover
   if rand < pCrossover
      %generate crossover site
      cs = floor(rand(1) * geneCount + 1);
      g(cs:end) = winner(cs:end);
   end

   %mutate
   for i = 1:geneCount
      if rand < pMutation
         if rand > 0.5
            adjustment = 1;
         else
            adjustment = -1;
         end

         k = g(i) + adjustment;
         %check for bounds overflow
         if k < 32
            g(i) = k + 1;
         elseif k > 126
            g(i) = k - 1;
         else
            g(i) = k;
         end
      end %if
   end%for
end

% Fitness computation
function [fitness,targetFitness] = ComputeFitness(Population,targetString)
% Fitness is the sum of abs distances of characters
% to the target string
e1 = sum(abs(Population - char(targetString)),2);
targetFitness = 0;
fitness = targetFitness - e1;
end

function PlotFitnessDistribution(colorVec,k,n,r,Fitness)
   figure(20+k);
   ff =Fitness;
   hold on;
   if (mod(n,50) == 0) && (r==1)
      colormap(colorVec);
      h = histfit(ff,100,'kernel');
      delete(h(1));
      set(h(2),'color',colorVec(n,:));
      hhh = colorbar;
      hhh.Label.String = 'Generations';
      caxis([1 GenerationCount]);
      title(sprintf('Fitness Distribution @ pCrossover = %0.3f', ...
                                                            pCrossover));
      xlabel('Fitness');ylabel('Freq');
      pause(0.1);
   end
   hold off;
end