Genetic algorithm using Octave to find solution to Stalagmite function

Introduction

Genetic algorithm is based on Evolutionary biology propagated by Charles Darwin. This is widely used to find optimal solutions to most complex problems which may take lifetime to solve. This algorithm is particularly inspired by the evolution process in nature. The logic is that neither the strongest or the intellectual survive, but the one capable of adapting to the environment survives and propagates the generation.

However, there are two other not so famous GA search theories. They are Lamrckian model and Baldwinian model. In this blog, however we are sticking to charles darwin's evolutionary lifetime adaption model. There are couple of terms and similarities between natural and computational process.

Population size is the subset of the feasible solution which in real world is synonymous with group of individuals competing for survival. Chromosome is single solution from the population set. each chromosome could be assumed to be array of strings and each character is referred to as the Genes. The value that each gene carries is called as Allele.

From the diverse set of parents or in computation worls terms, initial subset of soultion, only those solution which can produce relatively better results to the objective function survives and gets carried to the next generation. In next generation a Child chromosome could be altered by means of crossover rate by gaining the better qualities from two parents and carrying it forward. To introduce the diversity in the evolution of solution, mutation could be brought in. This results in random change in the gene of the child object. However, Mutation probability should be kept relatively low as higher value leads to random search.

This evolution can continue forever, hence the termination criteria is brought in. This is achieved by means of Number of generations, Number of iteration and saturation of solution. When the optimal solution doesnt change over the number of iteration or when maximum generations is reached, Search is terminated.

This particular instance can take a lot of time and hence GA designer needs to design the Number of iterations, Population size, Mutation rate, Crossover rate, Number of generations, Constrained search space according to problem as lowering the bar just results in leading to one simple solution which could be true or false and higher values leads to prolonged time in completing the search.

In Octave, genetic algorithm is already coded with inbuilt packages, however, the variables as to be altered to find the right solution.

Syntax of GA in Octave:

[x,fopt] = ga(@f,nvariables,a,b,aeq,beq,lb,ub,nclon,options)

where Outputs: x stands for the local input value at which the value has been returned

fopt = optimal value found with 'x' to the fitness function

@f stands for the fitness function which is an objective function in most number of cases

nvariables stands for number of variables varied in the objective function

a,b,aeq,beq stands for set of linear and non linear constraints

lb stands for lower bound for finding solution and ub stands for upper bound to find solution

options are used to change the settings of the genetic algorithm such as Population size.

Stalagmite function:

This is the reference fitness function used to test the genetic algorithm. This is particularly inspired by the rock formation in the caves. It generates a set of local maxima points. However, since the GA is coded to find the minimum value an additive inverse of the stalagmite function is taken as the Objective function and the result would again be the additive inverse of the optimal solution which would be the global maximum value.

Octave code:

%This code is developed by Sweekar, contact [email protected]
%Code is an intellectual property of Sweekar, please mail for queries
%Genetic algorithm is based on Evolutionary biology
%Algorithm is based on Charles darwin theory of Natural selection and adaption
%According to theory, neither the strongest and intelligent species survive,but the one quick to adapt
%Crossover rate, Mutation rate, Population size and Number of generations is used as tuning factors
%Genetic algorithm always returns minimum value for the objective function
%Goal of this code is to find the global maximum, hence the negative of objective function is imported
%This code returns global minimum value for negative of objective function

%This code could be further improved by adding the While loop for complex problems to determine
%optimal population size and use the termination criteria when solution is reached

%Cleanup
close all
clear all
clc

x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
[xx yy] = meshgrid(x,y);

for i = 1:length(xx)
  for j = 1:length(yy)
    input_vector(1)=xx(i,j);
    input_vector(2)=yy(i,j);
    f(i,j)=stalagmite(input_vector);
  end
end

%Case studies on Genetic algorithm
num_cases = 50;

%case 1 Default Genetic algorithm unbounded inputs
%tic
%for j=1:num_cases
% [inputs,fopt(j)] = ga(@stalagmite,2);
%  xopt(j)= inputs(1);
%  yopt(j)= inputs(2);
%end
%study1_time = toc

%case 2 Default genetic algorithm bounded inputs
%tic
%for j=1:num_cases
%  [inputs,fopt(j)] = ga(@stalagmite,2,[],[],[],[],[0.05;0.05],[1;1]);
%  xopt(j)= inputs(1);
%  yopt(j)= inputs(2);
%end
%study1_time = toc

%case3 Modified Population size, bounded inputs
%tic
%options = gaoptimset('PopulationSize',170)
%for j=1:num_cases
%  [inputs,fopt(j)] = ga(@stalagmite,2,[],[],[],[],[0.05;0.05],[1;1],[],options);
%  xopt(j)= inputs(1);
%  yopt(j)= inputs(2);
%end
%study1_time = toc

%case4 Modified population size 170, number of generations 150, bounded inputs
%tic
%options = gaoptimset('PopulationSize',170,'Generations',150)
%for j=1:num_cases
%  [inputs,fopt(j)] = ga(@stalagmite,2,[],[],[],[],[0.05;0.05],[1;1],[],options);
%  xopt(j)= inputs(1);
%  yopt(j)= inputs(2);
%end
%study1_time = toc

%case5 Modified population size170, number of generations 250, bounded inputs
%tic
%options = gaoptimset('PopulationSize',170,'Generations',250)
%for j=1:num_cases
%  [inputs,fopt(j)] = ga(@stalagmite,2,[],[],[],[],[0.05;0.05],[1;1],[],options);
%  xopt(j)= inputs(1);
%  yopt(j)= inputs(2);
%end
%study1_time = toc

%case6 Modified population size270, number of generations 250, bounded inputs
%tic
%options = gaoptimset('PopulationSize',270,'Generations',250)
%for j=1:num_cases
%  [inputs,fopt(j)] = ga(@stalagmite,2,[],[],[],[],[0.05;0.05],[1;1],[],options);
%  xopt(j)= inputs(1);
%  yopt(j)= inputs(2);
%end
%study1_time = toc

%case7 Modified population size270, number of generations 500, bounded inputs
tic
options = gaoptimset('PopulationSize',270,'Generations',250)
for j=1:num_cases
  [inputs,fopt(j)] = ga(@stalagmite,2,[],[],[],[],[0.05;0.05],[1;1],[],options);
  xopt(j)= inputs(1);
  yopt(j)= inputs(2);
end
study1_time = toc

%Plotting the results

figure(1)
subplot(2,1,1)
hold on
surfc(xx,yy,f)
xlabel('xaxis')
ylabel('yaxis')
shading interp
plot3(xopt,yopt,fopt)
subplot(2,1,2)
plot(fopt)
title('Optimal value')
xlabel('Number of iterations')
ylabel('Optimal value')

function [F]= stalagmite(input_vector)
x = input_vector(1);
y = input_vector(2);

f1x = (sin((5.1*pi().*x)+0.5)).^6;
f1y = (sin((5.1*pi().*y)+0.5)).^6;
f2x = exp(((-4)*log(2)).*((x-0.0667).^2)./0.64);
f2y = exp(((-4)*log(2)).*((y-0.0667).^2)./0.64);

[F] = -(f1x.*f1y.*f2x.*f2y);

end

Results

Trial 1: Unbounded inputs

Trial 2: Bounded search space

Trial 3: Population size 170

Trial 4: Population Size 170 Number of generations 150

Trial 5: Population size 170 Number of generations 250

Trial 6: Population Size 270 Number of generations 250

Trial 7: Population size 500 Number of generations 250

Discussion on Results

1) As the number of generations are population increases time required for computation increases exponentially. For ex: Unbouded required ~70s, Trial 7 ~ 23hours!!!!!! ( Stupid crazy end of me calibrating GA)

2) After a point, dependency on number of generation saturates

3) Increased population size results in higher diveristy of candidates and higher probablity of reaching solution

4) Number of iterations ensure the repeatability of results as the GA is solely based on random set generation

5) Mutation rate is kept low and crossover rate is kept at 0.8 in all of this simulation

6) No linear or non linear constraints are specified.

7) Termination criteria is solely based on Absolute number of generations and number of iterations specified.

8) For better solution, While loop could be added and population size could be increased however, it would take a lot of time to attain the solution

9) From the final trial, solution at 1, with inputs at 0.06,0.06. But, it takes a lot of time to reach, it is almost 7X the time taken for trial 6.