Genetic Algorithm to find Global Maxima using MATLAB

1. AIM :

• To write a program to find global maxima in stalagmite function using solver ‘Genetic Algorithm’ in MATLAB.

2. THEORY :

1. Genetic Algorithm:

• A genetic algorithm is an optimization technique 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.
• Genetic Algorithm can be briefly broken down into 5 different steps as follows

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

Genetic Algorithm Flowchart:

2. Stopping Criteria:

• The algorithm terminates if the population has does not produce offspring which are significantly different from the previous generation. Then it is said that the genetic algorithm has provided a set of solutions to our problem.

3. Syntax for Genetic Algorithm:

Study 1: Statistical Behaviour

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

Study 2: Statistical Behaviour with constraints

x = ga(fun,nvars,A,b,Aeq,beq,lb,ub) defines a set of lower and upper bounds on the design variables, x, so that a solution is found in the range lb ≤ x ≤ ub. (Set Aeq=[] and beq=[] if no linear equalities exist.)

Study 3: Statistical Behaviour with constraints & increased population

x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,options) minimizes with the default optimization parameters replaced by values in options. (Set nonlcon=[] if no nonlinear constraints exist.) Create options using optimoptions.

4. Significance of Iterations:

• The purpose of iteration in GAs is to introduce diversity into the sampled population. They are used in an attempt to avoid local minimaby preventing the population of chromosomes from becoming too similar to each other, thus slowing or even stopping convergence to the global optimum.
• This reasoning also leads most GA systems to avoid only taking the fittestof the population in generating the next generation, but rather selecting a random set with a weighting toward those that are fitter.

3. FUNCTION TO BE EVALUATED :

4. CODE :

% Initial Stalagmite Function
function f = stalagmite(input_vector)
x=input_vector(1);
y=input_vector(2);

f1_x = (sin(5.1*pi*x + 0.5))^6;
f1_y = (sin(5.1*pi*y + 0.5))^6;

f2_x = exp(-4.*log(2)*((x-0.0667)^2)/0.64); 
f2_y = exp(-4.*log(2)*((y-0.0667)^2)/0.64);

f = -(f1_x*f1_y*f2_x*f2_y);
end

close all
clear all
clc

% Defining Inputs

x = linspace(0,0.6,150);
y = linspace(0,0.6,150);

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

% Initial Stalagmite

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

% Plot
surfc(xx,yy,-f)
shading interp

xlabel('x values')
ylabel('y values')
title('Initial Stalagmite')

[inputs, fval] = ga(@stalagmite, 2);

% Study 1 (Statistical behaviour)

tic
n = 50;
for i = 1:n
    [inputs, fopt(i)] = ga(@stalagmite,2);
    xopt1(i) = inputs(1);
    yopt1(i) = inputs(2);

end
study1_time = toc

% Plot
figure(1)
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
plot3(xopt1,yopt1,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('Unbound Inputs')
subplot(2,1,2)
plot(-fopt)
xlabel('Iterations')
ylabel('Maximum Value')

% Study 2 Statistical behaviour with Upper & Lower constrints

tic
n = 50;
for i = 1:n
    [inputs, fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
    xopt2(i) = inputs(1);
    yopt2(i) = inputs(2);

end
study2_time = toc

% Plot
figure(2)
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
plot3(xopt2,yopt2,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded Inputs')
subplot(2,1,2)
plot(-fopt)
xlabel('Iterations')
ylabel('Maximum Value')

% Study 3 Statistical behaviour with increased population size

options = optimoptions('ga');
options = optimoptions(options,'populationsize',500);
tic
n = 50;
for i = 1:n
    [inputs, fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],options);
    xopt3(i) = inputs(1);
    yopt3(i) = inputs(2);

end
study3_time = toc

% Plot
figure(3)
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
plot3(xopt3,yopt3,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded Inputs with increased population size')
subplot(2,1,2)
plot(-fopt)
xlabel('Iterations')
ylabel('Maximum Value')

5. BODY OF CONTENT :

• To start with, we create 1D matrix (x,y) including values 0 to 0.6 with 150 gaps using linspace command.
• Then convert it into a 2D matrix using meshgrid command.
• Take number of iterations as 50
• Write the stalagmite function with all the formulas given in the question.
• Now we plot the function using surface command to get a 3D plot.
• Provide the required labels and titles.

Studies:

• For each studies we used different syntax as mentioned above. Everything else remains the same.
• We also plot the optimum maximum value with respect to number of iterations.

6. OUTPUT :

Initial Stalagmite:

Study 1 Unbound Inputs:

Study 2 Bounded Inputs:

Study 3 Bounded Inputs with increased Population size:

Error Faced:

• Steps to overcome this Error

Changed the code from

plot3 (xopt1, yopt1, fopt,'marker','o','markersize',’5’)

To

plot3 (xopt3, yopt3,-fopt,'marker','o','markersize', 5)

7. CONCLUSION :

• The time taken to execute each study are as follows:

study1_time = 4.0173

study2_time = 6.2599

study3_time = 37.8231

• From all the studies it is concluded that there is more variations in first and second graphs as compared to that of third graph.
• This is because in Study 3, the plot is converged into a single peak (Global Maxima) and hence the variation in readings are very low.
• Therefore study 3 (Bounded Inputs with increased Population size) gives the most optimum solution.