Finding the Global Maxima using Genetic Algorithm in MATLAB.

AIM: Write the code in MATLAB to optimize the stalagmite function and find out the global maxima of the function.

OBJECTIVE:

1. Clearly explain the concept of genetic algorithm and explain the syntax for ga in MATLAB.
2. Make sure the code gives the same output.
3. Plotting the graph for the three studies i.e. unbounded inputs, bounded inputs, and bounded inputs with modified population size.

THEORY:

• Optimization:

Optimization is the process of making something better. In any process, we have a set of inputs and a set of outputs as shown in the following figure.

Optimization refers to finding the values of inputs in such a way that we get the "best" output values. The definition of "best" varies from problem to problem, but in mathematical terms, it refers to maximizing or minimizing one or more objective functions, by varying the input parameters. The set of all possible solutions or values which the inputs can take makes up the search space. In this search space, lies a point or a set of points that gives the optimal solution. The aim of optimization is to find that point or set of points in the search space.

• Stalagmites:

A 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. Stalagmites are typically composed of calcium carbonate but may consist of lava, mud, peat, pitch, sand, sinter, and amber (crystallized urine of packrats).

A stalagmite is an upward-growing mound of mineral deposits that have precipitated from water dripping onto the floor of a cave. Most stalagmites have rounded or flattened tips. A stalagmite function generally refers to the function with which we are generating values over a stalagmite kind of surface for finding out the local and global maxima and minima of that particularly given function.

• Genetic Algorithm:

In computer science and operations research, a genetic algorithm (GA) is a metaheuristic inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms (EA). Genetic algorithms are commonly used to generate high-quality solutions to optimization and search problems by relying on biologically inspired operators such as mutation, crossover, and selection. It is inspired by Charles Darwin's theory of natural evolution. This algorithm reflects the process of natural selection where the fittest individuals are selected for reproduction to produce offspring of the next generation.

• Charles Darwin's Theory of Natural Evolution:

The theory of evolution by natural selection, first formulated in Darwin's book "On the Origin of Species" in 1859, is the process by which organisms change over time as a result of changes in heritable physical or behavioral traits. Changes that allow an organism to better adapt to its environment will help it survive and have more offspring Evolution by natural selection is one of the best-substantiated theories in the history of science, supported by evidence from a wide variety of scientific disciplines, including paleontology, geology, genetics, and developmental biology.

Genetic algorithms (GAs) are stochastic search methods based on the principles of natural genetic systems. They perform a search in providing an optimal solution for the evaluation (fitness) function of an optimization problem. GAs deal simultaneously with multiple solutions and use only the fitness function values. While solving an optimization problem using GAs, each solution is coded as a string (called "chromosome") of finite length over a finite alphabet A. Each string or chromosome is considered an individual. A collection of M (M is finite) such individuals is called a population.

The genetic algorithm starts with a randomly generated population of size M. During the process of iteration, a new population of the same size is generated from the current population using three basic operations on the individuals of the population.

Five phases are considered in a genetic algorithm.

1. Initial population

2. Fitness function

3. Selection

4. Crossover

5. Mutation

1. Initial Population:

• The process begins with a set of individuals which is called a Population. Each individual is a solution to the problem you want to solve.
• An individual is characterized by a set of parameters (variables) known as Genes. Genes are joined into a string to form a Chromosome (solution).
• In a genetic algorithm, the set of genes of an individual is represented using a string, in terms of an alphabet. Usually, binary values are used (a string of Is and Os). We say that we encode the genes in a chromosome.

2. Fitness function:

• The fitness function determines how to fit an individual is (the ability of an individual to compete with other individuals). It gives a fitness score to each individual. The probability that an individual will be selected for reproduction is based on its fitness score.

3. Selection:

• The idea of the selection phase is to select the fittest individuals and let them pass their genes to the next generation.
• Two pairs of individuals (parents) are selected based on their fitness scores. Individuals with high fitness have more chances to be selected for reproduction.

4. Crossover:

• Crossover is the most significant phase in a genetic algorithm. For each pair of parents to be mated, a crossover point is chosen at random from within the genes.

5. Mutation:

• In certain new offspring formed, some of their genes can be subjected to a mutation with a low random probability. This implies that some of the bits in the bit string can be flipped.

The syntax for Genetic Algorithm:

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

1. Write Stalagmite Function.
2. Evaluating the stalagmite function.
3. Writing the code for Unbounded Inputs.
4. Writing the code for the Bounded Inputs.
5. Writing the code for the Bounded Inputs with modified population size.

Writing the Stalagmite Function Code:

% Writing the Stalagmite Fuction
function [f] = stalagmite(input_vector)

x = input_vector(1);
y = input_vector(2);
% Converting the actual Genetic Algorithm formula into Matlab Formula.
f1 = (sin(5.1*pi*x + 0.5)).^6;
f2 = exp(-4*log(2)*((x-0.0667).^2)./0.64);
f3 = (sin(5.1*pi*y + 0.5)).^6;
f4 = exp(-4*log(2)*((y-0.0667).^2)./0.64);
% The Global maxima formula becomes.
f = -(f1*f2*f3*f4);

end

Explanation of Above Code:

• The above code is for the function code of the Stalagmite and it plays a big role.
• The function follows the formula inputted by using the Equation.
• The Function input is used to write the function code.
• I converted the Genetic Algorithm formula into Matlab Formula and made a function file for it.

Writing the Global Maxima Code:

clear all
close all
clc

% Initial input values
lower_bound = input('Enter the Lower Bound Value: ');
upper_bound = input('Enter the Upper Bound Value: ');

% Input Variables with proper line spaces
x = linspace(lower_bound,upper_bound,150);
y = linspace(lower_bound,upper_bound,150);

% 3D Matrix Creation
[xx, yy] = meshgrid(x,y);

% Giving the count/ Number of Iterations for the optimal generation.
count = 50; 
% Tic Starts the Clock time for the function
tic
% Now starting the For Loop
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

study_time = toc; % TOc stops the timer and shows the end time
figure(1)
surf(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)

% Study 1 Unbounded/random sampling Inputs
% Tic Starts the Clock time for the function
tic
% Now starting the For Loop
for i = 1:count
    [inputs,fopt(i)] = ga(@stalagmite,2);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2);
end
studytime_1 = toc;

figure(2)
subplot(2,1,1)
surfc(x,y,-f)
shading interp
title('Unbounded Inputs')
xlabel('X Value')
ylabel('Y Value')

hold on

plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r');
subplot(2,1,2)
plot(-fopt)
xlabel('Itertaions')
ylabel('Function Maximum')
saveas(2,'Unbound Inputs.png')

% Study 2 -  Statistical behvaiour with upper and lower bound Sampling (Bounded Inputs)
% Tic Starts the Clock time for the function
tic
% Now starting the For Loop
for i = 1:count
    [inputs,fopt(i)] = ga(@stalagmite,2, [],[],[],[], [lower_bound;lower_bound],[upper_bound;upper_bound]);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2);
end
studytime_2 = toc;

figure(3)
subplot(2,1,1)
surfc(x,y,-f)
shading interp
title('Bounded Inputs')
xlabel('X Value')
ylabel('Y Value')

hold on

plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','m');
subplot(2,1,2)
plot(-fopt)
xlabel('Itertaions')
ylabel('Function Maximum')
saveas(3,'Bounded Inputs.png')

% Study 3 -  Code for Upper and Lower bound sampling and increase the population size
options = optimoptions(@ga);
options = optimoptions(options,'populationsize',170);
% Tic Starts the Clock time for the function
tic
% Now starting the For Loop
for i = 1:count
    [inputs,fopt(i)] = ga(@stalagmite,2, [],[],[],[], [lower_bound;lower_bound],[upper_bound;upper_bound],[],[],options);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2);
end
studytime_3 = toc;

figure(4)
subplot(2,1,1)
surfc(x,y,-f)
shading interp
title('Bounded Inputs with modified population size')
xlabel('X Value')
ylabel('Y Value')

hold on

plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','c');
subplot(2,1,2)
plot(-fopt)
xlabel('Itertaions')
ylabel('Function Maximum')
saveas(4,'Bounded Inputs with modified population size.png')

% For Finding the Global Maxima
global_maxima = -fopt;

Explanation of the above code:

1. Evaluating the Stalagmite Function:

• This code is written to check if the function is returning an output.
• Starting with the Initial Input Values which include the lower_bound and the upper_bound equation.
• Then the input variables with proper line spaces, for this I used the linspace command for the X and Y values.
• Now towards the 3D Matrix creation, for this using the meshgrid command which converts the 2D coordinates into 3D.
• Then I included the count command to give count or give the number of Iteration for the optimal generation.
• A tic command was also included to start the clock time for the function.
• After this, I included the For Loop command and gave the value of the variable "i" as well as "j".
• To stop the timer a toc command was included.
• For the plotting purpose, the commands such as figure, xlabel, ylabel, legend title, etc. were used, and also a surfc command was used to create a three-dimensional surface plot with a contour plot underneath, also I included the saveas command to save the plot file.

2. Writing the code for Unbounded Inputs:

• For the Unbounded Stalagmite, the code is almost the same as the Stalagmite function code, it has the tic, toc, and the for loop commands as used above.
• In addition to these commands, there is a ga command which finds the minimum of the function.
• All the syntax used is from the theory section.
• For plotting purposes, the commands such as the figure, subplot, surfc, shading, title, xlabel, and ylabel are included.
• A plot3 command is used so that the plotting of a 3D figure can be done.
• This plot3 command includes commands such as marker which creates a marking in the plot, and for the marker, the markersize and markerfacecolor command is given to give the required size and color to the marker.

3. Writing the code for the Bounded Inputs:

• This is study 2 for the statistical behavior with upper and lower bound sampling.
• This part also has the same code and the commands as from the above Unbounded Stalagmite with few changes in the values and namings.
• All the syntax used is from the theory section.
• The terms used will be explained in the terms used section.

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

• Towards the final part of the code i.e. Code for the upper and lower bound sampling and increase the population size.
• This part has a new command optimoptions command, this command is used because some options don't appear in the listing that's why.
• Rest the code is the simple modification made for the above codes with the changes in the value.
• All the syntax used is from the theory section.
• The last step of the code is the formula for the calculation of the Global Maxima.

Terms Used:

• Ga: Ga function is used to find the minimum of the function using a genetic algorithm.
• Surfc: surfc function contours the plot under the surface plot. surfc(X, Y, Z) creates a three-dimensional surface plot with a contour plot underneath. A surface plot is a three-dimensional surface that has solid edge colors and solid face colors. The function plots the values in matrix Z as heights above a grid in the x-y plane defined by X and Y. The color of the surface varies according to the heights specified by Z.
• Shading: The shading function controls the color shading of the surface and patches graphics objects. Shading flat each mesh line segment and face has a constant color determined by the color value at the endpoint of the segment or the corner of the face that has the smallest index or indices. Shading faceted flat shading with superimposed black mesh lines. This is the default shading mode. Shading interp varies the color in each line segment and face by interpolating the colormap index or true color value across the line or face. shading(axes_handle,...) applies the shading type to the objects in the axes specified by axes_handle, instead of the current axes. Use single quotes when using a function form. For example: shading(gca,'interp')
• Plot3: plot3(X, Y, Z) plots coordinates in 3-D space. To plot a set of coordinates connected by line segments, specify X, Y, and Z as vectors of the same length. To plot multiple sets of coordinates on the same set of axes, specify at least one of X, Y, or Z as a matrix and the others as vectors.
• Optimoptions: options = optimoptions(SolverName) return a set of default options for the SolverName solver. options = optimoptions(oldoptionsName, Value) returns a copy of oldoptions with the named parameters altered with the specified values.
• Tic- Toc: tic works with the toc function to measure elapsed time. The 'tic' function records the current time, and the toc function uses the recorded value to calculate the elapsed time. toc reads the elapsed time since the stopwatch timer started by the call to the tic function. MATLAB reads the internal time at the execution of the toc function and displays the elapsed time since the most recent call to the tic function without an output. The elapsed time is expressed in seconds.

RESULTS:

These are the results that show the generation of the stalagmites. The start and end boundaries are taken as inputs:

The Unbounded Sampling output is shown below:

The Bounded samples output are shown below:

The bounded sample with the given population size are shown below:

Values in the Workspace:

ERRORS:

This was a small typo I wrote the linspace command as linespace.

This was another error that I faced here I didn't know the name of the file shouldn't be 'ga' as its a function of genetic algorithm, because of this the code was not running so had to change the name of the script file, and the other error it showing is the legend I have used more no of legend command I corrected it later.

CONCLUSION:

The above results show that the bounded samples with population size have an áccurate solution. This is because the code shows the random samples which can start and end at random points.

To overcome the issue, the bounded samples method is used giving the lower and upper limits. (Therefore, it will take the values which are greater than the upper Bound or less than the lower bound.)

This loop gives an output with different Local maxima with bounded inputs. To conquer this problem, we need to increase the population size as it increases the probability to converge to a global maximum.

The Global maximum of a function can be found by inverting the function. Find the minimum value of the inverted function, the negative of the minimum value will give the global maximum of the function.

REFERENCES:

https://in.mathworks.com/help/gads/genetic-algorithm-options.html

https://skill-lync.com/knowledgebase/genetic-algorithm-explained

https://towardsdatascience.com/introduction-to-genetic-algorithms-including-example-code-e396e98d8bf3

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

https://en.wikipedia.org/wiki/Genetic_algorithm

https://en.wikipedia.org/wiki/Stalagmite

https://in.mathworks.com/help/matlab/ref/surfc.html#:~:text=surfc(%20Z%20)%20creates%20a%20surface,as%20the%20first%20input%20argument.

https://in.mathworks.com/help/matlab/creating_plots/create-line-plot-with-markers.html