Week 4.1 - Genetic Algorithm

Aim : Explanation about Genetic algorithm and syntax for Genetic algorithm in MATLAB and To Write a code in MATLAB to optimise the stalagmite function and find the global maxima of the function.

Explanation :

Before knowing about genetic algorithm ,we will know about global optimization

Global optimization :

It is intended to locate a global optima, it is also called as global search refers to searching for the global optima.

It is suited to traversing the entire input search space and getting close to the extrema of the function.

Global optimization is a branch of applied mathematics and numerical analysis that attempts to find the global minima or

maxima of a function or a set of functions on a given set.

Optimization : It is the process of selection from the set of values for the imposed targets and the constraints.

It's been very difficult to manage and select the appropriate range of values for the defined targets and constraints.

• To make this process ease, optimization techinques helps us to find a way to get the best out of it.

Population algorithms : An algorithm that maintains an entire set of candiate solutions, and each solution corresponds to a

unique point in the search space of the problem known as population based algorithm.

Genetic algorithm :

It is a method for solving both constrained and unconstrained optimization problems that is based on natural selection.

which generates solutions to optimization problems using techniques inspired by natural evolution ,such as

1) Selection - selecting the best-fit individuals(parents)

2) crossover - Two best-fit individuals combine to form children for next generation

3) Mutation - It adds to the diversity of a population

Simply we can say that how the genetic algorithm works

Procedure :

• Selecting the best-fit individuals for reproduction
• Breed new individuals through crossover and mutation operation to give birth of childrens
• Again evaluating the individuals fitness of new individuals
• Replace least-fit population with new individuals.

At each step,the genetic algorithm uses the current population to create the children that make up the next generation, in these group of individuals in the current population ,called parents. The algorithm usually selects individuals that have better fitness values as parents.

The types of children produced for next generation from the current population parents as ,

• Elite child - individuals having best fitness values
• Crossover child - created by combining the parents
• Mutation child - created by doing random changes to the single parent

Stopping conditions for the Genetic algorithm :

The genetic algorithm uses the following options to determine when to stop,

• Maxgenerations - The algorithm stops when the number of generations reaches maxgenerations.

The algorithm stops as soon as any one of these conditions is met.

Syntax for Genetic algorithm :

x = ga(fair,nvars,A,b,Aeq,beq,lu,ub,nonicon,options)

here,

fair is a Objective function

nvar is a Number of variables (specified as positive integer)

A is a Linear inequality constraints (A = Real matrix)

b is a Linear inequality constraints (b = Real vector)

Aeq, beq is a Linear equality constraints (A is Real matrix, b is Real vector)

lb,ub is a Lower bounds and upper bounds

nonicon is a Nonlinear constraints

options is a option to change population

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

Now we are going to write a code,

1. we know that 'close' this will close all figures and plots
2. 'clear' this will clear all the data in work space
3. 'clc' this will clear the data in command window
4. Next give the possible range of inputs for the GA solver
5. The inputs will be considered as the space for the algorithm to solve
6. Then,Use a for loop it will be helpful to cover the two dimensional inputs both (x and y) and plotting
7. For every point in the xy plane stalagmite function will be called to calculate the 'f' value
8. Using the meshgrid and surface functions
9. Now coding the stalagmite function
10. This function creates the contour of peaks for the defined input variables with suitable range
11. Now performing unbounded GA study
12. Then performing bounded GA study
13. Finally performing bounded GA study with population size

code :

Now we are coding for Unbounded Genetic algorithm,

clear
close
clc

% defining inputs
x = linspace(0,0.6,100);
y = linspace(0,0.6,100);

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

for i = 1:length(x)
     for j = 1:length(y)
         inputs(1) = xx(i,j);
         inputs(2) = yy(i,j);
         f(i,j) = stalagmite2(inputs);
     end
end

figure
surf(xx,yy,f)
shading interp

%  Study1 Statistical behaviour
tic
for i = 1:50
    [inputs,fopt(i)] = ga(@stalagmite2,2);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2);
end
study1_time = toc;

figure(1)

surf(x,y,-f)
shading interp
hold on
plot3(xopt,yopt,-fopt,'marker','o','markersize',10)
xlabel('x-axis')
ylabel('y-axis')
zlabel('z-axis')
title('Unbounded inputs')

Here it is stalagmite function code :

function [f] = stalagmite2(inputs)
x = inputs(1);
y = inputs(2);

f1x = (sin((5.1*pi*x)+0.5))^6;
f1y = (sin((5.1*pi*y)+0.5))^6;
f2x = exp(-4*log(2)*(((x-0.667)^2)/0.64));
f2y = exp(-4*log(2)*(((y-0.667)^2)/0.64));

f = -(f1x*f1y*f2x*f2y);
end

It is one of the 'test functions' which is used to validate the performance

Result :

In the above figure GA syntax the lower and upper bounds are not defined, having a high probability for getting inaccurate results.

When the bounds are not confined the results of GA tends to be random. The outputs tends to be unstable.

Now coding for Bounded Genetic algorithm

code :

% Study2 - Statistical behaviour - with upper and lower bounds
    tic
for i = 1:50
    [inputs,fopt(i)] = ga(@stalagmite2,2,[],[],[],[],[0;0],[0.6;0.6]);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2);
end
study2_time = toc;

figure(2)

surf(x,y,-f)
shading interp
hold on
plot3(xopt,yopt,-fopt,'marker','o','markersize',10)
xlabel('x-axis')
ylabel('y-axis')
zlabel('z-axis')
title('Bounded inputs')

Result :

In the above figure GA syntax defined with lower and upper bounds.

Defined bounds of x from 0 to 0.4 and bounds of y from 0 to 0.4 it results in the better optimization.

Now plotting for bounded inputs with increasing population size

code :

% Study 3 Increasing Genetic algorithm
options = optimoptions('ga');
options = optimoptions(options,'PopulationSize',200);
tic
for i = 1:50
    [inputs,fopt(i)] = ga(@stalagmite2,2,[],[],[],[],[0;0],[0.6;0.6],[],[],options);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2);
end
study3_time = toc;

figure(3)

surf(x,y,-f)
shading interp
hold on
plot3(xopt,yopt,-fopt,'marker','o','markersize',10)
xlabel('x-axis')
ylabel('y-axis')
zlabel('z-axis')
title('Bounded inputs with modified population size')

Result :

In the above figure population size denotes the number of data points initialised in the space for the simulation. Population size can be added as the feature using options in the ga syntax.

Increasing the population size until the single optimum point is achived.

Final output for global maxima :

Errors while programming :

1) Got error asking that vectors must be the same length

got solved after using in line27 fopt(i)

2) Got an error saying that unrecognized variable name (optoins), it's actually spelling mistake

got resolved after using correct spelling

3) Its showing that wrong graph for figure 1 i don't know where i missed

after i solved using negative sign (-) for that line no 35 (-f).

Reference i used MATLAB help desk to understand about GA and got help from online session class

Conclusion : Coded in MATLAB to optimise the stalagmite function and finded the of the function a global maxima Explanation about GA and ga syntax

Plotted the graph for three studies for F maximum vs no. of iterations.