Genetic Algorithm

Introduction:

A genetic algorithm (GA) is a method for solving both constrained and unconstrained optimization problems based on a natural selection process that mimics biological evolution. The algorithm repeatedly uses individuals from the current generation and uses them as the parent for the next generation. The GA also includes options like Crossover, mutations, population size, etc.

The GA can be used for any kind of problem whose objective function is highly nonlinear, non-differentiable and discontinuous.

By doing this for several iterations, the GA reached a value nearby to the optimal solution.

Objective:

optimize the stalagmite function and find the global maxima of the function.

Genetic Algorithm Concept:

1. The algorithm begins by creating a random initial population.
2. Then the algorithm creates a sequence of population. The parents from the current generation for the next individuals are selected upon some criteria.
3. Each individual is assigned with a fitness value which is called as raw fitness scores
4. These raw scores are changed to meaningful values. Are called expectation scores
5. Parents are selected upon the expectations
6. Some of the individuals in the population are inducted directly into the next generation. They are called elite individuals.
7. Children are produced randomly or by making changes to a single parent(mutation) or by transferring changes from different parents(crossover)
8. Algorithm strops when the stopping criteria is attained.

GA syntax:

CASE 1: Unbounded Values

[input_a fval1(i)]= ga(@stalagmite,2)

The “input_a” returned by the solver is the best point in the final population computed by command ‘ga’.

The fval1 is the value of the function stalagmite evaluated at the point “input_a”.

The function gives a local unconstrained minimum ’input_a‘ to the objective function stalagmite. ‘2’ is the number of design variables.

CASE 2: with upper and lower bound values

MATLAB syntax: x = ga(fun,nvars,A,b,Aeq,beq,lb,ub)

Programmed syntax: [inputs2, fval2(i)] = ga (@stalagmite,2, [], [], [], [], [0;0], [1;1]);

The syntax defines a lower and upper band for the design variables so that the solution falls between both the bounds (lb ≤ x ≤ ub ). This is done when we know the boundary conditions for the specific problem. Which involves both technical and analytical knowledge.

A, b, Aeq, beq are left empty as the problem under consideration exists with nonlinear inequalities.

CASE 3: with increased population size

With a large population size, the genetic algorithm searches the space for a global minimum. If the population size is low, there are chances that a local minimum can be obtained. A disadvantage in increasing population size is that it increases the time.

Matlab syntax: options = optimoptions(SolverName,Name,Value)

Options = optimoptions ('ga','populationsize',5000)

this options returns the value of the function with the solver ‘ga’ with given optimisation options.

Stalagmite function:

Code content:

clear all
close all
clc

x = linspace(0,0.6,50);                                  % x values
y = linspace(0,0.6,50);                                  %y values
[XX, YY] =  meshgrid(x,y);                               %creation of meshgrid with x and y values

for i = 1:length(XX);
    for j = 1:length(YY);
        input_vector(1) = XX(i,j);                      %fetching values from XX and YY
        input_vector(2) = YY(i,j);
        f(i,j)= stalagmite(input_vector);               % call for stalagmite fuction, takes value f.
    end
end

%Case 1 
%UNBOUNDED VALUES

num_cases=50;                                          %number of iterations
tic
%looping
for i=1:num_cases;
    Fitness_function  = @stalagmite;
    [input_a fmin1(i)]=ga(Fitness_function ,2);
    X1(i)=input_a(1);
    Y1(i)=input_a(2);
end
time1=toc

%plotting
figure(1)
subplot(2,1,1)                                        %dividing the plot into 2
hold on
surfc(XX,YY,f)                                                      
xlabel('x-value')
ylabel('y-value')
zlabel('function value')
shading interp
plot3(X1,Y1,fmin1,'marker','*')
title('Case 1 (Unbounded Values)')
subplot(2,1,2)                                       %2nd plot
plot(fmin1)
xlabel('ITERATIONS')
ylabel('FUNCTION MAXIMUM')

%end of Case1 study

%next case will have bounds so that we give boundary conditions for getting
%most specific results

%case 2 
%with lower bound and upper bound
num_cases = 50;
tic
%looping
Fitness_function = @stalagmite;
for i=1:num_cases;
    [inputs_b, fmin2(i)]=ga(Fitness_function,2,[],[],[],[],[0;0],[1;1]);
    X2(i)=inputs_b(1);
    Y2(i)=inputs_b(2);
end
time2=toc
study2_time=toc;

%plotting
figure(2)
subplot(2,1,1)
hold on
surfc(XX,YY,f);
shading interp
xlabel('x-value')
ylabel('y-value')
zlabel('function value')
shading interp
plot3(X2,Y2,fmin2,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded Statistical Behvaiour')
subplot(2,1,2)
plot(fmin2)
xlabel('iterations')
ylabel('function maximum')

%end of case 2 study

%case 3 with increased population size
options=optimoptions('ga','populationsize',5000)
%looping
tic
iterations = 50;
for i=1:iterations
    Fitness_function = @stalagmite;
   [input_c fmin3(i)]=ga(Fitness_function,2,[],[],[],[],[0;0],[1;1],[],[],options);
   %calling ga function with just lower and upper bounds
   X3(i)=input_c(1);
   Y3(i)=input_c(2);
end
time3=toc

%plotting
figure(3)
subplot(2,1,1)
hold on
surfc(XX,YY,f);
shading interp
plot3(X3,Y3,fmin3,'marker','*','markersize',5)
title('Case 3 (Increased Population by 5000)')
subplot(2,1,2)
plot(fmin3)
xlabel('ITERATIONS') 
ylabel('FUNCTION MAXIMUM')

Code for the stalagmite function:

Since the genetic algorithm tool in MATLAB minimizes a function, we need to pass a negative value of Stalagmite function. As the negative Stalagmite function would be minimized, consequently the Stalagmite function would be maximized.

function [f]=stalagmite(input_vector)        %input vectors are defined

a = input_vector(1);                         %assigning input vector values to variables .
b = input_vector(2);

f1=(sin(5.1*pi.*a+0.5)).^6;
f2=exp(-4*0.6931.*(a-0.0667).^2/0.64);
f3=(sin(5.1*pi.*b+0.5)).^6;
f4=exp(-4*0.6931.*(b-0.0667).^2/0.64);

f=-f1.*f2.*f3.*f4;

end
    
    

CASE 1: unbounded values

CASE 2: with lower and upper bound

CASE 3: with increased population size

Result:

Thus the genetic algorithm is used to find the optimal solution for the given function. We can see that the Case3 took time more than case1 since we have mentioned the population size.