Week 4.1 - Genetic Algorithm

Matlab program:

function[f]=stalagmite(input_vector)
x=input_vector(1);
y=input_vector(2);

t1=(sin((5.1*pi*x)+0.5))^6;
t2=(sin((5.1*pi*y)+0.5))^6;
t3=exp(-4*log(2)*((x-0.0667)^2)/0.64);
t4=exp(-4*log(2)*((y-0.0667)^2)/0.64);

f=-(t1*t2*t3*t4);
end

clear all
close all
clc

x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
n=150
%creating 2d array
[xx yy]=meshgrid(x,y);

% calculating 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

% study1:Statistical behaviour
tic
for i=1:n
    [inputs,fopt(i)]=ga(@stalagmite,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
xlabel('X-axis')
ylabel('Y-axis')
title('Statistical behaviour with unbound inputs')
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
subplot(2,1,2)
plot(-fopt)
xlabel('No of Iterations')
ylabel('Function maximum')

clear all
close all
clc

x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
n=150
%creating 2d array
[xx yy]=meshgrid(x,y);

% calculating 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

% study2:statistical behaviour with upper and lower bounds
tic
for i=1:n
    [inputs,fopt(i)]=ga(@stalagmite,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
xlabel('X-axis')
ylabel('Y-axis')
title('statistical behaviour with upper and lower bounds')
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
subplot(2,1,2)
plot(-fopt)
xlabel('no of iterations')
ylabel('function maximum')

clear all
close all
clc

%define our search space
x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
n=150
%creating 2d array
[xx yy]=meshgrid(x,y);

% calculating 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

%study3 statistical behaviour with increasing interations of GA

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

tic
for i=1:n
    [inputs,fopt(i)]=ga(@stalagmite,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
xlabel('X-axis')
ylabel('Y-axis')
title('Unbounded Inputs');
legend('STALAGMITE','GLOBAL MAXIMA')
subplot(2,1,2)
hold on 
plot(fopt)
xlabel('Iterations');
ylabel('Function Maxima');
title('Variation in F')
legend('Change in F value')

Program Explanation:

1.The code starts with "clear all","close all","clc".

2.Then x array and y array is defined using 'linspace' command to create values at 150 equal intervals.

3.A 2D mesh of x and y array is created by using 'meshgrid' command and the no. of interations or cases that the code should perform is defined.(n=50).

4.To evaluate the stalagmite function,'for' looop is used where 'i' is initialized and for every value of 'i' another 'for' loop is used to initialize 'j'.

5.The input vector values of 'xx' and 'yy' are defined and the stalagmite function for these input vector is defined.This will form a basic stalagmite function and we can plot it seperately if needed.

6.After preparing the inputs needed for the function,next step is to obtain the results for 3 cases of the genetic algorithm.In first case or study,the maximum value of function is found out with no restrictions,no bounds and no limits.

7.This is done using 'for' loop where we use 'ga' syntax to give values for inputs and optimum max value.The stalagmite function is called in 'ga' syntax and number of variables 'nvars' are 2.

8.To know the time that is taken to solve the loop for 50 interations,'tic' and 'toc' command is used before and after the loop respectively.

9.Then the functio created in the loop is plotted by using 'surfc' command for 'xx','yy'and function output.To neglet the gridliness on the surface and obtain a smooth and clean plot,'shading interp' command is used.The 'subplot(2,1,1)' is used to plot multiple plots on same figure which also divides figure in grid of 2x1 and axes to be placed at 1.

10.The 'plot3' command plots the 3D points at 'xopt','yopt' and optimum value of function with 'o' shaped and red colour.The labels and title are then provided.Now in the same figure,the values of optimum function 'fopt' are plotted for 50 iterations.

11.The results of the above case will be different for each time we run the program.To get same value each time,we need to restrict the program within specific bounds namely upper bound and lower bound.The procedure for coding and plottind this procedure is same as study 1.The only difference is in the 'ga' syntax.This time the algorithm is provided lower limits and upper limits as[0;0] and [1;1] respectively.

12.After plotting the results for study2 or the bounded case,it is observed that the results are not same every time the program terminates.A solution to this problem is to increase the number of cases or iterations.

13.So for study 3,the number of iterations are increased to 300.So for this study,the syntax,

"options=optimoptions('Solvername','Name','Value')" is used which returns with named parameter 'Population' with the altered values '300'.

14.The syntax for 'ga' contains 'option' term and the rest of the code is same as for study 1 and 2.

GENETIC ALGORITHM

The Genetic Algorithm works on the process of natural selection where the fittest individuals are selec

produce offspring of the next generation. It is a method for solving both constrained and unconstraine

based on natural selection. The algorithm begins by creating a random initial population of individua

modifying this population repeatedly creating a sequence of new population. The algorithm uses the i

generation to create the next population. 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.

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 basic steps in creating a genetic algorithm is as follows,
1. The algorithm creates a random initial population at beginning.
2. Then to create new population, the algorithm scores each member of the current population by computing its fitness value and converts them into a more usable range of values.
3. Then based on these new values the algorithm selects members, called as parents.
4. Then the algorithm produces children from the parents. Children are produced either by making random changes to a single
parent which is mutation or by combining the vector entries of a pair of parents which is crossover.
5. In this way the algorithm replaces the current population with the children to form the next generation.
6. The algorithm stops when it reaches any one of the specified factors factors such as time limit, fitness limit, generations, function tolerance, constraint tolerance, etc.

Syntax for defining ‘ga’ (Genetic Algorithm) in matlab :

The ‘ga’ syntax in matlab is used to find the minimum of function using genetic algorithm. There are several ways to define the ‘ga’ function depending on the problem being solved. The syntax used for this study is shown below.

• x = ga(fun,nvars)
  where, x = optimal solution/variables;
  fun = Objective function;
  nvars = Number of variables;
  Sometimes ‘[x,fval]’ is used instead of ‘x’ where ‘fval’ gives objective function value at the solution
• x = ga(fun,nvars,A,B,Aeq,Beq,lb,ub)
  where, A, B = Linear inequality constraints
  Aeq, Beq = Linear equality constraints
  If there are no linear equalities and inequalities, then A, B, Aeq, Beq are set to ‘[ ]’.
• x = ga(fun,nvars,A,B,Aeq,Beq,lb,ub,nonlcon,IntCon,options)
  where, nonlcon = Nonlinear constraints
  IntCon = Integer Values
  options = Optimization options
  If there are no nonlinear constraints and integer values, the nonlcon and intCon are set to '[]'

OUTPUTS:

study1:

study2:

study3:

Reference:

https://en.wikipedia.org/wiki/Genetic_algorithm

Conclusion:

• The idea behind the above studies is to observe how the “ga ()” commands works with different inputs and how to obtain a same value for a function even if “ga” is run several times.
• Thus Global Maxima is found for the stalagmite function.
• Genetic Algorithm is one of the most used method for obtained optimized value.
• Genetic Algorithm is mostly used to find the minimum value of a function , for example to find minimum drag force that will created by the Aerofoil.
• Similar approach as above code can be used to find maximum value using “ga” command.