Week 4 - Genetic Algorithm

AIM:

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

PROGRAMMING LANGUAGE USED IS MATLAB

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.

STALAGMITE FUNCTION-A stalagmite is an upward-growing mound of mineral deposits that have precipitated from water dripping onto the floor of a cave.

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:

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.

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.

PSEUDON CODE

START

Generating the initial population

Compute fitness

REPEAT

Selection

Cross over

Mutation

Compute fitness

iterate untill the 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.

%Creating the stalagmite function

function[fxy]=stalagmitenew(input_vector)

%Passing the values in x and y for the ease of programmig

x=input_vector(1);
y=input_vector(2);

%Writing the stalgamite function programme

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.0667).^2)./0.64);
f2y=exp((-4*log(2)*(y-0.0667).^2)./0.64);

fxy=-(f1x*f1y*f2x*f2y);%Negative sign is used to maximize the stalagmite function
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 our searchspace

x=linspace(0,0.6,150);
y=linspace(0,0.6,150);

searchnum=50;

%Creating a 2-D mesh
[X,Y]= meshgrid(x,y);

%Evaluating the stalagmite function

for i=1:length(X)
for j=1:length(Y)
input_vector(1)=X(i,j);
input_vector(2)=Y(i,j);
f(i,j)=stalagmitenew(input_vector);
end
end

%First iteration studying the statistical behaviour

tic
for i=1:searchnum
[inputs,f_optimum(i)]=ga(@stalagmitenew,2);
x_optimum(i)=inputs(1);
y_optimum(i)=inputs(2);
end
iteration1_Time=toc

%Plotting
figure(1)
subplot(2,1,1)
hold on
surfc(X,Y,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 study bonding the values
tic
for i=1:searchnum
[inputs , f_optimum(i)] = ga(@stalagmitenew,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(X,Y,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:searchnum
[inputs , f_optimum(i)] = ga(@stalagmitenew,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(X,Y,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

----//Errors faced while programming//----

This is not a complicated code so the only error that can occur is while creating the functions and only minute issues and can be solved by the following methods

Error 1-Saving the name of the file different as that given in matlab

solution--The file name should be the same as that of the function name other wise it may cause error

Error 2- writing the equations wrong ,always write the correct equations and cross check with the value obtained mathematically with the values obtained through the code.

Error 3- While using the plot function always check to give the right parameters

Error4 --Matlab is Case Sensitive so take care of that

Error5-- Make sure to provide % sign before command statements .