Week 5 - Genetic Algorithm
AIM: Write a code in MATLAB to optimize the stalagmite function using genetic algorithm and find the global maxima of the function.
THEORY:
STALAGMITE AND STALACTITES
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 etc
A stalactite is a mineral formation that hangs from the ceiling of caves, hot springs, or man-made structures such as bridges and mines. Any material that is soluble and that can be deposited as a colloid, is in suspension, or is capable of being melted, may form a stalactite
The stalagmite function is given by:
GENETIC ALGORITHM
Genetic Algorithms(GAs) are adaptive heuristic search algorithms
They belong to evolutionary algorithms.
Genetic algorithms are based on the ideas of natural selection and genetics.
These are intelligent exploitation of random search provided with historical data to direct the search into the region of better performance in solution space.
They are commonly used to generate high-quality solutions for optimization problems and search problems.
PROGRAM FOR STALAGMITE 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.667)^2)/0.64);
f4 = exp((-4*log(2)*(y-0.667)^2)/0.64);
f = -(f1*f2*f3*f4);
end
FLOW CHART
HOW DOES THE GENETIC ALGORITHM WORK?
The flow chart of the genetic algorithm is shown above
First, we need to start, after starting we create an initial random population
The next step is calculating the fitness of each individual and noting down their fitness scores
If optimal or best solution is obtained we end the process
If not, then we select the fittest individuals based on their fitness evaluation
After selecting, we use the genetic operator either Crossover or Mutation to enhance the fitness of the individuals
This process is repeated until we get the most optimal solution.
A Genetic algorithm basically consists of 3 operators
Selection operator: selects the individuals, called parents, that contribute to the population at the next generation.
Crossover operator: combines two parents to form children for the next generation
Mutation: applies random changes to individual parents to form children
BASIC PROGRAM FOR STALAGMITE
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
[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_func(input_vector);
end
end
surfc(xx,yy,f)
shading interp
[x fval] = ga(@stalagmite_func,2)
OUTPUT :
MAIN CODE:
clear all
close all
clc
% defining our search space
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
limit = 30; %runs the ga 30 times
[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_func(input_vector);
end
end
tic
%study 1 - unbounded condition
for i= 1:limit
[input,fval(i)] = ga(@stalagmite_func,2);
x_out(i) = input(1);
y_out(i) = input(2);
end
case_time_1 = toc;
figure(1)
subplot(2,1,1)
surfc(xx,yy,-f)
xlabel('x')
ylabel('y')
title('case1 (unbounded)','color','k')
shading interp
hold on;
plot3(x_out,y_out,-fval,'marker','o','markersize',6,'markerfacecolor','r');
subplot(2,1,2)
plot(-fval)
xlabel('No of Iterations')
ylabel('max function value')
tic
%study 2 - Inserting bounding box
for i= 1:limit
[input,fval(i)] = ga(@stalagmite_func,2,[],[],[],[],[0;0],[0.6;0.6]);
x_out(i) = input(1);
y_out(i) = input(2);
end
case_time_2 = toc;
figure(2)
subplot(2,1,1)
surfc(xx,yy,-f)
xlabel('x')
ylabel('y')
title('case2 ','color','k')
shading interp
hold on;
plot3(x_out,y_out,-fval,'marker','o','markersize',6,'markerfacecolor','r');
subplot(2,1,2)
plot(-fval)
xlabel('No of Iterations')
ylabel('max function value')
tic
%study 3
options = optimoptions('ga');
options = optimoptions(options,'populationsize',300)
for i= 1:limit
[input,fval(i)] = ga(@stalagmite_func,2,[],[],[],[],[0;0],[0.6;0.6],[],[],options);
x_out(i) = input(1);
y_out(i) = input(2);
end
case_time_3 = toc;
figure(3)
subplot(2,1,1)
surfc(xx,yy,-f)
xlabel('x')
ylabel('y')
title('case3 ','color','k')
shading interp
hold on;
plot3(x_out,y_out,-fval,'marker','o','markersize',6,'markerfacecolor','r');
subplot(2,1,2)
plot(-fval)
xlabel('No of Iterations')
ylabel('max function value')
display(input)
CODE EXPLAINATION:
A random array of x and y values were created and using the meshgrid command a corresponding 2D array was obtained
A nested for loop was created to assign values from this array to another array input_vector which is the input to the stalagmite function
A separate program is written for the stalagmite function which is then called in the main program
The output of the genetic algorithm is Global Minima, but we need the Global Maxima hence a negative sign is given to the output of the stalagmite function to obtain the Global Maxima.
To get the running time of each case we use the Tic-Toc commands
In the first case we bounds were not defined and the plot was made.
To get the stalagmite function upwards a negative sign is given to the value f in the surface function
In the next two cases bounding is provided so that the number of solutions approaches more accuracy
The global maxima is found out and the x and y values for which the function has maximum value is also obtained
Inorder to reduce the program execution time the iterations can be reduced
OUTPUT:
CASE 1
CASE 2
CASE 3
The point on the peak is the global maxima
RESULTS:
The global maxima of the stalagmite function can be found out using genetic algorithm
Genetic algorithm by default calculates the global minima. In order to make it show the global maxima ,we add -ve sign to 'f' and 'fopt' everywhere