Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Exploration of fast convergence of Genetic Algorithms
%% 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment