Week 4.1 - Genetic Algorithm
AIM - The main aim is to optimize the Stalagmite function and to find the global maxima of the function by clearly explaining the concept of genetic algorithm and plotting the graph for the three studies i.e. unbounded inputs, bounded inputs modified population size.
THEORY :
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 amberat (crystallized urine of packrats).
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.
Working Principle:
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 as 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 (string of 1s and 0s). We say that we encode the genes in a chromosome.
2. Fitness function:
- The fitness function determines how 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.
Equations Used:
The Function is for the Genetic Algorithm of the global minima but in order to attain the maxima value the ‘-’ is placed before the equation.
Process of Solving:
The Order in which the code is written is as below
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:
Procedure:
1. Writing the Stalagmite function:
-- The Stalagmite function is a core part of the code.
-- The function follows the formula stated in the Equations Used.
-- The ‘Function’ input is used to write a function code.
% Genetic Algorithm Function Code.
function [P] = gene_alg(input_vector)
x = input_vector(1);
y = input_vector(2);
f1x = (sin(5.1*pi*x + 0.5)).^6;
f1y = (sin(5.1*pi*y + 0.5)).^6;
t1 = ((x-0.0667).^2/(0.64));
t2 = ((y-0.0667).^2/(0.64));
f2x = exp(-4.*log(2)*t1);
f2y = exp(-4.*log(2)*t2);
P = (f1x.*f2x.*f1y.*f2y);
end2. 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.
% Stalagmite - Genetic Algorithm Concept.
clear all
close all
clc
% Search space for the function.
x = linspace(0,1,350);
y = linspace(0,1,350);
% Use of meshgrid command to get 2D arrays.
[xx yy] = meshgrid(x,y);
% Number of iterations performed by the function.
num_case = 150
% Surface plot for genetic algorithm function.
for i = 1:length(xx)
for j = 1:length(yy);
input_vector(1) = xx(i,j);
input_vector(2) = yy(i,j);
p(i,j) = gene_alg(input_vector);
end
end
% Generate the surface for the plot.
surfc(xx,yy,-p);
% Remove the line produce by meshgrid.
shading interp3. 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.
-- Ga is explained clearly in the ‘Terms Used’
-- The plot is generated with unbounded stalagmites.
STUDY - 1 Unbounded Inputs
% Initiate timer for calculating survey time.
tic
for i = 1:num_case
% Calculate the optimized value of the function.
[inputs,popt(i)] = ga(@gene_alg,2);
% Optimised value at ech iterations.
xopt(i) = inputs(1);
yopt(i) = inputs(2);
end
% Display time taken to complete the survey.
survey1_time = toc
% Plot the graph with the obtained optimized data.
figure(1)
subplot(2,1,1)
surfc(xx,yy,-p);
hold on
shading interp
plot3(xopt,yopt,-popt,'Marker','o','MarkerSize',5,'MarkerFaceColor','g');
title('Unbounded Inputs');
xlabel('x');
ylabel('y');
grid on
subplot(2,1,2)
plot(-popt);
xlabel('iterations');
ylabel('function with min value');4. Writing the code for the Bounded Inputs:
-- The code is written for the genetic algorithm function built-in inside the 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.
STUDY - 2 Bounded Inputs
% Initiate timer for calculating survey time.
tic
for j = 1:num_case
% Calculate the optimized value of the function.
[inputs,popt(j)] = ga(@gene_alg,2,[],[],[],[],[0;0],[1;1]);
% Optimised value at ech iterations.
xopt(j) = inputs(1);
yopt(j) = inputs(2);
end
% Display time taken to complete the survey.
survey2_time = toc
% Plot the graph with the obtained optimized data.
figure(2)
subplot(2,1,1)
surfc(xx,yy,-p);
hold on
shading interp
plot3(xopt,yopt,-popt,'Marker','o','MarkerSize',5,'MarkerFaceColor','g');
title('Bounded Inputs');
xlabel('x');
ylabel('y');
grid on
subplot(2,1,2)
plot(-popt);
xlabel('iterations');
ylabel('function with min value');
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.
STUDY - 3 Code for increase in size of the populations
%Increase the population by using the 'optimoption' command.
options = optimoptions('ga','PopulationSize',300)
% Initiate timer for calculating survey time.
tic
for k = 1:num_case
% Calculate the optimized value of the function.
[inputs,popt(k)] = ga(@gene_alg,2,[],[],[],[],[0;0],[1;1],[],[],options);
% Optimised value at ech iterations.
xopt(k) = inputs(1);
yopt(k) = inputs(2);
end
% Display time taken to complete the survey.
survey3_time = toc
% Plot the graph with the obtained optimized data.
figure(3)
subplot(2,1,1)
surfc(xx,yy,-p);
hold on
shading interp
plot3(xopt,yopt,-popt,'Marker','o','MarkerSize',5,'MarkerFaceColor','g');
title('Statistical study with increase in population');
xlabel('x');
ylabel('y');
grid on
subplot(2,1,2)
plot(-popt);
xlabel('iterations');
ylabel('function with min value');
MAIN FUNCTION CODE :
% Stalagmite - Genetic Algorithm Concept.
clear all
close all
clc
% Search space for the function.
x = linspace(0,1,350);
y = linspace(0,1,350);
% Use of meshgrid command to get 2D arrays.
[xx yy] = meshgrid(x,y);
% Number of iterations performed by the function.
num_case = 150
% Surface plot for genetic algorithm function.
for i = 1:length(xx)
for j = 1:length(yy);
input_vector(1) = xx(i,j);
input_vector(2) = yy(i,j);
p(i,j) = gene_alg(input_vector);
end
end
% Generate the surface for the plot.
surfc(xx,yy,-p);
% Remove the line produce by meshgrid.
shading interp
% Initiate timer for calculating survey time.
tic
for i = 1:num_case
% Calculate the optimized value of the function.
[inputs,popt(i)] = ga(@gene_alg,2);
% Optimised value at ech iterations.
xopt(i) = inputs(1);
yopt(i) = inputs(2);
end
% Display time taken to complete the survey.
survey1_time = toc
% Plot the graph with the obtained optimized data.
figure(1)
subplot(2,1,1)
surfc(xx,yy,-p);
hold on
shading interp
plot3(xopt,yopt,-popt,'Marker','o','MarkerSize',5,'MarkerFaceColor','g');
title('Unbounded Inputs');
xlabel('x');
ylabel('y');
grid on
subplot(2,1,2)
plot(-popt);
xlabel('iterations');
ylabel('function with min value');
% Initiate timer for calculating survey time.
tic
for j = 1:num_case
% Calculate the optimized value of the function.
[inputs,popt(j)] = ga(@gene_alg,2,[],[],[],[],[0;0],[1;1]);
% Optimised value at ech iterations.
xopt(j) = inputs(1);
yopt(j) = inputs(2);
end
% Display time taken to complete the survey.
survey2_time = toc
% Plot the graph with the obtained optimized data.
figure(2)
subplot(2,1,1)
surfc(xx,yy,-p);
hold on
shading interp
plot3(xopt,yopt,-popt,'Marker','o','MarkerSize',5,'MarkerFaceColor','g');
title('Bounded Inputs');
xlabel('x');
ylabel('y');
grid on
subplot(2,1,2)
plot(-popt);
xlabel('iterations');
ylabel('function with min value');
%Increase the population by using the 'optimoption' command.
options = optimoptions('ga','PopulationSize',300)
% Initiate timer for calculating survey time.
tic
for k = 1:num_case
% Calculate the optimized value of the function.
[inputs,popt(k)] = ga(@gene_alg,2,[],[],[],[],[0;0],[1;1],[],[],options);
% Optimised value at ech iterations.
xopt(k) = inputs(1);
yopt(k) = inputs(2);
end
% Display time taken to complete the survey.
survey3_time = toc
% Plot the graph with the obtained optimized data.
figure(3)
subplot(2,1,1)
surfc(xx,yy,-p);
hold on
shading interp
plot3(xopt,yopt,-popt,'Marker','o','MarkerSize',5,'MarkerFaceColor','g');
title('Statistical study with increase in population');
xlabel('x');
ylabel('y');
grid on
subplot(2,1,2)
plot(-popt);
xlabel('iterations');
ylabel('function with min value');
Error:
The Errors were made which were simple syntax errors that are rectified right away with the help of the instructions in the command window.
Terms Used:
1. Ga:
Ga function is used to find the minimum of the function using a genetic algorithm.
Syntax:
-- For Random Inputs:
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.
-- For Bounded Inputs:
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.)
--- For Population size:
x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon,options) requires that the variables listed in IntCon take integer values.
Where,
Fun - function,
Nvars – Number of Variables
A – Linear inequality constraints
B – Linear inequality constraints
Aeq - linear equality constraints
beq – linear equality constraints
lb – lower Bounds
ub – Upper Bounds
nonlcon – Non- Linear Constraints
IntCon – Integer Constraints
2. 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.
3. Shading:
- The shading function controls the color shading of surface and patch 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')
4. 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.
5. Optimoptions:
- options = optimoptions(SolverName) returns a set of default options for the SolverName solver.
- options = optimoptions(oldoptions,Name,Value) returns a copy of oldoptions with the named parameters altered with the specified values.
6. 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 :
-- The results show the generation of the stalagmites with the boundaries condition taken as input.
STALAGMITE FUNCTION
-- The random sampling output is shown below : UNBOUNDED INPUTS
-- The bounded samples output is shown below : BOUNDED INPUTS
-- The bounded samples with the given population size are shown below:
BOUNDED INPUT WITH MODIFIED POPULATION SIZE
- The above results show that the bounded samples with population size have an accurate solution. This is because the code showsvthe 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 valuesvwhich are greater than 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.