Week 4 - Genetic Algorithm

Introduction:

The genetic algorithm is inspired by the process that drives biological evolution. The process of evolution starts with the selection of fittest individuals from a population. Then 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 at the end, a generation with the fittest individuals will be found. And this is the main working principle for the algorithm because at each step, the genetic algorithm selects randomly from the current population to be parents and uses them to produce the children for the next generation. Over successive generations, the population evolves toward 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 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 at the next generation.
• 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.

Algorithm working sequence:

Then 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, it uses the fitness function which is the function you want to optimize. For standard optimization algorithms, this is known as the objective function. The toolbox software tries to find the minimum of the fitness function.

The algorithm performs the following steps:

• 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 expectation.
• Along the individual that have high fitness value, 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. Also it produces Children by making random changes to a single parent—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

Fig:Mechanism for producing children

Fig:Final answer developing with iterations.

Input function:

f(x,y)=f1,x⋅f2,x⋅f1,y⋅f2,yf(x,y)=f1,x⋅f2,x⋅f1,y⋅f2,y

where,

f1,x=[sin(5.1πx+0.5)]6f1,x=[sin(5.1πx+0.5)]6

f1,y=[sin(5.1πy+0.5)]6f1,y=[sin(5.1πy+0.5)]6

f2,x=exp[−4ln(2)(x−0.0667)20.64]f2,x=exp[-4ln(2)(x-0.0667)20.64]

f2,y=exp[−4ln(2)(y−0.0667)20.64]f2,y=exp[-4ln(2)(y-0.0667)20.64]

Main code:

clear all
close all 
clc
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
num_cases=50;
% Creating a 2D Mesh
[xx yy] = meshgrid(x,y);

% Evaluating Stalagmite Function
for i = 1 : length(xx);
    for j = 1 : length(yy);
        input_value(1)= xx(i,j);
        input_value(2) = yy(i,j);
        f(i,j) = stalagmite(input_value);
    end
end
%unbounded statistical behaviour
tic
for i=1:num_cases;
    [inputs1,fopt1(i)]=ga(@stalagmite,2);
    xopt(i)=inputs1(1);
    yopt(i)=inputs1(2);
end
study1_time=toc;
figure(1)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
xlabel('x-value')
ylabel('y-value')
zlabel('function value')
shading interp
plot3(xopt,yopt,-fopt1,'marker','o','markersize',5,'markerfacecolor','r')
title('Unbounded Statistical Behvaiour')
subplot(2,1,2)
plot(-fopt1)
xlabel('iterations')
ylabel('function maximum')
%statastical behaviour with upper and  lower bound
tic;
for i=1:num_cases;
    [inputs2,fopt2(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
    xopt(i)=inputs2(1);
    yopt(i)=inputs2(2);
end
study2_time=toc;
figure(2)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
xlabel('x-value')
ylabel('y-value')
zlabel('function value')
shading interp
plot3(xopt,yopt,-fopt2,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded Statistical Behvaiour')
subplot(2,1,2)
plot(-fopt2)
xlabel('iterations')
ylabel('function maximum')

%increasing Ga population size
options=optimoptions('ga');
options=optimoptions(options,'populationsize',170);
tic
for i=1:num_cases;
    [inputs3,fopt3(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
    xopt(i)=inputs3(1);
    yopt(i)=inputs3(2);
end
study3_time=toc;
figure(3)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
xlabel('x-value')
ylabel('y-value')
zlabel('function value')
shading interp
plot3(xopt,yopt,-fopt3,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded Statistical Behvaiour with Increased Population Size')
subplot(2,1,2)
plot(-fopt3)
xlabel('iterations')
ylabel('function maximum')   
Total_Time = study1_time+study2_time+study3_time
fprintf ('n The Results Are Below :')

fprintf ('nn Study 1 : Unbounded Statistical Behvaiour')
fprintf ('nn The Time taken for the study 1 is : %f',study1_time)
fprintf ('n The Co-ordinates of x and y for the Global Maxima of the Function are : %f,%f',inputs1(1),inputs1(2))
fprintf ('nn The Global Maxima of the Function is : %f',-(mean(fopt1)))

fprintf ('nn Study 2 : Bounded Statistical Behvaiour')
fprintf ('nn The Time taken for the study 2 is : %f',study2_time)
fprintf ('n The Co-ordinates of x and y for the Global Maxima of the Function are : %f,%f',inputs2(1),inputs2(2))
fprintf ('nn The Global Maxima of the Function is : %f',-(mean(fopt2)))

fprintf ('nn Study 3 : Bounded Statistical Behvaiour with Increased Population Size')
fprintf ('nn The Time taken for the study 3 is : %f',study3_time)
fprintf ('n The Co-ordinates of x and y for the Global Maxima of the Function are : %f,%f',inputs3(1),inputs3(2))
fprintf ('nn The Global Maxima of the Function is : %f',-(mean(fopt3)))

fprintf ('nn The Total Time taken to Complete the total Study = %f',Total_Time)

Main code explaination:

• First, Linspace command is used to define x and y with 150 elements between zero and 0.6 including the bounds

• Then num_cases is set which will be used as counter for iterations to 50
• Then a 2D grid is made using meshgrid command is created from x and y input to be outputted to xx and yy
• Then for loop is used to solve the genetic algorithm for every element in the 2D mesh grid
• The length of rows and columns (which have equal length) are used as counters
• Then the input vector is declared as ga requires input vector which is each value in the mesh grid
• Then output of stalagmite function is stored in matrix
• Then tic command is used to start a timer
• Then for loop bounded by the number of iterations is formed
• Then ga code is entered for unbounded statistical study which have the following format :

[inputs,fopt] = ga(fun,nvars)

Inputs represent the values of parameters x and y for which the function has the least value (fopt)

fun - The function to be optimized, in this case Stalagmite

nvars - the number of design variables, in this case only x and y are the variables to be plotted

• Then smallest (minimum ) value of the function for each iteration is outputted and its x and y coordinates Which are stored in separate variable
• Then toc command is used to stop the timer and the output is stored in study_time 1
• Then figure 1 is plotted by the following steps:
• First subplot command is used to partition the plot window in order to draw more than one plot in the same windows ,two rows and one column are specified and then the position of each plot is selected
• Then Hold on command is used to prevent plot from being removed
• The surfc command is used to plot contour with xx value and yy value from the mesh grid as input and negative optimum value is used because we need to maximize the function
• Then x, y ,and z axis are labeled
• Then shading interp is used to smoothen the function plot and to remove the grid lines
• Then plot 3 command is used to plot a point in 3 dimensions,here it will plot -fopt because we need the maximum value of the function not the minimum
• Then the graph title is selected
• Then -fopt value of the function is plotted on the second plot in the second row
• Then its x and y axis are labeled
• Then the same study is made but this time it is bounded (has lower and upper limit) which requires the same commands and steps except the ga command which have the following format:

[inputs,fopt] = ga(fun,nvars,A,b,Aeq,beq,lb,ub)

Inputs, fopt,fun and nvars are the same as Study 1
A - Linear inequality constraints : real matrix, if there are none, then []
b - Linear inequality constraints : real vector, if there are none, then []
Aeq - Linear equality constraints : real matrix, if there are none, then []
beq - Linear equality constraints : real vector, if there are none, then []
lb - Lower bounds, specified as a real vector or array
ub - Upper bounds, specified as a real vector or array

• The range of the genetic algorithm is Bounded by introducing values for lower and upper bounds and hence the values of global maxima and the values of x and y will be within the defined search space in inputs.
• Then increasing population size study was done which is the same as before but it had different ga code of:

[inputs,fopt]=ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,IntCon,options)

inputs, fopt,fun and nvars,A,b,Aeq,beq,lb,ub are the same as Study 1 and Study 2 respectively)

nonlcon - Nonlinear constraints, specified as a function handle or function name. If there are none,then []
IntCon - Integer variables, specified as a vector of positive integers, if there are none, then []
Options - Optimization options, specified as the output of optimoptions or a structure.

• The range of the genetic algorithm is Bounded as in Study 2 but to improve the accuracy, the commands optimoptions is introduced to increase the Population Size.
• Then total time is computed
• Then using fprintf command the results are printed in the command windows
• Then the study time is printed
• Then x,y coordinates of the maximum optimum value are printed
• Then the optimum value of the function (maximum value) is printed which is calculated from the (negative mean) of the all iterations of the output value ,and the negative sign is used to get the maximum value.
• Then the study time of the whole 3 studies combined is printed.

Stalagmite function code:

function [f] = stalagmite(input_value)

f_1_x = (sin(5.1*pi*input_value(1) + 0.5))^6;
f_1_y = (sin(5.1*pi*input_value(2) + 0.5))^6;
f_2_x = exp(-4*log(2)*(((input_value(1) - 0.0667)^2)/(0.64)));
f_2_y = exp(-4*log(2)*(((input_value(2) - 0.0667)^2)/(0.64)));

f = -(f_1_x*f_1_y*f_2_x*f_2_y);
end

Stalagmite function code explaination:

• First the function is declared and its input vector is specified
• Then equations are written with inputs from mesh grid
• Then in the last step negative sign is used because we want to maximize the function

Errors during programming:

This error happened because there was a bracket[] missing,it was then corrected

OUTPUT:

Unbounded statastical behaviour plot

Bounded statastical behaviour plot

Modified population size plot

Stalagmite function output print in command window

References:

https://www.mathworks.com/help/gads/how-the-genetic-algorithm-works.html

https://www.mathworks.com/help/gads/ga.html