Week 4.1 - Genetic Algorithm

AIM: To optimize the stalagmite function and to find the global maxima of the function.

OBJECTIVES OF THE PROJECT: Explaining the concept of genetic algorithm and also explaining the syntax for ga in MATLAB.

Plot graphs for all 3 studies and for F maximum vs no. of iterations.

INTRODUCTION:

The genetic algorithm is a method for solving both constrained and unconstrained optimization problems that is 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 nonlinear. The genetic algorithm can address problems of mixed integer programming, where some components are restricted to be integer-valued.

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 genetic algorithm differs from a classical, derivative-based, optimization algorithm in two main ways, as summarized in the following table.

Classical Algorithm	Genetic Algorithm
Generates a single point at each iteration. The sequence of points approaches an optimal solution.	Generates a population of points at each iteration. The best point in the population approaches an optimal solution.
Selects the next point in the sequence by a deterministic computation.	Selects the next population by computation which uses random number generators.

FLOW CHART:

Syntax for GA:

[x,fval ,exitflag ,output ,population ,scores]= ga(func,nvars,A,b,Aeq,Beq,lb,ub,nonlcon,Intcon,options)

x = optimum solution

exitflag = reason ga stopped

output= information about optimization process

population=final population

scores= final scores

f=ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon,options)

fun - fitness function.

nvars- number of variables,

A,b= Linear inequality constraints

Aeq,beq=Linear equality constraints

lb- Lower bound(limit),

ub- Upper bound(limit),

nonlcon : Use for nonlinear constraints

IntCon : to get a solution in integer.

options- To set population size minimize with non-default options

BODY OF THE CONTENT:

• FITNESS FUNCTION

• The above equations are used in the stalagmite function to plot the graph in the main functions.

CEATION OF FUNCTION MATLAB CODE:

%creating a function
function[f] = stalagmite_fun(input_vector)
x = input_vector(1);
y = input_vector(2);

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

• While using the function at the end as we are using the (-ve) sign so that the plot will be reversed as we have to find the maxima of the given function using ga.

MAIN CODE:

clear all
close all
clc

%defining our search space
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
num_cases = 50; %Number of iteration for which the function will evaluate the fitness

%creating 2dimensional mesh
[xx yy] = meshgrid(x,y);

%Evoluating 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_fun(input_vector);%values of function in given search space

end
end
surfc(xx,yy,-f);
shading interp %To remove the lines produced by the mesh grid

%study case 1-statistical behavior
tic %To find time taken while running
for k = 1:num_cases
    [inputs,fopt(k)] = ga(@stalagmite_fun,2);
    xopt(k) = inputs(1);
    yopt(k) = inputs(2);
end
study1_time = toc;
figure(1)
subplot(2,1,1);
hold on
surfc(xx,yy,-f);
shading interp
%plotting the optimizing values
plot3(xopt,yopt,-fopt,'marker','o','MarkerSize',5,'MarkerFaceColor','r');
subplot(2,1,2);
%plotting optimized function values
plot(-fopt);
xlabel('iterations');
ylabel('unbounded inputs');
title('unbounded inputs');

%study case 2-statistical behaviour
tic
for k=1:num_cases
    [inputs,fopt(k)]=ga(@stalagmite_fun,2,[],[],[],[],[0;0],[1;1]);
    xopt(k)=inputs(1);
    yopt(k)=inputs(2);
end
study2_time=toc;
figure(2)
subplot(2,1,1);
hold on
surfc(xx,yy,-f);
shading interp;
%plotting the optimizing values
plot3(xopt,yopt,-fopt,'marker','o','MarkerSize',5,'MarkerFaceColor','r');
subplot(2,1,2);
%plotting optimized functions values
plot(fopt);
hold off
xlabel('iterations');
ylabel('function maximum');
title('Bounded inputs');

%study case 3-increasing GA iterations

options=optimoptions('ga');
options=optimoptions(options,'PopulationSize',350);
tic
for k=1:num_cases
    [inputs,fopt(k)]=ga(@stalagmite_fun,2,[],[],[],[],[0;0],[1;1],[],[],options);
    xopt(k)=inputs(1);
    yopt(k)=inputs(2);
end

study3_time=toc;
figure(3)
subplot(2,1,1);
hold on
surfc(xx,yy,-f);
shading interp;
%plotting the optimizing values
plot3(xopt,yopt,-fopt,'marker','o','MarkerSize',5,'MarkerFaceColor','r');
subplot(2,1,2);
%plotting optimized functions values
plot(-fopt);
hold off
xlabel('iterations');
ylabel('function maximum');
title('modifying the population');

global_maxima = -fopt

• Firstly, creating the mesh from the two vectors which will be acting as a search space to find the maxima of the function.
• Creating the mesh of these two vectors using the ‘mesh’ command and defining the no. of iterations as num_cases to iterate the values of the optimum values of the function.
• Now calculating the values of fitness function at each point of the mesh grid formed.
• Now creating its surface through ‘surfc’ command which will also provide the contour of the generated surface.
• While using surfc applying the -ve sign to the function will generate the surface upside down which will be quite good to get the maxima of the function, as it will provide positive value for the maxima using the -ve sign.

STATISTICAL STUDY WITHOUT BOUNDATION:

• In this evaluating the optimum value of fitness function at each iteration and calculating it using the above-mentioned syntax in the intro part (which gives the inputs ie. Values of x and y at which the stalagmite function is minimum)
• Then plotting it into the surf command and also providing the optimum values of the function that how it is varying.
• Also using the tic and tok command to evaluate the time used for optimizing the function.

• From the figure as shown above it is clear that the results are not that accurate and give a lot of variation in optimizing the function.

STATISTICAL STUDY WITH BOUNDATION

• The difference over here is in providing the upper and the lower limit in the ga so that the search space is reduced with the upper and lower boundary
• And then plotting it as similar to the above study.

• It is clearly seen from the above that after providing the boundary limits the variation in the optimum value of the function has reduced.

STATISTICAL STUDY WITH INCREASE IN SIZE OF POPULATION

• In this study using the ‘optimoptions’ command to increase the size of population.
• The benefit of that will be it will be working on the large set of numbers and which will be led to increase the possibilities of finding the better fitness of the function.
• The drawback is that the time for evaluation will increase.

• It is clearly seen in the above case that the value of the variation range has changed to a large extent.

CONCLUSION:

ga is useful for optimizing the function but still the results are not accurate as the maximum value for the function lies at -1.