Week 4.1 - Genetic Algorithm

AIM : to write a code in MATLAB to optimise the stalagmite function and to find global maxima and minima

Theory : A genetic algorithm (GA) is a method for solving both constrained and unconstrained optimization problems based on a natural selection process that mimics biological evolution. The algorithm repeatedly modifies a population of individual solutions. At each step, the genetic algorithm randomly selects individuals from the current population and uses them as parents 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 problems that are not well suited for standard optimization algorithms, including problems in which the objective function is discontinuous, nondifferentiable, stochastic, or highly nonlinear. Generates a population of points at each iteration. The best point in the population approaches an optimal solution Selects the next population by computation which uses random number generators.

PROCEDURE :

1. initially stalagmite function is defined in a separate script
2. a negative sign is used in front of the function to obtain the maxima of the funtion rather than minima
3. a nested for loop is utilized to iterate each of the elements
4. GA is used to determine the optimal of the function
5. plot is generated for different cases

The cases considered are:

1. Unbounded inputs
2. Bounded inputs - Restricted with upper and lower boubnds
3. Bounded inputs with options - increasing no of iterations by giving population size

STALAGMITE FUNCTION :

A stalagmite function generally refers to the function with which we are generating values over a stalagmite kind of surface for finding out the local and global maxima and minima of that particular given function.

ga : The GA is a stochastic global search method that mimics the metaphor of natural
biological evolution. GAs operate on a population of potential solutions applying
the principle of survival of the fittest to produce (hopefully) better and better
approximations to a solution. At each generation, a new set of approximations is
created by the process of selecting individuals according to their level of fitness in
the problem domain and breeding them together using operators borrowed from
natural genetics. This process leads to the evolution of populations of individuals
that are better suited to their environment than the individuals that they were
created from, just as in natural adaptation.
Individuals, or current approximations, are encoded as strings, chromosomes,
composed over some alphabet(s), so that the genotypes (chromosome values) are
uniquely mapped onto the decision variable (phenotypic) domain. The most
commonly used representation in GAs is the binary alphabet {0, 1} although other
representations can be used, e.g. ternary, integer, real-valued etc. Having decoded the chromosome representation into the decision variable domain,
it is possible to assess the performance, or fitness, of individual members of a
population. This is done through an objective function that characterises an
individual’s performance in the problem domain. In the natural world, this would
be an individual’s ability to survive in its present environment. Thus, the objectivefunction establishes the basis for selection of pairs of individuals that will be
mated together during reproduction.
During the reproduction phase, each individual is assigned a fitness value derived
from its raw performance measure given by the objective function. This value is
used in the selection to bias towards more fit individuals. Highly fit individuals,
relative to the whole population, have a high probability of being selected for
mating whereas less fit individuals have a correspondingly low probability of
being selected.
Once the individuals have been assigned a fitness value, they can be chosen from
the population, with a probability according to their relative fitness, and
recombined to produce the next generation. Genetic operators manipulate the
characters (genes) of the chromosomes directly, using the assumption that certain
individual’s gene codes, on average, produce fitter individuals. The recombination
operator is used to exchange genetic information between pairs, or larger groups,
of individuals. The simplest recombination operator is that of single-point
crossover.

Sytax for ga :

% Define stalagmite function

function [F] = stalagmite(input_vector)
a = input_vector(1);
b = input_vector(2);

f1 = (sin((5.1*pi*a)+0.5))^6;
f2 = (sin((5.1*pi*b)+0.5))^6;
f3 = exp((-4*log(2)*((a-0.0667)^2))/(0.64));
f4 = exp((-4*log(2)*((b-0.0667)^2))/(0.64));

F = -(f1*f2*f3*f4);
end

the negative sign will invert stalagmite plot which will eventually give the maxima plot

now we can proceed with the coding of the stalagmite function.

clear all 
close all
clc

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

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

%evaluating a 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

%study1 : statistical behaviour

tic
for i = 1:n
    [inputs,fopt(i)] = ga(@stalagmite,2);
        xopt(i) = inputs(1);
        yopt(i) = inputs(2);
end
study1_time = toc

figure(1)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
shading interp
xlabel('x-axis')
ylabel('y-axis')
title('statistical behaviour with unbound inputs')
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
subplot(2,1,2)
plot(-fopt)
xlabel('No. of iterations')
ylabel('Function maximum')
%study2 : statistical behaviour with lower bounds

tic
for i = 1:n
    [inputs,fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1,1]);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2);
end
study2_time = toc;

figure(2)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
shading interp 
xlabel('X-axis')
ylabel('Y-axis')
title('statistical behaviour with upper and lower bounds')
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
subplot(2,1,2)
plot(-fopt)
xlabel('No.of iterations')
ylabel('Function maximum')

%study3 : statistical behaviour with increasing iterations

options = optimoptions('ga');
options = optimoptions(options,'populationsize',300);

tic
for i =1:n
    [inputs,fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2);
end
study3_time = toc

figure(3)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
shading interp
xlabel('X-axis')
ylabel('Y-axis')
title('Staristical behaviour with increasing iterations')
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
subplot(2,1,2)
plot(-fopt)
xlabel('no.of iterations')
ylabel('function maximum')

RESULTS :

study 1 : statistical behaviour

study 2 : statistical behaviour with upper and lower bounds:

study 3 : statistical behaviour in increasing iterations of ga:

on rotating the plot we can clearly see that global maxima value as: X =0.06683 and Y = 0.06683