Week 4.1 - Genetic Algorithm

AIM:

To create a program to optimise the stalagmite function and determine the global maxima of the function.

THEORY:

Optimisation:

Optimisation is used to get the best results using a set of prioritized constraints. It is a decision making process that is executed ny comparing various solutions until a satisfactory solution is found.  

Genetic Algorithm:

Genetic Algorithm (GA) is a search-based optimization technique based on the principles of Genetics and Natural Selection. It is frequently used to find optimal or near-optimal solutions to difficult problems which otherwise would take a lifetime to solve. It is frequently used to solve optimization problems, in research, and in machine learning.

In GAs, we have a pool or a population of possible solutions to the given problem. These solutions then undergo recombination and mutation (like in natural genetics), producing new children, and the process is repeated over various generations. Each individual (or candidate solution) is assigned a fitness value (based on its objective function value) and the fitter individuals are given a higher chance to mate and yield more “fitter” individuals. This is in line with the Darwinian Theory of “Survival of the Fittest”.

           

Fitness Function:

The function where solution is taken in an input and produces the suitability of the solution as the output. This evaluates how close the solution of the desired problem.

Stalagmite Function:

It is the function which is used in generating values over a stalagmite kind of surface for finding out the local and global maxima or minima of the given function.

Syntax for ga:

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.

x = ga(fun,nvars,A,b) finds a local minimum x to fun, subject to the linear inequalities A*x ≤ b. ga evaluates the matrix product A*x as if x is transposed (A*x').

x = ga(fun,nvars,A,b,Aeq,beq) finds a local minimum x to fun, subject to the linear equalities Aeq*x = beq and A*x ≤ b. (Set A=[] and b=[] if no linear inequalities exist.) ga evaluates the matrix product Aeq*x as if x is transposed (Aeq*x').

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

x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon) subjects the minimization to the constraints defined in nonlcon. The function nonlcon accepts x and returns vectors C and Ceq, representing the nonlinear inequalities and equalities respectively. ga minimizes the fun such that C(x) ≤ 0 and Ceq(x) = 0. (Set lb=[] and ub=[] if no bounds exist.)

x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,options) minimizes with the default optimization parameters replaced by values in options. (Set nonlcon=[] if no nonlinear constraints exist.) Create options using optimoptions (recommended) or gaoptimset.

x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon) or x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon,options) requires that the variables listed in IntCon take integer values.

x = ga(problem) finds the minimum for problem, where problem is a structure.

 [x,fval] = ga(___), for any previous input arguments, also returns fval, the value of the fitness function at x.

[x,fval,exitflag,output] = ga(___) also returns exitflag, an integer identifying the reason the algorithm terminated, and output, a structure that contains output from each generation and other information about the performance of the algorithm.

[x,fval,exitflag,output,population,scores] = ga(___) also returns a matrix population, whose rows are the final population, and a vector scores, the scores of the final population.

CODE:

Stalagmite Function Code:

function   [f] = stalagmite(input) 

term1 = (input(1)-0.0667)^2/0.64;
term2 = (input(2)-0.0667)^2/0.64;
term3 = -4*log(2);
f1 = (sin(5.1*pi*input(1)+0.5))^6;
f2 = (sin(5.1*pi*input(2)+0.5))^6;
f3 = exp(term3*term1);
f4 = exp(term3*term2);

f = -f1*f2*f3*f4;
end

Code Explanation:

The stalagmite is defined by defining the four functions f1,f2,f3 and f4 with input as the nodes within the search space. ‘-ve’ sign is given to get maximum value because ga only determine minimum value.

Main Code:

clear all
close all 
clc

% defining our search face
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);

% creatig a 2D mesh
[xx yy] = meshgrid(x,y);

% evaluating stalagmite function
for i = 1:length(xx)
    for j = 1 : length(yy)
        input(1) = xx(i,j);
        input(2) = yy(i,j);
        f(i,j) = stalagmite(input);
    end
end

num_case =50;

% Study 1- statistical behaviour
% start timer
tic
for i = 1:num_case
  [input1,fopt1(i)] = ga(@stalagmite,2);
  xopt1(i) = input1(1);
  yopt1(i) = input1(2);
end
%end timer
study1_time = toc

figure(1)
subplot(2,1,1)
surfc(xx,yy,-f)
shading interp
hold on
plot3(xopt1,yopt1,-fopt1,'marker','o','markersize',5,'markerfacecolor','r')
title('Unbounded inputs')
subplot(2,1,2)
plot(-fopt1)
xlabel('Iteration')
ylabel('function maximum')

% Study 2- statistical behaviour with upper and lower boundaries
tic
for i = 1:num_case
  [input2,fopt2(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
  xopt2(i) = input2(1);
  yopt2(i) = input2(2);
end
study2_time = toc

figure(2)
subplot(2,1,1)
surfc(xx,yy,-f)
shading interp
hold on
plot3(xopt2,yopt2,-fopt2,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded inputs')
subplot(2,1,2)
plot(-fopt2)
xlabel('Iteration')
ylabel('function maximum')

% Study 3- statistical behaviour with upper and lower boundariesand
% population

options = optimoptions('ga');
options = optimoptions(options,'PopulationSize',300);
tic
for i = 1:num_case
  [input3,fopt3(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[0.2;0.2],[],[],options);
  xopt3(i) = input3(1);
  yopt3(i) = input3(2);
end
study3_time = toc

figure(3)
subplot(2,1,1)
surfc(xx,yy,-f)
shading interp
hold on
plot3(xopt3,yopt3,-fopt3,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded inputs and increasing population')
subplot(2,1,2)
plot(-fopt3)
xlabel('Iteration')
ylabel('function maximum')

Code Explanation:

1. Define the search space for the stalagmite function using linspace command and also define the nodes of the grid using meshgrid command.
2. The function named stalagmite is called to calculate the function values for the nodes.
3. The number of iterations is given 50 and for loop is used to run the ga for 50 times.
4. Inside the loop the ga is defined without any boundary for Study 1.
5. The commands tic and toc is used to calculate the time taken for the ga to run.
6. For plotting figure and subplot commands are used to get both the plot in the same window.
7. In plot 1, surf is used to get the stalagmite function and plot3 is used to get the 3D plot of the optimization.
8. For 2^nd plot, plot is used to plot the optimum value with its corresponding iterations. Also xlabel and ylabel are used to define axes.
9. For Study 2, the same procedure is repeated and inside the loop ga is defined with lower bound of 0 and upper bound of 1.
10. Again,, in Study 3 the same procedure for Study 2 is continued and optimoptions command is used to give population and options is used to provide ga with population.

RESULT:

Statistical behaviour with Unbounded Condition:

Statistical behaviour with Bounded Condition:

Statistical behaviour with Bounds and Population:

CONCLUSION:

The stalagmite function is optimised and find the global maxima of the function.
The GA is only used for the minimum function therefore to maximize the function we inversed the minimum function.

REFERENCE:

https://skill-lync.com/knowledgebase/genetic-algorithm-explained

https://www.tutorialspoint.com/genetic_algorithms/genetic_algorithms_introduction.htm

https://in.mathworks.com/help/gads/ga.html?s_tid=srchtitle#mw_a9a9e523-4242-481e-b6b9-acbe194a2432