Genetic algorithm

AIM:

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

THEORY:

DEFINITION:

GENETIC ALGORITHM is a search heuristic that is inspired 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 generation.

PROCESS OF NATURAL SELECTION:

This process starts with selection of fittest individual form a given set of population.

They produce offsprings which inherit the characteristic of the parents and will be added to next generation.

If the parents are fit enough, their offsprings will be better than their parents and will have better chances of surviving.

This process keeps on iterating and at the end a generation of fittest individuals will be obtained.

This whole notion can be helpful in search problems.

We select a set of solutions to a problem and sort out a set of best ones out of them. This will eventually narrow down to one best solution that gives optimum results for the given problem.

There are five phases in gentic algorithm and are explained as below:

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:

Offsprings are created by exchanging genes of parents among themselves until the crossover point is reached.

The new offspring is then added to the population.

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.

PSEUDOCODE:

START
      Generate intial population
      Compute fitness
REPEAT
      Selection
      Crossover
      Mutation
      Compute fitness
Iterate until population has converged
STOP

PROGRAM FOR GENETIC ALGORITHM IN MATLAB:

1.)The first code below defines the stalagmite function that will be called in the main 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;
 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

i.) The above function defines the stalagmite function which will be used in the main function.

ii.) The input vectors \'x\' and \'y\' will be assigned with the required values in the main function.

iii.) 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)
        input_vector(1) = xx(i,j);
        input_vector(2) = yy(i,j);
        f(i,j) = stalagmite(input_vector);
    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(xopt,yopt,fopt,\'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(xopt,yopt,fopt,\'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:

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