Week 4 - Genetic Algorithm

1. The algorithm begins by creating a random initial population.

2. 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. To create the new population, the algorithm performs the following steps:

   1. Scores each member of the current population by computing its fitness value. These values are called the raw fitness scores.

   2. Scales the raw fitness scores to convert them into a more usable range of values. These scaled values are called expectation values.

   3. Selects members, called parents, based on their expectation.

   4. Some of the individuals in the current population that have lower fitness are chosen as elite. These elite individuals are passed to the next population.

   5. Produces children from the parents. Children are produced either by making random changes to a single parent—mutation—or by combining the vector entries of a pair of parents—crossover.

   6. Replaces the current population with the children to form the next generation.

3. The algorithm stops when one of the stopping criteria is met.

In MATLAB, we can use the Global Optimization Toolbox in order to get the global minima as output for the given fucntion.

GENETIC ALGORITHM - SYNTAX

• 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.
• x= ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,options) minimizes with the default optimization parameters replaced by values in options. (Set nonlcon=[] if no nonlinear constraints exist.)
• 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. (Set Aeq=[] and beq=[] if no linear equalities exist.)

STALAGMITE FUNCTION

A stalagmite is a type of speleothem that rises from the floor of a limestone cave due to the dripping of mineralized solutions and the deposition of calcium carbonate. The function we have considered GA optimization is similar to stalagmite, hence the name stalagmite function.

The following is the stalagmite function that is used in this project.

Implemetation

The following is the code for the stalagmite function which is called in the main program

function [f] = stalagmite (input_vector)
x=input_vector(1);
y=input_vector(2);
f_1x= (sin((5.1*pi*x)+0.5))^6;
f_1y= (sin((5.1*pi*y)+0.5))^6;
f_2x= exp(-4*log(2).*((x-0.0667).^2)./0.64);
f_2y= exp(-4*log(2).*((y-0.0667).^2)./0.64);
f=-(f_1x*f_1y*f_2x*f_2y);
end

The stalagmite function is divided into small parts as whole which is a product of the parts.

The output is taken as negative because the as the ga function always results the minimum value so to provide the output as a maximum value we consider it to be negative.

Now the main program is classified into 3 studies with an initial usage of the ga function. The following is the code for the main program.

clear all
close all
clc

%defining our search space
x= linspace(0,0.6,150);
y= linspace(0,0.6,150);
num_cases=50;

%create 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(input_vector);
    end
end
figure(1)
surfc(x,y,-f)
shading interp
xlabel('x value')
ylabel('y value')

[inputs,fval]=ga(@stalagmite,2)
tic
%study 1-statistical behavior
for k=1:num_cases
    [inputs,fopt(k)]=ga(@stalagmite,2);
    xopt(k)=inputs(1);
    yopt(k)=inputs(2);
end
study1_time = toc

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('iterations')
ylabel('function maximum')

%study 2- with upper and lower bounds
tic
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

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('iterations')
ylabel('function maximum')

%study 3 increasing ga iterations

 options=optimoptions('ga')
 options=optimoptions(options,'populationsize',400);
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
 
 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('bounder inputs with modified population size')
 subplot(2,1,2)
 plot(-fopt)
 xlabel('iterations')
 ylabel('function maximum')
 
fprintf(' The Function value')
disp(-fopt(num_cases));
inputs

The x and y values are taken as a loop with a number of cases as mentioned.

The initial code is to run the ga code and to know that the input final value varies for all the iterartion when we run the code. So to get the maximum value and also the input values.

Study 1 is to find the statistical behaviour with the unbounded boundaries as a result we would be getting many values of the local maxima and minima values as points.

Study 2 is to find the statistical behaviour with the bounded boundaries with lower and upper boundaries as a result we would get the minimum number of local maxima and minima values as points.

Study 3 is to find the statistical behaviour with the bounded boundaries by increasing the population size of the ga function and we would be getting the least number of the local maxima and minima values as points.

As the number of cases i.e. population increases there by the number of the local maxima and minima values would be reduced andd finally the final global maxima or minima is obtained in the plot. As per the above code we would be finding the global maxima.

In the above code, inorder to find the time taken for the each study we use the function tic-toc. We use the subplot to plot 2 graphs in a single figure window and also plot3 is used to plot the 3 dimensional figure with thte surface function.

Finally the global maxima and the inputs are printed at the end of the program

The following the outputs for the above codes.

The above is the initial ga code run by considering the input range.

The above is figure that shows, Study 1: statistical behaviour with unbounded inputs.

The above is figure that shows, Study 2: Statistical behaviour with bounded inputs - lower and upper boundaries.

The above is figure that shows, Study 3: Statistical behaviour with bounded inputs by increasing the population size for the ga function.

The following are the results for the above code in the command window and the workspace.

The errors faced while coding are some typo's which are immediately corrected asa detected in the command window. The following is the screenshot showing the error faced while coding.

Conclusion:

As the genetic algorithm used in the program will always be giving the global minimum value, so to find the maximum value we need to inverse the function to get the result.

References:

• https://in.mathworks.com/discovery/genetic-algorithm.html?s_eid=PEP_12669
• https://in.mathworks.com/help/gads/examples/genetic-algorithm-options.html
• https://in.mathworks.com/help/gads/how-the-genetic-algorithm-works.html
• https://in.mathworks.com/help/gads/ga.html#d120e41882
• https://www.youtube.com/watch?v=1i8muvzZkPw&t=110s
• https://towardsdatascience.com/introduction-to-optimization-with-genetic-algorithm-2f5001d9964b