Week 4.1 - Genetic Algorithm

Aim:

To optimise the given stalagmite function and Global maxima of the function.

What is Genetic Algoritm?

A genetic algorithm is a search heuristic that is inspired by Charles Darwin’s theory of natural evolution. This algorithm reflects the process of natural selection where the fittest individuals are selected for reproduction in order to produce offspring of the next generation.

Five phases are considered in a genetic algorithm.

1. Initial population
2. Fitness function
3. Selection
4. Crossover
5. Mutation

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

Introduction of stalagmite and stalactites:

Stalagmite: It is upward growing mound of mineral deposite that have precipitated from water dripping onto the floor of a cave Most stalagmites have rounded or flattened tips. it was opposed from stalactites.

Stalactites: It is upward growing mound of mineral deposite that have precipitated from water dripping from caves. These formattion hang from the ceiling. it was opposed from stalagmite.

The formula for stalagmite functions

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 GA

• 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.

• Machine Learning − as already discussed, genetics based machine learning (GBML) is a niche area in machine learning.

• Robot Trajectory Generation − GAs have been used to plan the path which a robot arm takes by moving from one point to another.

• Parametric Design of Aircraft − GAs have been used to design aircrafts by varying the parameters and evolving better solutions.

• DNA Analysis − GAs have been used to determine the structure of DNA using spectrometric data about the sample.

• Multimodal Optimization − GAs are obviously very good approaches for multimodal optimization in which we have to find multiple optimum solutions.

Traveling salesman problem and its applications − GAs have been used to solve the TSP, which is a well-known combinatorial problem using novel crossover and packing strategies.

Reference link https://www.tutorialspoint.com/genetic_algorithms/genetic_algorithms_application_areas.htm

CODE

FUNCTION CODE
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


MAIN CODE

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');

Code Explanation

First a random array of a x,y value are created and corresponding 2d array was obtained using meshgrid function. A nested loop is used to create the array into array named as input_vector, the stalagmite function is written seperately. this function used to identify the genetic algorithms(ga)for global maxima.GA stands only to find global minima . tic toc command is used to get running time of each case.In the first cases the bound were not finished and plot were made. Bounding is given in next cases so that number of solution approaches more accuracy.The population is increased in the subsequent cases and plotting is done. the global maximum is find at the last case. the x and y values for which the function has which maximum value is displayed.The iteration were decrease to a such a value that the result didnt vary and the program were consumed minimum time to execute.

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

Error

The error that I faced in making of function program, i didnt place the x and y value so that is minor mistake of this program

Thus,by increasing the number of population size and iterations, GA gives more accurate results

REFERENCE LINK;

https://in.mathworks.com/help/gads/what-is-the-genetic-algorithm.html#:~:text=The%20genetic%20algorithm%20is%20a,a%20population%20of%20individual%20solutions.