Week 4.1 - Genetic Algorithm

% Matlab program to solve the Genetic Algorithm 

clear all
close all
clc

% Providing the search space for the function
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
[xx,yy] = meshgrid(x,y);

iterations = 50 %the number of iterations for which the function will evaluate the fitness
% Creating the surface plot for 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); %value of the function in given search space
    end
end
surfc(xx,yy,-f) %generating the surface 
xlabel('x values')
ylabel('y values')
shading interp %to remove the grid lines on the plot that are produced by the meshgrid
[x,fval] = ga(@stalagmite,2)

% Statistical behaviour(Unbounded)

tic                 %calculating the study time through tic and toc commands
for i = 1:iterations
    [inputs,fopt(i)] = ga(@stalagmite,2); %calculating the optimized value of the function
    xopt(i) = inputs(1); %at each iteration
    yopt(i) = inputs(2);
end 
study1_time = toc  %displaying the time taken to evaluate
figure(1)
subplot(2,1,1)
surfc(xx,yy,-f);
hold on
shading interp
plot3(xopt,yopt,-fopt,'marker','o','MarkerSize',5,'MarkerFaceColor','r');
xlabel('x value');
ylabel('y value');
grid on
subplot(2,1,2)
plot(-fopt)
xlabel('iterations')
ylabel('function max value')
title('Unbounded inputs')


% Statistical Behaviour(Bounded)

tic      %calculating the study time through tic and toc commands
for j = 1:iterations
    [inputs,fopt(j)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]); %calculating the optiomized value of the function 
    xopt(i) = inputs(1); %at each iteration
    yopt(i) = inputs(2);
end

study2_time = toc
% Plotting
figure(2)
subplot(2,1,1)
hold on
surf(xx,yy,-f)
shading interp
plot3(xopt,yopt,-fopt,'marker','o','MarkerSize',5,'MarkerFaceColor','r');
xlabel('x');
ylabel('y');
grid on
subplot(2,1,2)
plot(-fopt)
xlabel('iterations')
ylabel('function max value')
title('Bounded inputs')


% Statistical study with increase in size of population

options = optimoptions('ga','PopulationSize',300)

tic      %calculating the study time through tic and toc commands
for k = 1:iterations
    [inputs,fopt(k)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options); 
    xopt(k) = inputs(1); %at each iteration
    yopt(k) = inputs(2);
end

study3_time = toc
% Plotting
figure(3)
subplot(2,1,1)
hold on
surf(xx,yy,-f)
shading interp
plot3(xopt,yopt,-fopt,'marker','o','MarkerSize',5,'MarkerFaceColor','r');
xlabel('x');
ylabel('y');
grid on
subplot(2,1,2)
plot(-fopt)
xlabel('iterations')
ylabel('function max value')
title('Bounded inputs with modified population size')

>> GENETIC ALGORITHM:

A Genetic Algorithm is a search experiential that is simulated by Charles Darwin's theory of natural evolution.
This algorithm reproduces the peocess of natural selection where the appropriate individuals are selected for reproduction in order to produce offspring of the next generation
The genetic algorithm is a technique for solving both constrained and unconstrained optimization problems that are based on natural selection, the process that drives biological evolution.
The genetic algorithm constantly modifies the population size of individual solutions.

** Phases in Genetic Algorithm:

1. Initialization of Population (Coding)
The code generates its random population of defined size and from that population the code evaluates the fitness of the members of the population according to which it forms new population based on number of iterations performed.

2. Fitness Function
It is that function which we have to optimize and its optimization is done with the help of number of generations which have been formed by the code accordance with the fitness value of each member generated these fitness values are used for the reproduction of the children.

3. Selection
The idea of the selection phase is to select the fittest individuals and let them pass their genes to the next generation. The main goal of this phase is to find the region where the chances of getting the best solution are more.
Inspiration for this is from the survival of the fittest. It should be a balance between exploration and exploitation of search space. GA tries to move the genotype to higher fitness in the search space. Too strong fitness selection bias can lead to sub-optimal solutions. Too little fitness bias selection results in unfocused search.

4. Reproduction
Generation of offspring happen in 2 ways:
- Crossover
- Mutation

a) Crossover
Crossover is the most significant stage in the genetic algorithm. During crossover, a random point is selected while mating a pair of parents to generate offspring.
There are 3 major types of crossover.
Single Point Crossover : A point on both parents’ chromosomes is picked randomly, and designated a ‘crossover point’.
Two-Point Crossover : Two crossover points are picked randomly from the parent chromosomes.
Uniform Crossover : In a uniform crossover, typically, each bit is chosen from either parent with equal probability. The new offspring are added to the population.

b) Mutation
In a few new offspring formed, some of their genes can be subjected to a mutation with a low random probability.
This indicates that some of the bits in the bit chromosome can be flipped. Mutation happens to take care of diversity among the population and stop premature convergence.

** Syntax for Genetic Algorithm:

** Syntax for Genetic Algorithm:
[x,fval ,exitflag ,output ,population ,scores]= ga(func,nvars,A,b,Aeq,Beq,lb,ub,nonlcon,Intcon,options)

x = optimum solution
exitflag = reason ga stopped
output = information about optimization process
population = final population
scores = final scores
f = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,IntCon,options)
func = fitness function.
nvars = number of variables,
A,b = Linear inequality constraints
Aeq,beq =Linear equality constraints
lb = Lower bound(limit),
ub = Upper bound(limit),
nonlcon : Use for nonlinear constraints
IntCon : to get solution in integer.
options : To set population size minimize with non-default options

>> STEP WISE EXPLINATION OF THE CODE:

*The main objective of the function is to optimise the stalagmite function and finding the global maxima of the function by using genetic algorithm

1. The inputs 'x' and 'y' arrays are created by using matlab "linspace" command, the 2D arrays (XX and yy) for the inputs x and y are created with the help of "meshgrid" command.
2. The two 'for loops' and a function called 'stalagmite' are used to solve 'ga' and the function commands are given below

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.*f2_x.*f1_y.*f2_y);
end
function explination:
- The above fuinction defines the stalagmite function which will be used in the main function
- The input vector 'x' and 'y' will be assigned with the required values in the main function
- Negative sign used in the last line is used to maximize the stalagmite function.

3. Plotted the stalagmite by using the matlab command 'surfc'
4. Used 'shading interp' command to remove the grid lines from the stalagmite plot for gettig more smoother and good looking plot.
5. Here, I have used below three study cases to find out the global maxima and the 'tic and toc' commands to display the study time for each case
- Statistical behaviour(Unbounded)
- Statistical behaviour(Bounded)
- Statistical study with increase in size of population
6. In the third study case, Statistical study with increase in size of population, the global maxima is obtained for the stalagmite funtion.
7. With the help of 'title' command we can give the titles for all the plots.

>> References:
1. https://in.mathworks.com/help/gads/how-the-genetic-algorithm-works.html

2. https://skill-lync.com/knowledgebase/genetic-algorithm-explained

3. https://www.iitg.ac.in/rkbc/CE602/CE602/Genetic%20Algorithms.pdf

4. https://in.mathworks.com/help/gads/genetic-algorithm.html

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