Week 4 - Genetic Algorithm

Genetic Algorithm

Aim

Write a code in MATLAB to optimise the stalagmite function and find the global maxima of the function.

Introduction

Genetic Algorithm (GA) is a search-based optimization technique based on the principles of Genetics and Natural Selection, in line with the Darwinian Theory of “Survival of the Fittest”. It is frequently used to find optimal or near-optimal solutions to difficult problems.

Optimization is the process of making something better. Optimization refers to finding the values of inputs in such a way that we get the “best” output values. The definition of “best” varies from problem to problem, but in mathematical terms, it refers to maximizing or minimizing one or more objective functions, by varying the input parameters.

Five phases are considered in a genetic algorithm.

1. Initial population
2. Fitness function
3. Selection
4. Crossover
5. Mutation

The process begins with a set of individuals which is called a Population. Each individual is a solution to the problem you want to solve. An individual is characterized by a set of parameters (variables) known as Genes. Genes are joined into a string to form a Chromosome (solution).

For example if an individual A = 1 0 1 1 0

Each 1 or 0 are a gene, but the string of 1 0 1 1 0 together is a chromosome. And a group of individuals is called a population.

The fitness function determines how fit an individual is (the ability of an individual to compete with other individuals). It gives a fitness score to each individual. The probability that an individual will be selected for reproduction is based on its fitness score.

Two pairs of individuals (parents) are selected based on their fitness scores. Crossover is for each pair of parents to be mated, a crossover point is chosen at random from within the genes. Offspring are created by exchanging the genes of parents among themselves until the crossover point is reached.

Example

A1 = 0 0 0 0 0 0

A2 = 1 1 1 1 1 1

if cross over point is 2 then their children will be

A3 = 1 1 0 0 0 0

A4 = 0 0 1 1 1 1

In certain new offspring formed, some of their genes can be subjected to a mutation with a low random probability. This implies that some of the genes in their chromosome can be flipped. Finally, the new children are recombined amongst themselves creating a new population.

The algorithm terminates if the population has converged (does not produce offspring which are significantly different from the previous generation). Then it is said that the genetic algorithm has provided a set of solutions to our problem.

Syntax of ga in MATLAB

x = ga(fun,nvars)
x = ga(fun,nvars,A,b)
x = ga(fun,nvars,A,b,Aeq,beq)
x = ga(fun,nvars,A,b,Aeq,beq,lb,ub)
x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon)
x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,options)
x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon)
x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon,options)
x = ga(problem)
[x,fval] = ga(___)
[x,fval,exitflag,output] = ga(___)
[x,fval,exitflag,output,population,scores] = ga(___)

'x' is the variable to store the output of the Genetic Algorithm.

'fun' is the function handle to call the function.

'A' and 'b' are used to represent the linear inequalities of the the function.

'Aeq' and 'beq' represent the equality constraints.

'lb' and 'ub' are used to specify the upper and the lower bounds of the variables of the function.

'nonlcon' is a function that is specified using a function handle. A separate function code must be written as per the constraints of the function. The function nonlcon accepts x and returns vectors C and Ceq, representing the nonlinear inequalities and equalities constraints respectively.

'IntCon' is used to specify the Integer Constraint. Variables listed in IntCon take integer values.

'options' is used to replace the values of the default optimization parameters

Stalagmite function to be optimised (maximisation)

`f1 = (sin(5.1*pi*x+0.5))^6`

`f2 = (sin(5.1*pi*y+0.5))^6`

`f3 = exp((-4*log(2)*(x-0.0667)^2)/(0.64))`

`f4 = exp((-4*log(2)*(y-0.0667)^2)/(0.64))`

`f = (f1*f2*f3*f4)`

The minimum value of '-f(x)' is the maximum value of 'f(x)'. So

`f = -(f1*f2*f3*f4)`

Code

i) Stalagmite function

function [F] = stalagmite(input_vector)
         x=input_vector(1) ;
         y=input_vector(2) ;
         
         f1_x = (sin(5.1*pi*x+0.5)).^6;
         f1_y = (sin(5.1*pi*y+0.5)).^6;
         f2_x = exp(-4*log(2)*((x-0.0667).^2)/0.64);
         f2_y = exp(-4*log(2)*((y-0.0667).^2)/0.64);
         [F] = -(f1_x.*f1_y.*f2_x.*f2_y);
end

The minimum value of '-f(x)' is the maximum value of 'f(x)'.

ii) Code - Unbounded

clear all
close all
clc

%Defining search space
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);

%Creating 2D Mesh
[xx yy] = meshgrid(x,y);

%Evaluating stalagmite function

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

    
%Study of statistical behaviour of genetic algorithm

num_cases =  50;    
tic 

for i =1: num_cases
    [inputs,fopt(i)] = ga(@stalagmite,2)
    xopt(i)=inputs(1);
    yopt(i)=inputs(2);
end
    
time_study = toc

%Plotting
figure(1)
subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','g')
subplot(2,1,2)
plot(fopt)
xlabel('iterations')
ylabel('gloabal values')

iii) Code - Bounded

clear all
close all
clc

%Defining search space
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);

%Creating 2D Mesh
[xx yy] = meshgrid(x,y);

%Evaluating stalagmite function

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

    
%Study of statistical behaviour of genetic algorithm with upper and lower bounds

num_cases =  50;    
tic 

for i =1: num_cases
    [inputs,fopt(i)] =ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
    xopt(i)=inputs(1);
    yopt(i)=inputs(2);
end
    
time_study = toc

%Plotting   
figure(1)
subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','g')
subplot(2,1,2)
plot(fopt)
xlabel('iterations')
ylabel('gloabal values')

iv) Code - Bounded and population increased

clear all
close all
clc

%Defining search space
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);

%Creating 2D Mesh
[xx yy] = meshgrid(x,y);

%Evaluating stalagmite function
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

num_cases =  50;

%Study of statistical behaviour of genetic algorithm with increasing 
%the population

options = optimoptions('ga');
options = optimoptions(options,'populationsize',235);
    
    tic 
for i =1:num_cases
    [inputs,fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
    xopt(i)=inputs(1);
    yopt(i)=inputs(2);
end
    
    time_study = toc
    
%Plotting
figure(1)
subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','g')
subplot(2,1,2)
plot(fopt)
xlabel('Iterations')
ylabel('Gloabal values')

Step by step explanation

First clearing workspace, command window & closing all plots using clear all, close all, clc commands. A search space is defined by using linspace command. Then we calculated a 2 Dimentionl mesh using meshgrid command. For evaluating the stalagmite function for each value of x & y for-loop was used. GA command was used for optimization (maximisation of the function) and then plotting the optimum values of x and y to find the global values of the function. Using GA command with bounded inputs we get optimum value more converged, but after using an increased initial population with bounded inputs we get optimum value more precisely.

Result

i) Unbounded

As the genetic optimization is unbounded the data points can be random and wide answers were got.

ii) Bounded

After giving an upper and lower bound the global values become more converged.

iii) Bounded and population increased

As the initial population also got increased with an upper and lower bound the global values become more converged to the actual optimised value.

iv) Bounded and population increased even more for precise answer (population = 500)

If the population is increased tremendeously the answer become more precise and converged.

Errors occured

I didn't have Matlab Global Optimization Toolbox addon installed, so I was unable to perform 'ga' command. After installing the addon the program ran and gave the output.

Reference

https://in.mathworks.com/help/gads/ga.html

https://towardsdatascience.com/introduction-to-genetic-algorithms-including-example-code-e396e98d8bf3

https://www.tutorialspoint.com/genetic_algorithms/genetic_algorithms_introduction.htm