Week 4 - Genetic Algorithm

1. The algorithm begins by creating a random initial population.

2. 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. To create a new population, the algorithm performs the following steps:

   1. Scores each member of the current population by computing its fitness value. These values are called raw fitness scores.

   2. Scales the raw fitness scores to convert them into a more usable range of values. These scaled values are called expectation values.

   3. Selects members, called parents, based on their expectations.

   4. Some of the individuals in the current population that have lower fitness are chosen as elite. These elite individuals are passed to the next population.

   5. Produces children from the parents. Children are produced either by making random changes to a single parent—mutation—or by combining the vector entries of a pair of parents—crossover.

   6. Replaces the current population with the children to form the next generation.

3. The algorithm stops when one of the stopping criteria is met. See Stopping Conditions for the Algorithm.

Syntaxes for GA:

1. 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.
2. 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').
3. 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').
4. 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.)
5. 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.)
6. 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.
7. x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon) : requires that the variables listed in IntCon take integer values.
8. x = ga(problem) : finds the minimum for problem, where problem is a structure.
9. [x,fval] = ga(___) : for any previous input arguments, also returns fval, the value of the fitness function at x.
10. [x,fval,exitflag,output] = ga(___) : also returns exitflag, an integer identifying the reason the algorithm terminated, and output, a structure that contains output from each generation and other information about the performance of the algorithm.
11. [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.

Stalagmite Function:

In this project, the judging criteria i.e, the way in which we can tell if the variable present in the solution is fit or not, is Stalagmite function.

The governing equations are:

`f_1x = [sin(5.1pix+0.5)]^6`

`f_2x = e^(-4ln(2)(x-0.0667)^2/0.64`

`f_1y = [sin(5.1piy+0.5)]^6`

`f_2y = e^(-4ln(2)(y-0.0667)^2/0.64`

Stalagmite Function: `f = f_1x*f_2x*f_1y*f_2y`

MATLAB CODES:

Codes for creating Stalagmite Fuction:

%Program to create the stalagmite function
function[f] = stalagmite_func(input_vector)

%inputs
x = input_vector(1);  %contains x values of the population taken
y = input_vector(2);  %contains y values of the population taken

%solution of the function f(x,y) = (f1,x)*(f2,x)*(f1,y)*(f2,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*f2x*f1y*f2y);
end

Codes for Genetic Algorithm with all 3 studies:

%program to calculate global maxima of a stalagmite function 

clear all
close all
clc

%defining the search space or range
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
numcases = 50;      %no. of times that the GA will run

%creating a 2D mesh
[xx, yy] = meshgrid(x,y);                           % creating matrix containing only x and y values

%Evaluating the stalagmite function
for i=1:length(xx)
    for j=1:length(yy)
        input_vector(1) = xx(i,j);                  % assigning a particular value of xx and yy to the input vector till the length of xx and yy is reached
        input_vector(2) = yy(i,j);
        f(i,j) = stalagmite_func(input_vector);     % calculating the fitness value as per the fitness function
    end
end
[inputs,fval] = ga(@stalagmite_func, 2)             % to evaluate the function using genetic algorithm and display values

tic                 %starting the time for calculate the time that the function took to run
% Study_1 : Statistical behaviour

for k=1:numcases
    [inputs,fopt(k)] = ga(@stalagmite_func,2);      % solving the function using ga and assigning solution values 
    xopt(k) = inputs(1);
    yopt(k) = inputs(2);                            % assigning solution values to x and subsequently y.
end
study1_time = toc       % end timer

figure(1)
subplot(2,1,1)          % deviding the plot are into 2*1 grid and assigning the plot sequence as 1
hold on
surfc(xx,yy,-f)         % surface creation
shading interp          % making gridlines invisible
plot3(xopt,yopt,-fopt, 'marker','o','markersize',5,'markerfacecolor','r')
title('Unbounded Inputs')
xlabel('x value')
ylabel('y value')

subplot(2,1,2)
plot(fopt)
xlabel('Iterations')
ylabel('Functions Maximum')
hold off

tic
% Study_2 : Statistical Behviour with upper and lower bounds

for i=1:numcases
    [inputs,fopt(i)] = ga(@stalagmite_func,2,[],[],[],[],[0;0],[.5;.5]);    %limits set for the range
    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('Statistical Behviour with upper and lower bounds')
xlabel('x value')
ylabel('y value')

subplot(2,1,2)
plot(fopt)
xlabel('Iterations')
ylabel('fopt')
hold off

% Study_3 : Increasing ga iterations
options = optimoptions('ga');
options = optimoptions(options,'populationsize',500);   %increasing population size

tic
for i=1:numcases
    [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 modified population size')
xlabel('x value')
ylabel('y value')

subplot(2,1,2)
plot(fopt)
xlabel('Iterations')
ylabel('Functions Maximum')
hold off

Results and Discussions:

Study:1 From Study 1 of maxima, we can see that there is too much variation between 0 and 1 thus a global maxima cannot be obtained from here.

Study:2 Study 2 shows a clearer objective by giving maxima values in a much smaller range between 0.8 to 1.

Study:3 Study 3 clearly tells us that the global maxima is 1 with decimal accuracy.

References:

1. https://in.mathworks.com/help/gads/how-the-genetic-algorithm-works.html
2. https://in.mathworks.com/discovery/genetic-algorithm.html
3. https://in.mathworks.com/help/gads/ga.html#mw_f69991d0-5b23-4023-8c8e-e2890f2474d5