Week 4.1 - Genetic Algorithm

GENETIC ALGORITHM [GA]

• GENETIC ALGORITHM is a search heuristic inspired by Charles Darwin in his THEORY OF EVOLUTION.
• This theory of Charles explains how the biological evolution occurs.
• Can be also well understood by the phrase " Survival of the fittest".
• The process starts with the selection of the fittest set of individual from a given set of population.
• Then they produce offsprings which are almost resemble their parent bodies.
• And in some cases some random mutation takes place due to the urge to adapt to the surrounding and the urge to survive and this called as evolution.
• These offsprings are then added to the next generation.
• The fittest individual survive and pass on their characterestic to the next generation.
• The individual not able to mutate or adapt according to the surrounding get extinct.
• The same process keeps on repeating itself and the set of fittest individuals are obtained.
• The same concept is used in MATLAB in a predefined function 'ga'.
• through 'ga' we select random solutions to a given problem and it sorts out the best one.
• This eventually narrows down to the best set of solutions that provide optimum results for the given problem.
• THE PHASES IN GENETIC ALGORITHM ARE AS FOLLOWS
  • Initial population
  • Fitness Function
  • Selection Phase
  • Crossover
  • Mutation
  • Termination
• PSEUDOCODE FOR GENETIC ALGORITHM

  • START
         Generate Initial Population
         Compute fitness
    
    REPEAT
          Selection
          Crossover
          Mutation
          Compute Fitness
          Iterate until population converges
    STOP
• SYNTAX FOR GENETIC ALGORITHM

  • F = ga(@fun,nvars,A,b,Aeq,Beq,lb,ub,nonlcon,IntCon,options)

  • F = is the local minima point (ga finds only minima but can be optimized to find maxima)
  • ga = is the the inbuilt predefined function
  • @fun = The userdefined functions called here (stalagmite in this case)
  • nvars = is the number of variables in the code
  • A = is the Linear inequality constraint
  • b = is the Linear inequality constraint
  • Aeq = is the Linear equality constraint
  • Beq = is the Linear equality constraint
  • lb = is the lower bounds specified to search space
  • ub = is the upper bounds specified to search space
  • nonlcon = is the nonlinear constraint (vectors representing inequalities or equalities)
  • Intcon = Indices of integer variables
  • options = Used to perform additional operations like modifications in Population Size etc.
• CODE FOR STALAGMITE FUNCTION DEFINED BY USER

  • function [F] = stalagmite(input_vector)
    
    x = input_vector(1);
    y = input_vector(2);
    
    f1 = (sin(5.1*pi*x + 0.5)).^6 ;
    f2 = (sin(5.1*pi*y + 0.5)).^6 ;
    f3 = exp((-4*log(2)*(x-0.0667).^2)/(0.64)) ;
    f4 = exp((-4*log(2)*(y-0.0667).^2)/(0.64)) ;
    F  =  -f1*f2*f3*f4 ;
    end
• CODE FOR GENETIC ALGORITHM ALL 3 CASES

  • clear all 
    close all
    clc
    
    %defining search space
    
    x = linspace(0,0.6,150);
    y = linspace(0,0.6,150);
    iterations = 50;
    
    %creating a 2D mesh
    
    [X Y] = meshgrid(x , y);
    
    %for loop for stalagmite function
    
    for i = 1 : length(X)
                for j = 1 : length(Y)
                input_vector(1) = X(i,j);
                input_vector(2) = Y(i,j);
                F(i,j) = stalagmite(input_vector) ;
                end
    end
    
    tic  %Time counter for CASE 1 starts here
    
    %for loop for CASE 1
    
    for  i = 1 : iterations
        [inputs , F_optimum(i)] = ga(@stalagmite,2);
        x_optimum(i) = inputs(1);
        y_optimum(i) = inputs(2);
    end
    
    CASE_1_time = toc; %Time counter for CASE 1 ends here
    
    %plotting for CASE 1
    
    figure (1)     %figure 1 refers to case 1
    subplot(2,1,1)
    hold on 
    surfc(X, Y, F)
    shading interp
    plot3(x_optimum, y_optimum, F_optimum,'color','r','linewidth',2, 'marker', 'o', 'markersize', 5, 'markerfacecolor', 'k')
    title('Unbounded inputs')
    subplot(2,1,2)
    plot(F_optimum,'linewidth',2, 'color', 'r')
    xlabel('Iterations')
    ylabel('Function Maximum')
    
    tic  %Time counter for CASE 2 starts here
    
    %for loop for CASE 2
    
    for  i = 1 : iterations
        [inputs , F_optimum(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6]);
        x_optimum(i) = inputs(1);
        y_optimum(i) = inputs(2);
    end
    
    CASE_2_time = toc; %Time counter for CASE 2 ends here
    
    %plotting for CASE 2
    
    figure (2)     %figure 2 refers to case 2
    subplot(2,1,1)
    hold on 
    surfc(X, Y, F)
    shading interp
    plot3(x_optimum, y_optimum, F_optimum,'color','r','linewidth',2, 'marker', 'o', 'markersize', 5, 'markerfacecolor', 'k')
    title('Bounded inputs')
    subplot(2,1,2)
    plot(F_optimum,'linewidth',2,'color', 'r')
    xlabel('Iterations')
    ylabel('Function Maximum')
    
    tic  %Time counter for CASE 3 starts here
    
    options = optimoptions('ga', 'PopulationSize',300)
    
    %for loop for CASE 3
    
    for  i = 1 : iterations
        [inputs , F_optimum(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6],[],[],options);
        x_optimum(i) = inputs(1);
        y_optimum(i) = inputs(2);
    end
    
    CASE_3_time = toc ;%Time counter for CASE 3 ends here
    
    %plotting for CASE 3
    
    figure (3)     %figure 3 refers to case 3
    subplot(2,1,1)
    hold on 
    surfc(X, Y, F)
    shading interp
    plot3(x_optimum, y_optimum, F_optimum,'color','r','linewidth',2, 'marker', 'o', 'markersize', 5, 'markerfacecolor', 'k')
    title('Bounded inputs with modified population size')
    subplot(2,1,2)
    plot(F_optimum,'linewidth',2, 'color', 'r')
    xlabel('Iterations')
    ylabel('Function Maximum')
    
• EXPLANATION
  • The code starts with defining the search space in form of x & y
  • Iterations are specified on the next line
  • 2D matrices X & Y aregenerated using meshgrid command using x,y.
  • Then a for loop is generated to define input vectors for stalagmite function
  • Matrices X & Y are used here
  • From here the program is further is divided into 3 different CASES..
  • the time taken for all 3 CASES is recorded using tic & toc.
  • The outputs and the plots of all 3 CASES are attached below
  • All 3 CASES are briefly explained below
  • CASE 01 -
    • In CASE 01 , the maxima or the GA is executed using the for loop without defining any search space.
    • Hence , the output is very confusing,random, and kind of useless.
  • CASE 02 -
    • In CASE 02 , the search space is defined , I:e the upper and lower bounds are defined and so we can see in the plots that the output is quite certain and varies in a specified region.
  • CASE 03 -
    • In CASE 03, the population size is modified I:e increased so as to converge the global maxima.