Week 4.1 - Genetic Algorithm

Aim:

To optimize the stalagmite function and find out the global maxima and plot the graph for the three studies i.e. Bounded condition, Unbounded condition and Bounded inputs with modified population size.

Theory:

Stalagmite: 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 pack rats).

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 Algorithm(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.

These are the five phases of the genetic algorithm:

1. Initial population
2. Fitness function
3. Selection
4. Crossover
5. Mutation

1. Initial population:

The process begins with a set of indic=viduals 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 if an individual is represented using a string, in terms of an alphabet. Usually, 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.

For example, consider the crossover point to be 3 as shown below.

Crossover point

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.

Mutation: Before and After

Mutation occurs to maintain diversity within the population and prevent premature convergence.

Equation used:

The function is represented for the Genetic Algorithm of the global minima is shown below,

Order of solving:

The order of the code is written,

1. Write the stalagmite function.
2. Evaluating the stalagmite function.
3. Writing the code for Unbounded condition(Random sampling condition).
4. Writing the code for Bounded condition(Statistical behaviour with upper and lower sampling).
5. Writing the code for Upper and Lower bound sampling and increasing the population size.

Procedure:

1. Write the stalagmite function:

• The stalagmite function is the core of the code.
• The function is written by following the formulas.

function [f] = stalagmite(input_vector)

x=input_vector(1);
y=input_vector(2);

f1_x = (sin(5.1*pi*x)+ (0.5)).^6;
f2_x = exp(-4*log(2)*((x-0.0667).^2)./0.64);
f1_y = (sin(5.1*pi*y) + (0.5)).^6;
f2_y = exp(-4*log(2)*((y-0.0667).^2)./0.64);

f5 = (f1_x*f2_x*f1_y*f2_y);

f = -f5;

end

2. Evaluating the stalagmite function:

• The function is checked for is it giving a proper output.
• The output is in the form of a 3D plot.

%Evaluating the stalagmite function
tic
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;
figure(1);
surfc(xx,yy,-f);
shading interp
xlabel('x value');
ylabel('y value');
legend('X Values','Y Values');
title('Stalagmite Function');
colorbar;
saveas(1,'Stalagmite.png');

[input, fval] = ga(@stalagmite,2);

%Study 1: Unbounded condition(Random sampling condition)
tic
for i=1:num_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(xx,yy,-f);
shading interp
xlabel('x value');
ylabel('y value');
title('Unbounded Input');
colorbar;

hold on
plot3(xopt,yopt,-fopt,'Marker','o','markersize',5,'markerfacecolor','#EBD120');
subplot(2,1,2);
plot(-fopt);
xlabel('Itreations');
ylabel('Function maximum');
saveas(2,'Unbounded inputs.png');

3. Writing the code for Unbounded condition(Random sampling condition).

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

%Study 2: Bounded condition(Statistical behaviour with upper and lower
%sampling)
tic
for i=1:num_count
    [inputs,fopt(i)]= ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6]);
    xopt(i)=inputs(1);
    yopt(i)=inputs(2);
end
studytime_2=toc;
figure(3);
subplot(2,1,1);
surfc(xx,yy,-f);
shading interp
xlabel('x value');
ylabel('y value');
title('Bounded Input');
colorbar;

hold on
plot3(xopt,yopt,-fopt,'Marker','o','markersize',5,'markerfacecolor','m');
subplot(2,1,2);
plot(-fopt);
xlabel('Itreations');
ylabel('Function maximum');
saveas(3,'Bounded inputs.png');

4. Writing the code for Upper and Lower bound sampling and increasing the 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: Upper and Lower bound sampling and increasing the
%population size
tic
options=optimoptions('ga','populationsize',2000);
for i=1:num_count
    [inputs,fopt(i)]= ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6],[],[],options);
    xopt(i)=inputs(1);
    yopt(i)=inputs(2);
end
studytime_3=toc;
figure(4);
subplot(2,1,1);
surfc(xx,yy,-f);
shading interp
xlabel('x value');
ylabel('y value');
title('Bounded Input with modified population size');
colorbar;

hold on
plot3(xopt,yopt,-fopt,'Marker','o','markersize',5,'markerfacecolor','c');
subplot(2,1,2);
plot(-fopt);
xlabel('Itreations');
ylabel('Function maximum');
saveas(4,'Bounded Input with modified population size.png');

Code:

Function code:

function [f] = stalagmite(input_vector)

x=input_vector(1);
y=input_vector(2);

f1_x = (sin(5.1*pi*x)+ (0.5)).^6;
f2_x = exp(-4*log(2)*((x-0.0667).^2)./0.64);
f1_y = (sin(5.1*pi*y) + (0.5)).^6;
f2_y = exp(-4*log(2)*((y-0.0667).^2)./0.64);

f5 = (f1_x*f2_x*f1_y*f2_y);

f = -f5;

end

Main code:

clear all
close all
clc

%Input variables with proper linspace command
x= linspace(0,0.6,150);
y= linspace(0,0.6,150);

%Creating the 3D matrix 
[xx,yy] = meshgrid(x,y);

num_count = 50; %Giving the count of Iteration for the optimal generation

%Evaluating the stalagmite function
tic
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;
figure(1);
surfc(xx,yy,-f);
shading interp
xlabel('x value');
ylabel('y value');
legend('X Values','Y Values');
title('Stalagmite Function');
colorbar;
saveas(1,'Stalagmite.png');

[input, fval] = ga(@stalagmite,2);

%Study 1: Unbounded condition(Random sampling condition)
tic
for i=1:num_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(xx,yy,-f);
shading interp
xlabel('x value');
ylabel('y value');
title('Unbounded Input');
colorbar;

hold on
plot3(xopt,yopt,-fopt,'Marker','o','markersize',5,'markerfacecolor','#EBD120');
subplot(2,1,2);
plot(-fopt);
xlabel('Itreations');
ylabel('Function maximum');
saveas(2,'Unbounded inputs.png');

%Study 2: Bounded condition(Statistical behaviour with upper and lower
%sampling)
tic
for i=1:num_count
    [inputs,fopt(i)]= ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6]);
    xopt(i)=inputs(1);
    yopt(i)=inputs(2);
end
studytime_2=toc;
figure(3);
subplot(2,1,1);
surfc(xx,yy,-f);
shading interp
xlabel('x value');
ylabel('y value');
title('Bounded Input');
colorbar;

hold on
plot3(xopt,yopt,-fopt,'Marker','o','markersize',5,'markerfacecolor','m');
subplot(2,1,2);
plot(-fopt);
xlabel('Itreations');
ylabel('Function maximum');
saveas(3,'Bounded inputs.png');

%Study 3: Upper and Lower bound sampling and increasing the
%population size
tic
options=optimoptions('ga','populationsize',2000);
for i=1:num_count
    [inputs,fopt(i)]= ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6],[],[],options);
    xopt(i)=inputs(1);
    yopt(i)=inputs(2);
end
studytime_3=toc;
figure(4);
subplot(2,1,1);
surfc(xx,yy,-f);
shading interp
xlabel('x value');
ylabel('y value');
title('Bounded Input with modified population size');
colorbar;

hold on
plot3(xopt,yopt,-fopt,'Marker','o','markersize',5,'markerfacecolor','c');
subplot(2,1,2);
plot(-fopt);
xlabel('Itreations');
ylabel('Function maximum');
saveas(4,'Bounded Input with modified population size.png');

%Finding the Global Maxima
global_maxima= -fopt;

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

5. 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 global maxima is calculated and the values are given below,

Unbounded condition with Random sampling condition output is given below,

Bounded condition output is given below,

Bounded condition output with given population size is given below,

Reference Links:

1. Stalagmite Wikipedia
2. Genetic Algorithm
3. Mathwork