Week 4.1 - Genetic Algorithm
AIM:
To write a code in MATLAB to optimize stalagmite function and find the Global Maxima of the same.
OBJECTIVES:
- Explaining the concept of Genetic Algorithm and also explain the syntax for ga in MATLAB
- Plot Graphs for all 3 studies and for Fmaximum Vs no. of iterations.
Theory:
GENETIC ALGORITHM
Genetic algorithm is a search experimental that is stimulated by Charles Darwin's theory of natural evolution.This algorithm reproduces the process 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 no. 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.
3.Selection
The idea of 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.
It should be a balance between exploration and exploitation of search space.Too strong fitness selection bias can lead to sub optimal search.
4.Reproduction
Generation of offspring happen in 2 ways:
- 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.
Single point Crossover,Two point Crossover,Uniform crossover are the major types of crossover.
- MUTATION
In a few 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.
Program For Stalagmite function in Matlab:
function [f] = stalagmite(input_vector)
x = input_vector(1);
y = input_vector(2);
f1 = (sin(5.1*pi*x+0.5)).^6;
f2 = exp(-4*log(2)*((x-0.0667).^2)./0.64);
f3 = (sin(5.1*pi*y+0.5)).^6;
f4 = exp(-4*log(2)*((y-0.0667).^2)./0.64);
f = -(f1*f2*f3*f4);
end
The first code below defines the stalagmite function that will be called in the main function
- The above function defines the stalagmite function which will be used in the main function.
- The input vectors '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.
Main Code To find the Global Maxima using 'ga' Function:
clear
close all
clc
% initial input values
lower_bound = input('Enter the Lower Bound Value: ');
upper_bound = input('Enter the Upper Bound Value: ');
% input variables with proper line spaces
x=linspace(lower_bound,upper_bound,150);
y=linspace(lower_bound,upper_bound,150);
% 3D Matrix creation
[xx, yy] = meshgrid(x,y);
count = 50;
tic
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_time = toc;
figure(1)
surfc(xx,yy,-f)
shading interp
xlabel('x label')
ylabel('y label')
legend('X Values','Y Values')
title('Stalagmite Function')
saveas(1, 'Stalagmite.png')
% [x, fval]=ga(@stalagmite,2)
% Study 1 Unbounded/random sampling inputs
tic
for i= 1:count
[inputs,fopt(i)]=ga(@stalagmite,2);
xopt(i)=inputs(1);
yopt(i)=inputs(2);
end
studytime_1 =toc;
figure(2)
subplot(2,1,1)
surfc(x,y,-f)
shading interp
title('Unbounded Inputs')
xlabel('x value')
ylabel('y value')
hold on
plot3(xopt,yopt,-fopt,'marker','o','MarkerSize',5,'MarkerFaceColor','#EDB120');
subplot(2,1,2)
plot(-fopt)
xlabel('Iterations')
ylabel('Function Maximum')
saveas(2,'Unbound Inputs.png')
% study 2 Statistical Behavior with upper and lower bound sampling
% Bounded inputs
tic
for i= 1:count
[inputs,fopt(i)]=ga(@stalagmite,2,[],[],[],[],[lower_bound;lower_bound],[upper_bound;upper_bound]);
xopt(i)=inputs(1);
yopt(i)=inputs(2);
end
studytime_2 =toc;
figure(3)
subplot(2,1,1)
surfc(x,y,-f)
shading interp
title('Bounded Inputs')
xlabel('x value')
ylabel('y value')
hold on
plot3(xopt,yopt,-fopt,'marker','o','MarkerSize',5,'MarkerFaceColor','m');
subplot(2,1,2)
plot(-fopt)
xlabel('Iterations')
ylabel('Function Maximum')
saveas(3,'Bounded Inputs.png')
% study 3 code for upper and lower bound sampling and increase the
% population size
options = optimoptions(@ga);
options = optimoptions(options,'PopulationSize',170);
tic
for i= 1:count
[inputs,fopt(i)]=ga(@stalagmite,2,[],[],[],[],[lower_bound;lower_bound],[upper_bound;upper_bound],[],[],options);
xopt(i)=inputs(1);
yopt(i)=inputs(2);
end
studytime_3 =toc;
figure(4)
subplot(2,1,1)
surfc(x,y,-f)
shading interp
title('Bounded Inputs with modified population size')
xlabel('x value')
ylabel('y value')
hold on
plot3(xopt,yopt,-fopt,'marker','o','MarkerSize',5,'MarkerFaceColor','c');
subplot(2,1,2)
plot(-fopt)
xlabel('Iterations')
ylabel('Function Maxima')
saveas(4,'Bounded Inputs with modified population size.png')
% Finding the Global maxima
global_maxima = -foptErrors Found:
The errors found are simple syntax errors and are solved by instructions from the command window.
Terms Used In the Code:
1.Ga
Ga function is used to find the minumum of the function using a genetic algorithm.
2.Surfc
Surfc function contours the plot under the surface plot.surfc(x,y,z) creates a three dimensional surface plot with a contour plot underneath.A surface plot is a three dimensional surface that has solid edge colors and solid face colors.
3.Shading
The shading function controls the color shading of surface and patch graphics objects.
shading flat each mesh line segment and face has a constant color determined by the color value at the endpoint of the segment or the corner of the face that has the smallest index or indices.
shading faceted flat shading with superimposed balck mesh lines.this is the default shading mode.
Shading interp varies the color in each line segment and face by interpolating the colormap index or true color value across the line or face.
4.Optimoptions:
Options=optimoptions(SolverName) returns a set of default options for the solvername solver.
options=optimoptions(oldoptions,Name,Value) returns a copy of oldoptions with the named parameters altered with the specified values.
5.Tic-Toc:
tic works with toc function to measure elapsed time.The 'tic' function records the current time,and toc function uses the recorded value to calculate the elapsed time.
toc reads the elapsed time since the stopwatch timer started by the call to the tic function.
Result:
The results show the generation of the stalagmites.The start and end boundaries are taken as inputs,
Study 1 plot:
With Unbounded inputs
Study 2 plot:
Bounded Inputs:
Study 3 plot:
Bounded inputs with modified Population size
The above results show that the bounded samples with population size have an accurate solution.This is because the code shows the random samples which can start and end at random points.So the bounded sample method is used giving the lower and upper limits.Hence it will take the values which are greater than the upper bound or less than the lower bound.
This loop gives an output with different local maxima with bounded inputs.so the population size is increased and it increases the probability to converge to a global maximum.
The Global Maximum of a function can be found by inverting the function.The negative of the minimum value will give the globalmaximum of the function.
CONCLUSION:
* If we compare the study time of all 3 cases study 1 gives the shortest study time but most uncertain soliton values are obtained and the study 3 has taken the longest time but has given an optimum solution and study 2 falls in between the study1 and study 3 in which it increases the convergence considerably but still fluctuation values are obtained.
* Thus the Global maxima of the stalagmite function is optimised using genetic algorithm in Matlab.
REFERENCES:
1.https://en.wikipedia.org/wiki/Genetic_algorithm?msclkid=5468c158cf6011ec8540f5e3c40959be