Week 4 - Genetic Algorithm

AIM: To write code in MATLAB to optimize the stalagmite function and find the global maxima of the function.

OBJECTIVE: 1) Explanation about the concept of a genetic algorithm.

                    2) Explanation of syntax for ga in MATLAB.

EQUATIONS : 

THEORY :

Genetic Algorithms(GAs) are adaptive heuristic search algorithms that belong to the larger part of evolutionary algorithms. Genetic algorithms are based on the ideas of natural selection and genetics. These are intelligent exploitation of random search provided with historical data to direct the search into the region of better performance in solution space.

“They are commonly used to generate high-quality solutions for optimization problems and search problems.”

A Fitness Score is given to each individual which shows the ability of an individual to “compete”. The individual having optimal fitness score (or near optimal) are sought.

The GAs maintains the population of n individuals (chromosome/solutions) along with their fitness scores. The individuals having better fitness scores are given more chance to reproduce than others.

Operators of Genetic Algorithms

Once the initial generation is created, the algorithm evolve the generation using following operators –

1) Selection Operator: The idea is to give preference to the individuals with good fitness scores and allow them to pass there genes to the successive generations.

2) Crossover Operator: This represents mating between individuals. Two individuals are selected using selection operator and crossover sites are chosen randomly. Then the genes at these crossover sites are exchanged thus creating a completely new individual (offspring). For example –

3) Mutation Operator: Mutation is a random process where once the genes are replaced by another to produce a new generic structure. The key idea is to insert random genes in offspring to maintain the diversity in population to avoid the premature convergence. For example –

This generational process is repeated until a termination condition has been reached. Common terminating conditions are:

• A solution is found that satisfies minimum criteria
• Fixed number of generations reached

Why use Genetic Algorithm

Fastest search technique.

Provide optimisation over large space state.

Does not require any derivative information

Always gets an answer to the problem, which gets better over the time.

Useful when the search space is very large and there are a large number of parameters involved.

Make no assumption about the problem space.

SYNTAX of GA :

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

Here,

Input Arguments

fun — Objective function 

nvars - number of variables

A - Linear inequality constaints

b - Linear inquality constraints

Aeq - Linear equality constraints

beq - linear equlity constarints

lb - lower bound

up - upper bound

nonlcon - Nonlinear constraints

options - integer variables

problem - problem descriptions

Output Arguments

x - solution

fval - Objective function value at the solution

PROGRAM :

MATLAB CODE 1:

clear all
close all
clc

% Defining search space

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

% Creating 2 dimensional 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(input_vector);
    end
end

surfc(xx,yy,-f)

xlabel('x values')
ylabel('y values')

shading interp

 [x,fval] = ga(@stalagmite,2)              

 Function code:

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

 OUTPUT :

MATLAB CODE 2 :

clear all 
close all
clc

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

num_cases = 50

% Creating 2 dimensional 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


% Study 1 - Statictical behavior

tic
for i = 1:num_cases
    [inputs,fopt(i)] = ga(@stalagmite_func,2);
        xopt(i) = inputs(1);
        yopt(i) = inputs(2);
end
study1_time = toc

figure(1)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('Unbounded inputs')
subplot(2,1,2)
plot(-fopt)
xlabel('Iterations')
ylabel('Function Maximum')

tic

% Study 2 - Statistical behavier - with upper & lower bounds

for i = 1:num_cases
      [inputs,fopt(i)] = ga(@stalagmite_func,2,[],[],[],[],[0,0],[1:1]);
        xopt(i) = inputs(1);
        yopt(i) = inputs(2);
end
study2_time = toc

figure(2)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded inputs')
subplot(2,1,2)
plot(-fopt)
xlabel('Iterations')
ylabel('Function Maximum')

% Study 3 - Increasing GA interations

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

tic

for i = 1:num_cases
      [inputs,fopt(i)] = ga(@stalagmite_func,2,[],[],[],[],[0,0],[1:1],[],[],options);
        xopt(i) = inputs(1);
        yopt(i) = inputs(2);
end
study3_time = toc

figure(3)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded inputs with increasing ga interations')
subplot(2,1,2)
plot(-fopt)
xlabel('Iterations')
ylabel('Function Maximum')
    
    

 Function code:

function [f] = stalagmite_func(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 Explanation :

1) Start with clear all ,close all, clc to clear all content previously stored.

2) linspace command is used to define 150 x & y values between 0 to 0.6 with 50 num_cases to run 50 time.

3) meshgrid command is used to form two dimentional array.

4) for loop is executed to evaluate the stalagmite function.

5) For case study 1 - statictical behavier for loop is executed.During execution stalagmite function is called with 'ga'.Respective plotting is done. Also, tic and toc command is used to measure time taken for execution.

6) For case study 2 - statictical behavier with upper & lower bounds ,for loop is executed.During execution stalagmite function is called with 'ga'.Also tic and toc command is used to measure time taken for execution.

7) Again ,  For case study 3 - with increasing interations ,for loop is executed.During execution stalagmite function is called with 'ga'.Here optimoptions function is used to return ga solver and to define population size. Also tic and toc command is used to measure time taken for execution.

Function Creation

Here function is created called 'stalagmite_func(input_vector)' using standard formulae .It is get called in main program.

 OUTPUT :

case 1:

case2:

case 3:

 REFERENCE:

 https://skill-lync.com/knowledgebase/genetic-algorithm-explained

 https://in.mathworks.com/help/gads/ga.html

 https://in.mathworks.com/help/optim/ug/optim.problemdef.optimizationproblem.optimoptions.html#btm47os-2