Week 4 - Genetic Algorithm
AIM:
To write a code in MATLAB to optimize stalagmite function and find the global Maxima of the same.
THEORY:
DEFINITION:
GENETIC ALGORITHM is a search heuristic that is inspired by Charles Darwin theory of natural evolution.
This algorithm reflects the process of natural selection where fittest individuals are selected for reproduction to generate offsprings for next generation.
PROCESS OF NATURAL SELECTION:
This process starts with selection of fittest individual form a given set of population.
They produce offsprings which inherit the characteristic of the parents and will be added to next generation.
If the parents are fit enough, their offsprings will be better than their parents and will have better chances of surviving.
This process keeps on iterating and at the end a generation of fittest individuals will be obtained.
This whole notion can be helpful in search problems.
We select a set of solutions to a problem and sort out a set of best ones out of them. This will eventually narrow down to one best solution that gives optimum results for the given problem.
The genetic algorithm differs from a classical, derivative-based, optimization algorithm in two main ways, as summarized in the following table.
Algorithm working sequence:
Then algorithm then creates a sequence of new populations. At each step, the algorithm uses the individuals in the current generation to create the next population. To create the new population, it uses the fitness function which is the function you want to optimize. For standard optimization algorithms, this is known as the objective function. The toolbox software tries to find the minimum of the fitness function.
There are five phases in gentic algorithm and are explained as below:
1.) Initial population
The problem intiates with a set of individuals which is called population. Each individual is a solution to the problem we want to solve.
Each individual is characterized by a set of parameters called genes.
Genes are joined into a string which yields us chromosome which is nothing but a solution.
2.)FITNESS FUNCTION:
The fitness function determines how fit an individual is. It gives a fitness score to each individual.
The probability that an individual will be selected for reproduction is based on this score.
3.)SELECTION PHASE
The main objective of this phase is to select the fittest individual and let them pass their Gene onto the next generation.
4.)CROSSOVER
For each pair of parents to be mated, crossover point is chosen at random from within the genes.
For example, consider the crossover point to be 3 as in the figure below:
Offsprings are created by exchanging genes of parents among themselves until the crossover point is reached.
The new offspring is then added to the population.
5.)MUTATION
In certain new offsprings formed, some of their genes can be subjected to mutation with low random probability.
This implies that some of the bits in the bit string can be flipped.
Mutation occurs to maintain diversity within population and prevent premature convergence.
TERMINATION:
Finally, the algorithm terminates if the population has converged.
Then it is said that genetic algorithm has provided a set of solution to our problem.
PSEUDOCODE:
START
Generate intial population
Compute fitness
REPEAT
Selection
Crossover
Mutation
Compute fitness
Iterate until population has converged
STOPPROGRAM FOR GENETIC ALGORITHM IN MATLAB:
clear all
close all
clc
%defining the search space
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
iterations = 50;
[xx, yy] =meshgrid(x,y);
%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
%1st iteration - studying the statistical behaviour
tic
for i=1:iterations
[inputs , f_optimum(i)] = ga(@stalagmite,2);
x_optimum(i) = inputs(1);
y_optimum(i) = inputs(2);
end
iteration_1_time = 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','r')
title('Unbounded inputs')
subplot(2,1,2)
plot(f_optimum)
xlabel('Iterations')
ylabel('Function maximum')
%2nd iteration with upper and lower limits
tic
for i=1:iterations
[inputs , f_optimum(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
x_optimum(i) = inputs(1);
y_optimum(i) = inputs(2);
end
iteration_2_time = toc
%plotting
figure (2)
subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded inputs')
subplot(2,1,2)
plot(f_optimum)
xlabel('Iterations')
ylabel('Function maximum')
%3rd iteration - increasing the size of population
options = optimoptions('ga');
options = optimoptions(options,'populationsize',200)
tic
for i=1:iterations
[inputs , f_optimum(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
x_optimum(i) = inputs(1);
y_optimum(i) = inputs(2);
end
iteration_3_time = toc
%plotting
figure (3)
subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp
plot3(x_optimum,y_optimum,f_optimum,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded inputs with modified population size')
subplot(2,1,2)
plot(f_optimum)
xlabel('Iterations')
ylabel('Function maximum')Errors during programming:
This error happened because there was a bracket[] missing,it was then corrected.
Stepwise explaination of the above program:
i.) First, the search space required to execute the program is defined which varies from 0 to 0.6 with 150 divisions in between.
ii.)using the meshgrid command, row vectors x and y are converted into matrices xx and yy.
iii.) With the help of for loop, the input vectors required for stalagmite function are defined using the matrices xx and yy.
From here onwards, whole program is divided into three iterations and will be made to run individually.
OUTPUT:
Unbounded statastical behaviour plot
Bounded statastical behaviour plot
Modified population size plot
Stalagmite function output print in command window
References:
https://www.mathworks.com/help/gads/how-the-genetic-algorithm-works.html
https://www.mathworks.com/help/gads/ga.html