Week 4.1 - Genetic Algorithm
Program : For finding the Global Maxima for the given Function (Stalagmite).
% Challenge Genetic Algorithm
clear all
close all
clc
% Code to optimize the stalagmite function
% Creating 1d-array for range
x = linspace(0,1,100);
y = linspace(0,1,100);
% 2d-arry by using 'meshgrid' command
[xx yy] = meshgrid(x,y);
% Evaluting the stalagmite_func and finding its values for x and y
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_max(input_vector);
% Note the stalagmite_max function is mention in the explanation
% As in the MATLAB genetic algorith always minimize the function so
% putting the negative sign to get maxima of function
end
end
% Using the surface plot to see the function
figure(1)
surf(xx, yy, -f) % using the negative sign for getting the graph upward
shading interp
xlabel('X values');
ylabel('Y values');
title('GA with random maxima Value')
% performing Genetic Algorithm
[inputo, fval] = ga(@stalagmite_max,2);
x_i = inputo(:,1);
y_i = inputo(:,2);
hold on
plot3(x_i,y_i,-fval,'Marker','o','MarkerSize',3,'MarkerFaceColor','r');
num_cases = 50;
% Case-1 unbounded Inputs
tic
for k = 1:num_cases;
[input1, fopt1(k)] = ga(@stalagmite_max,2);
xopt1(k) = input1(1);
yopt1(k) = input1(2);
end
study_time1 = toc
figure(2)
subplot(2,1,1)
surf(xx, yy, -f)
shading interp
xlabel('X values');
ylabel('Y values');
hold on
plot3(xopt1,yopt1,-fopt1,'Marker','o','MarkerSize',3,'MarkerFaceColor','r')
title('Unbounded Inputs')
subplot(2,1,2)
plot(-fopt1)
xlabel('Iteration')
ylabel('Function Maxima')
% Case-2 Bounded Inputs
tic
for l = 1:num_cases;
[input2, fopt2(l)] = ga(@stalagmite_max,2,[],[],[],[],[0;0],[1;1]);
xopt2(l) = input2(1);
yopt2(l) = input2(2);
end
study_time2 = toc
figure(3)
subplot(2,1,1)
surf(xx, yy, -f)
shading interp
xlabel('X values');
ylabel('Y values');
hold on
plot3(xopt2,yopt2,-fopt2,'Marker','o','MarkerSize',3,'MarkerFaceColor','r')
title('Bounded Inputs')
subplot(2,1,2)
plot(-fopt2)
xlabel('Iteration')
ylabel('Function Maxima')
% Case-3 Increasing Genetic Algorithm Iterations
tic
for m = 1:num_cases;
options = optimoptions('ga');
options = optimoptions(options,'PopulationSize',400);
[input3, fopt3(m)] = ga(@stalagmite_max,2,[],[],[],[],[0;0],[1;1],[],[],options);
xopt3(m) = input3(1);
yopt3(m) = input3(2);
end
study_time3 = toc
figure(4)
subplot(2,1,1)
surf(xx, yy, -f)
shading interp
xlabel('X values');
ylabel('Y values');
hold on
plot3(xopt3,yopt3,-fopt3,'Marker','o','MarkerSize',3,'MarkerFaceColor','r')
title('Bounded Inputs with Increasing Iteration')
subplot(2,1,2)
plot(-fopt3)
xlabel('Iteration')
ylabel('Function Maxima')
fprintf('The Function Global Maxima')
disp(-fopt3(num_cases));
Function code :
% Function to evaluate stalagmite function.
(Note : The GA in matlab only minimize the function so The function is modified such that
it will give us the results in maximum of GA.)
function [stalagmite_modif] = stalagmite_max(input_vector)
x = input_vector(1);
y = input_vector(2);
f1_x = [sin(5.1*pi * x +0.5)].^6;
f2_y = [sin(5.1*pi * y +0.5)].^6;
f3_x = exp((-4*0.6931).*(x-0.0667)^2/(0.64));
f4_y = exp((-4*0.6931).*(y-0.0667)^2/(0.64));
[stalagmite_modif] = -(f1_x.*f2_y.*f3_x.*f4_y)
end
Note : The negative sign in the function is to get the Local and Global maxima in Ga as matlab only minimizes the function by default.
Explanation :
Step1 : First the search space is define by one dimensional arry using the linspace comand and x and y values are obtain.
Step2 : After definig the search space the 2 Dimensional array [xx yy] are obtain using the meshgrid comand.
Step3 : The function Stalagmite is evaluated using the for loop comand (the function code is given above)
Step4 : Once the function is define we plot them using the surf comand and shading interp for graphical representation of the function.
Step5 : Then the Genetic Algorithm method is used to evaluate the functions Global or Local Maxima for the given inputs. Now in order to calculate the global maxima we need to conduct certain studies that will evaluate the global maixima for the given function.
Case1 : Where the Inputs are unbounded for GA of n number of iterstion where the function gives us the Global and Local maxima with ga synax x = ga(fun,nvars) where x is the Maxima fun is given function and nvars is the number of variable used in the function. Ploting this for better representation with using the figure() comand then ploting the stalagmite function using the surf(xx, yy, -f) and the hold on comand and then ploting the unbounded inputs function outputs for n number of itteration by using plot3() comand with subplot() comand and ploting the function values to itteration using the plot(-fopt) in other subplot.
Case2 : Here the inputs are made bounded with upper and lower limits that will constrain the results the GA syntax used for this x = ga(fun,nvars,A,b,Aeq,beq,lb,ub) where A is linear inequalities constrain as matrix, b is linear inequalities constrain as real vector,Aeq is linear equalities constrain as Matrix, beq is linear equalities constrain as real vector, lb is lower bound and ub is upper bound, Using this we will get more optimum soltion for the function
Case3 : Here the inputs are not only bounded but the number of iteration is also increased that will reults in Globa maxim of the function by using the GA syntax x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,intcon,options) here the nonlcon is non linear constrain and intcon is for integer constrain and options is here to increase the iteration using the optimoptions('ga') and optimoption(option,'populationsize',n) where n is number of itteration to get optimum value. When this graph is plot in figure() we can see the clear represantaion of global maxima of the stalgmite function using the GA.
(Note : where ther no constrian or 0 constrain use [])
Step6 : Finally using the fprintf('') comand diplaying the value of the global maxima disp(final function value/ or case3 value)
Graph :
Figure (1) Function with Random GA maxima.
Figure(2) With Unbounded inputs
Figure(3) With Bounded Inputs
Figure(4) With Bounded Inputs and Increasinf GA Iteration
Workspace
Study Time for Inputs Unbounded, Bounded and Bounded with increasing Iteration
The Global Maximum value for the Stalagmite Function.
Explanation of Genetic Algorithm :
Concept of Genetic Algorithm :
The Genetic Algorithm concept is developed by Jhon Holland.
Genetic Algorith is nothing but a method to find out the optimum solution from the given set of solution.
This method is used to find out the high quality solution to optimization problems by biologically
inspired operators such as mutation,crossover and selection.
How this Genetic Algorithm Works
The algorithm begins with creating random population, from that population a new population is created from the individual of the erlier population, now for forming new population each individual goes through certain criteries,
1) Calculation of fitnes: The each individual of the current population is given a value which help to define its goodness which is known as its Raw Fitness value.
2) Expectation values : This Raw Fitness values are then scaled and then converted to the expectation values based on this expectation values the parent are selcted or decided that in future will be used to generate new population with better goodness from the erlier population.
3) Method of Generation of new Population are parent muatation and parent crossove
Syntax used in GA :
x = ga(fun,nvars)
x = ga(fun,nvars,A,b)
x = ga(fun,nvars,A,b,Aeq,beq)
x = ga(fun,nvars,A,b,Aeq,beq,lb,ub)
x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon)
x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,options)
x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,intcon)
x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,intcon,options)
x = ga(problem)
[x,fval] = ga(___)
Here the
fun = given function
nvars = number of variable used in function
A = linear inequality constrain as matrix
b = linear inequality constrain as real vector
Aeq = linear equality constrain as matrix
beq = linear equality constrain as real vector
lb = lowe bound, ub = uper bound
nonlcon = non linea constrain
fval = value of fitness function at given input values
intcon = integer constrain
option = optimoptions(options,'populationsize', (required number of itteration)) for increasing the the itteration
Reference
https://in.mathworks.com/help/gads/what-is-the-genetic-algorithm.html
https://in.mathworks.com/help/gads/how-the-genetic-algorithm-works.html
Find minimum of function using genetic algorithm - MATLAB ga - MathWorks India