Week 4 - Genetic Algorithm

AIM:
To optimise the stalagmite function and find the global maxima of the function.

OBJECTIVES OF THE PROJECT:

Explaining the concept of genetic algorithm and also explain the syntax for ga in MATLAB.
Plot graphs for all 3 studies and for F maximum vs no. of iterations.

INTRODUCTION:

A Genetic Algorithm is a search experiential 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 modies the population size of individual solutions.
Phases in Genetic Algorithm1.

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.

1. 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 tness values are used for the reproduction of the children.

1. Selection

The idea of the selection phase is to select the ttest 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 tness selection bias can lead to sub-optimal solutions.

Too little fitness bias selection results in unfocused search.

1. Reproduction

Generation of offspring happen in 2 ways:

Crossover

Mutation

1. a) Crossover

Crossover is the most signicant 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.

1. 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.

FLOW CHART:

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

x = optimum solution

exitag = reason ga stopped

output= information about optimization process

population=final population

scores= final scores

f=ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon,options)

fun -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

BODY OF THE CONTENT:

• FITNESS FNUCTION

• The above equations are used in the stalagmite function to plot the graph in the main functions.

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;
 t1 = ((x-0.0667).^2)/(0.64);
 f2_x = exp(-4.*log(2)*t1);
 t2 = ((y-0.0667).^2)/(0.64);
 f2_y = exp(-4.*log(2)*t2);
 f = -(f1_x.*f2_x.*f1_y.*f2_y);

end

While using the function at the end as we are using the -ve sign so that the plot will be reversed as we have to find the maxima of the given function using ga.

MAIN BODY

• Firstly, creating the mesh from the two vectors which will be acting as a search space to find the maxima of the function.
• Creating the mesh of these two vectors using the ‘mesh’ command and dening the no. of iterations as num_cases to iterate the values of the
  optimum values of the function.
• Now calculating the values of fitness function at each point of the mesh grid formed.
• Now creating its surface through ‘surfc’ command which will also provide the contour of the generated surface.
• While using surfc applying the -ve sign to the function will generate the surface upside down which will be quite good to get the maxima of the function, as it will provide positive value for the maxima using the -ve sign.

clear
close all
clc
%% PROVIDING THE SEARCH SPACE FOR THE FUNCTION
 x=linspace(0,0.6,150);
 y=linspace(0,0.6,150);
 [X,Y]=meshgrid(x,y);

 num_cases=50; %Number of itreation for which the function will evaluate the fitness

 n%% CREATING THE SURFACE PLOT OF STALAGEMITE FUNCTION
 for i=1:length(X)
 for j=1:length(Y)
 input_vector(1)=X(i,j);
 input_vector(2)=Y(i,j);
 f(i,j)=stalagmite(input_vector); %values of function in given search space
 end
 end
 surfc(X,Y,-f); %generating the surface
 shading interp %To remove the lines produced by the mesh grid



%% STATISTICAL BEHAVIOUR (UNBOUNDED)

tic %calculating the study time through tic and toc command
for i=1:num_cases

 [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

 % PLOTING THE GRAPH
 figure(1)
 subplot(2,1,1)
 surfc(X,Y,-f);
 hold on
 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 min value')

%% STATISTICAL BEHAVIOUR (BOUNDED)
tic %calculating the study time through tic and toc command
 for j=1:num_cases

 [inputs,fopt(j)]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]); %calculating the optimized value of the function
 xopt(j)=inputs(1); %at each iteration with boundation
 yopt(j)=inputs(2);

 end
study2_time=toc

 %PLOTTING
 figure(2)

 subplot(2,1,1)
 hold on
 surfc(X,Y,-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 min value')

%% MODIFYING THE NUMBER OF POPULATION

 options=optimoptions('ga','populationsize',300) %increaing the sixe of population by using

 %optimoptions function
 tic
for k=1:num_cases

 [inputs,fopt(k)]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
 xopt(k)=inputs(1);
 yopt(k)=inputs(2);

end
study3_time=toc

 %PLOTTING
 figure(3)

 subplot(2,1,1)
 hold on
 surfc(X,Y,-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 min value')

Explanation :

1. 200 cases are assigned to run through the stalagmite function & genetic algorithm .
2. Stalagmite function is called then from the code shown later which produces the stalagmite and is passed to the genetic algorithm in the main command
shown above .

3. Study 1 :
4. Is done for 200 iterations as mentioned and further genetic algorithm is used for the stalagmite function comprising of the equations shown above in the picture with its 2 variables .
5. the syntax used in this one is : [inputs , fopt(i)] = ga(@stalagmite, 2);
6. which is : x = ga(fun,nvars) finds a local unconstrained minimum, x, to the objective function, fun. nvars is the dimension (number of design variables) of fun
7. the study is timed using tic toc commands.
8. The study 1 is done for statistical behaviour of the stalagmite function and its values are random and changes and not much optimized .
9. markers are plotted using plot3 command over the tness values obtained in the rst study and also a 2d graph is shown for a more understanding to its
global maxima.
10. for first study there is a high variation.

11. Study 2 :
12. This study is done for further optimization of the stalagmite function .
13. Similar approach as first study is made and the syntax for GA is further modied and upper and lower bounds are assigned from 0-1 for both x and y.
14. [inputs , fopt(i)] = ga(@stalagmite, 2, [],[] ,[],[],[0;0],[1;1]);
15. syntax - x = ga(fun,nvars,A,b,Aeq,beq,lb,ub) , where A ,B and Aeq and beq are blanks . lb and ub represents lower and upper bounds respectively.
16. It denes a set of lower and upper bounds on the design variables, x, so that a solution is found in the range lb ≤ x ≤ ub. (Set Aeq=[] and beq=[] if no linear
equalities exist.)
17. The rest approach is same as study 1 .

18. Study 3 :
19. Study 2 sucessfully optimized the function but it can still be further optimized, hence we do further one more study where we increase the ga
populationsize by modifying the syntax for GA and set it to 500 from default 50.
20. [inputs , fopt(i)] = ga(@stalagmite, 2, [], [] ,[],[],[0;0],[1;1],[],[],options);
21. Syntax - x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,options) minimizes with the default optimization parameters replaced by values in options. (Set nonlcon=
[] if no nonlinear constraints exist.) Create options using optimoptions.
22. where values not placed are simply replaced with blank brackets .
23. Again similar approach as study 1 is followed.

OUTPUTS

final plots