Week 4.1 - Genetic Algorithm

Aim : To optimise the stalgmite function and find the global maxima of function using genetic Algorithm in MATLAB.

Objectives :

• write a code in MATLAB to optimise the stalagmite function and find the global maxima of function.
• Expalin the concept of genetic algorithm.
• Explain the syntax for ga in MATLAB.

Theory :

Concept of genetic Algorithm :

A genetic algorithm ( ga ) is a method for solving both constrained and unconstrained optimization problems based on a natural selection process that minimize biological evolution. The algorithm repeatedly modifies a population of individual solutions. At each step, the genetic algorithm randomly selects individual from the current population and uses them as parents to produce the children for the next generation.Over successive generation, the population 'evolves' toward an optimal solution.

We can apply the genetic algorithm to solve problems that are not well suited for standard optimization algorithms, including problems in which the objective function is discontinuous, nondifferentiabl, stochastic, or highly nonlinear.

The genetic algorithm differs from aclassical, derivative-based optimization algorithm in two main ways, As summarized in the following table.

Classical Algorithm	Genetic Algorithm
1. Generates a single point at each iteration. The sequence of point approaches an optimal solution.	1. Generates a population of points at each iteration. the best point in the population approaches an optimal solution.
2. Selects the next point in the sequence by a deterministic computation.	2. Selects the next population by computation which uses random number generators.

How Genetic Algorithm works :

The following outline summarizes the genetic algorithm work :

• The algorithm begins by creating a random initial population.
• The algorithm then creates a sequence of new population. At each step, the algorithm uses the individuals in the current generation to creat the next population. To create the new population, the algorithm performe the following steps:

1. Scores each member of the current population by computing its fitness value. These values are called the raw fitness scores.
2. Scales the raw fitness scores to convert them into a more usable rang of values. These scaled values are called expectation values.
3. Selects members, called parents,based on their expectation.
4. Some of the individuals in the current population that have lower fitness are chosen as elite.These elite individuals are passed to the nxet population.
5. Produces children from the parents. Children are produced either by making random changes to a single parent-muutation-or by combining the vector entries of a pair of parents-crossover.
6. Replaces the current population with the children to form the next generation.

• The algorithm stops when one of the stopping criteria is met

Syntax for ga :

f_min = ga(@function,nvars,A,B,Aeq,Beq,LB,UB,nonlcon,intcon,options)

Explaination of terms involved are following :

• f_min is the local minima point.
• @function is the function to be called.
• nvaes indicates the number of variables used.
• A and B are used to indicate any kind inequalities that exist in the function.
• Same goes with Aeq and Beq.
• LB = lower bound.
• UB = upper bound.
• nonlcon gives a two vectors representing inequalities and equalities.
• options is used to perform addition operations like increasing population size. This is done with the help of optimo options.

stalagmite function :

Code For the stalagmite function :

function [f] = stalagmite_function(input_vector)
x = input_vector(1);
y = input_vector(2);

f1 = (sin(5.1*pi*x+0.5))+0.5))^6;
f2 = (sin(5.1*pi*y+0.5))+0.5))^6;
f3 = exp(-4*log(2)*((x-0.0667)^2)/0.64);
f4 = exp(-4*log(2)*((y-0.0667)^2)/0.64);

f = -(f1*f2*f3*f4);

MATLAB COD 2 :

clear all
close all
clc

x = linspace(0,0.6,150);
y = linspace(0,0.6,150);

num_cases = 50

%Creating 2D mesh
[xx, yy] = meshgrid(x,y);

% Evaluting 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_function(input_vector);
   end
end

% Study 1 - Statical behavior 
tic
for i = 1:num_cases
    [input1,fopt1(i)] = ga(@stalagmite_function,2);
    xopt1(i) = input1(1);
    yopt1(i) = input1(2);

end

Study1_time = toc

figure(1)
subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp
plot3(xopt1,yopt1,fopt1,'marker','o','markersize',5,'markerfacecolor','auto')
title('Unbounded inpute'0
subplot(2,1,2)
plot(fopt1)
xlabel('Iteration')
ylabel('Function maximum')

tic

% Study 2 - Statistical behavier - with upper and lower bound

for i = 1:num_cases
    [input2,fopt2(i)]=ga(@stalagmite_function,2,[],[],[],[],[0,0],[1:1]);
     xopt2(i) = input2(1);
     yopt2(i) = input2(2);
end

Study2_time = toc

figure(2)
subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp
plot(xopt2,yopt2,fopt2,'marker','o','markersize',5,'markerfacecolor','auto')
title('Bounded input')
subplot(2,1,2)
plot(fopt2)
xlabel('Iterations')
ylabel('Fuction Maximum')

% Study 3 - Increasing GA interations

options = optimoption('ga')
options = optimoption(option,'PopulationSize',250);

tic

for i = 1:num_cases
    [input3,fopt3(i)] = ga(@stalagmite_funcion,2,[],[],[],[],[0,0],[1:1],[],[],options);
    xopt3(i) = input3(1);
    yopt3(i) = input3(2);
end

Study3_time = toc
 
figure(3)
subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp
plot(xopt3,yopt3,fopt3,'marker','o','markersize',5,'markerfacecolor','auto')
title('Bounded inputs with increasing ga in interation')
subplot(2,1,2)
plot(fopt3)
xlabel('Iteration')
ylabel('Function Maximum')

Code Explanation :

• Start with clear all ,close all,clc content previously stored.
• linspace command is used to define 250 x & y values between 0, to 0.6 with 50 num_cases to run 50 time.
• meshgrid command is uesd to form two dimentional array.
• for loop is executed to evaluate the stalagmite fuction.
• for case study 1 - statictical behavier for loop is executed. during execution stalagmite function is called with 'ga'. Respective plotting is done. Also, tic and toc command is used to measure time taken for execution.
• foe case study 2 - statictical behavier with upper and lower bound, for loop is executed. during execution stalagmite funtion is called with'ga'. Also tic and toc command is used to measure time for execution.
• Again, for case study 3 - with increasing, for loop is executed. during execution stalagmite function is called with 'ga'. Here optimoptions function is used to return ga solver and to define population size. Also tic and toc command is used to measure time taken for execution.

Result :

Study 1:

Study 2 :

Study 3 :