Week 5 - Genetic Algorithm

Objectives: -

1. Write a code in MATLAB to optimize the stalagmite function and find the global maxima of the function.

2. Explain the concept of genetic algorithm and also explain the syntax for ga in MATLAB.

3. Plot graphs for all 3 studies and F maximum vs no. of iterations.

Theory: -

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 was inspired by Charles Darwin and named the "Theory of evolution". The process of evaluation starts with the selection of fittest individuals from a population. Then they produce offspring that 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 of surviving. This process keeps on iterating and in the end, a generation with the fittest individuals will be found. This is the main working principle for the algorithm because, at each step, the genetic algorithm selects randomly from the current populations to be parents and uses them to produce the children for the next generation. Over successive generations, the population evolves towards an optimal solution. The genetic algorithm can be applied 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 working:-

• The algorithm begins by creating a random initial population.
• Then it scales the raw fitness scores to convert them into a more usable range of values. These scaled values are called expectation values.
• Then it selects members, called parents, based on their expectations.
• Along with the individual that has high fitness value, some of the individuals i the current population that have lower fitness are chosen as elite. These elite individuals are passed on to the next population. Also, it produces children by making random changes to a single parents-mutation-or by combining the vector entries of a pair of parents-crossover.
• It then replaces the current population with the children to form the next generation.
• Then it scores each member of the current population by computing its fitness value. These values are called the raw fitness scores
• then the algorithm stops when one of the stopping criteria is met.

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 vectors.

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 bounds are 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 optimizations or a structure help 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. The stalagmite function is the mathematical function that generates similar shapes to stalagmites. The stalagmite function is a two-variable function, mathematically it is represented as: -

MATLAB 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 MATLAB Code:-

%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;


%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;

% 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;


% 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 1 – Statistical behavior (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 the other is the coordinates of the minimum value. The minimum value of the 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 the other showing the function value.
• 'Plot3' command is used to plot a set of coordinates connected by line segments.
• 'tic' and 'toc' command are 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.

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 the results are plotted in figure 3.

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:-

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 clearer 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 between 0.99999980 to 0.99999985.

Conclusions: -

1. The ga solver is an inbuilt algorithm in MATLAB for optimization problems.
2. Using the solver with bounded inputs gets more accurate results.
3. The maximum value of the function lies between 0.99999983 to 0.99999985.