Week 4 - Genetic Algorithm

AIM : Write a code in MATLAB to optimise the stalagmite function and find the global maxima of the function.

OBJECTIVE : to optimise the stalagmite function and find the global maxima of the function and to explain the concept of genetic algorithm in your own words and also explain the syntax for ga in MATLAB

EXPLANATION : The genetic algorithm is a 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. 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. You can apply the genetic algorithm to solve a variety of optimization 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 can address problems of mixed integer programming, where some components are restricted to be integer-valued.

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.

The genetic algorithm differs from a classical, derivative-based, optimization algorithm in two main ways, as summarized in the following table.

Classical Algorithm	Genetic Algorithm
Generates a single point at each iteration. The sequence of points approaches an optimal solution.	Generates a population of points at each iteration. The best point in the population approaches an optimal solution.
Selects the next point in the sequence by a deterministic computation.	Selects the next population by computation which uses random number generators.

PROCEDURE :

STEPS USED IN THE GENETIC ALGORITHM (GA)

• Initialize population
• Selection according to fitness
• Crossover between the selected chromosomes
• Perform the mutation
• Repeat cycle till the condition of the stop if true

INPUT FUNCTION :

`f(x,y)=f1,x⋅f2,x⋅f1,y⋅f2,y`

`f1,x=[sin(5.1πx+0.5)]^6`

`f1,y=[sin(5.1πy+0.5)]^6`

`f2,x=exp[-(4ln(2)(x-0.0667)^2)/(0.64)]`

`f2,y=exp[-(4ln(2)(x-0.0667)^2)/(0.64)]`

There are three ways to perform this function

1. Study of genetic algorithm for the random sampling
2. Study of genetic algorithm with upper and lower bound sampling
3. Study of genetic algorithm with upper and lower bound and increase the population size

PROGRAM :

clear all
close all
clc

x=linspace(0,0.6,150);
y=linspace(0,0.6,150);

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


%Evaluating the stalagmite function
for i=1:length(xx)
    
   for j=1:length(yy)
       input_vector(1)=xx(i,j);
       input_vector(2)=yy(i,j);
       val(i,j)=stalagmite(input_vector);
    
   end
   
end

%Plotting the stalagmite function
figure('Name','Stalagmite function','NumberTitle','off')
    surfc(xx,yy,-val);
    shading interP;

%Running the genetic algorithm
[coord, htval]=ga(@stlagmite,2);


%Case 1: Statistical behaviour

%Defining no. of iterations:
num_cases=50;

tic %Setting up timer to know the time required (tic-toc command)

for k=1:num_cases %Running the genetic algorithm multiple times

    [inputs, fopt(k)]= ga(@stalagmite,2);
    xopt(k)=inputs(1);
    yopt(k)=inputs(2);
     
end

fopt=fopt*(-1); %Since we want the maxima of stalagmite function

case_1_time=toc

%Creating new figure window and plotting the data
figure('Name','Case 1: Statistical Behaviour','NumberTitle','off') 

subplot(2,1,1);
    hold on
    srf_pt= surfc(x,y,-val);
    shading interp;
    fopt_plot(3)= plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','r');
    title('Unbounded inputs');

    subplot(2,1,2);
    twodplot(4)= plot(fopt);
    axis([0 50 -1 2 -1 1]);
    xlabel('Iterations');
    ylabel('Function maximum');


%Case 2: Statistical behaviour with upper and lower bounds

tic
for l=1:num_cases
    
    %The seventh and eighth position of 'ga' syntax is for setting limits
    [inputs, fopt_2(l)]= ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
    xopt_2(l)=inputs(1);
    yopt_2(l)=inputs(2);
     
end
case_2_time=toc

fopt_2=fopt_2*(-1);

figure('Name','Case 2: Bounded upper and lower limits of search space','NumberTitle','off')

    subplot(2,1,1);
        hold on
        srf_pt=surfc(x,y,-val);
        shading interp;
        fopt_plot(5)=plot3(xopt_2,yopt_2,fopt_2,'marker','o','markersize',5,'markerfacecolor','r');
        title('Bounded inputs');

    subplot(2,1,2)
        twodplot(6)= plot(fopt_2);
        axis([0 50 -1 2 -1 1]);
        xlabel('Iterations');
        ylabel('Function maximum');


%Case 3: Increasing the no. of ga iterations

%Setting population size to 200
%optimoptions allows to change the options in an optimization algorithm
options=optimoptions('ga','PopulationSize',200); 

tic

for m=1:num_cases
    
  [inputs, fopt_3(m)]= ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
  xopt_3(m)=inputs(1);
  yopt_3(m)=inputs(2); 
        
end

case_3_time=toc

fopt_3=fopt_3*(-1);

figure('Name','Case 3: Increasing the Population Size','NumberTitle','off')

    subplot(2,1,1);
        hold on
        srf_pt= surfc(x,y,-val);
        shading interp;
        fopt_plot(7)= plot3(xopt_3,yopt_3,fopt_3,'marker','o','markersize',5,'markerfacecolor','r');
        title('Bounded inputs with high population size');

    subplot(2,1,2);
        twodplot(8)= plot(fopt_3);
        axis([0 50 -1 2 -1 1]);
        xlabel('Iterations');
        ylabel('Function maximum');

ERRORS :

UPDATED PROGRAM :

clear all
close all
clc

x=linspace(0,0.6,150);
y=linspace(0,0.6,150);

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


%Evaluating the stalagmite function
for i=1:length(xx)
    
   for j=1:length(yy)
       input_vector(1)=xx(i,j);
       input_vector(2)=yy(i,j);
       val(i,j)=stalagmite(input_vector);
    
   end
   
end

%Plotting the stalagmite function
figure('Name','Stalagmite function','NumberTitle','off')
    surfc(xx,yy,-val);
    shading interP;

%Running the genetic algorithm
[coord, htval]=ga(@stalagmite,2);


%Case 1: Statistical behaviour

%Defining no. of iterations:
num_cases=50;

tic %Setting up timer to know the time required (tic-toc command)

for k=1:num_cases %Running the genetic algorithm multiple times

    [inputs, fopt(k)]= ga(@stalagmite,2);
    xopt(k)=inputs(1);
    yopt(k)=inputs(2);
     
end

fopt=fopt*(-1); %Since we want the maxima of stalagmite function

case_1_time=toc

%Creating new figure window and plotting the data
figure('Name','Case 1: Statistical Behaviour','NumberTitle','off') 

subplot(2,1,1);
    hold on
    srf_pt= surfc(x,y,-val);
    shading interp;
    fopt_plot(3)= plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','r');
    title('Unbounded inputs');

    subplot(2,1,2);
    twodplot(4)= plot(fopt);
    axis([0 50 -1 2 -1 1]);
    xlabel('Iterations');
    ylabel('Function maximum');


%Case 2: Statistical behaviour with upper and lower bounds

tic
for l=1:num_cases
    
    %The seventh and eighth position of 'ga' syntax is for setting limits
    [inputs, fopt_2(l)]= ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
    xopt_2(l)=inputs(1);
    yopt_2(l)=inputs(2);
     
end
case_2_time=toc

fopt_2=fopt_2*(-1);

figure('Name','Case 2: Bounded upper and lower limits of search space','NumberTitle','off')

    subplot(2,1,1);
        hold on
        srf_pt=surfc(x,y,-val);
        shading interp;
        fopt_plot(5)=plot3(xopt_2,yopt_2,fopt_2,'marker','o','markersize',5,'markerfacecolor','r');
        title('Bounded inputs');

    subplot(2,1,2)
        twodplot(6)= plot(fopt_2);
        axis([0 50 -1 2 -1 1]);
        xlabel('Iterations');
        ylabel('Function maximum');


%Case 3: Increasing the no. of ga iterations

%Setting population size to 200
%optimoptions allows to change the options in an optimization algorithm
options=optimoptions('ga','PopulationSize',200); 

tic

for m=1:num_cases
    
  [inputs, fopt_3(m)]= ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
  xopt_3(m)=inputs(1);
  yopt_3(m)=inputs(2); 
        
end

case_3_time=toc

fopt_3=fopt_3*(-1);

figure('Name','Case 3: Increasing the Population Size','NumberTitle','off')

    subplot(2,1,1);
        hold on
        srf_pt= surfc(x,y,-val);
        shading interp;
        fopt_plot(7)= plot3(xopt_3,yopt_3,fopt_3,'marker','o','markersize',5,'markerfacecolor','r');
        title('Bounded inputs with high population size');

    subplot(2,1,2);
        twodplot(8)= plot(fopt_3);
        axis([0 50 -1 2 -1 1]);
        xlabel('Iterations');
        ylabel('Function maximum');

FUNCTION CODE :

function output=stalagmite(input_vector)

x = input_vector(1);
y = input_vector(2);

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

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

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

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

output = val1*val2*val3*val4;

output=output.*(-1);

end

RESULTS :

Fig-1 3-d surface generated by GA for random sampling

Fig-2 3-D plot generated by GA for the unbounded inputs

Fig-3 The plot generated by GA using upper and lower bound

Fig-4 The plot generated by GA using for increasing the population size and bounded region

Time taken to run the three case studies are :