Week 4.1 - Genetic Algorithm

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

OBJECTIVE : Explainig the theory of genetic algorithm and also explain the syntax for ga in matlab.

INTRODUCTION: Genetic algorithms simulate the process of natural selection which means those species who can adapt to changes in their environment are able to survive and reproduce and go to next generation. they simulate “survival of the fittest” among individual of consecutive generation for solving a problem. Each generation consist of a population of individuals and each individual represents a point in search space and possible solution.

The genetic algorithms is a techniquue for solving both constrained and unconstrained optimization problem that arebased on natural selection, the process that drives biological evolution. The genetic algorithm constantly modifies the population size of individual solutions.

There are five phases in genetic algorithms.

1.) Initial population

The problem intiates with a set of individuals which is called population. Each individual is a solution to the problem we want to solve.

Each individual is characterized by a set of parameters called genes.

Genes are joined into a string which yields us chromosome which is nothing but a solution.

2.)FITNESS FUNCTION:

The fitness function determines how fit an individual is. It gives a fitness score to each individual.

The probability that an individual will be selected for reproduction is based on this score.

3.)SELECTION PHASE

The main objective of this phase is to select the fittest individual and let them pass their Gene onto the next generation.

4.)CROSSOVER

For each pair of parents to be mated, crossover point is chosen at random from within the genes.

For example, consider the crossover point to be 3 as in the figure below:

5.) MUTATION

In certain new offsprings formed, some of their genes can be subjected to mutation with low random probability.

This implies that some of the bits in the bit string can be flipped.

Mutation occurs to maintain diversity within population and prevent premature convergence.

TERMINATION:

Finally, the algorithm terminates if the population has converged.

Then it is said that genetic algorithm has provided a set of solution to our problem.

CODE FOR GENETIC ALGORITHMS

1) firstly code for stalagmite function

function [F] = stalagmite(int_xy)
 x = int_xy(1);
 y = int_xy(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

• stalagmite function will be used in main function
• 'int_xy' assigned for x and y.
• Negative sign used in the last line is used to maximize the stalagmite function.

2) The main code below uses the stalagmite function defined to find the global maxima using MATLAB's in-built 'ga' function:

clear all 
close all
clc 

%defining the search space
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
iterations = 50;
[xx, yy] =meshgrid(x,y);

%stalagmite function
for i=1:length(xx)
    for j = 1:length(yy)
        int_xy(1) = xx(i,j);
        int_xy(2) = yy(i,j);
        f(i,j) = stalagmite(int_xy);
    end
end

%1st iteration - studying the statistical behaviour

tic 
for i=1:iterations
[inputs , f_optimum(i)] = ga(@stalagmite,2);
x_optimum(i) = inputs(1);
y_optimum(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_optimum,y_optimum,f_optimum,'marker','o','markersize',5,'markerfacecolor','r')
title('Unbounded inputs')
subplot(2,1,2)
plot(f_optimum)
xlabel('Iterations')
ylabel('Function maximum')

%2nd iteration with upper and lower limits

tic
for i=1:iterations
[inputs , f_optimum(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
x_optimum(i) = inputs(1);
y_optimum(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_optimum,y_optimum,f_optimum,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded inputs')
subplot(2,1,2)
plot(f_optimum)
xlabel('Iterations')
ylabel('Function maximum')

%3rd iteration - increasing the size of population
 
options = optimoptions('ga');
options = optimoptions(options,'populationsize',200)

tic
for i=1:iterations
[inputs , f_optimum(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
x_optimum(i) = inputs(1);
y_optimum(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_optimum,y_optimum,f_optimum,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded inputs with modified population size')
subplot(2,1,2)
plot(f_optimum)
xlabel('Iterations')
ylabel('Function maximum')

: Stepwise explaination of the above program:

i.) First, the search space required to execute the program is defined which varies from 0 to 0.6 with 150 divisions in between.

ii.)using the meshgrid command, row vectors x and y are converted into matrices xx and yy.

iii.) With the help of for loop, the input vectors required for stalagmite function are defined using the matrices xx and yy.

From here onwards, whole program is divided into three iterations and will be made to run individually:

1st iteration:

In the first iteration, the behaviour of the algorithm is studied by not defining the limits.

results:

2nd iteration:

Here the limits i.e., the lower and upper bounds are defined so as to know the boundaries within which the global maxima lies.

results:

3rd iteration:

In the next step, the population size is increased so as to converge to the global maxima.

result:

ga syntax explaination:

The format for writing genetic algorithm in matlab is as follows:

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

Explaination of terms involved:

• f_min is the local minima point.
• @function is the function to be called.(In our case, its the stalagmite function)
• nvars indicates the no of variables used.
• A and B are used to indicate any kind inequalities that exist in the function.
• Same goes with Aeq and Beq.
• LB = lower bound.
• UB = upper bound.
• nonlcon gives a two vectors representing inequalities and equalities.
• options is used to perform additional operations like increasing population size. This is done with the help of optimooptions.