Week 4.1 - Genetic Algorithm

Aim:

To optimize the Stalagmite function in Matlab & find the global maxima of the function. Plot graphs for all 3 studies and for F maximum vs no. of iterations.

Introduction:

A Genetic Algorithm is a search experiential that is stimulated by Charles Darwin’s theory of natural evolution. This algorithm reproduces the process of natural selection where the appropriate individuals are selected for reproduction in order to produce offspring of the next generation.

The genetic algorithm is a technique for solving both constrained and unconstrained optimization problems that are based on natural selection, the process that drives biological evolution. The genetic algorithm constantly modifies the population size of individual solutions.

Phases in Genetic Algorithm:

Initialization of Population (Coding)

The code generates its random population of defined size and from that population, the code evaluates the fitness of the members of the population according to which it forms a new population based on no. of iterations performed.

Fitness Function

It is that function that we have to optimize and its optimization is done with the help of a number of generations that have been formed by the code in accordance with the fitness value of each member-generated, these fitness values are used for the reproduction of the children.

Selection

The idea of the selection phase is to select the fittest individuals and let them pass their genes to the next generation. The main goal of this phase is to find the region where the chances of getting the best solution are more.

Inspiration for this is from the survival of the fittest.

It should be a balance between exploration and exploitation of search space.

GA tries to move the genotype to higher fitness in the search space.

Too strong fitness selection bias can lead to sub-optimal solutions.

Too little fitness bias selection results in an unfocused search.

Reproduction

Generation of offspring happens in 2 ways:

Crossover

Mutation

a) Crossover

Crossover is the most significant stage in the genetic algorithm. During crossover, a random point is selected while mating a pair of parents to generate offspring.

There are 3 major types of crossover

Single Point Crossover: A point on both parents’ chromosomes is picked randomly, and designated a ‘crossover point’.

Two-Point Crossover: Two crossover points are picked randomly from the parent chromosomes.

Uniform Crossover: In a uniform crossover, typically, each bit is chosen from either parent with equal probability. The new offspring are added to the population.

b) Mutation

In a few new offspring formed, some of their genes can be subjected to a mutation with a low random probability. This indicates that some of the bits in the bit chromosome can be flipped. Mutation happens to take care of diversity among the population and stop premature convergence.

Advantages of GAs

GAs have various advantages which have made them immensely popular. These include:−

• Does not require any derivative information (which may not be available for many real-world problems).
• Is faster and more efficient compared to the traditional methods.
• 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.
• Always gets an answer to the problem, which gets better over time.
• Useful when the search space is very large and there are a large number of parameters involved.

Limitations of GAs

• Like any technique, GAs also suffer from a few limitations. These include −
• GAs are not suited for all problems, especially problems that are simple and for which derivative information is available.
• The fitness value is calculated repeatedly which might be computationally expensive for some problems.
• Being stochastic, there are no guarantees of the optimality or the quality of the solution.
• If not implemented properly, the GA may not converge to the optimal solution.

APPLICATIONS of GA:

Genetic Algorithms are primarily used in optimization problems of various kinds, but they are frequently used in other application areas as well.

In this section, we list some of the areas in which Genetic Algorithms are frequently used. These are:−

• Optimization:− Genetic Algorithms are most commonly used in optimization problems wherein we have to maximize or minimize a given objective function value under a given set of constraints. The approach to solving Optimization problems has been highlighted throughout the tutorial.
• Economics:− GAs are also used to characterize various economic models like the cobweb model, game theory equilibrium resolution, asset pricing, etc.
• Neural Networks:− GAs are also used to train neural networks, particularly recurrent neural networks.
• Parallelization:− GAs also have very good parallel capabilities, prove to be a very effective means of solving certain problems, and also provide a good area for research.
• Image Processing:− GAs are used for various digital image processing (DIP) tasks as well as dense pixel matching.
• Vehicle routing problems:− With multiple soft time windows, multiple depots, and a heterogeneous fleet.
• Scheduling applications:− GAs are used to solve various scheduling problems as well, particularly the timetabling problem.
• Machine Learning:− as already discussed, genetics-based machine learning (GBML) is a niche area in machine learning.
• Robot Trajectory Generation:− GAs have been used to plan the path that a robot arm takes by moving from one point to another.
• Parametric Design of Aircraft:− GAs have been used to design aircraft by varying the parameters and evolving better solutions.
• DNA Analysis:− GAs have been used to determine the structure of DNA using spectrometric data about the sample.
• Multimodal Optimization:− GAs are obviously very good approaches for multimodal optimization in which we have to find multiple optimum solutions.
• Traveling salesman problem and its applications:− GAs have been used to solve the TSP, which is a well-known combinatorial problem using novel crossover and packing strategies.

Explanation:

• The stalagmite function is defined separately. This function is later called into the main Genetic Algorithm program.
• Now we define the x and y inputs using the linspace command.
• Then the input vectors are transformed into an array [xx, yy] so that it can be used to evaluate the functions of two variables and plot three-dimensional mesh/surface plots.
• Now the values in the different matrixes created can be put as an input into the function that we have created, by calling it. By this, we can get the value of the stalagmite function at various values of x & y.
• Now since we have got the value of the function at various values, we now need to calculate the maxima value, which can be calculated using the ga command, which is an in-built function in MATLAB.
• Then, the total number of times the ga needs to run is defined using num_cases, and with help of for loop ga is made to run for each iteration and the value is stored in an array.
• GA generally gives the minima value(in-built in MATLAB), but we need the maxima hence we can just inverse the stalagmite function by introducing a 'Negative sign'(This inverses the stalagmite curve, and the Global maxima can be found, instead minima)
• The total study time is calculated using the 'tic' and 'toc' commands at the start and end of the ga for loop respectively.
• The results are then plotted using the surfc command and plot command.

The Genetic Algorithm is made to run for 3 iterations, with each iteration having bounded inputs, unbounded inputs, and increasing population size.

COMMANDS USED:

meshgrid - The command is used to create a two-dimensional array from the 1D array, syntax:[xx yy] = meshgrid(x,y) where x and y is a one-dimensional array.

ga - This is the command for the genetic algorithm which is the inbuilt function whose types of syntax are defined below.

tic-toc - It is the command used to calculate the processing time of an operation, the operation where we need the processing time should be written/scripted within the tic and toc.

surfc - The surfc command is used to create a three-dimensional surface plot with colors peak region is depicted in different colors having syntax: surfc(x,y,z)

shading interp - The shading interp command is used to remove the grid lines in the surface plot and make them neat, this command is written after the surface plot.

plot3 - plot3(x,y,z) plots coordinates in 3-D space.It plots multiple sets of coordinates on the same set of axes, specifies at least one of X, Y, or Z as a matrix and the others as vectors.

subplot - subplot(m,n,p) divides the current figure into an m-by-n grid and creates axes in the position specified by p. The first subplot is the first column of the first row, the second subplot is the second column of the first row, and so on. If axes exist in the specified position, then this command makes the axes the current axes.

saveas - The saveas command is used to save the plot, surfaceplot automatically while the code is running in the folder where the program is stored we can change the folder by using mkdir, cd.

options - This option is used to differ from the default value which is in the old position to be replaced with the new value.

Syntax for GA:

[x,fval ,exitflag ,output ,population ,scores]= ga(func,nvars,A,b,Aeq,Beq,lb,ub,nonlcon,Intcon,options)

x = optimum solution, the local minima point.

exitflag = reason ga stopped

output = information about optimization process

population = final population

scores = final scores

f = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon,options)

fun - fitness function, fun is the function to be called. (In our case, its the stalagmite function)

nvars- number of variables, nvars indicate the no of variables used.

A,b = Linear inequality constraints, A & b are used to indicate any kind of inequalities that exist in the function.

Aeq, beq = Linear equality constraints.

lb- Lower bound(limit).

ub- Upper bound(limit).

nonlcon : Use for nonlinear constraint, nonlcon gives two vectors representing inequalities and equalities.

IntCon : to get solution in integer.

options - To set population size to minimize with non-default option. options are used to perform additional operations like increasing population size. This is done with the help of "optimoptions".

The above equations are used in the stalagmite function to plot the graph in the main functions.

1. Writing the Stalagmite function:

The Stalagmite function is a core part of the code.

The function follows the formula stated in the fitness function.

The ‘Function’ input is used to write a function code.

% Stalagmite function with input as input_vector which contains the x & y variables.
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);

% The Negative sign denotes the inverse of the Stalagmite function and 
% Is added in order to find the maximum value, 
% As GA algorithm always gives the Minimum value.

f = -(f_1x.*f_2x.*f_1y.*f_2y);

end

We start the program using defining function where it has two inputs x and y

The function has four unknown f1x, f2x, f1y, and f2y they are defined with the given formula.

Then define the function by multiplying the unknowns and multiplying them with a negative value since the given function gives a minimum value. make sure you end the function.

2. Evaluating the stalagmite function:

The code is written to check if the function is returning an output.

The function creates a 3D plot showing the Algorithm.

% defining are search space
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
 
% Creating 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

surfc(xx,yy,f)
shading interp
xlabel('x label')
ylabel('y label')
legend('X Values','Y values')
title('Stalagmite Function')
saveas(1, 'Stalagmite.png')
[x, fval] = ga(@stalagmite, 2)

3. Writing the code for Unbounded Inputs:

For the Unbounded Stalagmites, the code starts with a ‘for’ loop having the inputs and optimal function with calling the function.

The plot is generated with unbounded stalagmites

% defining are search space

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

% Iteration Count
num_cases = 500;

% Creating a 2D 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
 
for i = 1:num_cases
    [inputs, fval(i)] = ga(@stalagmite,2);
    opt_x(i) = inputs(1);
    opt_y(i) = inputs(2);
end

figure(1)
subplot(2,1,1)
surfc(xx,yy,-f)
hold on

% Removing gridlines on the 3D surface plot 

shading interp
plot3(opt_x,opt_y,-fval,'marker','*','markersize',3)
title('UNBOUNDED INPUTS')
subplot(2,1,2)
plot(-fval)
xlabel('NUMBER OF ITERATIONS')
ylabel('F MAXIMUM')

write the main code with clearing and closing previous commands. Then we create two different one-dimensional arrays, and that two-dimensional array is created using meshgrid command. For loop is created with the population size as its limit and calling the function to run. Then three cases are coded to get the maximum value of the function. The first case is done with unbounded inputs. The second case is done with bounded inputs so that the function gets the maximum limit within that range. We set a limit for the lower bound and upper bound for x and y. The third case is done with increased population size. we write the function with a negative value so that it can get global maxima since the 'ga' command gets only the minimum value. plot3 command is used to plot three values which are optimized values derived from the function. In the third case, we use the command 'option' which is used to change the default value with the new value using optimoption tool. After finding the function value we plot the graph for the maximum function value and the number of iterations for the three studies or cases. Each case or study is plotted in a different figure, each figure has two plots one is a surface plot another is a maximum value plot to get that we use a subplot. Then we use the save as a command is used to save the plot while the code is executing.

The below image depicts the plot for the condition of the unbounded input where we have a clumsy graph.

The results obtained for the unbounded inputs vary over a large-sized interval. Thus, providing a vague idea of the global maxima. But it can be observed that the value of ‘F MAXIMUM’ lies between the interval [0, 1]. Therefore, we can opt for bounded inputs that can give more precise results.

4. Writing the code for the Bounded Inputs:

The code is written for the genetic algorithm function built-in inside MATLAB. An empty array is created with starting and ending points of the x and y values.

The plot is created with the inputs in the proper order.

% BOUNDED INPUTS
for i = 1:num_cases
    [inputs, fval(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
    opt_x(i) = inputs(1);
    opt_y(i) = inputs(2);
end
 
figure(2)
subplot(2,1,1)
surfc(xx,yy,-f)
xlabel('x value')
ylabel('y value')
hold on
shading interp
plot3(opt_x,opt_y,-fval,'marker','*','markersize',3)
title('BOUNDED INPUTS')
subplot(2,1,2)
plot(-fval)
xlabel('NUMBER OF ITERATIONS')
ylabel('F MAXIMUM')

The below image depicts the plot for the condition of the bounded input where the maximum function value range is reduced compared to the previous one.

From the above-obtained plot, we can infer that the value of global maxima, somewhat lies in the interval [0.8, 1]. To have a better insight, we can specify a ‘POPULATION SIZE’ that can justify our results and provide us with a near-to-exact solution.

5. Writing the code for the Bounded Inputs with modified population size:

The code begins with writing ‘optimoptions’. The details are given in the ‘Terms Used’

The plot is then created as the previous method.

The Global Maxima is calculated.

% BOUNDED INPUTS WITH MODIFIED POPULATION SIZE
options = optimoptions('ga');
options = optimoptions(options,'PopulationSize',600);
for i = 1:num_cases
    [inputs, fval(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options)
    opt_x(i) = inputs(1);
    opt_y(i) = inputs(2);
end
 
figure(3)
subplot(2,1,1)
surfc(xx,yy,-f)
xlabel('x value')
ylabel('y value')
hold on
shading interp
plot3(opt_x,opt_y,-fval,'marker','*','markersize',3)
title('BOUNDED INPUTS WITH ALTERED POPULATION SIZE')
subplot(2,1,2)
plot(-fval)
xlabel('NUMBER OF ITERATIONS')
ylabel('F MAXIMUM')

The below image depicts the plot for the increased population size condition where the maximum function value range is much reduced. By increasing the iteration or population size we can get the best fit value so far. The processing time will also increase.

The use of ‘POPULATION METHOD’ within bounded inputs increases the probability of determining the exact value of the Global Maxima. The assumed value of population size is ‘600’.

The value of GLOBAL MAXIMA comes out to be 0.99999985.

Initially, the stalagmite function was mentioned with appropriate argument vectors.

The program has been subdivided into three studies based on the limitations of the previous study.

The first study deals with unbounded inputs, thereby expanding the boundary wherein the results can be obtained.

The second study brings in the aspect of bounded inputs providing a better solution for the drawback faced.

The third study lays an appreciable platform to determine the exact solution.

Plots of all three studies have been displayed, thus giving a clear insight into the results.

The processing time increases from one case to another case1<case2<case3.

Reference:

Wikipedia and Find minimum of function using genetic algorithm - MATLAB ga - MathWorks India