Challenge

Week 5 - Genetic Algorithm

VVidu Bansal2 Dec 2022

AIM

Optimization Method using MATLAB
Genetic Algorithm

THEORY

Optimization

Optimization is a decision-making process, it helps to find the best results under a set of prioritized criteria or constraints. It is a procedure which is executed iteratively by comparing various solutions till an optimum or satisfactory solution is found. These include maximizing factors such as productivity, strength, reliability, efficiency, utilization, etc.

Techniques available to perform Optimization

Deterministic Method

They use specific rules for moving one solution to another. In this technique, the output of the model is fully determined by the parameter values and the initial conditions. Example - Stress analysis of the component.

Stochastic Method

These are gaining popularity due to certain properties which deterministic algorithms do not possess. Stochastic models possess some inherent randomness, it is a probabilistic approach.

The procedure followed by any Optimization process

Genetic Algorithm

The genetic algorithm is one of the optimization processes. A genetic Algorithm (GA) is a search–based optimization technique based on the principles of Genetics and natural selection. It is frequently used to find optimal or near-optimal solutions.

The genetic algorithm is a method for solving both constrained and unconstrained optimization problems that are 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 children for the next generation. Over successive generations, the population “evolves” toward an optimal solution. The genetic algorithm can address problems of mixed integer programming, where some components are restricted to be integer-valued.

How does GA work?

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

Selection rules select the individuals, called parents that contribute to the population of the next generation. The selection is generally stochastic and can depend on the individuals’ scores.
Crossover rules combine two parents to form children for the next generation.
Mutation rules apply random changes to individual parents to form children.

The genetic algorithm differs from a classical, derivative-based, optimization algorithm in two main ways, as summarized in the following table:

Classical Algorithm	Genetic Algorithm
Generates a single point at each iteration. The sequence of points approaches an optimal solution.	Generates a population of points at each iteration. The best point in the population approaches an optimal solution.
Selects the next point in the sequence by a deterministic computation.	Selects the next population by computation which uses random number generators.
Typically converges quickly to a local solution.	Typically takes many function evaluations to converge. May or may not converge to a local or global minimum.

Where GA is used?

Genetic Algorithms are primarily used in optimization problems of various kinds, but they are frequently used in other application areas as well.

The areas in which GA are frequently used are listed below:

Optimization – Genetic Algorithms are most commonly used in optimization problems wherein we have to maximize or minimize a given objective function value under a given set of constraints.
Economics – GA is also used to characterize various economic models like the cobweb model, game theory equilibrium resolution, asset pricing, etc.
Neural Networks – GA are also used to train neural networks, particularly recurrent neural networks.
Image Processing – GA is used for various digital image processing (DIP) tasks as well as dense pixel matching.

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 particularly given function.

CODE

MAIN CODE

% Genetic Algorithm %

close all
clear all
clc

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

% number of iterations
num_cases = 50;

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

% f = get_stalagmite(x,y);
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

tic
% Study 1 - Statistical behavior
for i = 1:num_cases
    [inputs, fopt(i)] = ga(@stalagmite, 2);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2);
end

study1_time = toc

% unbounded 
figure(1)
subplot(2,1,1)
surfc(x,y,-f)
hold on 
shading interp 
plot3(xopt,yopt,-fopt,'marker','o','MarkerSize',5,'MarkerFaceColor','r')
title('Unbounded Inputs')
subplot(2,1,2)
plot(-fopt)
xlabel('Iterations')
ylabel('Function Minimum')

tic
% Study 2 - Statistical behaviour - with upper and lower bounds
for i = 1: num_cases
    [inputs, fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2);
end

study2_time = toc

% bounded
figure(2) 
subplot(2,1,1)
surfc(x,y,-f)
hold on
shading interp
plot3(xopt,yopt,-fopt,'marker','o','MarkerSize',5,'MarkerFaceColor','r')
title('Bounded Inputs')
subplot(2,1,2)
plot(-fopt)
xlabel('Iterations')
ylabel('Function Minimum')

% Study 3 - increasing GA iterations
options = optimoptions('ga');
options = optimoptions(options,'PopulationSize',170);

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

study3_time = toc

% Optimised
figure(3)
subplot(2,1,1)
surfc(x,y,-f)
hold on
shading interp
plot3(xopt,yopt,-fopt,'marker','o','MarkerSize',5,'MarkerFaceColor','r')
title('Optimized Inputs')
subplot(2,1,2)
plot(-fopt)
xlabel('Iterations')
ylabel('Function Minimum')

FUNCTION CODE

% Stalagmite Function 

function [f] = stalagmite(input_vector)

f1x = (sin((5.1*pi).*input_vector(1) + 0.5)).^6;
f1y = (sin((5.1*pi).*input_vector(2) + 0.5)).^6;

f2x = exp((((input_vector(1) - 0.0667).^2)/0.64).*(-4*log(2)));
f2y = exp((((input_vector(2) - 0.0667).^2)/0.64).*(-4*log(2)));

f = -f1x*f1y*f2x*f2y;

end

OUTPUT

The first study ( Unbounded )

The second study (Bounded)

The third study (Optimized)

CODE EXPLANATION

Study 1 - Statistical Behaviour - UNBOUNDED

GA syntax

x = ga(fun,nvars)

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

nvars – Number of variables, specified as a positive integer. The solver passes row vectors of length nvars to fun.

fun – Objective function, specified as a function handle or function name. Write a objective function to accept a row vector of length nvars and return a scalar value.

Study 2 - Statistical Behaviour – WITH UPPER AND LOWER BOUNDS

GA Syntax

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

This 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.)

A – Linear inequality constraints, specified as a real matrix. A is a M-by-nvars matrix, where M is the number of inequalities.

A encodes the M linear inequalities

A*x <= b,

Where x is the column vector of nvars variables x(:), and b is a column vector with M elements.

b – Linear inequality constraints, specified as a real vector. b is an M-element vector related to the A matrix. If you pass b as a row vector, solvers internally convert b to the column vector b(:).

b encodes the M linear inequalities

A*x <= b,

Where x is the column vector of N variables x(:), and A is a matrix of size M-by-N.

Aeq – Linear equality constraints, specified as a real matrix. Aeq is an Me-by-nvars matrix, where Me is the number of equalities.

Aeq encodes the Me linear equalities

Aeq*x = beq,

Where x is the column vector of N variables x(:), and beq is a column vector with Me elements.

beq – Linear equality constraints, specified as a real vector. beq is an Me-element vector related to the Aeq matrix. If your pass beq as a row vector, solvers internally convert beq to the column vector beq(:).

beq encodes the Me linear equalities

Aeq*x = beq,

Where x is the column vector of N variables x(:), and Aeq is a matrix of size Meq-by-N.

lb – Lower bounds, specified as a real vector or array of doubles. lb represents the lower bounds element-wise in lb <= x <= ub.

Internally, ga converts an array lb to the vector lb(:).

ub – Upper bounds, specified as a real vector or array of doubles. ub represents the upper bounds element-wise in lb <= x <= ub.

Internally, ga converts an array ub to the vector ub(:).

Study 3 - INCREASING GA ITERATIONS

Options = optimoptions(‘ga’);

Options = optimopions(options,’PopulationSize’,170);

Option – PopulationSize

Description – Size of the population

Values – Positive integer | {50} when numberOfVariables <= 5, {200} otherwise | {min(max(10*nvars,40),100)} for mixed-integer problems

GA Syntax

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

This minimizes with the default optimization parameters replaced by values in options. (Set nonlcon = [] if no nonlinear constraints exist.) Create options using optimoptions.

nonlcon – Nonlinear constraints, specified as a function handle or function name. nonlcon is a function that accepts a vector or array x and returns two arrays, c(x) and ceq(x).

c(x) is the array of nonlinear inequality constraints at x. ga attempts to satisfy

c(x) <= 0

for all entries of c.

c(x) is the array of nonlinear inequality constraints at x. ga attempts to satisfy

ceq(x) = 0

for all entries of ceq.

Optimization options, are specified as the output of optimoptions or a structure. Optomoptions hides the options listed in italics.

Values in {} denote the default value.
{}* represents the default when there are linear constraints, and for MutationFcn also when there are bounds.
I* indicates default for integer constraints, or indicates special considerations for integer constraints.
NM indicates that the option does not apply to gamultiobj.

OUTPUT EXPLANATION

The above results show that the bounded samples with population size have an accurate solution. This is because the code shows the random samples which can start and end at random points.

To overcome the issue, the bounded samples method is used giving the lower and upper limits. (Therefore, it will take the values which are greater than the upper bound or less than the lower bound.)

This loop gives an output with different local maxima with bounded inputs. To conquer this problem, we need to increase the population size as it increases the probability to converge to a global maximum.

The global maximum of a function can be found by inverting the function. Find the minimum value of the inverted function, the negative of the minimum value will give the global maximum of the function.

REFERENCES

Week 5 - Genetic Algorithm

Ship work like this
in your own course.

Talk to a career counsellor

Ship work like thisin your own course.

Talk to a career counsellor

Ship work like this
in your own course.