Week 4.1 - Genetic Algorithm

AIM : To write a code in MATLAB to optimize stalagmite function and find global Maxima of the same.

THEORY :

GENERIC ALGORITHM is a search heuristic that is inspires by Charles Darwin theory of natural evolution. This algorithm reflects the process of natural selection where fittest individuals are selected for reproduction to generate offsprings for next generations.

There are five phases in generic 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.

An individual is characterized by a set of parameters (variables) known as Genes. Genes are joined into a string to form a Chromosome (solution).

In a genetic algorithm, the set of genes of an individual is represented using a string, in terms of an alphabet. Usually, binary values are used (string of 1s and 0s). We say that we encode the genes in a chromosome.

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.

For example, consider the crossover point to be 3 as shown below.

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.

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 PROGRAM :

1. Stalagmitete function is called first.

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;
f3 = exp((-4*log(2)*(x-0.0667).^2)/(0.64));
f4 = exp((-4*log(2)*(y-0.0667).^2)/(0.64));
F = -f1*f2*f3*f4;
end

2. Main code with 3 iterations.

clear all
close all
clc

x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
iterations = 50;
[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

%1st iteration-studying the behaviour
tic
for i = 1:iterations
    [inputs,f_optimum1(i)] = ga(@stalagmite,2);
    x_opt1(i) = inputs(1);
    y_opt1(i) = inputs(2);
end

iteration_1_time = toc

%plotting
figure(1)
subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp
plot3(x_opt1,y_opt1,f_optimum1,'marker','o','markersize',5,'markerfacecolor','r')
title('Unbounded inputs')
subplot(2,1,2)
plot(f_optimum1)
xlabel('Iterations')
ylabel('Function maximum')


% 2nd Iteration with upper and lower limits
tic
for i = 1:iterations
    [inputs,f_optimum2(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[0.4;0.4]);
    x_opt2(i) = inputs(1);
    y_opt2(i) = inputs(2);
end

iteration_2_time = toc

%plotting
figure(2)
subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp
plot3(x_opt2,y_opt2,f_optimum2,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded inputs')
subplot(2,1,2)
plot(f_optimum2)
xlabel('Iterations')
ylabel('Function maximum')

%3rd Iteration  with increasing size of population
options = optimoptions('ga');
options = optimoptions(options,'populationsize',200)

tic
for i = 1:iterations
    [inputs,f_optimum3(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[0.4;0.4],[],[],options);
    x_opt3(i) = inputs(1);
    y_opt3(i) = inputs(2);
end

iteration_3_time = toc


%plotting
figure(3)
subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp
plot3(x_opt3,y_opt3,f_optimum3,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded inputs with modified population size')
subplot(2,1,2)
plot(f_optimum3)
xlabel('Iterations')
ylabel('Function maximum')

Stepwise explanition of the program :

• First the srarch space required to execute the program is defined which varies from 0 to 0.6 with 150 divisions.
• Using the MESHGRID command, row vectors x,y are converted into xx,yy matrices.
• With the help of 'for' loop, the input vectors required for the stalagmite are difined using the matrices 'xx' and 'yy'.
• from here the program is executed in three different iterations

1. In the first iteration, the behviour of the program is studied by not defining the limits. The plot results are

2. In the second iteration, the lower and upper bounds are defined. The plot results are

3. Here the population size is increased so as to converge the global maxima. The plot results are

ga syntax explanition :

The syntax format writing in matlab is

f_min = ga(@function,nvars,A,B,Aeq,Beq,LB,UB,nonlcon,intcon,options)

• f_min = the local minima point.
• @function = the function to be called.
• nvars = the number of variables used.
• A,B,Aeq,Beq = they indicates any kind of inequalities exist in the finction.
• LB,UB = lower boundary and upperboundary.
• nonlcon gives two vectors representing inequalities and equalities.
• options is used to preform aditonal operations like increasing population size. This is done with optimooptions.