Week 4.1 - Genetic Algorithm

A. OBJECTIVE:

1. Write a code in MATLB to optimize the stalagmite function and find the global maxima of the function.
2. Explain the concept of Genetic Algorithm and the syntax of GA in MATLAB.
3. Display same output when made to run several times.
4. Plot graph between Function Maximum (stalagmite function) vs no of iterations.

B. TERMINOLOGIES:

1. Stalagmite function

        A stalagmite function generally refers to the function with which we are generating values over a stalagmite (growing mound of mineral deposits) surface for finding out the global maxima and minima of a                given function.

    1.1 How to maximize the function?

         The stalagmite function defined returns the minima value. To modify the function to get the maxima value we have to reverse the sign.

2. Genetic Algorithm

        Genetic Algorithm or GA was developed by Prof. John Holland, his colleagues and students at the university of Michigan around 1975.

    2.1 What is Genetic Algorithm?

       The genetic algorithm is an method for solving both constrained and unconstrained optimization problems that is based on natural selection, the process that drives biological evolution. The genetic algorithm           repeatedly modifies a population of individual solutions.

    2.2 How does it work ?

      At each step, the genetic algorithm selects individuals at random from the current population to be parents and uses them to produce the children for the next generation. Over successive generations, the                population "evolves" toward an optimal solution.

     Three basic operations that constitute a GA, are as follows:

• Selection: It defines which solutions to preserve for further reproduction e.g. roulette wheel selection.
• Crossover: It describes how new solutions are created from existing ones e.g. n-point crossover.
• Mutation: Its aim is to introduce diversity and novelty into the solution pool by means of randomly swapping or turning-off solution bits e.g. binary mutation.

    2.3 Applications of GA 

    Concept of GA tho was looked skeptically by mathematicians initially as it was not based on proofs, it is now widely implemented in many fields owing to its success.

    Few of the fields it is used are as follows.

1. Production Planning - Trying to optimize the minimum time for manufacturing.
2. Engine Performance - Maximize efficiency
3. Travelling Sales man - to reduce the time taken to travel by finding the best path

    2.4 Advantages and Disadvantages of GA

    ADVANTAGES

• The concept is easy to understand
• It is good for ‘noisy’ environments
• GA search from a population of points, not a single point.
• Works well on mixed discrete/continuous problems.

   DISADVANTAGES

• The implementation requires good research.
• GA requires less information about the problem, but designingan objective function and getting the representation and operators right can be difficult.
• GA is computationally expensive I.e. Time Consuming

   Since GA is time consuming an effective was of finding an optimum solution is to initially start with GA and then shift to gradient based method once you find the region of optimization.

    2.5 Syntax of GA in MATLAB

    Syntax for GA that are being used in this case are as follows.

1. x = ga(fun,nvars)

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

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

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.

C. FORMULAS:

1. Stalagmite Function

D. PROGRAMMING IN MATLAB

clear all
close all
clc
 
�fining an 1D array of random values from the search space 0-1
x = linspace(0,1,300);
y = linspace(0,1,300);
iterations = 50;
 
�fining a 2D array
[xx,yy] = meshgrid(x,y);
for i=1:length(x)
    for j=1:length(y)
        input(1)=xx(i,j);
        input(2)=yy(i,j);
        f(i,j) = stalagmite(input);
    end
end

�SE 1 - Without any boundary condition
 
 tic
 for i=1:iterations
     [results,func_optimum(i)]=ga(@stalagmite,2)
     x_optimum(i) = results(1)
     y_optimum(i) = results(2)
 end
  CASE_1_TimeTaken = toc % will display the time taken to complete the command
  
%Plot of CASE 1
 
figure(1)
subplot(2,1,1)
surf(x,y,-f)
shading interp
hold on
plot3(x_optimum,y_optimum,-func_optimum,'marker','o','color','r')
subplot (2,1,2)
plot(-func_optimum)
xlabel('iterations')
ylabel('Fucntion Maximum')

�SE 2 - With boundary condition and limited population size
 
tic
    for i=1:iterations
     [results,func_optimum(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1])
     x_optimum(i) = results(1)
     y_optimum(i) = results(2)
 end
  CASE_2_TimeTaken = toc % will display the time taken to complete the command
  
%Plot of CASE 2
 
figure(2)
subplot(2,1,1)
surf(x,y,-f)
shading interp
hold on
plot3(x_optimum,y_optimum,-func_optimum,'marker','o','color','r')
subplot (2,1,2)
plot(-func_optimum)
xlabel('iterations')
ylabel('Fucntion Maximum')

�SE 3 - With boundary condition and increased population size
tic
options = optimoptions('GA')
options = optimoptions(options,'Populationsize',300)
    for i=1:iterations
     [results,func_optimum(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options)
     x_optimum(i) = results(1)
     y_optimum(i) = results(2)
 end
  CASE_3_TimeTaken = toc % will display the time taken to complete the command
  
%Plot of CASE 3
 
figure(3)
subplot(2,1,1)
surf(x,y,-f)
shading interp
hold on
plot3(x_optimum,y_optimum,-func_optimum,'marker','o','color','r')
subplot (2,1,2)
plot(-func_optimum)
xlabel('iterations')
ylabel('Fucntion Maximum')

E. EXPLANATION

1. Clear all,close all,clc command is used to clear data stored in workspace,close plot and figures and clear the command window respectively.
2. A one dimensional array was defined taking values between 0 and 1 using the lindspace command. The values of X and Y are stored in the variables.
3. A 2D matrix was formed from the above 1D matrix and stored in an variable array.
4. Here we define the fitness of the values with the stalagmite function, which is defined as follows:

%function defining stalagmite function

 

function [value] = stalagmite(input)

x = input(1);

y = input(2);

 

f1 = (sin(5.1*pi*x+0.5)).^6;

f2 = exp((-4*log(2)*((x-0.0667).^2))/0.64);

 

f3 = (sin(5.1*pi*y+0.5)).^6;

f4 = exp((-4*log(2)*((y-0.0667).^2))/0.64);

 

value = -(f1*f2*f3*f4); %'-' is used to reverse the function output to show maxima

5. Minus is added to the value to output the maxima.
6. CASE 1

• we run the GA function using the stalagmite function set to 2 variables upto 50 iterations.
• No boundary is set therefore the GA initially choose random value to create population.
• Then this population is selected, crossover and mutated to get best fitness values.
• Tic Toc command is used to compute the amount of time taken to execute the code.

�SE 1 - Without any boundary condition

 

 tic

 for i=1:iterations

     [results,func_optimum(i)]=ga(@stalagmite,2)

     x_optimum(i) = results(1)

     y_optimum(i) = results(2)

 end

  CASE_1_TimeTaken = toc % will display the time taken to complete the command​

7. CASE 2

• we run the GA function using the stalagmite function set to 2 variables upto 50 iterations.
• Here we set a lower and upper bound values so that the GA can narrow down the values within that range.
• Then this population is selected, crossover and mutated to get best fitness values.
• Tic Toc command is used to compute the amount of time taken to execute the code.

�SE 2 - With boundary condition and limited population size

 

tic

    for i=1:iterations

     [results,func_optimum(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1])

     x_optimum(i) = results(1)

     y_optimum(i) = results(2)

 end

  CASE_2_TimeTaken = toc % will display the time taken to complete the command

  

8. CASE 3

• we run the GA function using the stalagmite function set to 2 variables upto n iterations.
• Here we set a lower and upper bound values so that the GA can narrow down the values within that range.
• Here we increase the population size using the optimoptions input within the GA function
• Then this population is selected, crossover and mutated to get best fitness values.
• Tic Toc command is used to compute the amount of time taken to execute the code.

 

�SE 3 - With boundary condition and increased population size

tic

options = optimoptions('GA')

options = optimoptions(options,'Populationsize',300)

    for i=1:iterations

     [results,func_optimum(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options)

     x_optimum(i) = results(1)

     y_optimum(i) = results(2)

 end

  CASE_3_TimeTaken = toc

 

9. Plot is generated between function maximum and number of iterations.

F. RESULTS

CASE 1

                                                               Plot

Time taken : 3.1839 sec

CASE 2

                                                               Plot

Time taken : 4.4213 sec

CASE 3

                                                               Plot

Time taken : 17.0779 sec

WorkSpace

G. ERRORS

• This error is dues to calling the variable by the wrong name.
• Variable was names iterations but was called as iteration.

H. CONCLUSION

• We observe that in Genetic algorithm optimization of function with increased population size global minimum or maximum can be found.
• As the generation progress the time taken also increases. As observed from above T3 > T2 > T1

I. REFERENCE

• Mathworks.com
• How GA works
• NPTEL Course