Week 4 - Genetic Algorithm

AIM : Find the Global Maxima of the Function

Objective : Write a code in MATLAB to optimise the stalagmite function and find the global maxima of the function.

Defination :

Stalagmite Function: Creating a function stalagmite by passing the input array as the argument for the variables x and y. The output of the function is stored in the variable sol. ... For assigning values to variables input(1) and input(2), two for loops are used.

Genetic Algorithm : 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.

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.

How Genetic Algorithm Works : The algorithm begins by creating a random initial population. The algorithm then creates a sequence of new populations. At each step, the algorithm uses the individuals in the current generation to create the next population.

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 at random 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.

The genetic algorithm uses three main types of rules at each step to create the next generation from the current population:

Fitness Functions

The fitness function is the function you want to optimize. For standard optimization algorithms, this is known as the objective function. The toolbox software tries to find the minimum of the fitness function.

Write the fitness function as a file or anonymous function, and pass it as a function handle input argument to the main genetic algorithm function.

A population is an array of individuals.

At each iteration, the genetic algorithm performs a series of computations on the current population to produce a new population. Each successive population is called a new generation.

SYNTAX OF GA IN MATLAB

The syntax of GA in MATLAB is as follows:

x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,IntCon,options)

Let us take the example of the following function to understand the syntac of GA:

" f(x) = 100*((x1)^2 - (x2)^2) + (1 - x(1)^2)^2 ".

The function is subjected to the following constraints:

1. Linear Constraints:

x(1) + x(2) > = 1.

x(2) - x(1) = 5.

2. Non-linear Constraints:

x(1)*x(2) + x(1) - x(2) + 1.5 <= 0.

10 - x(1)*x(2) <= 0.

3. Bounds:

0 <= x(1) <= 1.

0 <= x(2) <= 2.

'x' is the variable to store the output of the Genetic Algorithm.

'fun' is the function handle to call the function.

'A' and 'b' are used to represent the linear inequalities of the the function, if any. Otherwise, they are

set as empty, '[]'.

As per the above constraints:

A = [1 1];

b =1;

'Aeq' and 'beq' are used to represent the equality constraints.

As per the above constraints:

Aeq = [-1 1];

beq = 5;

'lb' and 'ub' are used to specify the upper and the lower bounds of the variables of the function.

As per the above values:

lb = [0,0];

ub = [1,1];

'nonlcon' is a function that is specified using a function handle. A separate function code must be

written as per the constraints of the function.

This function gives two arrays 'c' and 'Ceq' as its outputs.

'c' stores the values of the equality constraints.

'Ceq' stores the values of the inequality constraints.

'IntCon' is used to specify the Integer Constraint, such that the value of the function is an integer.

'options' is used to provide the values of the default parameters using named parameters, if it is

required to replace the default parameters. This is done by using the function 'optimoptions'.

MATLAB code to optimise the stalagmite function and find the global maxima of the function.

close all
clear all
clc

% Defining our serach space

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

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

% surfc(x,y,f)
% shading interp
% [x, f] = ga(@stalagmite_func,2)

% study 1 - Statisical Behaviour 

n_iteration = 50; 

tic
for i = 1:n_iteration
    [input1,fopt1(i)] = ga(@stalagmite_func,2);
    xopt1(i) = input1(1);
    yopt1(i) = input1(2);
end
study_time1 = toc;

% plotting
figure(1)
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
plot3(xopt1,yopt1,-fopt1,'marker','o','markersize',5,'markerfacecolor','r')
title('Unbounded Points')
subplot(2,1,2)
plot(fopt1)
xlabel('Iteration')
ylabel('Function maximum')

%study2 - statistical behaviour with upper and lower bounds

n_iteration = 50;

tic

for i = 1:n_iteration
    [input2,fopt2(i)] = ga(@stalagmite_func,2,[ ],[ ],[ ],[ ],[0,0],[1,1]);
    xopt2(i) = input2(1);
    yopt2(i) = input2(2);
end

study_time2 = toc;

% plotting
figure(2)
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
plot3(xopt2,yopt2,-fopt2,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded Points')
subplot(2,1,2)
plot(fopt2)
xlabel('Iteration')
ylabel('Function maximum')

%study3 increasing the population size

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

tic
n_iteration = 50;

for i = 1:n_iteration
    [input3,fopt3(i)] = ga(@stalagmite_func,2,[ ],[ ],[ ],[ ],[0 ,0],[1,1],[ ],[ ],options);
    xopt3(i) = input3(1);
    yopt3(i) = input3(2);
end
study_time3 = toc;

% plotting
figure(3)
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
plot3(xopt3,yopt3,-fopt3,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded inputs with modified population size')
subplot(2,1,2)
plot(fopt2)
xlabel('Iteration')
ylabel('Function maximum')

MATLAB code for stalagmite function

function [f] = stalagmite_func(input_vector)
          
          x = input_vector(1);
          y = input_vector(2);
          
          term1 = (sin((5.1*pi*x)+ 0.5))^6;
          term2 = (sin((5.1*pi*y)+ 0.5))^6;
          term3 = exp(-4*log(2)*((x-0.0667)^2/0.64));
          term4 = exp(-4*log(2)*((x-0.0667)^2/0.64));
          
          f = -(term1*term2*term3*term4);
end

Output of Study 1:Statisical Behaviour

Output Study 2: Statistical behaviour with upper and lower bounds

Output Study 3 Increasing the population size

Explanation to the code

1. first i gave the limits of search space also called genotype in genetic algorithm
2. specified every node within the search space using meshgrid command
3. to found optimised value created stalagmite function seperately with 2 variables of x,y
4. then called the ga function to solve stalagmite function
5. to get maximum value we used negative sign in function because ga only provides min value
6. then run the program with different iteration in three seperate studies then ploted necessary plots and figures.

The errors while programming

Here i made syntax error then correct it.

References:

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

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

https://in.mathworks.com/help/gads/genetic-algorithm.html?s_tid=CRUX_lftnav

Thank you.