Week 5 - Genetic Algorithm

Genetic Algorithm: Optimization of stalagmite function

Objectives: -

• Write a code in MATLAB to optimise the stalagmite function and find the global maxima of the function.
• Expalin the concept of genetic algorithm in and also explain the syntax for ga in MATLAB.
• Plot graphs for all 3 studies and for F maximum vs no. of iterations.

The concept of Genetic Algorithm

A genetic algorithm is a natural process that is used for the selection of the fittest individuals. The main use of the genetic algorithm is for reproduction to produce offspring of the next generation, this process of selecting and reproducing the fittest individual is inspired by Charles Darwin’s and named it the "Theory of evolution".

The process of natural selection starts with the selection of the fittest individuals from a population. They produce offspring which inherit the characteristics of the parents and will be added to the next generation. If parents have better fitness, their offspring will be better than parents and have a better chance at surviving. This process keeps on iterating and in the end, a generation with the fittest individuals will be found.

Five phases are considered in a genetic algorithm. They are

Initial population
Fitness function
Selection
Crossover
Mutation

Initial Population- the process begins with a set of individuals which is called a Population. An individual is characterized by a set of parameters (variables) known as Genes. Genes are joined into a string to form a Chromosome (solution).

What is fitness function?

To determine the fitness function we are comparing how fittest an individual is, basically we are comparing the individuals with one another. It gives a fitness score to each individual and based on the fitness score the individual will be selected for reproduction. To perform the optimization in GAs we need to optimize the stalagmite function to find its minima. these have two inputs (x,y).

Selection -The idea of the selection phase is to select the fittest individuals and let them pass their genes to the next generation. Here, two pairs of individuals are selected according to their fitness score, higher will be the fitness the more chance is for the selection for reproduction.

cross over - cross over is a process of taking two-parents' solutions and producing a child from them. For each pair of parents to be mated, a crossover point is chosen at random from within the genes.

Offspring are created by exchanging the genes of parents among themselves until the crossover point is reached.

now the new offsprings are added to the population.

Mutation- Mutation is used to carry out the genetic diversity from one generation of the population of chromosomes to the next generation. This mutation process is too important to perform because if it is not performed then the chromosomes will be too similar to each other. The mutation occurs to maintain diversity within the population and prevent premature convergence and results in local minima.

Advantages of GAs

• GAs have various advantages that have made them immensely popular. These include −
• Does not require any derivative information (which may not be available for many real-world problems).
• Has very good parallel capabilities.
• Optimizes both continuous and discrete functions and also multi-objective problems.
• Provides a list of “good” solutions and not just a single solution.
• Useful when the search space is very large and there are a large number of parameters involved.
• Always provide good results over time.

Limitations of GAs

• If not implemented properly, the GA may not converge to the optimal solution.
• Where there is simple problem and for that the derivative values is known then this is not suited i.e genetic algorithm

Syntax for GA algorithm

The syntax used in this program are as follows: -

x = ga(fun,nvars)-finds a local unconstrained minimum, x, to the objective function, fun. nvars is the dimension (number of design variables) of fun, where, fun- objective function and nvars-number of variables.

x = ga(fun,nvars,A,b,Aeq,beq,lb,ub)- 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. When there is no linear inequalities we set Aeq and Beq as null vector.

x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon) or x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,intcon,options) requires that the variables listed in IntCon take integer values.

Where, A and b are A=[] and b=[] if no linear inequalities.

lb and ub are lower bound and upper bound. Lower bounds, and upper bound specified as a real vector or array of doubles.

nonlcon is a function that accepts a vector or array.

Intcon- integer variable vectors of positive integers.

options- Optimization options, specified as the output of optimoptions or a structure it helps in constraint tolerance by increasing the population size.

Stalagmite function

Stalagmite is a type of rock formation that rises from the floor of a cave due to the accumulation of material deposited on the floor from ceiling drippings. Stalagmite function is the mathematical function which generates similar shapes to stalagmites. Stalagmite function is a two-variable function, mathematically it is represented as: -

Code for 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)));
f1=f1x*f1y*f2x*f2y;
f=-f1;
end

Main code for optimization

%Creating the search space to be optimized
%one dimensional

clear all 
close all
clc

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

%creating two dimensional grid
[xx, yy] = meshgrid(x,y);
tic
%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

figure(1)
surfc(xx, yy, f)
shading interp
xlabel('x value');
ylabel('y value');

study_time=toc;

Stepwise explanation of the program

• Firstly, search space has been defined using the linspace command, and meshgrid command is used to create the 2d array.
• A sub program is created to evaluate stalagmite function and result is stored in f variable.
• Figure 1 is plotted to show the 3d representation of stalagmite function.

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

figure(2)
subplot(2,1,1)
hold on
surfc (x,y,-f)
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('unbounded inputs')
subplot(2,1,2)
plot(-fopt)
xlabel('no. of iterations');
ylabel('function max');

study_time1=toc;

Case study 1 – Statistical behaviour (unbounded)

• 'ga' solver is iterated for 150 times, and in this case no limits are provided.
• 'ga' solver returns two outputs, one is the minimum function value and other is the coordinates of the minimum value. Minimum value of function is stored in 'fopt(i)' and coordinates are stored in 'xopt' and 'yopt' respectively. This loop is run for 150 times and results are plotted.
• Figure 2 holds two plots, one showing the 3d representation of stalagmite with optimization results and other showing the function value.
• 'Plot3' command is used to plot a set of coordinates connected by line segments.
• 'tic' and 'toc' command is used to monitor the time taken to complete the iterations.
• There is no upper and lower limit provided, hence algorithm is searching outside the search space.

% second case (bounded inputs)
tic
for i = 1:n
    [inputs,fopt(i)]= ga(@stalagmite, 2,[],[],[],[],[0;0],[0.6;0.6]);
    xopt(i)=inputs(1);
    yopt(i)=inputs(2);
end

figure(3)
subplot(2,1,1)
hold on
surfc (x,y,-f)
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('bounded inputs')
subplot(2,1,2)
plot(-fopt)
xlabel('no. of iterations');
ylabel('function max');

study_time2=toc;

Case study 2 – bounded inputs

• In the second case 'ga' solver is run with upper and lower limits. This narrows down the search space and it becomes easier for the solver to find global minima.
• Four null vectors are passed in the solver syntax because there is no linear inequality involved in the stalagmite function.
• Again, the loop is run for 150 times and results are plotted in figure 3.

% third case (bounded inputs with increased population)

tic
options=optimoptions('ga');
options=optimoptions(options,'PopulationSize',500);

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

figure(4)
subplot(2,1,1)
hold on
surfc (x,y,-f)
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('bounded inputs with increases population')
subplot(2,1,2)
plot(-fopt)
xlabel('no. of iterations');
ylabel('function max');

study_time3=toc;

Case study 3 – bounded inputs with increased population size

• In the third case the 'ga' solver is run with the bounded inputs along with the increased population size.
• PopulationSize specifies how many individuals are there in each generation. With a large population size, the genetic algorithm searches the solution space more thoroughly, thereby reducing the chance that the algorithm returns a local minimum that is not a global minimum. However, a large population size also causes the algorithm to run more slowly.
• Optimoptions command is used to create optimization options.
• options= optimoptions(SolverName) returns a set of default options for the SolverName

Results and discussion

1) Plot for stalagmite function

The above plot shows the 3d representation of stalagmite function. A function named stalagmite has been created to evaluate the mathematical expression and store the result in the form of an array. surfc(X,Y,Z) has been used to create a three-dimensional surface plot with a contour plot underneath.

2) Plot for unbounded inputs

As from the above plot it can be observed that with the unbounded inputs ga solver is unable to calculate the global maxima. Due to random sampling the maximum value ranges between 0.1 to 1, hence further optimization is needed.

3) Plot for bounded inputs

The above plot shows that using 'the bounded inputs' gives more clear result than the previous one. Here the maximum value ranges between 0.7 to 1. But still optimization is needed.

4) Plot for bounded inputs with increased population size

With the increased population size we get the most accurate result which is in between 0.99999980 to 0.99999985.

Conclusions: -

• The ga solver is an inbuilt algorithm in matlab for optimization problem.
• Using the solver with bounded inputs gets more accurate results.
• The maximum value of the function lies between 0.99999983 to 0.99999985.