Week 4.1 - Genetic Algorithm

Write a code in MATLAB to optimise the stalagmite function and find the global maxima of the function.

 Stalagmite function:-  It is generally refers to the function with which we are generating values over a stalagmite kind of surface for finding out the local and global maxima and minima of that particular given function using Genetical Algorithm.

Concept of Genetic Algorithm:- It is first introduced by Holland in (1975) is a powerful stochastic search algorithm based on the mechanics of natural genetics and selection as Goldberg in (1989). It is a method for solving both constrained and unconstrained optimization problems.

A general description is as follow:-

• It is start with an initial set of random solution called as populations.
• Each individual in the population is called chromosomes representing a solution to the problem at hand.
• The chromosomes evolve through succesive iterations called generations.
• During each generation the chromosomes are evaluated using some measure of fitness.
• To create the next generation, new chromosomes called offspring are formed by either (a) Merging two chromosomes from current generation using a crossover operator or (b) Modifying a chromosome using mutation operator.
• A new generation is formed by (a) Selecting according the fitness value some of the parents and offspring and (b) Rejecting others so as to keep the population size constant.
• Fitter chromosomes have higher probabilities of being selected.
• After several generations the algorithm converges to the best chromosome which hopefully represents the optimum or suboptimal solution to the problem. 

Objectives:- 

1. Optimise the stalagmite function.
2. find the global maxima of the function.

GA Syntax:-

1] ga(@fcn,nvars)   

where nvars means number of variable used.

2] ga(@fcn,nvars,[],[])

where [],[] = A and b linear inequalities A*x ≤ b.

3] ga(@fcn,nvars,[],[],[],[])

where [],[] = Aeq and beq linear equalities Aeq*x = beq and A*x ≤ b.

4] ga(@fcn,nvars,[],[],[],[],lb,ub)

where lb = lower bound, ub = upper bound.

5]ga(@fcn,nvars,[],[],[],[],lb,ub,[],options)

where [] = nonlcon it defined equality and inequality C(x) ≤ 0 and Ceq(x) = 0. 

options = create options using optimoptions.

Stalagmite function:-

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

`f1x = [sin(5.1pix+0.5)]^6`

`f1y = [sin(5.1piy+0.5)]^6`

`f2x = exp[-4ln(2)frac{(x-0.0667)^2}{0.64}]`

`f2y = exp[-4ln(2)frac{(y-0.0667)^2}{0.64}]`

Function code:- The above equations are used to create stalagmite function to plot the graph in main program. While -ve sign using at the end so the plot will be reversed as we have to find global maxima as using ga.

function f = stalagmite(input_vector)
x = input_vector(1);
y = input_vector(2);
f1x = ((sin(5.1*pi*x+0.5))^6);
f1y = ((sin(5.1*pi*y+0.5))^6);
a1 = (((x-0.0667)^2)/0.64);
a2 = (((y-0.0667)^2)/0.64);
f2x = exp((-4*log(2))*a1);
f2y = exp((-4*log(2))*a2);
fx =(f1x*f1y*f2x*f2y);
f = -fx;
% -ve sign gives global maxima
end

Procedure:-

Firstly clear all the data.

Create 1d array of two vectors using linspace command.

Create 2d mesh of these two vectors using meshgrid command.

Evaluate stalagmite function through for loop.

Create 3d surface with contour using surfc command.

Then give command shading interp for removal of grid lines on surface.

Calculate Maxima value uisng the ga command which is in-built function in MATLAB.

then the input of numcases with the help of for loop ga is made to run for each iteration and the value is stored in an array. 

then give tic and toc command for calculating time at the start and end of the ga for loop.

then change the sign as negative for global maxima value.

the ga is run for 3 studies with each study having bounded inputs,unbounded inputs,and increasing population size.

Main codes:- 

clear all
close all
clc

%create 1d array
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);

%create 2d mesh using 1d array
[X Y] = meshgrid(x,y);

%evaluate stalagmite 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);
    end
end

%plotting
surfc(X,Y,-f) %create 3d surface with contour
shading interp  %remove grid lines on diagram

Generated plot:-

Study1:- Unbounded statistical behaviour

In this study the behaviour of the algorithm is studied by not defining the limits. the GA does not run within a particular searchspace since we have not defined bounds.

clear all
close all
clc

%Iteration:- I
%Study1:- Unbounded statistical behavoiur

%create 1d array
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);

%create 2d mesh using 1d array
[X Y] = meshgrid(x,y);

%inputs
nvars = 2;  %number of variable
num_cases = 50;  %run for iterations

%evaluate stalagmite 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);
    end
end

%evaluate stalagmite data and gives optimise soln
tic  %study 1 count time start
for k = 1:num_cases;
    %syntax : x = ga(fun,nvars)
    %obj function is stalagmite and the nvars is the variable used
    [inputs fopt(k)] = ga(@stalagmite,nvars);
    %fopt = it gives global maxima & minima values
    %-ve sign gives maxima & +ve sign gives minima
    xopt(k) = inputs(1);
    yopt(k) = inputs(2);
end
studytime_1 = toc  %study 1 count time end

%plotting
subplot(2,1,1)
surfc(X,Y,-f) %create 3d surface with contour
shading interp  %remove grid lines on diagram
hold on
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('Unbounded Inputs')
xlabel('X values')
ylabel('Y values')
subplot(2,1,2)
plot(-fopt)
xlabel('Iterations')
ylabel('function minimum')

Generated plot:- Iterations = 50

From the fig as shown above it is clear that the result are not much accurate and giving lot of variations in optimizing the function.

Study 2:- Bounded statistical behaviour with lower and upper bound

Here the lower and upper bounds are defined as to know the boundaries within which the global maxima lies.

clear all
close all
clc

%Iteration:- II
%Study1:- Bounded statistical behavoiur with lower and upper bound

%create 1d array
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);

%create 2d mesh using 1d array
[X Y] = meshgrid(x,y);

%inputs
nvars = 2;  %number of variable
num_cases = 100;  %run for iterations

%evaluate stalagmite 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);
    end
end

%evaluate stalagmite data and gives optimise soln
tic  %study 2 count time start
for k = 1:num_cases;
    %syntax : x = ga(fun,nvars,A,b,Aeq,beq,lb,ub)
    %obj function is stalagmite and the nvars is the variable used
     %a,b,aeq,beq is the no linear equalities and inequalities constraints in this function
    %lb = lower boundary of variable x & y
    %ub = upper boundary of variable x & y
    [inputs fopt(k)] = ga(@stalagmite,nvars,[],[],[],[],[0,0],[1,1]);
    %fopt = it gives global maxima & minima values
    %-ve sign gives maxima & +ve sign gives minima
    xopt(k) = inputs(1);
    yopt(k) = inputs(2);
end
studytime_2 = toc  %study 2 count time end

%plotting
subplot(2,1,1)
surfc(X,Y,-f) %create 3d surface with contour
shading interp  %remove grid lines on diagram
hold on
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded Inputs')
xlabel('X values')
ylabel('Y values')
subplot(2,1,2)
plot(fopt)
xlabel('Iterations')
ylabel('function minimum')

Generated plot:- Iterations = 100

It is clearly seen from the above that after providing the boundary limits the variation in optimum value of the function  has reduced.

Study 3:- Increasing GA Iterations

In this study the population size and iterations is increased so as to converge to the global maxima.

clear all
close all
clc

%Iteration:- III
%Study3:- Increasing GA iterations

%create 1d array
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);

%create 2d mesh using 1d array
[X Y] = meshgrid(x,y);

%inputs
nvars = 2;  %number of variable
num_cases = 150;  %run for iterations

%evaluate stalagmite 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);
    end
end

%evaluate stalagmite data and gives optimise soln
options = optimoptions('ga');
options = optimoptions(options,'populationsize',300)
%populationsize is defined using options 
tic  %study 3 count time start
for k = 1:num_cases;
    %syntax : x = ga(fun,nvars,A,b,Aeq,beq,lb,ub)
    %obj function is stalagmite and the nvars is the variable used
     %a,b,aeq,beq is the no linear equalities and inequalities constraints in this function
    %lb = lower boundary of variable x & y
    %ub = upper boundary of variable x & y
    %options = population size
    [inputs fopt(k)] = ga(@stalagmite,nvars,[],[],[],[],[0,0],[1,1],[],options);
    %fopt = it gives global maxima & minima values
    %-ve sign gives maxima & +ve sign gives minima
    xopt(k) = inputs(1);
    yopt(k) = inputs(2);
end
studytime_3 = toc  %study 3 count time end

%plotting
subplot(2,1,1)
surfc(X,Y,-f) %create 3d surface with contour
shading interp  %remove grid lines on diagram
hold on
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded Inputs with modified population size')
xlabel('X values')
ylabel('Y values')
subplot(2,1,2)
plot(fopt)
xlabel('Iterations')
ylabel('function minimum')

Generated plot:- Iterations = 150, populations size = 300

As we seen in this graph getting the optimised value of global maxima with accurate range since we increased the number of iteration and population size.

Full Program:-

clear all
close all
clc

%create 1d array
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);

%create 2d mesh using 1d array
[X Y] = meshgrid(x,y);

%evaluate stalagmite 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);
    end
end

%Iteration:- I
%Study1:- Unbounded statistical behavoiur

%inputs
nvars = 2;  %number of variable
num_cases1 = 50;  %run for iterations
num_cases2 = 100;
num_cases3 = 150;

%evaluate stalagmite data and gives optimise soln
tic  %study 1 count time start
for k = 1:num_cases1;
    %syntax : x = ga(fun,nvars)
    %obj function is stalagmite and the nvars is the variable used
    [inputs fopt(k)] = ga(@stalagmite,nvars);
    %fopt = it gives global maxima & minima values
    %-ve sign gives maxima & +ve sign gives minima
    xopt(k) = inputs(1);
    yopt(k) = inputs(2);
end
studytime_1 = toc  %study 1 count time end

%plotting
figure(1)
subplot(2,1,1)
surfc(X,Y,-f) %create 3d surface with contour
shading interp  %remove grid lines on diagram
hold on
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('Unbounded Inputs')
xlabel('X values')
ylabel('Y values')
subplot(2,1,2)
plot(-fopt)
xlabel('Iterations')
ylabel('function minimum')

%Iteration:- II
%Study2:- Bounded statistical behavoiur with lower and upper bound

%evaluate stalagmite data and gives optimise soln
tic  %study 2 count time start
for k = 1:num_cases2;
    %syntax : x = ga(fun,nvars,A,b,Aeq,beq,lb,ub)
    %obj function is stalagmite and the nvars is the variable used
     %a,b,aeq,beq is the no linear equalities and inequalities constraints in this function
    %lb = lower boundary of variable x & y
    %ub = upper boundary of variable x & y
    [inputs fopt(k)] = ga(@stalagmite,nvars,[],[],[],[],[0,0],[1,1]);
    %fopt = it gives global maxima & minima values
    %-ve sign gives maxima & +ve sign gives minima
    xopt(k) = inputs(1);
    yopt(k) = inputs(2);
end
studytime_2 = toc  %study 2 count time end

%plotting
figure(2)
subplot(2,1,1)
surfc(X,Y,-f) %create 3d surface with contour
shading interp  %remove grid lines on diagram
hold on
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded Inputs')
xlabel('X values')
ylabel('Y values')
subplot(2,1,2)
plot(fopt)
xlabel('Iterations')

%Iteration:- III
%Study3:- Increasing GA iterations

%evaluate stalagmite data and gives optimise soln
options = optimoptions('ga');
options = optimoptions(options,'populationsize',300)
%populationsize is defined using options 
tic  %study 3 count time start
for k = 1:num_cases3;
    %syntax : x = ga(fun,nvars,A,b,Aeq,beq,lb,ub)
    %obj function is stalagmite and the nvars is the variable used
     %a,b,aeq,beq is the no linear equalities and inequalities constraints in this function
    %lb = lower boundary of variable x & y
    %ub = upper boundary of variable x & y
    %options = population size
    [inputs fopt(k)] = ga(@stalagmite,nvars,[],[],[],[],[0,0],[1,1],[],options);
    %fopt = it gives global maxima & minima values
    %-ve sign gives maxima & +ve sign gives minima
    xopt(k) = inputs(1);
    yopt(k) = inputs(2);
end
studytime_3 = toc  %study 3 count time end

%plotting
figure(3)
subplot(2,1,1)
surfc(X,Y,-f) %create 3d surface with contour
shading interp  %remove grid lines on diagram
hold on
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded Inputs with modified population size')
xlabel('X values')
ylabel('Y values')
subplot(2,1,2)
plot(fopt)
xlabel('Iterations')
ylabel('function minimum')
ylabel('function minimum')

Conclusion:-

The GA gives more accurate results in case of bounded inputs and by increasing the number of iterations and population size.

Dharmesh Bonde