Genetic Algorithm - MATLAB

AIM:

        To optimise the stalagmite function and find the global maxima of the function using MATLAB code.

OBJECTIVE:

          To explain the concept of Genetic algorithm and its syntax and also to find the global maxima of the function.

DESCRPTION:

            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.You can apply the genetic algorithm to solve problems that are not well suited for standard optimization algorithms, including problems in which the objective function is discontinuous, nondifferentiable, stochastic, or highly nonlinear.The genetic algorithm differs from a classical, derivative-based, optimization algorithm in two main ways

          
           GA SYNTAX:               

                 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.    

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,[],[],lb,ub,nonlcon,IntCon)

x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon,options)

x = ga(problem)

[x,fval] = ga(___)

[x,fval,exitflag,output] = ga(___)

[x,fval,exitflag,output,population,scores] = ga(___)

     1.x=ga(fun,nvars)  finds a local unconstrained minimum, x, to the objective function fun. nvars is           dimension (number of design variables) of fun.

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

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

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

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

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

7. x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,Intcon)  requires that the variables listed in IntCon take integer values.

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

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

10. [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.

11. [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.

 WORKING OF GA:    

             The algorithm begins by creating a random initial population.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 the 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.

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

STOPPING CRITERIA :

                      Stopping criteria determines what causes the algorithm to terminate.

Generations specifies the maximum number of iterations the genetic algorithm performs.

Time limit specifies the maximum time in seconds the genetic algorithm runs before stopping.

Fitness limit — If the best fitness value is less than or equal to the value of Fitness limit, the algorithm stops.

Stall generations — If the average change in the fitness function value over Stall generations is less than Function tolerance, the algorithm stops.

Stall time limit — If there is no improvement in the best fitness value for an interval of time in seconds specified byStall time limit, the algorithm stops.

Stall test — Determines whether the definition of “stall” is average change over the last Stall generations, or is the geometric weighted average change, where the geometric weighting factor is (1/2)N for N generations from the end.

Function tolerance — If the average change in the fitness function value over Stall generations is less than Function tolerance, the algorithm stops.

Constraint tolerance — Tolerance for the maximum nonlinear constraint violation. Also,max(sqrt(eps),sqrt(Constraint tolerance)) is the tolerance for linear constraint violations. Not a stopping criterion, the tolerance measures feasibility.

STALAGMITE FUNCTION:   

                          A stalagmite is an upward-growing mound of mineral deposits that have precipitated from water dripping onto the floor of a cave. The figures we get is in the shape of stalagmite so we use this name here. These formulas are represented in the below code.

PROGRAM: 

           DEFINING FUNCTION CODE 

function [f] = func(input_vector)  

a1 = (sin(5.1*pi*input_vector(1)+0.5))^6;
a2 = (sin(5.1*pi*input_vector(2)+0.5))^6;
a3 = exp(-4*log(2)*((input_vector(1)-0.0667)^2)/(0.64)); 
a4= exp(-4*log(2)*((input_vector(2)-0.0667)^2)/(0.64)); 
f = -(a1*a2*a3*a4);

end

               The formulas are well defined in the function code so that it can be called during the required time.

               a1,a2,a3,a4 values are multiplied by each other and the whole values is multiplied by -1 and stored in the variable f in order to get a maximum value. 

               If we did not multiply by -1 , ga in default calculate the minimum value.  

CODE FOR ALL THREE STUDIES:

close all
clear all
clc

%inputs
x = linspace(0,0.6,150)
y = linspace(0,0.6,150)
num_cases = 60


% storing in 2d array
[xx yy] = meshgrid(x,y);

%calling the 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) = func(input_vector);
    end
end

%study 1 behaviour
tic
for i = 1:num_cases
    [inputs,fopt(i)] = ga(@func,2);
     xopt(i) = inputs(1);
     yopt(i) = inputs(2);
end
studytime1 = toc
%unbounded inputs
figure(1)
subplot(2,1,1)
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 maximum')

%study 2 behaviour
tic
for i = 1:num_cases
    [inputs,fopt(i)] = ga(@func,2,[],[],[],[],[0,0],[0.5,0.5]);
     xopt(i) = inputs(1);
     yopt(i) = inputs(2);
end
studytime2 = toc
%bounded inputs
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 maximum')

%study3 behaviour
options = optimoptions('ga');
options = optimoptions(options,'PopulationSize',200);
tic
for i = 1:num_cases
    [inputs,fopt(i)] = ga(@func,2,[],[],[],[],[0;0],[0.5;0.5],[],[],options);
     xopt(i) = inputs(1);
     yopt(i) = inputs(2);
end
studytime3 = toc
%optimisation
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('Optimisation')
subplot(2,1,2)
plot(-fopt)
xlabel('iterations')
ylabel('function maximum')

 PROCEDURE:

             Initially x and y range is given as 0 to 0.6 with range of 150 and num_cases is given as 60.

             We will store the x,y value in a 2d array by using meshgrid function.

             The function which we stored is called in this code for loop function in which our input_vector is differentiated into input_vector(1) and input_vector(2).

             The study behaviour for figure 1 with unbounded inputs includes calling our predefined function in a loop function and running it with our number of num_cases.The study time for 1st plot is calculated and surface plot is employed here.The subplot defines the rows,columns and the position of the variable.

             The study behaviour for figure 2 with bounded inputs includes calling our predefined function  as in study behaviour 1. The only difference between 1 and 2 is, the plot 2 will have different syntax of ga such that it will define along with the range of inputs.

             The study behaviour for figure 3 with increase in options includes calling our predefined function as in both studies. The difference among all the three studies are, in the third study we increase the population size so that the number of populations in each generations is given as 350.

              Thus all three figures have obtained with the given values.

             num_cases = 60, It is mainly used to check the consistency of the values we are getting in the plot. 

FIGURE 1:

 FIGURE 2:        

FIGURE 3:

 WORKSPACE VALUES:

RESULT:

            Thus we have optimised stalagmite function and found the global maxima for the function. 

 REFERNCES:      

https://in.mathworks.com/help/gads/what-is-the-genetic-algorithm.html

https://in.mathworks.com/help/gads/how-the-genetic-algorithm-works.html