Week 4.1 - Genetic Algorithm
`AIM:TO CALCULATE THE GLOBAL MAXIMA OF A STALGAMATE FUNCTION USING MATLAB.
OBJECTIVE:
- To write the Matlab code to optimize the stalagmite fuction and find the global maxima of the function.
- To explain the syntax of (ga) in Matlab.
INTRODUCTION TO GENETIC ALGORITHM:
A Genetic Algorithm is a search heuristic that is inspired by Charles Darwin's Theory of natural evolution.This algorithm reflects the process of natural selection where the fittest individuals are selected for reproduction in order to produce offspring of the next generation.
NATURAL SELECTION:
The process of natural selection starts with the selection of fittest individuals from a population.They produce offspring which inherit the characteristics of the parents and will be added to the next generation. If parents have better fitness,their offspring will be better fitness,their offspring will be better than parents and have a better chance of surviving.This process keeps on iterating and at the end,a generation with the fittest individuals will be found.
FIVE PHASES OF GENETIC ALGORITHM:
- Initail population
- Fitness function
- Selection
- Crossover
- Mutation
INITIAL POPULATION:
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.Gens are joined into a string to form a Chromosome.In a genetic algorithm,the set of genes of an individual is represented using a string,interms of an alphabet.Usually,binary values are used(string of 1s and 0s).we say that we encode the genes i n chromosome.
FITNESS FUNCTION:
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 fitness score.
SELECTION:
The idea of selection phase is to select the fittest individuals and let them pass their genes to the next generation.Two pairs of individuals (parents)are selected based on their fitness scores.Individuals with high fitness have more chance to be selected for reproduction.
CROSSOVER:
Crossover is the most significant phase in genetic algorithm.for each pair of parents to be mated,a crossover point is chosen at random from within the genes.
For example,consider the crossover point to be 3 as shown below.
offspring are created by exchanging the genes of parents among themselves untill the crossover point is reached.
The new offspring are added to the population.
MUTATION:
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 bits in the bit string can be flipped.
Mutation occurs to maintain diversity within the population and prevent premature convergence.
TERMINATION:
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.
PSEUDOCODE:
START
Generate initial poulation
Compute fitness
REPEAT
Selection
Crossover
Mutation
Compute fitness
Iterate untill population has converged
STOP
STUCTURE PROCESS:
ADVANTAGES OF GENETIC ALGORITHM:
- It does not require any derivative information(which may not be available for many real-world problems)
- It is faster and more efficient as compared to 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.
- Useful when the search space is very large and there are a large number of parameters involved.
LIMITATIONS OF GENETIC ALGORITHM:
- GA are not suited for all problems,only used for simple problems which derivative information is available.
- Fitness value is calculated repeatedly which might be computationally expensive for some problems.
- Being stochastic ,there are no guarentees on the optimality or the quality of the solution.
- If it was not implemented properly, the GA may not converge to the optimal solution.
APPLICATIONS OF GENETIC ALGORITHM:
- OPTIMIZATION:Genetic Algorithms are most commenly used in optimization problems wherein we have to maximize or minimize a given objective function value under a given set of constraints.
- ECONOMICS:GAs are also used to characterize various economic models like the cobweb model,game theory equilibrium resolution,asset pricing,etc.
- IMAGE PROCESSING:GAs are for various digital image processing tasks as well like dense pixel matching.
- ROBOT TRAJECTORY GENERATION:GAs have been used to plan the path which a robot arm takes by moving from one point to another.
- DNA ANALYSIS:GAs have been used to determine the structure of DNA using spectrometric data about the sample.
The stalagmite function is as follows:
PROGRAM FOR 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);
endSYNTAX OF GENETIC ALGORITHM(ga) IN MATLAB:
x=ga(fun,nvars,Aineq,bineq,Aeq,beq,1b,ub,nonlcon,options);
- X is the local minima point
- fun is the function to be called .(in this case it is an stalagmite function)
- nvars indicates the no of variables used.
- Aineq and bineq are used to indicate any kind of inequalities that exist in the function.
- Aeq and beq also denotes the inequalities.
- lb=lower bound
- ub=upper bound
- nonlcon gives a two vectors representing inequalities and equalities.
- options is used to perform additional operations like increasing population size.this is done with the help of optimoptions.
PROGRAM TO PLOT STALAGMITE FUNCTION:
%program to plot stalagmite function
clear all
close all
clc
%defining our search space
x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
%creating 2d mesh
[xx,yy]=meshgrid(x,y);
%evaluate the stalagmate 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);%function we created to find the value
end
end
surfc(xx,yy,f)%to generate the stalagmite function
shading interp%to show the function in smooth
xlabel('x value')
ylabel('y value')
PLOTTING STALGAMATE FUNCTION:
PROGRAM FOR THE UNBOUNDED INPUTS:
%program for UNBOUNDED INPUTS
clear all
close all
clc
%defining our search space
x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
%creating 2d mesh
[xx,yy]=meshgrid(x,y);
%evaluate the stalagmate 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);%values for the function in the search space
end
end
num_cases=50;%number of iteration
tic%calculating the study time
for i=1:num_cases
[inputs,f_opt(i)]=ga(@stalagmite,2);%calculate the optimized value for the funtion
x_opt(i)=inputs(1);
y_opt(i)=inputs(2);
opt_f(i)=-f_opt(i);%ga gives us only minimum value.so we take inverse to get the maximum value
end
study1_time=toc%display the time taken to evaluate
figure(1)
subplot(2,1,1)
hold on
surfc(xx,yy,f)%generate the stalgamate function
shading interp%to show the curve surface in smooth
plot3(x_opt,y_opt,f_opt,'marker','o','markersize',4,'markerfacecolor','g')%plotting the optimum value of x and y,and the stalgamate function
title('unbounded inputs')%to visible in title of figure window
subplot(2,1,2)
plot(opt_f)%plotting for each value
xlabel('Number of iteration')%shows in x axis
ylabel('Function max')%shows in y axis
OUTPUT FOR THE UNBOUNDED INPUTS:
PROGRAM FOR THE BOUNDED INPUTS:
%program for BOUNDED INPUTS
num_cases=100;%number of iteration
tic
for i=1:num_cases
[inputs,f_opt(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6]);%calculate the optimized value of function
x_opt(i)=inputs(1);
y_opt(i)=inputs(2);
opt_f(i)=-f_opt(i);%ga gives only minimum value so take inverse to get maximum value
end
study2_time=toc%display the time taken to evaluate
figure(2)
subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp%to show the curve surface smooth
plot3(x_opt,y_opt,f_opt,'marker','o','markersize',4,'markerfacecolor','g')%plotting the optimum values of x, y and stalgamate function
title('bounded inputs')%to show the title o figure window
subplot(2,1,2)
plot(opt_f)%plotting for each value
xlabel('Number of iteration')%show in xaxis
ylabel('Function max')%show in y-axis
OUTPUT FOR THE BOUNDED INPUTS:
PROGRAM FOR THE BOUNDED INPUTS WITH ALTERED POPULATION SIZE:
%program bounded inputs with ALTERED POPULATON SIZE
num_cases=150;%no of iterations
options=optimoptions('ga');
options=optimoptions(options,'populationsize',450);%population size is given to get the better function of global maxima
tic%time to evaluate the process
for i=1:num_cases
[inputs,f_opt(i)]=ga(@stalagmite,2,[],[],[],[],[0,0],[0.6,0.6],[],[],options);%calculate the optimized value of x,y and stalagmite function
x_opt(i)=inputs(1);
y_opt(i)=inputs(2);
opt_f(i)=-f_opt(i);%ga gives only minimum value so we taken inverse to get maximum value.
end
study3_time=toc%display the time taken to evaluate
figure(3)
subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp%to show the curve surface smooth
plot3(x_opt,y_opt,f_opt,'marker','o','markersize',4,'markerfacecolor','g')
title('bounded inputs with increased population size')%to show the title of figure window
subplot(2,1,2)
plot(opt_f)
xlabel('Number of iteration')%show in x axis
ylabel('Function max')%show in y axis
OUTPUT FOR THE BOUNDED INPUTS WITH ALTERED POPULATION SIZE:
EXPLANATION:
- In the first program,the stalgamate function has to be plotted with the values of x and y in the stalgamite function.
- meshgrid command is used to mesh the values of x and y
- For loop is used for the iteration process of the stalgamite function.
- surfc command is used to make the surface and contour plot.uses the row and column indices.
- Then in study_1 program,with an unbounded inputs,the number of iteration has to be given as 50.
- In this (ga) genetic algorithm function is to be used to calculate the values of an unbounded points.
- In the function fopt the value shows the global minimum we need to calculate the global maximum,so we take inverse of function to get the global maximum value.
- In study_1 plotting we did not get the proper position of global maxima,so we move on to next study of bounded inputs.
- In study_2,the (ga) genetic algorithm function we set the boundary limits to get the proper output for the optimized value.
- The boundary limits are [0,0] and [0.6,0.6].
- from the boundary limits we have plotted the values,from that we get an improved figure then the previous or unbounded inputs plots
- But we need to get the global maxima,so we have the change the population size in the bouded inputs program.
- In study_3 the number of iteration is to be increased to 150 and we have to give the value of population size in the (ga) genetic algorithm function.
- The population size value is to be 450 for the (ga) function.
- Then the program run to give the proper figure to find the global maxima value.
- shade interp commandis used to get the stalagmite function in smooth, without grid lines.
- subplots are plotted to visualize the maxima function is graphical.
- xlabel is used to show the number of iterations and ylabel is used to show the maximum value of function.
- Tic and toc command are used to measure the time to evaluate the process of the program.
- GLOBAL MAXIMA value is 0.99999985
ERROR I GOT: 1.)
i have missed the [], in the formula of the (ga) function.i added the [] brakets in the formula to solve the error.
2.)
i have corrected my error by putting (_) sign between opt and f as opt_f
WORKSPACE VALUES:
RESULTS:
Hence the optimization of stalagmite function has been done using matlab code and the global maxima of the function has been calculated.
REFERENCES: