Week 4.1 - Genetic Algorithm

Aim: To find the global maxima for the stalagmite function using genetic algorithm in MATLAB.

Theory:
What is a Genetic Algorithm?
A genetic algorithm (GA) is a method for solving both constrained and unconstrained optimization problems based on a natural selection process that mimics biological evolution. The algorithm repeatedly modifies a population of individual solutions. At each step, the genetic algorithm randomly selects individuals from the current population and uses them as parents to produce the children for the next generation. Over successive generations, the population "evolves" toward an optimal solution.
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.
How does the Genetic Algorithm Work?
The following outline summarizes how the genetic algorithm works:
1. The algorithm begins by creating a random initial population.
2. The 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, the algorithm performs the following steps:

• Scores each member of the current population by computing its fitness value. These values are called raw fitness scores.
• Scales the raw fitness scores to convert them into a more usable range of values. These scaled values are called expectation values.
• Selects members, called parents, based on their expectation.
• 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.
• Produces children from the parents. Children are produced either by making random changes to a single parent—mutation —or by combining the vector entries of a pair of parents—crossover.
• Replaces the current population with the children to form the next generation.

3. The algorithm stops when one of the stopping criteria is met.

Genetic Algorithm (ga) Syntax (used in our program):
1. x = ga (@func, nvars), where "func" is the function name and "nvars" is the number of variables.
2. x = ga (@func, nvars, A, B, Aeq, Beq), a set of lower and upper bounds is given so that the solution lies in that range.
3. x = ga (@func, nvars, A, B, Aeq, Beq, lb, ub, nonlcon, IntCon, options), where
A, B = linear inequality constraints
Aeq, Beq = linear equality constraints
lb = lower bound
up = upper bound
nonlcon = non-linear constraints
Intcon = vector of positve integers

Stalagmite Function:
What is a 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 may be composed of lava, minerals, mud, peat, pitch, sand, sinter and amber.

Here, in this program, the graph we get looks like hanging stalagmites, that is why it is referred to as stalagmite function.
The equation of stalagmite function is:

Program for function:

function f=stalagmite_func(input_vector)
x=input_vector(1);
y=input_vector(2);
f1=(sin(5.1*pi*x+0.5))^6;
f2=(sin(5.1*pi*y+0.5))^6;
f3=exp((-4*log(2)*(x-0.0667)^2)/0.64);
f4=exp((-4*log(2)*(y-0.0667)^2)/0.64);
f=-(f1*f2*f3*f4);
end

Program for finding Global Maxima:

% Defining our search space
x=linspace(0,1,150);
y=linspace(0,1,150);
num_cases=50; % To run the ga 50 times
[X,Y]=meshgrid(x,y)
% Evaluating the stalagmite function
for i=1:length(X)
for j=1:length(Y)
input_vector(1)= X(i,j);
input_vector(2)= Y(i,j);
f(i,j)=stalagmite_func(input_vector);
% stalagmite function takes in the data given inside parantheses and calculates f
end
end
surfc(X,Y,f);
xlabel('X axis')
ylabel('Y axis')
shading interp

tic
% Study 1 - Unbounded Condition
for i=1:num_cases
[inputs,fopt(i)]=ga(@stalagmite_func,2);
% ga is an in-built function
% @ defines what function to minimise
% ga always minimises a function
% 2 denotes the no. of variables in the function, here it is x and y
xopt(i)=inputs(1);
yopt(i)=inputs(2);
end
study1_time = toc;
% tic toc is used to measure how long it takes to study
figure(1)
subplot(2,1,1) % To have multiple plots inside the same figure window
hold on
surfc(x,y,-f)
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('Unbounded Inputs')
subplot(2,1,2)
plot(-fopt)
xlabel('Iterations');
ylabel('Function minimum');

tic
% Study 2 - Statistical behaviour - with upper and lower bounds
for i=1:num_cases
[inputs,fopt(i)]=ga(@stalagmite_func,2,[],[],[],[],[0;0],[1;1]);
xopt(i)=inputs(1);
yopt(i)=inputs(2);
end
study2_time=toc;
figure(2)
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded Inputs')
subplot(2,1,2)
plot(-fopt)
xlabel('Iterations');
ylabel('Function minimum');
% Study 3 - Increasing GA Iterations
options=optimoptions('ga')
options=optimoptions(options,'PopulationSize',300);
tic
for i=1:num_cases
[inputs,fopt(i)]=ga(@stalagmite_func,2,[],[],[],[],[0;0],[1;1],[],[],options);
xopt(i)=inputs(1);
yopt(i)=inputs(2);
end
study3_time=toc;
figure(3)
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded Inputs with Modified Population Size')
subplot(2,1,2)
plot(-fopt)
xlabel('Iterations');
ylabel('Function minimum');

Study1:

Study2:

Study3:

This point on the peak is called the global maxima.

Results and Conclusions:
Hence by using generic algorithm, we were able to find the Global maxima point of the stalagmite function.
By default in MATLAB, ga calculates the global minima. In order to make it show the global maxima, we add a -ve sign to 'f' and 'fopt' everywhere.
Initially, the time required to run the program is long. We can reduce this time by reducing the limits. Decreasing the population size will get more accurate results.