GENETIC ALGORITHM

1.AIM :

WRITE MATLAB PROGRAM TO OPTIMIZE THE STALAGMITE FUNCTION AND FIND THE GLOBAL MAXIMA OF FUNCTION

2.THEORY :

GENETIC ALGORITHM

The genetic algorithm is inspired by Charles Darwin's theory of natural evolution in which out of all the fittest individuals are selected for reproduction in order to produce offspring of the next generation. The process of natural selection starts with the selection of fittest individuals from a population. They produce offspring which inherit the characteristics of the parents and will be added to the next generation. If parents have better fitness, their offspring will be better than parents and have a better chance at surviving. This process keeps on iterating and at the end, a generation with the fittest individuals will be found.

Genetic algorithm uses this technique of Evolution as an optimizing process, here the heuristic search strategy is used in which the optimization of a problem is done by iteratively improving the solution.

There are 5 steps in the Genetic algorithm

1. Initialization: It is Starts with an initial generation of candidate solution that is tested against the objective function. Subsequent Generation evolves from the first through Selection, Crossover and then Mutation. which continues until the cycle stop with the true value.
2. Selection: In this we retain the best performing bit strings and pass it on to the next generation.
3. Crossover: We take common things out of the best performing candidates and create a child candidate.
4. Mutation: In this step we take candidate and mutate certain variable and create a child candidate based on mutation.

Stopping criteria:-

The genetic algorithm stops when one of the stopping criteria is met, there are different coniditions which can be used as stopping criteria

The genetic algorithm uses the following conditions to determine when to stop:

The algorithm stops as soon as any one of these conditions is met.

GENETIC ALGORITM SYNTAX

1) x=ga(fun,nvars)

Finds a local unconstrained minimum, x, to the objective function, fun. nvars is the dimension (number of design variables) of fun.

2) x = ga(fun,nvars,A,b):

Finds a local minimum x to fun, subject to the linear inequalities A*x ≤ b. ga evaluates the matrix product A*x as if x is transposed (A*x').

3) x = ga(fun,nvars,A,b,Aeq,beq):

Finds a local minimum x to fun, subject to the linear equalities Aeq*x = beq and A*x ≤ b. (Set A=[] and b=[] if no linear inequalities exist.) ga evaluates the matrix product Aeq*x as if x is transposed (Aeq*x').

4) x = ga(fun,nvars,A,b,Aeq,beq,lb,ub):

Defines a set of lower and upper bounds on the design variables, x, so that a solution is found in the range lb ≤ x ≤ ub. (Set Aeq=[] and beq=[] if no linear equalities exist.)

5) x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon):

Subjects the minimization to the constraints defined in nonlcon. The function nonlcon accepts x and returns vectors C and Ceq, representing the nonlinear inequalities and equalities respectively. ga minimizes the fun such that C(x) ≤ 0 and Ceq(x) = 0. (Set lb=[] and ub=[] if no bounds exist.)

6) x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,options):

Minimizes with the default optimization parameters replaced by values in options. (Set nonlcon=[] if no nonlinear constraints exist.) Create options using optimoptions.

7) x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon):

Requires that the variables listed in IntCon take integer values.

8) x = ga(problem):

Finds the minimum for problem, where problem is a structure.

9) [x,fval] = ga(___):

For any previous input arguments, also returns fval, the value of the fitness function at x.

10) [x,fval,exitflag,output] = ga(___):

Also returns exitflag, an integer identifying the reason the algorithm terminated, and output, a structure that contains output from each generation and other information about the performance of the algorithm.

11) [x,fval,exitflag,output,population,scores] = ga(___):

Also returns a matrix population, whose rows are the final population, and a vector scores, the scores of the final population.

STALAGMITE FUNCTION:-

The stalagmite function which is to be optimized and global maxima is to be found is

`f(x,y)=f_(1,x) f_(2,x) f_(1,y) f_(2,y`

`f_(1.x)=[sin(5.1πx+0.5)]^6`

`f_(1.y)=[sin(5.1πy+0.5)]^6`

`f_(2.x)=exp⁡[-4 ln⁡(2) (x-0.0667)^2/0.64 ]`

`f_(2.y)=exp⁡[-4 ln⁡(2) (y-0.0667)^2/0.64 ]`

3.OBJECTIVES :

1. Optimize the stalagmite function using Statistical behaviour method, Statistical behaviour with bounds method and Statistical Behaviour with increasing GA iterations.
2. Calculate Global Maxima of the function.

4.MATLAB PROGRAM AND RESULTS :

The MATLAB program for stalagmite function is given below

%Stalagmite function definition and body
function [f] = stalagmite_func(input_vector)

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

%Function is given as f(x,y) = (f1,x)*(f2,x)*(f1,y)*(f1,y)

%Calculation of all terms
term1 = (sin((5.1*pi*x )+ 0.5))^6;
term2 = (sin((5.1*pi*y) + 0.5))^6;
term3 = exp(-4*log(2)*((x-0.0667)^2)/0.64);
term4 = exp(-4*log(2)*((y-0.0667)^2)/0.64);

f = -(term1*term2*term3*term4);

end

To find the maximum value of the function, the sign of function is reversed, so that it will give value for the reverse case of minima, i.e. maxima.

MATLAB program to optimise the stalagmite function and find the global maxima of the function

Here 3 different studies have been done:

1) Statistical Behavior

In this case, maximum value of the function is found out with no restrictions, no bounds, and no limits. Genetic algorithm is free to choose the population then reproduce and mutate.

2) Statistical Behavior - with Upper and Lower Bounds

Here the program has been restricted within specific bounds namely upper bound and lower bound.

Upper and lower limit of the x is 0 and 0 respectively.

Upper and lower limit of the y is 1 and 1 respectively.

3) Statistical Behaviour with increasing GA iterations

Here we are going to increase the population size because if initial population is too small then it not going to find out global maxima, it only finds the local maxima.

Here the population size have been increased to 250.

MATLAB program:-

%Program to calculate Global maxima of a Stalagmite function

clear all
close all
clc


%defining search space
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);

%creating a 2D mesh
[xx, yy] = meshgrid(x,y);

%evaluating the 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_func(input_vector);
    end    
end

%Total no. of Iterations
n = 50;

%Study 1: statistical behaviour

tic %to calculate study time
for i=1:n
    [inputs,fopt(i)]=ga(@stalagmite_func,2); %using inbuilt t=genetic algorithm 'ga()'
    %stalagmite_func is the function passed and '2' is the no of variable
    %inputs stores the optimum value and the fopt stores the function value at x
    
    xopt(i)=inputs(1);
    yopt(i)=inputs(2);
end

study_1_time=toc
figure(1)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
xlabel('x values')
ylabel('y values')
title('Unbounded Inputs')
subplot(2,1,2)
plot(-fopt)
xlabel('Iterations')
ylabel('Function maximum')

%Study 2: statistical behaviour with bounds

tic
for k = 1:n
[inputs2 , fopt2(k)] = ga(@stalagmite_func, 2,[],[],[],[],[0;0],[1;1]);
xopt2(k) = inputs2(1);
yopt2(k) = inputs2(2);
end
study_2_time=toc

figure(2)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
shading interp
plot3(xopt2,yopt2,-fopt2,'marker','o','markerfacecolor','r')
xlabel('x values')
ylabel('y values')
title('Statistical Behaviour - with upper and lower bound')
subplot(2,1,2)
plot(-fopt2)
xlabel('Iterations')
ylabel('function maximum')
title('Statistical Behaviour - with upper and lower bound')

%Study 3 increasing GA iterations

options= optimoptions('ga');
options= optimoptions(options,'PopulationSize',250);

tic
for i=1:n
[inputs, fopt(i)]= ga(@stalagmite_func,2,[],[],[],[],[0;0],[0.5;0.5],[],[],options);
xopt(i)=inputs(1);
yopt(i)=inputs(2);
end

study_3_time= toc;
figure(3)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
xlabel('x values')
ylabel('y values')
title('Bounded inputs with modified population size')
subplot(2,1,2)
plot(-fopt)
xlabel('Iterations')
ylabel('Function maximum')

Explanation:-

1)At first we have to define our search space, the search space is chosen to be between 0 to 0.6 with 150 intervals using the 'linspace()' command.

2)initially the no of iterations are restricted to 50 ('n=50').

3)The vectors created which are named 'x' and 'y' are converted into a matrix using 'meshgrid(x,y)'.

4)The values from matrix are taken and solved in the stalagmite function and stored in a variable.

5)Finally genetic algorithm for all 3 cases are solved and plotted.

RESULTS:-

Result for the 3 cases studied with the study time is given below

1) Statistical Behavior

Here we get multiple results due to random sampling and most of the values lies between 0.2 to 0.8.

Study time is 12.5293 seconds.

2) Statistical Behavior - with Upper and Lower Bounds

Results in this case are more better than the previous one, most of the values lies between 0.8 to 0.95.

Study time is 18.5009 seconds.

3) Statistical Behaviour with increasing GA iterations

Here we get the most accurate result, most of the values lies between 0.99999983 to 0.99999985.

Study time is 70.8371 seconds.

The maximum value of function is 1

Errors Faced:-

1) In 'meshgrid(x,y)' command instead of comma, dot was written.

2) Name of function in the program while calling the function was written wrong.

5.CONCLUSION :

1. The stalagmite function was optimized.
2. Global maxima of the function was found.

6.REFERENCES :

1. https://in.mathworks.com/help/gads/ga.html#d120e39200
2. https://www.youtube.com/watch?v=1i8muvzZkPw
3. https://in.mathworks.com/help/gads/how-the-genetic-algorithm-works.html