Genetic Algorithm

Genetic Algorithm

Genetic Algorithm (GA) is a metaheuristic inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms (EA). Genetic algorithms are commonly used to generate high-quality solutions to optimization and search problems by relying on biologically inspired operators such as mutation, crossover and selection.

The genetic algorithm is a method for solving both constrained and unconstrained optimization problems that is based on natural selection, the process that drives biological evolution. The genetic algorithm repeatedly modifies a population of individual solutions. At each step, the genetic algorithm selects individuals from the current population to be parents and uses them to produce the children for the next generation. Over successive generations, the population "evolves" toward an optimal solution. You can apply the genetic algorithm to solve a variety of optimization problems that are not well suited for standard optimization algorithms, including problems in which the objective function is discontinuous, nondifferentiable, stochastic, or highly nonlinear. The genetic algorithm can address problems of mixed integer programming, where some components are restricted to be integer-valued.

ga() - is used to find minimum of function using genetic algorithm.

SYNTAX of ga() -

z = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,intcon,options)

where,

1. z is the minima
2. fun is the function to be called.
3. nvars indicates the no of variables used.
4. A and b are used to indicate any kind inequalities that exist in the function.
5. Aeq and Beq also denotes the inequalities.
6. lb = lower bound.
7. ub = upper bound.
8. nonlcon gives a two vectors representing inequalities and equalities.
9. options is used to perform additional operations like increasing population size. This is done with the help of "optimoptions".

Stalagmite function

Equations

Code

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;
            t1 = ((x-0.0667).^2)/(0.64);
            f2_x = exp(-4.*log(2)*t1);
            t2 = ((y-0.0667).^2)/(0.64);
            f2_y = exp(-4.*log(2)*t2);

            f = -(f1_x.*f2_x.*f1_y.*f2_y); % The Negative sign denotes he inverse of the Stalagmite function and is added in order to find the Maximum value.
                                          
end

Finding global maxima

This is done in 3 cases. They are,

1. Unbounded Inputs

2. Bounded Inputs

3. Bounded Inputs with altered population size

Code

clear all
close all
clc

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

%creating a 2D 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

%Case 1 - Unbounded inputs
tic %start timer
num_cases = 300
for i = 1:num_cases
    [input_vector, fopt1(i)] = ga(@stalagmite, 2);
    xopt1(i) = input_vector(1);
    yopt1(i) = input_vector(2);
end
study_time_1 = toc %stop timer

figure(1)
subplot(2,1,1) %1st plot under subplot
hold on
surfc(xx,yy,-f) %surface plot of ga in unbounded inputs and -f is used as the stalagmite func was modified for max func value 
shading interp %removes grid lines on plot and performs shading instead of the lines
plot3(xopt1,yopt1,-fopt1,'marker', '*', 'markersize', 5, 'markerfacecolor', 'red') %'-fopt' is used as we are finding the maxima
title('Unbounded inputs')
subplot(2,1,2) % 2nd Plot under subplot
plot(-fopt1)  %plots the maximum func value returned for each iteration. we add '-' operator as the stalagmite func was modified for max func value
xlabel('Iterations')
ylabel('Function Maxima')

%Case 2 - Bounded inputs
tic
for i=1:num_cases
    [input_vector, fopt2(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
     xopt2(i) = input_vector(1);
     yopt2(i) = input_vector(2);
end
study_time_2 = toc %stop timer

figure(2)
subplot(2,1,1) %1st plot under subplot
hold on
surfc(xx,yy,-f) %surface plot of ga in unbounded inputs and -f is used as the stalagmite func was modified for max func value
shading interp %removes grid lines on plot and performs shading instead of the lines
plot3(xopt2,yopt2,-fopt2,'marker', '*', 'markersize', 5, 'markerfacecolor', 'red') %'-fopt' is used as the stalagmite func was modified for max func value
title('Bounded inputs')
subplot(2,1,2) % 2nd Plot under subplot
plot(-fopt2) %plots the maximum func value returned for each iteration. we add '-' operator as the stalagmite func was modified for max func value
xlabel('Iterations')
ylabel('Function Maxima')

%Case 3 - Specified Population Size
options = optimoptions('ga');
options = optimoptions(options, 'PopulationSize', 450);

tic
for i=1:num_cases
    [input_vector, fopt3(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
     xopt3(i) = input_vector(1);
     yopt3(i) = input_vector(2);
end
study_time_3 = toc %stop timer

figure(3)
subplot(2,1,1) %1st plot under subplot
hold on
surfc(xx,yy,-f) %surface plot of ga in unbounded inputs and -f as the stalagmite func was modified for max func value
shading interp %removes grid lines on plot and performs shading instead of the lines
plot3(xopt3,yopt3,-fopt3,'marker', '*', 'markersize', 5, 'markerfacecolor', 'red') %'-fopt' is used as as the stalagmite func was modified for max func value
title('Bounded inputs with altered population size')
subplot(2,1,2) % 2nd Plot under subplot
plot(-fopt3) %plots the maximum func value returned for each iteration. we add '-' operator as the stalagmite func was modified for max func value
xlabel('Iterations')
ylabel('Function Maxima')

Results and Explaination

Case 1 - Unbounded Input

Study Time - 10.5212

From the image below, it can be assertained that the maxima values are outside the staglamite which makes this case inaccurate.

Case 2 - Bounded Input

Study Time - 16.8923

From the image below, it can be assertained that the maxima values are inside the staglamite which makes this case accurate than the previous case. But this case is not yet fully accurate, as there are multiple points.

Case 3 - Bounded inputs with altered population size

Study Time - 114.9772

From the image below, it can be seen that there is only maxima value is inside the staglamite which makes this case accurate than the previous case. The maxima value is 0.99999985

Refrences

1. https://in.mathworks.com/help/gads/ga.html

2. https://en.wikipedia.org/wiki/Genetic_algorithm

3. https://in.mathworks.com/discovery/genetic-algorithm.html?s_tid=srchtitle_genetic%2520algorithm_2