Week 4.1 - Genetic Algorithm

Aim :-

To find the global maxima for the given function using the concept of genetic algorithm in matlab.

Objective :-

• Write a code to optimize a stalagmite function .
• Write a code to find out global maxima of the function.
• Explain the concept of genetic algorithm.
• Explain the syntax for genetic algorithm.

Theory :-

Optimization :-

Optimization refers to finding the values of inputs in such a way that we get the best output values.

The set of all the possible solutions or values which the inputs can take make up the search space, lies a point or a set of points which gives the optimal solution.

Genetic Algorithm :-

Genetic algorithm is a search based optimization technique on the principle of genetics and natural selection. It is used to find optimal solutions to difficult problems or to solve optimization problems. Optimization refers to finding the values of inputs in such a way that we get the “best” output values.

Need of GA :-

• Solving difficult problems – problems which takes even years to solve in such cases GA provides usable near optimal solution in a short amount of time.
• Getting a good solution in lesser time.

Genetic Algorithms are adaptive heuristic search algorithms that belong to the larger part of evolutionary algorithms. GA’s are based on the ideas of natural selection and genetics. They are commonly used to generate high quality solutions for optimization problems and search problems.

In simple words GA selects the best and remove the waste . They stimulate survival of the fittest among individuals of consecutive generation for solving a problem.

Steps taken in Genetic algorithm :-

1. Initial population :-

The process begins with a set of individuals which is called a population. Each individual is a solution to the problem you want to solve. It selects the random input values.

2. Fitness function :-

Fitness score is given to each individual. The probability that an individual will be selected for reproduction is depends on its fitness score. The best fit value will be proceed for genes.

3. Selection :-

The idea of selection phase is to select the fittest individuals and let them pass their genes to the next generation.

4. Crossover :-

For each pair of parents to be mated, a crossover point is chosen at random from within the genes.

5. Mutation :-

The key idea is to insert random genes in offspring to maintain the diversity in population to avoid the premature convergence.

Syntax for GA in matlab :-

X = ga(fun,nvars)

X = ga(fun,nvras,A,b)

X = ga(fun,nvras,A,b,Aeq,beq)

X = ga(fun,nvras,A,b,Aeq,beq,lb,ub)

X = ga(fun,nvras,A,b,Aeq,beq,lb,ub,nonlcon)

X = ga(fun,nvras,A,b,Aeq,beq,lb,ub,nonlcon,options)

X = ga(fun,nvras,A,b,Aeq,beq,lb,ub,nonlcon,intcon)

X = ga(fun,nvras,A,b,[],[],lb,ub,nonlcon,intcon)

X = ga(fun,nvras,A,b,[],[],lb,ub,nonlcon,intcon,options)

X = ga(problem)

Ga = linear name of the function

fun = name of function

nvars = number of design variables

Aineq = A matrix for linear inequality constraints

Bineq = b vector for linear inequality constraints

Aeq = Aeq matrix for linear equality constraints

Beq = beq vector for linear equality constraints

Ib, ub = upper and lower bounds

Nonlcon = nonlinear constraint functions

Stalagmite Function :-

1. Stalagmite is a type of rock formation that rises from the floor of a cave due to the accumulation of material deposited on the floor from ceiling drippings.

2. Stalactite and stalagmite, elongated forms of various minerals deposited from solution by slowly dripping water. A stalactite hangs like an icicle from the ceiling or sides of a cavern . A stalagmite appears like an inverted stalactite, rising from the floor of a cavern.
3. Stalactites hanging from the ceilings of caverns commonly exhibit a central tube or the trace of a former tube whose diameter is that of a drop of water hanging by surface tension. A drop on the tip of a growing stalactite leaves a deposit only around its rim.

Code :-

% Declaring the function

function [out] = stalagmite(input_vector)
%Defining input conditions
x = input_vector(1);
y = input_vector(2);
%Solving the equations to obtain the values of the function
f1x = (sin((5.1*pi*x)+0.5))^6;
f1y = (sin((5.1*pi*y)+0.5))^6;
f2x = exp(-4*log(2)*(((x-0.0667)^2)/0.64));
f2y = exp(-4*log(2)*(((y-0.0667)^2)/0.64));
F = f1x*f1y*f2x*f2y;
%Output is taken negative to find global maxima instead of global minima 
%in the genetic algorithm
out = -F

end




% Finding global maxima of the function by optimising the stalagmite
% function using genetic algorithm

clear all
close all
clc

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

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

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



% Study 1 - Statistical behabiour

num_cases = 40
tic

for i = 1:num_cases
    [inputs, f1_opt(i)] = ga(@stalagmite, 2);
    x1_opt(i) = inputs(1);
    y1_opt(i) = inputs(2);
end

study1_time = toc

figure(1)
subplot(2, 1, 1)
hold on
surf(xx, yy, -f)
shading interp
plot3(x1_opt,y1_opt,-f1_opt,'marker','o','markersize',5,'markerfacecolor','r')
title('unbounded inputs')
xlabel('x axis')
ylabel('y axis')
subplot(2, 1, 2)
plot(-f1_opt)
xlabel('Iterations')
ylabel('function maximum')

tic
%Study 2 - Statistical behaviour - with upper and lower bounds
for i = 1:num_cases
    [inputs, f2_opt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
    x2_opt(i) = inputs(1);
    y2_opt(i) = inputs(2);
end
study2_time = toc

figure(2)
subplot(2,1,1)
hold on
surfc(xx, yy, -f)
shading interp
plot3(x2_opt,y2_opt,-f2_opt,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded inputs')
xlabel('x axis')
ylabel('y axis')
subplot(2,1,2)
plot(-f2_opt)
xlabel('Iterations')
ylabel('Function maximum')


%Study 3 Increasing GA iterations
options = optimoptions('ga');
options = optimoptions(options,'populationsize',170);

tic
for i=1:num_cases
    [inputs, f3_opt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
    x3_opt(i) = inputs(1);
    y3_opt(i) = inputs(2);
end

study3_time = toc
figure(3)
subplot(2,1,1)
hold on
surfc(xx, yy, -f)
shading interp
plot3(x3_opt,y3_opt,-f3_opt,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded inputs with controlled populationsize')
xlabel('x axis')
ylabel('y axis')
subplot(2,1,2)
plot(-f3_opt)
xlabel('Iterations')
ylabel('Function maximum')



%Study 4 - Increasing GA iterations and specifying population
options = optimoptions('ga');
options = optimoptions(options,'populationsize',170);

tic
for i=1:num_cases
    [inputs, f4_opt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[0.4;0.4],[],[],options);
    x4_opt(i) = inputs(1);
    y4_opt(i) = inputs(2);
end

study4_time = toc
figure(4)
subplot(2,1,1)
hold on
surfc(xx, yy, -f)
shading interp
plot3(x4_opt,y4_opt,-f4_opt,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded inputs with controlled populationsize and increasing iteration')
xlabel('x axis')
ylabel('y axis')
subplot(2,1,2)
plot(-f4_opt)
xlabel('Iterations')
ylabel('Function maximum')

Code explanation :-

1. We write a stalagmite function to find the global maxima of the function.
2. GA gives the values of minima hence we simply invert the function to get the maxima of the function. We changed the function value to negative instead of positive.
3. We define the range of the function.
4. Then created 2D array using ‘meshgrid’, command and store them in ainput_vector array.
5. For study1 we take no of iterations and use GA to calculate maxima of the function.
6. We store the output into results contains maxima and f_opt.
7. Here ga is initiated with the random values.
8. We use plot3 command to make plot for maxima of x_opt,y_opt,-f_opt
9. Marker and markersize command is used to specify points on the plot.
10. To estimate the time taken to find the maxima we use tic toc command.
11. As it takes random values optimal values went outside the stalagmite surface.
12. In study 2 we specified the upper and lower bound with random population.
13. It gives the values within the specified limits but did not give the exact maxima value.
14. In study 3 we specified upper and lower bound with certain population.
15. Now it gives exact global maxima value for the function.

Results :-

Study 1 :-

It gives the unbounded inputs which goes outside the desired space.

Study 2:-

By adding upper and lower bounds it shows the values within the specified search space.

Study 3:-

After adding upper and lower bounds with the population size it gives the value for global maxima of the function.

Conclusion :-

1. From the above assignment for finding global maxima of a given function using stalagmite we can say that the complex problems which takes long time to salve we can solve that problems using stalagmite in a very short time.
2. Here the concept of genetic algorithm is used which shows that random values are initiated and we find the best suited value to find the maxima using number of iterations.