Challenge

Week 4.1 - Genetic Algorithm

RRamendra Sharma6 Dec 2021

Stalagmite - A stalagmite is a type of rock formation that rises from the floor of a cave due to the accumulation of material deposited on the floor from ceiling drippings. It is an upward-growing mound of mineral deposited that have precipited from water drippin g onto the floor of a cave. Most stalagmite have rounder or flattened tips.

Stalagmite function - A stalagmite function generally refers to the function with which we are generating values over a stalgmite kind of surface for finding out the local and global maxima and minima of that particular given function. stalagmite function is defined as by the govering equation

In matlab we are using a method called 'Optimization'. It is a programming which does a selection of the best element with the help of some criterion set of population. To perform Optimization we use 'Genetic Algorithm' method which is a inbuild function in matlab to find the global maxima of that given stalagmite function.

Genetic Algorithm - The genetic algorithm is a method for solving both constrained and unconstrained optimization problems that is based on the natural selection,the process that drives biological evolution. The genertic algorithm repeatedly modifies a population of individual solutions. GAs are a subset of a much larger branch of computation known as Evolutionary Computation.

GAs were developed by John Holland and his students and colleagues at the University of Michign, most notably David E.Goldberg and has since been tried on various optimization problems with a high degree of success. In GAs , we have a pool or a population of possible solutionbs 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 individual 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'.

In this way we keep 'evolving' better individuals or solutions over generations,till we reach a stopping criterion.

Genetic Algorithm are sufficiently randomized in nature, but they perform much better than random local search (in which we just try various random solutions keeping track of the best so far), as they exploit historical information as well.

Advantages of GAs -

Generates a population of points at each iteration. The best point in the population approaches an optimal solution
Useful when the search space is very large and there are a larger number of parameters involved.
It is faster and more efficient as compared to the traditional method.
Optimizes both continuous and discrete functions.

Limitations of GAs - GAs is not applicable for simple function and those function which we have easily find the derivative i.e the function which derivative information is available.

Syntax for GAs

x=ga(@stalagmite,2,A,B,Aeq,Beq,lb,ub,nonlcon,options)

x=ga(fun,nvars,A,B,Aeq,Beq,lb,ub,nonlcon,options)

x is the local minima point.
ga is the Genetic algorithm function
fun is the function to be called .(in this case fun is stalagmite function)
nvars indicates the no of variables i.e 2 in this case
A and Bare used to indicate any kind of inequalities that exist in the function.
Aeq and Beq also denotes the inequalities.
lb is lower bound
ub is upper bound
nonlcon is nonlinear inequalities and equalities.
Options is used for increasing the population size.

code for stalagmite function

function [f]=stalagmite(input_vector)

x=input_vector(1); % input value for x
y=input_vector(2); % input valve for y
f1x=(sin((5.1*pi*x)+0.5))^6;
f1y=(sin((5.1*pi*y)+0.5))^6;
f2x=exp((-4)*log(2)*((x-0.0667)^2)/0.64);
f2y=exp((-4)*log(2)*((y-0.0667)^2)/0.64);
f=-(f1x*f1y*f2x*f2y); % negative sign is used for find maximum value
end

first iteration- there is no constrained i.e not defining the limits.

% first iteration

clear all
close all
clc

x=linspace(0,0.6,150); % x value inputs     
y=linspace(0,0.6,150); % y value inputs

[xx,yy]=meshgrid(x,y);

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)=stalagmite(input_vector);
    end
end

num_cases=50;  % ga runs for 50 iteration
tic            % study time count start
for i=1:num_cases
    [inputs,f_input(i)]=ga(@stalagmite,2); %ga function is used to run the stalagmite data and give the optimal solution
                                           
     x_output(i)=inputs(1);
      y_output(i)=inputs(2);
    % f_output(i)=f_input(1) as ga gives us minimum value
end

study1_time=toc;   % study time count end
figure(1)
subplot(2,1,1)
surfc(xx,yy,-f)    % generation of stalagmite function
shading interp     % to bring viusally smooth curve surface without mesh lines
hold on
plot3(x_output,y_output,-f_input,'marker','*','Markersize',4,'MarkerEdgeColor','r');
title('unbounded inputs')
subplot(2,1,2)
plot(-f_input)
xlabel('iteration')
ylabel('function max')
toc

results

2nd iteration- there are use of constrained i.e we have to define the boundaries. Here the lower and upper bounds are defined so as to know the global maxima is occour.

% second iteration

clear all
close all
clc

x=linspace(0,0.6,150);  % x value inputs
y=linspace(0,0.6,150);  % y value inputs

[xx,yy]=meshgrid(x,y);

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)=stalagmite(input_vector);
    end
end

num_cases=100;   % ga runs for 100 iteration
tic              % study time count start
for i=1:num_cases
     % objective function is stalagmite and the number of variable is 2
     % A,B,Aeq,Beq is defined by [] , as there is no linear equalities and inequalities constrains in this function
     % lower boundary of variables x and y in ga algorithm is set as [0,0]
     % upper bounday of variables x and y in ga algorithm is set as[0.6,0.6]

    [inputs,f_input(i)]=ga(@stalagmite,2,[],[],[],[],[0,0],[0.6,0.6])
    x_output(i)=inputs(1);
    y_output(i)=inputs(2);
 % f_output(i)=-f_input(1) ga gives us minimun value inverse of f_input is taken for maximum value 
   
end
study2_time=toc; % study time end
figure(2)
subplot(2,1,1)
surfc(xx,yy,-f)  % generation of stalagmite function
shading interp   % to bring viusally smooth curve surface without mesh lines
hold on
plot3(x_output,y_output,-f_input,'marker','*','Markersize',4,'MarkerEdgeColor','y');
title('unbounded inputs')
subplot(2,1,2)
plot(-f_input)
xlabel('iteration')
ylabel('function max')
toc

results

3rd iteration- use of Optimization by increasing the population size by which we have to find the global maxima with in the population size.

% Third iteration
clear all
close all
clc

x=linspace(0,0.6,150);  % x value inputs
y=linspace(0,0.6,150);  % y value inputs

[xx,yy]=meshgrid(x,y);

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)=stalagmite(input_vector);
    end
end
num_cases=50;   % ga runs for 50 iteration

options=optimoptions('ga')
options=optimoptions(options,'PopulationSize',300);

tic % study time start
for  i=1:num_cases
     % objective function is stalagmite and the number of variable is 2
     % A,B,Aeq,Beq is defined by [] , as there is no linear equalities and inequalities constrains in this function
     % lower boundary of variables x and y in ga algorithm is set as [0,0]
     % upper bounday of variables x and y in ga algorithm is set as[0.6,0.6]
     % populationsize is defined by using options in the algorithm
     [inputs,f_input(i)]=ga(@stalagmite,2,[],[],[],[],[0,0],[0.6,0.6],[],options);

     x_output(i)=inputs(1);
     y_output(i)=inputs(2);
 %f_output(i)=-f_input(1)as ga gives as minimum value reverse f_input is taken for maximum value
 end
study3_time=toc; %study time end
figure(3)
subplot(2,1,1)
surfc(xx,yy,-f)   % generation of stalagmite function
shading interp    % to bring viusally smooth curve surface without mesh lines
hold on
plot3(x_output,y_output,-f_input,'marker','*','Markersize',4,'MarkerEdgeColor','g');
title('bounded inputs with increased populationsize')
subplot(2,1,2)
plot(-f_input)   % plotting -f_input value for every iteration
xlabel('number of iteration')
ylabel('function max')
toc

results