Week 4.1 - Genetic Algorithm

AIM:-

• Write a code in MATLAB to optimize the stalagmite function and find the Global Maxima of the function.

Introduction:-

• Genetic Algorithm (GA) is a search-based optimization technique based on the principles of Genetics and Natural Selection. It is frequently used to find optimal or near-optimal solutions to difficult problems which otherwise would take a lifetime to solve. It is frequently used to solve optimization problems, in research, and in machine learning

What is Stalagmite function?

• It is a function that contains the input parameters that are to be given a plot like a stalagmite structure. Calling the function stalagmite that contains the code for evaluates the value of the function using the array input. For the study of the statistical behaviour of the Genetic Algorithm, primarily a stopwatch is started.

It contains the following formulas to generate the data that causes to be plot,
F = (F x * F y * F x * F y)
F y = (sin (5.1*π*y1+0.05))
F x = exp(-4*log(2)*((x1-0.0667) )/0.64)
F y = exp(-4*log(2)*((y1-0.0667) /0.64)

Stalagmite function generated plot

Genetic Algorithm

• A genetic algorithm is a search method used in artificial intelligence and computing. It is used for finding optimized solutions to search problems based on the
  theory of natural selection and evolutionary biology.
• ga is good for searching large and complex data sets
• ga are most commonly used in optimization problems where we have to maximize a given objective function and set of constraints.

Working of Genetic Algorithm:

• 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
• Then the sequence of points approaches an optimal solution

Genetic algorithm

• A genetic algorithm is a search heuristic that is inspired by Charles Darwin’s theory of natural evolution. This algorithm reflects the process of natural selection
  where the fittest individuals are selected for reproduction in order to produce offspring of the next generation.

Process of natural selection

• The process of natural selection starts with the selection of the fittest individuals from a population. They produce offspring which inherit the characteristics of the parents and will be added generation. If parents have better fitness, their offspring will be better than parents and have a better chance at surviving. This process keeps on iterating and at the end, a generation with the fittest individuals will be found.
• This notion can be applied to a search problem. We consider a set od solutions for a problem and select the set of best ones out of them.
• Five phases are considered in a genetic algorithm.
  1. Initial population
  2. Fitness function
  3. Selection
  4. Crossover
  5. Mutation

ga is function of MATLAB

Syntax

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(___)

Description

• x = ga(fun,nvars) finds a local unconstrained minimum, x, to the objective function, fun. nvars is the dimension (number of design variables) of fun.
  Note
  Passing Extra Parameters explains how to pass extra parameters to the objective function and nonlinear constraint functions, if necessary.
• 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').
• 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').
• 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.)
• 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.)
• 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.
• x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon) or x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon,options) requires that the variables listed in IntCon take integer
  values.
  Note
  When there are integer constraints, ga does not accept linear or nonlinear equality constraints, only inequality constraints.
• x = ga(problem) finds the minimum for problem, a structure described in problem.
• [x,fval] = ga(___), for any previous input arguments, also returns fval, the value of the fitness function at x.
• [x fval exitflag output] = ga( ) also returns exitflag an integer identifying the reason the algorithm terminated and output a structure that contains output
  
• [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.

MATLAB Stalagmite function program:

function [f] = stalagmite_func(input_vector);
x1 = input_vector(1);
y1 = input_vector(2);
f1x = (sin(5.1*pi*x1+0.5))^6;
f1y = (sin(5.1*pi*y1+0.5))^6;
f2x = exp(-4*log(2)*((x1-0.0667).^2)/0.64);
f2y = exp(-4*log(2)*((y1-0.0667).^2)/0.64);
f = -(f1x*f1y*f2x*f2y);
end

MATLAB Program:

clear all
close all
clc
%Defining our search space

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

%Creating a 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);
f(i,j)=stalagmite_func(input_vector);
    end
end
figure(1)
surfc(xx,yy,-f)
shading interp
xlabel('x value')
ylabel('y value')
title('stalagmite')
%study 1
n_iteration = 50;
tic
for i = 1:n_iteration
[inputs,fopt(i)] = ga(@stalagmite_func,2);
xopt1(i) = inputs(1);
yopt1(i) = inputs(2);
end
study_time1 = toc;
%plotting
figure(2)
subplot(2,1,1)
hold on
surfc(x,y,-f)
title('unbounded input')
xlabel('x value')
ylabel('y value')
shading interp
hold on
plot3(xopt1,yopt1,-fopt,'marker','o','markersize',4,'markerfacecolor','r')
subplot(2,1,2)
plot(-fopt)
xlabel('iteration')
ylabel('function minimum')
tic

%study2 - statistical behaviour with upper and lower bounds
for i=1:n_iteration
[inputs,fopt(i)] = ga(@stalagmite_func,2,[],[],[],[],[0;0],[0.6;0.6]);
xopt(i) = inputs(1);
yopt(i) = inputs(2);
end
study2_time=toc
%plotting
figure(3)
subplot(2,1,1)
surfc(x,y,-f)
shading interp
title('bounded inputs')
xlabel('x value')
ylabel('y value')
hold on
plot3(xopt1,yopt1,-fopt,'marker','o','markersize',4,'markerfacecolor','b')
subplot(2,1,2)
plot(-fopt)
xlabel('iteration')
ylabel('function minimum')
%study3 increasing the population size
options = optimoptions(@ga);
options = optimoptions(@ga,'populationsize',500)
tic
for i=1:n_iteration
[inputs,fopt(i)]=ga(@stalagmite_func,2,[],[],[],[],[0;0],[0.6;0.6],[],[],options);
xopt(i)=inputs(1);
yopt(i)=inputs(2);
end
study3_time=toc;
figure(4)
subplot(2,1,1)
surfc(x,y,-f)
shading interp
title('bounded inputs with increased population size')
xlabel('x value')
ylabel('y value')
hold on
plot3(xopt1,yopt1,-fopt,'marker','o','markersize',4,'markerfacecolor','m')
subplot(2,1,2)
plot(-fopt)
xlabel('iteration')
ylabel('function minimum')

OUTPUTS:

1. Stalagmite Function:

2. Unbounded Inputs

3. Bounded Inputs

4. Bounded Inputs with Increase Population