Week 4.1 - Genetic Algorithm

AIM:-

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

WHAT IS GENETIC ALGORITHM:-

Genetic Algorithm (GA) is a search-based optimization technique based on the principles of Genetics and Natural Selection. It is frequently used to find optimal or near-optimal solutions to difficult problems which otherwise would take a lifetime to solve. It is frequently used to solve optimization problems, in research, and in machine learning.it uses concepts of evolutionary biology(Darwin's theory of evolution).

Five phases are considered in a genetic algorithm.

• Initial population
• Fitness function
• Selection
• Crossover
• Mutation

For more details one can visit this reference link,
https://towardsdatascience.com/introduction-to-genetic-algorithms-including-example-code-e396e98d8bf3

INTRODUCTIONS OF STALAGMITES:

Stalagmites are thin piles of mineral deposits that have fallen from the roof to the floor of a cave. They're sometimes connected to the stalactites that dangle down from the top. Because stalagmites form from drops of water combined with minerals, they get their name from the Greek stalagmos, "a dropping," and share a root with stalactite — the Greek stalassein, "to trickle."

The stalagmite function is defined below:

Syntax

x = ga(fun,nvars)

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

APPLICATION OF GENETIC ALGORITHM:

• Optimization − Genetic Algorithms are most commonly used in optimization problems wherein we have to maximize or minimize a given objective function value under a given set of constraints. The approach to solve Optimization problems has been highlighted throughout the tutorial.
• Economics − GAs are also used to characterize various economic models like the cobweb model, game theory equilibrium resolution, asset pricing, etc.
• Neural Networks − GAs are also used to train neural networks, particularly recurrent neural networks.
• Parallelization − GAs also have very good parallel capabilities, and prove to be very effective means in solving certain problems, and also provide a good area for research.
• Image Processing − GAs are used for various digital image processing (DIP) tasks as well like dense pixel matching.
• Vehicle routing problems − With multiple soft time windows, multiple depots and a heterogeneous fleet.
• Scheduling applications − GAs are used to solve various scheduling problems as well, particularly the time tabling problem.etc

CODE:-

MAIN PROGRAM:

close all
clear all
clc

%Defining our search space
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
iterations=50;


%Creating a Dimensional mesh
[xx yy] = meshgrid(x, y);

%Evaluating 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



%study 1- statitcal behaviour
tic
for i = 1:iterations
     [inputs, f_optimum(i)] = ga(@stalagmite,2);
     xoptimum(i)= inputs(1);
     yoptimum(i)= inputs(2);
end
iteration_1_time=toc

figure(1)
subplot(2,1,1)
hold on;
surfc(xx,yy,f)
shading interp
plot3(xoptimum,yoptimum,f_optimum,'marker','o','markerSize',6,'markerfaceColor','r')
title('unbounded')
subplot(2,1,2)
plot(f_optimum)
xlabel('iterations');
ylabel('Function minimum');

%study2 statistical behaviour-with upper and lower bounds
tic
for i = 1:iterations
     [inputs, f_optimum(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
     xoptimum(i)= inputs(1);
     yoptimum(i)= inputs(2);
end
iteration_2_time=toc

figure(2)
subplot(2,1,1)
hold on;
surfc(xx,yy,f)
shading interp
plot3(xoptimum,yoptimum,f_optimum,'marker','o','markerSize',5,'markerfaceColor','r')
title('bounded inputs')
subplot(2,1,2)
plot(f_optimum)
xlabel('iterations');
ylabel('Function minimum');

%study 3 increasing GA iterations
options = optimoptions('ga');
options = optimoptions(options,'populationsize',200)


tic
for i = 1:iterations
    [inputs, f_optimum(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
    xoptimum(i)= inputs(1);
    yoptimum(i)= inputs(2);
end
iteration_3_time=toc

figure(3)
subplot(2,1,1)
hold on;
surfc(xx,yy,f)
shading interp
plot3(xoptimum,yoptimum,f_optimum,'marker','o','markerSize',6,'markerfaceColor','r')
title('bounded inputs with modify population size')
subplot(2,1,2)
plot(f_optimum)
xlabel('iterations');
ylabel('Function minimum');

FUNCTION PROGRAM:

function [f] = stalagmite(input_vector)

x = input_vector(1);
y = input_vector(2);

f1 = (sin(5.1*pi*x+0.5))^6;
f2 = (sin(5.1*pi*y+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);
end

CODE EXPLANATION:-

• Firstly a random array of x and y values are created and the correponding 2D array was obtained using meshgrid function.
• a nested loop was used to assign values from this array into array named input_vector.this is the input to stalagmite function.the stalagmite function is written as seperate.
• Minus(-)sign is given to the output of stalagmite function so that, after the ga process it we get global maxima.
• Tic toc commands are used to get the running time of each case.
• in the first case the bounds were not defined and the plots were made
• negative sign is given for f value inside surface function to get the stalagmite functions upwards
• bounding is given in next case so that the number of solution approches more accuracy.
• the population is incresed in subsequent cases and plotting procedure is done
• the global maxima is found in last case
• the x and y values for which the function has maximum values is also diplayed

Stopping criteria:

• Generation - The algorithms stops when the number generation reaches when the values generation
• Time limit - The algorithms stops after running an amount of time is equal to time limit
• Fitness limit - The algorithms stops when the value of the fitness function for the best point in the current population is less than or equal to fitness limit

OUTPUT:-

Case 1: Unbounded

Case 2: Bounded inputs

Case 3 Bounded inputs with modify population size

ERROR :

The error that face in making of function program, i didn't place the x and y value so that is minor mistake of this program

CONCLUSION:

In this challenge,the concept of genetic algorithm was used to optimize the stalagmite function to find the global maxima.the concept and working of genetic algorithm are studied and used in three cases to optimize the function and to find global maxima.

REFERENCE LINK:

https://in.mathworks.com/help/gads/genetic-algorithm.html

https://towardsdatascience.com/introduction-to-genetic-algorithms-including-example-code-e396e98d8bf3

https://skill-lync.com/knowledgebase/genetic-algorithm-explained