Week 4.1 - Genetic Algorithm

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

THEORY:

A genetic algorithm is a method for solving both constrained and unconstrained optimization problems based on a natural selection process that mimics biological evolution. The algorithm repeatedly modifies a population of individual solutions. At each step, the genetic algorithm randomly selects individuals from the current population and uses them as parents to produce the children for the next generation. Over successive generations, the population "evolves" toward an optimal solution.

Five phases are considered in a genetic algorithm.

1. Initial population

The process begins with a set of individuals which is called a Population. Each individual is a solution to the problem you want to solve.

2. Fitness function

The fitness function determines how fit an individual is (the ability of an individual to compete with other individuals). It gives a fitness score to each individual. The probability that an individual will be selected for reproduction is based on its fitness score.

3. Selection

The idea of selection phase is to select the fittest individuals and let them pass their genes to the next generation. Two pairs of individuals (parents) are selected based on their fitness scores. Individuals with high fitness have more chance to be selected for reproduction.

4. Crossover

Crossover is the most significant phase in a genetic algorithm. For each pair of parents to be mated, a crossover point is chosen at random from within the genes. Offspring are created by exchanging the genes of parents among themselves until the crossover point is reached. The new offspring are added to the population.

Crossover point Exchange between parents New offspring

5. Mutation

In certain new offspring formed, some of their genes can be subjected to a mutation with a low random probability. This implies that some of the bits in the bit string can be flipped. Mutation occurs to maintain diversity within the population and prevent premature convergence.

MATLAB CODE (FOR FUNCTION)

function [f] = stalagmite(input_vector)
x = input_vector(1);
y = input_vector(2);
f1 = (sin(5.1*pi*x+0.5))^6;
f2 = (sin(5.1*pi*y+0.5))^6;
a = ((x-0.667)^2)/0.64;
b = ((y-0.667)^2)/0.64;
f3 = exp(-4*log(2)*a);
f4 = exp(-4*log(2)*b);
f = -(f1*f2*f3*f4);
end

MATLAB CODE (FOR UNBOUNDED STATISTICAL BEHAVIOR)

close all
clc
 
x = linspace(0,0.6,150); %x value inputs
y = linspace(0,0.6,150); %y value inputs
[xx,yy] = meshgrid(x,y); %creating  a 2D mesh
 
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
 
n = 50; %number of iterations
 
%%Unbounded statistical behavior
 
tic %study time counter start
for k=1:n
[inputs, f_opt(k)] = ga(@stalagmite,2);
x_opt(k) = inputs(1);
y_opt(k) = inputs(2);
opt_f(k) = -f_opt(k);
end
 
study1_time = toc;
figure(1)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
xlabel('x value');
ylabel('y value');
shading interp
 
plot3(x_opt,y_opt,-f_opt,'marker','o','markersize',5,'markerfacecolor','r')
subplot(2,1,2)
plot(-f_opt)
xlabel ('Number of iterations');
ylabel('Maximum function');

MATLAB CODE (BOUNDED STATISTICAL BEHAVIOR)

close all
clc
 
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
[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);
    end
end
 
n=50;
%%Statistical behaviour with upper and lower bounds
 
tic %study time counter start
for k=1:n
[inputs, f_opt(k)] = ga(@stalagmite,2,[],[],[],[],[0,0],[0.6,0.6]);
x_opt(k) = inputs(1);
y_opt(k) = inputs(2);
opt_f(k) = -f_opt(k);
end
 
study_time = toc;
figure(1)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
xlabel('x value');
ylabel('y value');
shading interp
 
plot3(x_opt,y_opt,-f_opt,'marker','o','markersize',5,'markerfacecolor','r')
subplot(2,1,2)
plot(-f_opt)
xlabel ('Number of iterations');
ylabel('Maximum function');
gm = -mean(f_opt);

MATLAB CODE (FOR BOUNDED STATISTICAL BEHAVIOR WITH INCREASED POPULATION SIZE)

close all
clc
 
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
[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);
    end
end
 
n=50;
%%Statistical behaviour with upper and lower bounds and increased
%%population size
 
options=optimoptions('ga');
options=optimoptions(options,'populationsize',170);
tic %study time counter start
for k=1:n
[inputs, f_opt(k)] = ga(@stalagmite,2,[],[],[],[],[0,0],[0.6,0.6],[],options);
x_opt(k) = inputs(1);
y_opt(k) = inputs(2);
opt_f(k) = -f_opt(k);
end
 
study_time = toc;
figure(1)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
xlabel('x value');
ylabel('y value');
shading interp
 
plot3(x_opt,y_opt,-f_opt,'marker','o','markersize',5,'markerfacecolor','r')
subplot(2,1,2)
plot(-f_opt)
xlabel ('Number of iterations');
ylabel('Maximum function');
gm = -mean(f_opt)

EXPLANATION OF CODE:

• Initially the stalagmite function is defined seperately. And then it is called in the main program.
• The x and y are defined using linspace command.
• The input vectors i.e. x & y are converted to array form of [xx yy] using meshgrid command.
• Now the matrix which we got above is given as an input to function 'stalagmite'. And accordingly the different values of x & y is obtained from the 'stalagmite' function.
• Now the maxima value is calculated using 'ga' command.
• The number of iterations is defined by input 'n=50'.
• 'ga' by default gives minima value in MATLAB. Hence to get the maxima value we have used a negative sign in the function code.
• The study time is calculated using 'tic' and 'toc' command.
• The results are then plotted using 'surfc' and 'plot' command.
• The same program is repeated by changing the 'ga' syntax i.e. unbounded, bounded and increasing the population size.

ERRORS:

1. This error is because of not giving correct command for plotting. Since we are plotting 3D plot. There are 3 variables hence we should use 'plot3'.
2. This error is due to missing bracket in the 'ga' syntax.

RESULTS:

1. UNBOUNDED STATISTICAL BEHAVIOR

2. BOUNDED STATISTICAL BEHAVIOR

3. BOUNDED STATISTICAL BEHAVIOR WITH INCREASED POPULATION SIZE

CONCLUSION:

• The time taken is less for unbounded statistical approach.
• Since the population size is increased the time taken is more in case of increased population size statistical approach.
• If we increase the number of iterations also the time is increased as well.
• The better results are obtained in case 3 i.e. increased population size approach.