Challenge

Week 4.1 - Genetic Algorithm

DDeepan Tushar Jagad24 Dec 2021

AIM :

To write a code in MATLAB to optimise the given stalagmite function and to find the global maxima of the function

INTRODUCTION :

Stalagmites structures are formed from the cave floor that point upward.Stalagmite functions are mathematical functions which represents similar to that of the stalagmites functions.

The stalagmite function is defined below:

Introduction to Genetic Algorithm(GA):

The Genetic Algorithm(GA) is an optimization technique used to solve non-linear optimization problems. It uses concepts of evolutionary biology(Darwin's theory of evolution) to find the global maxima for optimization of a problem. An initial set of solutions is tested against the objective function. Subsequent generations evolve through the process mentioned below.

Genetic Algorithm is done in 3 steps:

Selection: A number of individuals is selected from the population in the mating pool.Based on the previously calculated fitness value, the best individuals based on a threshold are selected.After that step, we will end selecting a subset of the population in the mating pool.

Crossover: Crossover in GA generates a new generation as same as the natural mutation.By mutating the old generation parents, the new generation offspring comes by carrying genes from both parents.The amount of genes carried from each parents in random.

Mutation: For each offspring,select some genes and change its values.Mutation prevents the solution from falling into a local minima.

SYNTAX :

x = ga(fun,nvars)

x = ga(fun,nvars) finds a local unconstrained minimum,x, to the objective function fun.nvars is the number of design variables of function,fun.

STOPPING CRITERIA:

Generations - The algorithm stops when the number of generations reaches the value of generations.
Time limit - The algorithm stops after running for an amount of time in seconds equal to the time limit.
Fitness limit - The algorithm stops when the value of the fitness function for the best point in the current population is less than or equal to fitness limit.

Below is the main program of Genetic algorithm :

PROGRAM


clear all
close all
clc

%Defining our sear space

x = linspace(0,0.8,150);
y = linspace(0,0.8,150);
limit=30;

%Creating a 2 Dimensional mesh

[xx yy] = meshgrid(x, y);

%Evaluating the stalagmite function by using Nested For loop

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
%Case 1 :

tic

for i=1:limit

    [input,fval(i)]=ga(@stalagmite_function,2);
    x_out(i)=input(1);
    y_out(i)=input(2);

end
case_time_1=toc

figure(1)
subplot(2,1,1)
surfc(xx,yy,-f)
xlabel('x value')
ylabel('y value')
shading interp
hold on;
plot3(x_out,y_out,-fval,'marker','o','markersize',6,'markerfacecolor','r');
subplot(2,1,2);
plot(-fval);
xlabel('Number of iterations')
ylabel('Max Function value')

%Case 2 : Inserting bounding box

tic
for i=1:limit
    [input,fval(i)]=ga(@stalagmite_function,2,[],[],[],[],[0;0],[0.8;0.8]);
    x_out(i)=input(1);
    y_out(i)=input(2);
end
case_time_2=toc

figure(2)
subplot(2,1,1)
hold on;
surfc(xx,yy,-f)
xlabel('x value')
ylabel('y value')
title('case 2','color','k')
shading interp
hold on
plot3(x_out,y_out,-fval,'marker','o','markersize',6,'markerfacecolor','r');
subplot(2,1,2);
plot(-fval);
xlabel('Number of iterations')
ylabel('Max Function value')

%Case 3
% options=optimoptions('ga')
options=optimoptions('ga','Populationsize',100)
tic
for i=1:limit
    [input,fval(i)]=ga(@stalagmite_function,2,[],[],[],[],[0;0],[0.8;0.8],[],[],options);
    x_out(i)=input(1);
    y_out(i)=input(2);
end
case_time_3=toc

figure(3)
subplot(2,1,1)
hold on;
surfc(xx,yy,-f)
xlabel('x value')
ylabel('y value')
title('case 3','color','k')
shading interp
hold on
plot3(x_out,y_out,-fval,'marker','o','markersize',6,'markerfacecolor','r');
subplot(2,1,2);
plot(-fval);
xlabel('Number of iterations')
ylabel('Max Function value')

%Case 4
options=optimoptions('ga')
options=optimoptions('ga','populationsize',300)
tic
for i=1:limit
    [input,fval(i)]=ga(@stalagmite_function,2,[],[],[],[],[0;0],[0.1;0.1],[],[],options);
    x_out(i)=input(1);
    y_out(i)=input(2);
end
case_time_4=toc

figure(4)
subplot(2,1,1)
hold on;
surfc(xx, yy,-f)
xlabel('x value')
ylabel('y value')
title('case 4','color','k')
shading interp
hold on
plot3(x_out,y_out,-fval,'marker','o','markersize',6,'markerfacecolor','r');
subplot(2,1,2);
plot(-fval);
xlabel('Number of iterations')
ylabel('Max Function value')

%Displaying values for inputs x and y for maximum value of function
display(input)

Explanation of the program:

Firstly we have created random arrays of x & y values.
We have used a meshgrid function from which we have obtained coressponding 2D array.
Then we have created a nested for loop to assign different values into a array named vector_input.
The vector_input is an input to the stalagmite function.
We have coded the calling of stalagmite function as a seperate program after the main program of Genetic algorithm(as shown below).
Normally 'ga' which is the in-built command gives an output for GLOBAL MINIMA. So, we have used the minus(-) sign to the stalagmite function so after the 'ga' processes we can get the GLOBAL MAXIMA.
The 'tic' & 'toc' commands are used in the process of getting the running time of each case.
In the first case, we can see that the bounds are not defined and the plots are made.
Minus(-)sign is given to 'f' value inside surface function to the get the stalagmite function and plotting upwards.
Theree is bounding given in the next case so there are more number of solutions having more accuracy.
Then there is also the next cases in which there is increase of population and are plotted accordingly.
We can find the GLOBAL MAXIMA in the last case.
The x & y values for which the function is maximum are also displayed.
There are iterations are considered in decrement so that the program takes minimum time to execute.

Stalagmite Function Program :

PROGRAM


function[f]=stalagmite_fun(input_vector)

f1x=(sin((5.1*pi).*input_vector(1)+0.5)).^6;
f1y=(sin((5.1*pi).*input_vector(2)+0.5)).^6;

f2x = exp(((-4*log(2))*(input_vector(1)-0.0667).^2)/0.64);
f2y = exp(((-4*log(2))*(input_vector(2)-0.0667).^2)/0.64);
f1=f1x*f1y*f2x*f2y;
f=-f1;
end

I have faced a couple of errors while programming, I have shared the screenshots of the errors thrown in the comman window and also explained how they can be resolved.

This error was thrown in the command window because I have assigned the optimoptions name as 'ga' (line 75) and while giving the inputs I have written 'options' (line 76). The name should be same as the input given. So we have to change 'options' and code 'ga' on line 76 to resolve the error.

This error was thrown in the command window because in the genetic algorithm we have used the input function handle as 'stalagmite_fun', but we have saved the function calling program name as 'stalagmite_function'. i.e. both are different. We should have the input function handle and the program of function calling same. By doing this our error is resolved.

RESULTS :

Case 1 : Unbounded.