Exploration of fast convergence of Genetic Algorithms
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
%% 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