Week 4.1 - Genetic Algorithm

AIM:- To optimize a given stalagmite function using 'GA' genetic algorithm command in MATLAB.

OBJECTIVES:-

To write a code to optimize stalagmite function and also to find global maxima.
Explaination about genetic algorithm and syntax for GA in MATLAB
Plotting graphs for all 3 studies and for F maximum vs no. of iterations.
EXPLAINATION:-

stalagmite function:-

It is a mathematical 3 Dimensional function. we generally optimize stalagmite function by finding global maxima and minima.

The name stalagmite is to a function as out put graph resembles stalagmites which we usually see in limestone caves formed due to accumulation of minerals deposited on the floor from ceiling drippings

Example:-

f(x,y) = stalagmite(x,y)

f(x,y) = f1x.f1y.f2x.f2y

where

1. f1x = sin((5.1pix + 0.5))^6

2. f1y = sin((5.1piy + 0.5))^6

3. f2x = e^-4ln2(2^(x-0.0667))/0.64

4. f2y = e^-4ln2((y-0.0667)^2/0.64)

GENETIC ALGORITHM:-

A genetic algorithm is a method for optimization problems based on a natural selection process that mimics biological evolution.

GA folloes Darwins Theory of survival of the fittest to evolve to an optimal solution. ga starts with an initial set of random solutions called "population". Each individual in the population is called chromosome represent a solution to problem at hand.

The chromosomes evolve through successive iterations called generation.

There are 5 steps in ga

1.Initial population

2.fittness function

3.selection

4.cross over

5. mutation

1.Initial population:

The process begin with a set of individuals called as polulation. Each individual is a solution to a problem we want to solve.

An individual is characterized by set of parameters(variables) knowns as genes. genes are joined to a string to form a chromosome(solution).

FITTNESS FUNCTION:

Fittness function determines how fit a individual is ( an ability of an imdividual to compete with other individuals). It gives a

fittness score to each individuals. The probability that individual will be selected as reproduction is based on its fittness score.

SELECTION OPERATOR :

The idea of selection phase is to select the fittest individuals and let them pass their genes to the next generation.

Two pair of individuals (parents) are selected based on their fittness score. Individual with high fittness have more chance to be

selected for reproduction.

Genetic operators:

manipulate chromosomes/solutions

1.selection operator

2.Mutation

3.Cross over

1). selection operator:(finding best parent)

process of selecting two or more parameters from the population for crossing.whn two parents meet to create a new child which has more good qualities than both the parents & the best is pass to the next generation.

By which we can find best solution i.e optimizing results.

2). Mutation

The meaning of mutation in terms of biology is a change that occurs in our DNA sequence. In same way in ga we can make use of mutation in chromosome by changing the sequence of bit/gene for every chromosome. As shown below A5 chromosome/individual had changed by changing genes/chromosome position.

3). crossover

crossover is a most significant phase in ga. For each pair of parents to be mated a crossover point is choosen random from with in the genes.

example as below.

offspring are created by exchanging the genes of parents among themselves until crossover point is reached.

new offspring added to offspring.

SYNTAX FOR GA:

ga is afunction which determines tghe minimum value of using genetic algorithm

[x,fval,exitflag,output,population,score] = ga(fun,nvar,A,b,[],[],lb,ub,nonlcon,intCon,options)

fun = objective function

nvars = no. of variables

A, b = linear inequality constraints of type A*x<=b

bounds - lb ub

nonlcon- (nonlinear constraints) a function that accept a vector or array x returns two arrays, c(x) and ceq(x).

options - optimization options output of optimoptions

clear all
close all
clc
%definiting for our search space
 x = linspace(0, 0.6, 150);
 y = linspace(0, 0.6, 150);

 %creating 2dimensional mesh grid
 [ xx, yy] = meshgrid(x, y);
 f = zeros;

 %evaluating the 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
 num_case = 30;
 %unbounded optimization
 figure(1)
 surf(xx, yy,-f)
 shading interp
 xlabel('x values')
 ylabel('y values')
 zlabel('f(x,y');

 tic
 objf = @stalagmite;
 for i = 1:num_case
     [maxima,f_opt(i)] = ga(objf, 2);
     x_opt(i) = maxima(1);
     y_opt(i) = maxima(2);
 end
 a = toc;

 figure(2)
 subplot(2,1,1)

 surf(x,y,-f)
 xlabel('x');
 ylabel('y');
 zlabel('f(x,y');
 title('unbounded optimization');
 shading interp
 hold on
 plot3(x_opt,y_opt,-f_opt,'marker','o','markerfacecolor','r');

 subplot(2,1,2)
 plot(abs(f_opt))
 xlabel('No. of Iterations');
 ylabel('max. function value');


 %%bound optimization with upper and lower bounds
 tic
 for i = 1:num_case
     [maximab,f_optb(i)] = ga(objf, 2, [], [], [], [], [0;0], [1;1]);
     x_optb(i) = maximab(1);
     y_optb(i) = maximab(2);
 end

 b = toc;

 figure(3)
 subplot(2,1,1)

 surf(x,y,-f)
 xlabel('x');
 ylabel('y');
 zlabel('f(x,y');
 title('bounded optimization');
 shading interp
 hold on
 plot3(x_optb,y_optb,-f_optb,'marker','o','markersize',6,'markerfacecolor','r');

 subplot(2,1,2)
 plot(abs(f_optb))
 xlabel('no. of iterations');
 ylabel('max. function value');


 %%increasing population size
 options=optimoptions('ga');
 options=optimoptions(options,'populationsize',500);

  tic
  for i = 1:num_case
      [maximaip,f_optip(i)] = ga(objf, 2, [], [], [], [], [0;0], [1;1], [], [], options); 
      x_optip(i) = maximaip(1);
     y_optip(i) = maximaip(2);
 end

 c = toc;

 figure(4)
 subplot(2,1,1)

 surf(x,y,-f)
 xlabel('x');
 ylabel('y');
 zlabel('f(x,y)');
 title('bounded optimization with increased population');
 shading interp
 hold on
 plot3(x_optip,y_optip,-f_optip,'marker','o','markersize',6,'markerfacecolor','r');

 subplot(2,1,2)
 plot(abs(f_optip))
 xlabel('no. of iterations');
 ylabel('max. function value');

 %%outputs
 disp(['time taken by genetic algorithm to optimize in unbound manner=' num2str(a), 'sec'])
 disp(['time taken by genetic algorithm to optimize in bound manner=' num2str(b), 'sec'])
 disp(['time taken by genetic algorithm to optimize in bound manner with increased population =' num2str(c), 'sec'])

 disp(['MAXIMA of stalagmite function when optimized in unbound manner =' num2str(max(-f_opt))])
  disp(['MAXIMA of stalagmite function when optimized in bound manner =' num2str(max(-f_optb))])
   disp(['MAXIMA of stalagmite function when optimized in bound manner with increased population=' num2str(max(-f_optip))])
    disp(['MAXIMA of stalagmite function lies at x  =' num2str(maximaip(1)) 'y = ' num2str(maximaip(2))])
 

RESULT: