Genetic Algorithm
Structure background -
Stalactite and stalagmite, elongated forms of various minerals deposited from solution by slowly dripping water. A stalactite hangs like an icicle from the ceiling or sides of a cavern. A stalagmite appears like an inverted stalactite, rising from the floor of a cavern.
Stalagmite Function -
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.
i.e f(x,y) = f1x,f2x,f1y,f2y
f1x = [sin(5.1pix+0.5)]^6
f1y = [sin(5.1piy+0.5)]^6
f2x = exp[-4ln(2)*((x-0.0667)^2/0.64)]
f2y = exp[-4ln(2)*((y-0.0667)^2/0.64)]
Genetic Algorithm -
A Genetic algorithm (GA) is inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms (EA)(Darwin's theory). Genetic algorithms are commonly used to generate high-quality solutions to optimization and search problems by relying on biologically inspired operators such as Selection, Crossover, and Mutation.
> Selection - During each successive generation, a portion of the existing population is selected to breed a new generation. Individual solutions are selected through a fitness-based process, where fitter solutions (as measured by a fitness function) are typically more likely to be selected.
> Crossover - crossover in GA generates new generation the same as natural mutation. By mutating the old generation parents, the new generation offspring comes by carrying genes from both parents. The amount of genes carried from each parent is random.
> Mutation - For each offspring, select some genes and change its value. Mutation prevents the solution from falling into local minima.
Genetic Algorithm Syntax-
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.
Optimization -
Optimization consists of maximizing or minimizing a real function by systematically choosing input values from within an allowed set and computing the value of the function. The generalization of optimization theory and techniques to other formulations constitutes a large area of applied mathematics. More generally, optimization includes finding "best available" values of some objective function given a defined domain (or input), including a variety of different types of objective functions and different types of domains.
% Stalagmite Mathematic Function
clear all
close all
clc
%Defining our search space
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
limit = 30;
% Creating the 2D array
[xx yy] =meshgrid(x,y);
% Nested loop for array value input
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
% case study 1 - Unbounded
tic
for i = 1:limit
[input,fval(i)] = ga(@stalagmite,2);
x_out(i) = input(1);
y_out(i) = input(2);
end
case_time1 = toc
figure(1)
subplot(2,1,1)
surfc(xx,yy,-f)
xlabel('x');
ylabel('y');
title('Case study 1 (Unbounded)','color','b')
shading interp
hold on;
plot3(x_out,y_out,-fval,'marker','*','markersize',6,'markerfacecolor','g');
subplot(2,1,2)
plot(-fval);
xlabel('No of Iteration')
ylabel('Max. Function Value')
% Case study 2 - Bounded
tic
for i = 1:limit
[input,fval(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6]);
x_out(i) = input(1);
y_out(i) = input(2);
end
case_time2 = toc
figure(2)
subplot(2,1,1)
surfc(xx,yy,-f)
xlabel('x');
ylabel('y');
title('Case study 2 (Bounded)','color','b')
shading interp
hold on;
plot3(x_out,y_out,-fval,'marker','*','markersize',6,'markerfacecolor','g');
subplot(2,1,2)
plot(-fval);
xlabel('No of Iteration')
ylabel('Max. Function Value')
% Case study 3 - with population size
options = optimoptions('ga');
options = optimoptions(options,'Populationsize',300);
tic
for i = 1:limit
[input,fval(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6],[],[],options);
x_out(i) = input(1);
y_out(i) = input(2);
end
case_time3 = toc
figure(3)
subplot(2,1,1)
surfc(xx,yy,-f)
xlabel('x');
ylabel('y');
title('Case study 3 (Population size)','color','b')
shading interp
hold on;
plot3(x_out,y_out,-fval,'marker','*','markersize',6,'markerfacecolor','g');
subplot(2,1,2)
plot(-fval);
xlabel('No of Iteration')
ylabel('Max. Function Value')
Explanation -
1.First we initialize the values of x & y by using the linspace command i.e from 0 to 0.6 to the length of 150 and given limit for the no. of iteration.
2.From the values of x & y we created the 2D array by using 'meshgrid' command.
3. By using the 'nested for loop' the above array has been stored as input_vector array, as it can be used as an argument to call the stalagmite function.
4. Wherein we created another function file for the stalagmite function. Here we take the output as -f since ga only minimizes the given function, so -f is considered automatically as a maximum function.
% Stalagmite Function for gobal maxima
function [f] = stalagmite(input_vector)
f1x = (sin((5.1*pi).*input_vector(1)+0.5)).^6;
f1y = (sin((5.1*pi).*input_vector(2)+0.5)).^6;
f2x = exp((((input_vector(1)-0.0667).^2)/0.64).*(-4*log(2)));
f2y = exp((((input_vector(2)-0.0667).^2)/0.64).*(-4*log(2)));
f1 = f1x*f1y*f2x*f2y;
f = - f1;
end
5.Case study 1- (Unbounded) We have given a limit for the no. of iteration and use ga function to calculate gobal maxima and store the output into inputs i.e x_out and y_out and fval which contains the f maxima. Also,we used tik toc command to calculate the case time.
As we have not given any bounded values ga takes the values randomly and gives the output. The same as been plotted in figure(1).
6.Case study 2 - (Bounded) We have given a limit for the no. of iteration and also given bounded values for x and y i.e upper and lower bounds to calculate the global maxima more accurately. Since we have not given any specific population size ga selcets randomly and calculate the same.
The same has been plotted in the figure (2).
7. Case study 3 _ (with given Population size) We have given a limit for the no. of iteration, bounded values for x and y i.e upper and lower bounds and also population size i.e 300 to calculate the global maxima more accurately.
The same has been plotted in the figure (3).
Errors -
1.As shared in the screenshot,file name was given as the function name which was already stored. Hence changed the file name to over come the error.
Reference -
1.https://www.britannica.com/science/stalactite
2.https://en.wikipedia.org/wiki/Genetic_algorithm
3.https://www.tutorialspoint.com/genetic_algorithms/genetic_algorithms_crossover.ht4.m
https://en.wikipedia.org/wiki/Mathematical_optimization