Week 4 - Genetic Algorithm
Find global maxima by optimizing staglamite function in MATLAB
AIM:
To understand the concept of genetic algorithm and to use to find the stalagmite function and to point the global maxima of the function.
Introduction to Optimization
Optimization is the process of making something better. In any process, we have a set of inputs and a set of outputs as shown in the following figure.
THE CONCEPT OF GENETIC ALGORITHM:
The genetic algorithm is a method for solving both constrained and unconstrained optimization problems that is based on natural selection, the process that drives biological evolution. The genetic algorithm repeatedly modifies a population of individual solutions.
What are Genetic Algorithms?
Nature has always been a great source of inspiration to all mankind. Genetic Algorithms (GAs) are search based algorithms based on the concepts of natural selection and genetics. GAs are a subset of a much larger branch of computation known as Evolutionary Computation.
GAs were developed by John Holland and his students and colleagues at the University of Michigan, most notably David E. Goldberg and has since been tried on various optimization problems with a high degree of success.
In GAs, we have a pool or a population of possible solutions to the given problem. These solutions then undergo recombination and mutation (like in natural genetics), producing new children, and the process is repeated over various generations. Each individual (or candidate solution) is assigned a fitness value (based on its objective function value) and the fitter individuals are given a higher chance to mate and yield more “fitter” individuals. This is in line with the Darwinian Theory of “Survival of the Fittest”.
In this way we keep “evolving” better individuals or solutions over generations, till we reach a stopping criterion.
Genetic Algorithms are sufficiently randomized in nature, but they perform much better than random local search (in which we just try various random solutions, keeping track of the best so far), as they exploit historical information as well.
Advantages of GAs
GAs have various advantages which have made them immensely popular. These include −
- Does not require any derivative information (which may not be available for many real-world problems).
- Is faster and more efficient as compared to the traditional methods.
- Has very good parallel capabilities.
- Optimizes both continuous and discrete functions and also multi-objective problems.
- Provides a list of “good” solutions and not just a single solution.
- Always gets an answer to the problem, which gets better over the time.
- Useful when the search space is very large and there are a large number of parameters involved.
Limitations of GAs
Like any technique, GAs also suffer from a few limitations. These include −
- GAs are not suited for all problems, especially problems which are simple and for which derivative information is available.
- Fitness value is calculated repeatedly which might be computationally expensive for some problems.
- Being stochastic, there are no guarantees on the optimality or the quality of the solution.
- If not implemented properly, the GA may not converge to the optimal solution.
OUR STALAGMITE FUNCTION:
STEP1:
To calculate the values of x & y and to _nd the global maxima we have to code the above formula as a function and then call this function into our main
Program
% stalagmite function
function [f]=stalagmite(input_vector)
x1=input_vector(1);
y1=input_vector(2);
term1=(sin(5.1*pi*x1+0.5)).^6
term2=(sin(5.1*pi*y1+0.5)).^6
term3=exp(-4*log(2)*((x1-0.0667).^2/0.64))
term4=exp(-4*log(2)*((y1-0.0667).^2/0.64))
f=-(term1.*term2.*term3.*term4);
end
STEP2:
Calling the stalagmite function into our main program
clear all
close all
clc
% Main program to find the global maxima
% Defining our search space
x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
num_cases=50;
% Creating a 2Dimensional mesh
[xx,yy]=meshgrid(x,y);
% Calling stalagmite function
% 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
STEP3:
The 3rd step is to conduct study 1 to calculate the statistical behaviour of unbounded inputs and plot graph.
% Study 1 - Statistical Behaviour
for i=1:num_cases
[inputs,fopt(i)]=ga(@stalagmite,2);
xopt(i)=inputs(1);
yopt(i)=inputs(2);
end
study1_time=toc;
%plotting
figure(1)
subplot(2,1,1)
hold on
surfc(x, y, -f)
hold on
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('unbounded inputs')
subplot(2,1,2)
plot(-fopt)
xlabel('iterations')
ylabel('function maximum')
Here in the above program we have de_ned the for loop for a length of num_cases to get the values of xopt, yopt and fopt
we have use the tic toc commands to calculate the time for study one
we have used the subplot command to plot the 3D representation of xopt,yopt,fopt and the 2d graph of f opt in the same window
As the genetic algorithm always _nd the minimum value, but our aim is to _nd the maximum value, Hence here in the above program we have used the -(minus)
sign to minimize the function f and fopt to calculate the maximum value
OUTPUT1:
CONCLUSION1:
In 1st study we _nd that the maximum values are not clearly de_ned and a lot of minimum values have been de_ned. hence, we are going to proceed with
study 2
STEP4:
Our 4th step is to conduct study 2 to calculate the statistical behaviour of bounded inputs and plot a graph.
tic
% Study 2 - Statistical Behaviour - with upper and lower bounds
for i=1:num_cases
[inputs,fopt(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1])
xopt(i)=inputs(1);
yopt(i)=inputs(2);
end
study2_time=toc;
%plotting
figure(2)
subplot(2,1,1)
hold on
surfc(x, y, -f)
hold on
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('bounded inputs')
subplot(2,1,2)
plot(-fopt)
xlabel('iterations')
ylabel('function maximum')
OUTPUT2:
Here in the above program we have de_ned the for loop for a length of num_cases to get the values of xopt, yopt and fopt
we have use the tic toc commands to calculate the time for study one
We are using the ga syntax to _x the upper and lower bound values i.e., [0;0] and [1;1]
We have used the empty braces to calculate the value of linear equality and linear inequality
we have used the subplot command to plot the 3D representation of xopt,yopt,fopt and the 2d graph of f opt in the same window
As the genetic algorithm always _nd the minimum value, but our aim is to _nd the maximum value, Hence here in the above program we have used the -(minus)
sign to minimize the function f and fopt to calculate the maximum value
STEP5:
Our 5th step is to conduct study 3 to calculate the statistical behaviour of bounded inputs with increased population size and plot a graph.
% Study 3 - Increasing GA iterations
options = optimoptions('ga');
options = optimoptions(options,'populationsize',180);
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
study_3 = toc
figure(3)
subplot(2,1,1)
hold on
%plotting
figure(3)
subplot(2,1,1)
hold on
surfc(x, y, -f)
hold on
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('bounded inputs with modified population size')
subplot(2,1,2)
plot(-fopt)
xlabel('iterations')
ylabel('function maximum')
OUTPUT3:
THE STUDY TIME FOR ALL THE THREE STUDIES:
CONCLUSION:
Thus by refering to various references and understanding the concept of GA the code to _nd the global maxima by optimising the stalagmite function has
been coded and and implemented successfully.
We understand that increasing the population size then the difference obtain in maximum value of function will decreases
REFRENCE:
https://en.wikipedia.org/wiki/Genetic_algorithm
https://www.tutorialspoint.com/genetic_algorithms/genetic_algorithms_introduction.htm