Week 4.1 - Genetic Algorithm

Aim:

• Write a code in MATLAB to optimize the stalagmite function and find the global maxima of the function.
• Plot graphs for all 3 studies and for F maximum vs no. of iterations.
• Clearly explain the concept of genetic algorithm in your own words and also explain the syntax for ga in MATLAB .

Genetic algorithms are commonly used to generate high-quality solutions to optimization and search problems by relying on biologically inspired operators such as mutation, crossover and selection.

The genetic algorithm is a technique for solving both constrained and unconstrained optimization problems that are based on natural selection, the process that drives biological evolution. The genetic algorithm constantly modifies the population size of individual solutions.

Phases in Genetic Algorithm-

• Initialization of Population (Coding)

The code generates its random population of defined size and from that population the code evaluates the fitness of the members of the population according to which it forms new population based on no. of iterations performed.

• Fitness Function

It is that function which we have to optimize and its optimization is done with the help of number of generations which have been formed by the code accordance with the fitness value of each member generated, these fitness values are used for the reproduction of the children.

• Selection

The idea of the selection phase is to select the fittest individuals and let them pass their genes to the next generation. The main goal of this phase is to find the region where the chances of getting the best solution are more.

Inspiration for this is from the survival of the fittest.

It should be a balance between exploration and exploitation of search space.

GA tries to move the genotype to higher fitness in the search space.

Too strong fitness selection bias can lead to sub-optimal solutions.

Too little fitness bias selection results in unfocused search.

• Reproduction

Generation of offspring happen in 2 ways:

• Crossover
• Mutation

• A) Crossover

Crossover is the most significant stage in the genetic algorithm. During crossover, a random point is selected while mating a pair of parents to generate offspring.

There are 3 major types of crossover.

• Single Point Crossover

A point on both parents’ chromosomes is picked randomly, and designated a ‘crossover point’.

Two-Point Crossover: Two crossover points are picked randomly from the parent chromosomes.

Unifofm Crossover: In a uniform crossover, typically, each bit is chosen from either parent with equal probability.

• B) Mutation

In a few new offspring formed, some of their genes can be subjected to a mutation with a low random probability. This indicates that some of the bits in the bit chromosome can be flipped. Mutation happens to take care of diversity among the population and stop premature convergence.

Function Equation

• Syntax for ga in Matlab

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.

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').

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').

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.)

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.)

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.

x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,intcon) or x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,intcon,options) requires that the variables listed in intcon take integer values.

x = ga(problem) finds the minimum for problem, a structure described in problem.

[x,fval] = ga(___), for any previous input arguments, also returns fval, the value of the fitness function at x.

[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.

[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.

ga functions used in the code

Study-1 Statistical behavior

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.

Study-2 Statistical Behavior (Bounded)

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.)

Study-3 Modifying the number of populations

x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,intcon,options) minimizes with the default optimization parameters replaced by values in options.Create options using optimoptions.

Code explanation

The search space is created using the linspace command.

x=linspace(0,0.6,150);

y=linspace(0,0.6,150);

2d vector of x and y is created using the meshgrid command.

[xx,yy]=meshgrid(x,y);

Using for loop ,the input_vector values are defined.

for i=1:length(xx)

for j=1:length(yy)

input_vector(1)=xx(i,j);

input_vector(2)=yy(i,j);

The function is called with the code

f(i,j)=stalagmite(input_vector);

Function file

function[f]=stalagmite(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.667)^2/0.64));

f2y=exp((-4*log(2)*(y-0.667)^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.

Now creating its surface through ‘surfc’ command

figure(1)

hold on

surfc(xx,yy,-f) % Generating the surface.

shading interp % Removing the grid lines.

title('Stalagmite Plot')

grid on

xlabel('X');

ylabel('Y');

Result

The no of iterations ‘num_cases’ is defined as 50.

The Matlab code is written in such a way that 3 studies are done to find the global maxima of the funcion.

Study-1: Unbounded.

The ga command does not run in defined search space.

Calculating Study time using 'tic' and 'toc' command.

tic

for i=1:num_cases

[inputs1,fopt1(i)]=ga(@stalagmite,2); % Calculating the optimized value of the function

xopt1(i)=inputs1(1);

yopt1(i)=inputs1(2);

end

studytime_1=toc;

% Plotting

figure(2)

subplot(2,1,1) % Divides the current figure into an m-by-n grid.

hold on

surfc(xx,yy,-f)

shading interp

plot3(xopt1,yopt1,-fopt1,'marker','o','MarkerSize',5,'MarkerFaceColor','r')

% Plots coordinates in 3-D space.

xlabel('X')

ylabel('Y')

grid on

title('Unbound inputs')

subplot(2,1,2)

plot(-fopt1)

xlabel('Iterations')

ylabel('Function Maximum')

Result

Study-2 Statistical Behavior(Bounded)

tic

for j=1:num_cases

[inputs2,fopt2(j)]=ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6]);

% Calculating the optimized value of the function with defined search space.

xopt2(j)=inputs2(1);

yopt2(j)=inputs2(2);

end

studytime_2=toc;

% Plotting

figure(3)

subplot(2,1,1)

hold on

surfc(xx,yy,-f)

shading interp

plot3(xopt2,yopt2,-fopt2,'marker','o','markersize',5,'markerfacecolor','g');

xlabel('X');

ylabel('Y');

title('Statistical Behavior (Bounded)')

grid on

subplot(2,1,2)

plot(-fopt2);

xlabel('iterations')

ylabel('Function maximum')

Result

Study-3 Modifying the number of population

options=optimoptions('ga')

options=optimoptions(options,'populationsize',400) %increasing the size of

% population by using optimoptions function

tic

for k=1:num_cases

[inputs3,fopt3(k)]=ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6],[],[],options);

xopt3(k)=inputs3(1);

yopt3(k)=inputs3(2);

end

study3_time=toc;

%Plotting

figure(4)

subplot(2,1,1)

hold on

surfc(xx,yy,-f)

shading interp

plot3(xopt3,yopt3,-fopt3,'marker','o','markersize',5,'markerfacecolor','b');

xlabel('X');

ylabel('Y');

title('Statistical Behavior(Bounded with modified population size)')

grid on

subplot(2,1,2)

plot(-fopt3);

xlabel('iterations')

ylabel('Function maximum')

Result

close all
clear all
clc
% Defining the search space using linspace command
x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
% Creating 2d array
[xx,yy]=meshgrid(x,y);
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); % Values of function in search space
end
end
% Plotting
figure(1)
hold on
surfc(xx,yy,-f) % Generating the surface.
shading interp % Removing the grid lines.
title('Stalagmite Plot')
grid on
xlabel('X');
ylabel('Y');
num_cases=50;

%% Study-1 Statistical behavior
tic % Calculating Study time using 'tic' and 'toc' command.
for i=1:num_cases
[inputs1,fopt1(i)]=ga(@stalagmite,2); % Calculating the optimized value of the function
xopt1(i)=inputs1(1);
yopt1(i)=inputs1(2);
end
studytime_1=toc;
% Plotting
figure(2)
subplot(2,1,1) % Divides the current figure into an m-by-n grid.
hold on
surfc(xx,yy,-f)
shading interp
plot3(xopt1,yopt1,-fopt1,'marker','o','MarkerSize',5,'MarkerFaceColor','r')
% Plots coordinates in 3-D space.
xlabel('X')
ylabel('Y')
grid on
title('Unbound inputs')
subplot(2,1,2)
plot(-fopt1)
xlabel('Iterations')
ylabel('Function Maximum')

%% Study-2 Statistical Behavior(Bounded)
tic
for j=1:num_cases
[inputs2,fopt2(j)]=ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6]);
% Calculating the optimised value of the function.
xopt2(j)=inputs2(1);
yopt2(j)=inputs2(2);
end
studytime_2=toc;
% Plotting
figure(3)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
shading interp
plot3(xopt2,yopt2,-fopt2,'marker','o','markersize',5,'markerfacecolor','g');
xlabel('X');
ylabel('Y');
title('Statistical Behavior(Bounded)')
grid on
subplot(2,1,2)
plot(-fopt2);
xlabel('iterations')
ylabel('Function maximum')

%% Study-3 Modifying the number of population
options=optimoptions('ga')
options=optimoptions(options,'populationsize',400) %increasing the size of 
% population by using optimoptions function
tic
for k=1:num_cases
[inputs3,fopt3(k)]=ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6],[],[],options);
xopt3(k)=inputs3(1);
yopt3(k)=inputs3(2);
end
study3_time=toc;
%Plotting
figure(4)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
shading interp
plot3(xopt3,yopt3,-fopt3,'marker','o','markersize',5,'markerfacecolor','b');
xlabel('X');
ylabel('Y');
title('Statistical Behavior(Bounded with modified population size)')
grid on
subplot(2,1,2)
plot(-fopt3);
xlabel('iterations')
ylabel('Function maximum')

%Function file
function[f]=stalagmite(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.667)^2/0.64));
f2y=exp((-4*log(2)*(y-0.667)^2/0.64));
f=-(f1x*f2x*f1y*f2y);
end