Week 4.1 - Genetic Algorithm

Aim: To write a code in MATLAB to optimise the stalagmite function and find the global maxima of the function.

Theory:

GENETIC ALGORITHM:

The genetic algorithm is a method for solving both constrained and unconstrained optimization problems that are based on natural selection, the process that drives biological evolution. The genetic algorithm repeatedly modifies a population of individual solutions. At each step, 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. You can apply the genetic algorithm to solve a variety of optimization problems that are not well suited for standard optimization algorithms, including problems in which the objective function is discontinuous, nondifferentiable, stochastic, or highly non-linear. The genetic algorithm can address problems of mixed-integer programming, where some components are restricted to be integer-valued.

Syntax for GA in Matlab:

x=ga(fun,nvars,A,B,Aeq,Beq,lb,ub,nonlcon,Intcon,options)

where...

'x' is the variable to store the output of the genetic algorithm.

'fun' is the function handle to call the function.

'A' and 'B' are used to represent the linear inequalities of the function, if the linear inequalities do not exist, they can be set as empty[].

'Aeq' and 'Beq' are used to represent the equality constraints. similarly, if the linear equalities do not exist, they can be set as empty[].

'lb' and 'ub' are used to specify the upper and the lower bounds of the variables of the function.

'nonlcon' represents the non-linear constraints.

'Intcon' represents the integer constraint, such that the value of the function is an integer.

'options' used to provide the value of the default parameters used named parameters, if it is required to replace the default parameters. This is done by using the 'optimoptions'.

Code:

clear all
close all
clc

%Defining our search space
x=linspace(0,0.6,150);
y=linspace(0,0.6,150);

%Creating a 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 axis')
ylabel('y axis')

shading interp

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

%STUDY-1 Statistical Behavior
num_cases=50

tic
for i=1:num_cases
    [inputs1,fopt1(i)]=ga(@stalagmite,2);
    xopt1(i)=inputs1(1);
    yopt1(i)=inputs1(2);
end
study1_time=toc;
mean1=-(mean(fopt1))

figure(1)
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
plot3(xopt1,yopt1,-fopt1,'marker','o','markersize',5,'markerfacecolor','r');
title('Unbounded inputs')
xlabel('X-Axis')
ylabel('Y-Axis')
subplot(2,1,2)
plot(fopt1)
xlabel('Iterations')
ylabel('Function minimum')

%study-2 statistical behavior with upper and lower bounds

tic
for i=1:num_cases
    [inputs2,fopt2(i)]=ga(@stalagmite,2,[],[],[],[],[0,0],[1,1]);
    xopt2(i)=inputs2(1);
    yopt2(i)=inputs2(2);
end
study2_time=toc;
mean2=-(mean(fopt2))


figure(2)
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
plot3(xopt2,yopt2,-fopt2,'marker','o','markersize',5,'markerfacecolor','r');
title('Bounded inputs')
xlabel('X-Axis')
ylabel('Y-Axis')
subplot(2,1,2)
plot(fopt2)
xlabel('Iterations')
ylabel('Function minimum')

%study-3 Increasing GA iterations

options=optimoptions('ga');
options=optimoptions(options,'populationsize',400);


tic
for i=1:num_cases
    [inputs3,fopt3(i)]=ga(@stalagmite,2,[],[],[],[],[0,0],[1,1],[],[],options);
    xopt3(i)=inputs3(1);
    yopt3(i)=inputs3(2);
end
study3_time=toc;
mean3=-(mean(fopt3))

figure(3)
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
plot3(xopt3,yopt3,-fopt3,'marker','o','markersize',5,'markerfacecolor','r');
title('Bounded inputs with modified population size')
xlabel('X-Axis')
ylabel('Y-Axis')
subplot(2,1,2)
plot(fopt3)
xlabel('Iterations')
ylabel('Function minimum')

Function Program Code:

function [f] = stalagmite(input_value)

f1x = (sin(5.1*pi*input_value(1) + 0.5)).^6;

f1y = (sin(5.1*pi*input_value(2) + 0.5)).^6;

f2x = exp(-4*log(2)*(((input_value(1) - 0.0667).^2)/(0.64)));

f2y = exp(-4*log(2)*(((input_value(2) - 0.0667).^2)/(0.64)));

f = -(f1x*f1y*f2x*f2y);

• Here the negative command is used in the function program in order to invert the plot as the 'ga' command finds only the minimum point.

Explanation of code:

1. Main Program:

• Clear all, close all and clc represents it deletes all temporary memory, closes all plots, and clears the command window.
• We assume x and y values using the linspace command. The uses of linspace command are that if we set lower and upper limits and the number of values we need it takes random values.
• In the next step, the mesh grid command is used in order to form an array of row and column values and it is stored in xx and yy variables.
• Then, for loop command is used. It repeats the function for the length of xx and yy.
• Then in the next step, we call the stalagmite function as stalagmite(input_vector).
• In the next step, surfc command is used in order to get a plot as a surface.
• Then, shading interp command is used in order to remove the grid-like structure in the plot, and color filling is done.you can refer it in the following figure.
• In the next step, the ga command is used. In the ga command, we call the stalagmite function and we need to enter the number of variables. In our problem, we have two variables x and y so we enter it as 2.
• Then in the next step x label and y label is used in order to get a clear picture of our plot.

2. Study-1 Statistical Behavior:

• In this study, we introduce the number of cases that ga needs to perform, and based on the mean value we need to calculate our global maximum value.
• We define it as num_cases=50 in this program. The 50 indicates that 50 times the ga need to repeat and it calculates the value.
• The tic command is used in order to find out the time taken for the program to complete.
• For loop command is used and the length of it set as the number of cases.
• Then ga command is used as before by calling the function and the number of variables in the program.
• The calculated x and y values are stored in xopt(i) and yopt(i).
• subplot command is used in order to get n number of plots in the same single figure plot.
• In the first plot, we plot the x,y, and f as a surface like structure by using the surf command.
• The negative sign is used in the function (f) while plotting since we invert initially and we need to revert it back to its original structure.
• Then we plot calculated maximum value as a dot-like structure by using the marker opting and marker size.
• In the next step title for the is mentioned using the title command.
• Then subplot command is used in order to plot in the same figure window.
• In this plot, we plot the values and the number of iterations, and the x label and y label is mentioned.
• In this study, we get a random value and we didn't get an exact global maximum value and the search space of ga is also not within our search space.
• Thus it indicates we need to have a better study method through which we get our exact global maximum value within our search space.

3. Study-2 Statistical Behavior with upper and lower bound limits:

• From the previous study, we inferred that the search space of the ga is not within our search space so to overcome this error we use the bounded script method.
• As the name suggests, in this study we will enter the boundary and within that boundary, only the ga will perform.
• All the commands used in this study are also the same as used in the previous study except the ga syntax.
• In this study as mentioned above the limit criteria, Initially, we call the stalagmite function and the number of variables mentioned as done earlier, and we enter the lower and upper boundary limit values.
• In our program, the lower boundary limit is set as 0,0 and the upper boundary limit is set as 1,1.
• After this, we plot the same way as before and we get our plot.
• Based on the output we inferred that even though this study is better than our previous study but still we didn't an exact single global maximum value.

4. Study-3 Increasing GA Iterations:

• All the commands used in this study are also the same as used in the previous study except the ga syntax.
• In the previous study, we set the lower and upper boundary limits but we didn't set the initial population size for the ga to perform.
• Thus in this optimization technique, we will try to set the initial population size that ga needs to perform within our boundary limits.
• Thus to set the initial population size we use the optimoptions command and in that we mention the options, population size.
• After this, we plot the same way as before and we get our plot.
• The population value is randomly increased up to which a single exact global maximum value is found out.
• By increasing like this we get a single exact point at the population size of 300.so we stop our program at this point.

Results:

Outputs:

inputs = -0.1279 0.0796

fval = -0.7463

num_cases = 50

mean1 = 0.4574

mean2 = 0.9275

mean3 = 1.0000

study1_time = 2.5066

study2_time = 3.6453

study3_time = 20.8527