OPTIMIZATION OF STALAGMITE FUNCTION USING GENETIC ALGORITHM.

AIM: OPTIMIZATION OF STALAGMITE FUNCTION USING GENETIC ALGORITHM.

THEORY AND GOVERNING EQUATIONS:

Stalagmite Function: Stalagmite is a type of rock formation that rises from the floor of a cave due to the accumulation of material deposited on the floor from ceiling drippings.

A stalagmite function is similar to stalagmite which consists of several peaks in its domain. The local peaks are local maxima region while there is only one global peak i.e. global maxima. In this project, we are interested in finding this global maximum of a stalagmite function.

The mathematic definition of stalagmite function is,

OBJECTIVE:

1. To optimize stalagmite function using genetic algorithm and find global maxima of the function.
2. To study the concept behind Genetic Algorithm.

WHAT IS GENETIC ALGORITHM?

Genetic Algorithm is an optimization technique which is based on natural selection i.e. the process that drives biological evolution. It can be used for both constrained and unconstrained optimization problems. The genetic algorithm repeatedly modifies a population of individual solutions. At each step, the genetic algorithm selects individuals at random from the current population to be parents and uses them to produce the children for the next generation. Over successive generations, the population "evolves" toward an optimal solution.

HOW GENETIC ALGORITHM WORKS?

Let’s take a hypothetical situation in which the ruling government of a country decide to remove all bad people from the country.

To make this happen, the government comes up the following policy which states that:

1. Select all good people and ask them to extend their generations by having children.
2. This will continue for a few generations and finally, there will be all good people.

So by using biological evolution, the government came to find the solution to the problem.

So basically,

• Firstly, we defined our initial population as the country.
• Then, we defined a function(fitness function) to classify whether is a person is good or bad.
• Then we selected good people for mating to produce their off-springs.
• And finally, these off-springs replace the bad people from the population and this process repeats to until we have all good people.

This is how the genetic algorithm actually works, which basically tries to mimic human evolution to some extent.           

STEPS INVOLVED IN GENETIC ALGORITHM:

1. Initialization: To solve this problem using a genetic algorithm, our first step would be defining our population.

2. Fitness function: The fitness function is the function you want to optimize. For standard optimization algorithms, this is known as the objective function.

3. Selection: Now, we select the parent species from our population which can mate and produce off-springs. The general thought is that we should select the fit members and allow them to produce off-springs. But that would lead to a population that is more close to one another in a few next generations, and therefore less diversity. Therefore, the selection is completely random.

4. Crossover: So in this previous step, we have selected parent chromosomes that will produce off-springs. So in biological terms, crossover is nothing but reproduction.

5. Mutation: During the growth of children, there is some change in the genes of children which makes them different from its parents. This process is known as mutation, which may be defined as a random tweak in the chromosome, which also promotes the idea of diversity in the population.

The off-springs thus produced are again validated using our fitness function, and if considered fit then will replace the less fit chromosomes from the population. This process continues until there is no improvement in the population and finally we obtain an optimized solution.

SYNTAX OF GA IN MATLAB:

1. 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').
2. 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').
3. 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.)
4. x= ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,IntCon,options) minimizes with the default optimization parameters replaced by values in options. (Set nonlcon=[] if no nonlinear constraints exist.) Create options using optimoptions.

       func = fitness function(objective function), nvars = no. of variables in fitness function

MAIN CODE:

%to find global maxima of a slalagmite function
clear all
close all 
clc
%creating 1-D array
xi=linspace(0,0.6,150);
yi=linspace(0,0.6,150);
%creating 2-D array
[xx yy]=meshgrid(xi,yi); 

%Getting output from stalagmite function and storing it
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)=slalagmite(input_vector);
        
    end
    
end

                    % STUDY:1 Unbound input values
                
iterations=100;
tic
for i=1:iterations
    
    [input1, f_val1(i)]= ga(@slalagmite, 2);
    x1(i)=input1(1);
    y1(i)=input1(2);
end
time1=toc;

%plotting unbound iteration case
figure(1)
subplot(2,1,1)
surfc(xx,yy,-f);
shading interp;
hold on;
plot3(x1,y1,-f_val1,'marker','*');
title('Study1: unbound input values');
xlabel('x_input');
ylabel('y_input');
zlabel('Z_value');
subplot(2,1,2)
plot(-f_val1);
axis([0,100,0,1]);
xlabel('iterations');
ylabel('z_max_1');

                          %STUDY:2 bounding input values
                          
tic
for i=1:iterations
    [input2, f_val2(i)]= ga(@slalagmite, 2,[],[],[],[],[0;0],[1;1]);
    x2(i)=input2(1);
    y2(i)=input2(2);
    
end
time2=toc;

%plotting bound iteration case
figure(2)
subplot(2,1,1)
surfc(xx,yy,-f);
shading interp;
hold on;
plot3(x2,y2,-f_val2,'marker','*');
title('Study2: bounding input values');
xlabel('x_input');
ylabel('y_input');
zlabel('Z_value');
subplot(2,1,2)
plot(-f_val2);
axis([0,100,0,1]);
xlabel('iterations');
ylabel('z_max_2');

                 %STUDY:3 Bounding input with increased poplation size
                 
opti=optimoptions('ga');
opti=optimoptions(opti,'PopulationSize',350);
tic
for i=1:iterations
    
    [input3, f_val3(i)]= ga(@slalagmite, 2,[],[],[],[],[0;0],[1;1],[],[],opti);
    x3(i)=input3(1);
    y3(i)=input3(2);
    
end
time3=toc;

time1
time2
time3
x_optimum=x3(1)
y_optimum=y3(1)
z_optimum=-f_val3(1)

%plotting with increased population
figure(3)
subplot(2,1,1)
surfc(xx,yy,-f);
shading interp;
hold on;
plot3(x3,y3,-f_val3,'marker','*');
title('Study3: bounding input with increased population');
xlabel('x_input');
ylabel('y_input');
zlabel('Z_value');
subplot(2,1,2)
plot(-f_val3);
axis([0,100,0,1]);
xlabel('iterations');
ylabel('z_max_3');

 FUNCTION USED:

function z = slalagmite(input)

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

fx_1 = (sin((5.1*pi.*x) + 0.5)).^6;
fx_2 = exp((-4*log(2).*((x-0.0667).^2))./0.64);
fy_1 = (sin((5.1*pi.*y) + 0.5)).^6;
fy_2 = exp((-4*log(2).*((y-0.0667).^2))./0.64);

z = -fx_1.*fx_2.*fy_1.*fy_2;

end

 STEPS:

1. Using 'linspace', xi and yi 1D array generated to form 2D matrix.

2. Using 'meshgrid' command, a 2D set of input matrix was generated.

3. Each pair of xx and yy was given as an argument to stalagmite function which calculates the z value for it.

4. The output values are stored in f matrix.

5. study 1: for 100 iterations, genetic algorithm was executed to find minimum values (note: we have defined stalagmite function as negative so mini value in it is max. value in positive stalagmite function) of function.

6. figure(1) was plotted for study 1, in which we create subplot to divide the figure window.

7. In figure1, max value of Z was plotted against no. of iterations and also a 3D plot of all mini value points were plotted.

8. study:2 using input bound syntax of GA, we can see the result's accuracy is increased.

9. study: 3 by increasing the population size, we get the optimized result.

ERROR FACED: no error encountered

OUTPUT:

                                                                Figure1

                                                                   Figure 2

                                                                    figure 3

REFERENCES:

https://in.mathworks.com/help/gads/how-the-genetic-algorithm-works.html

https://www.analyticsvidhya.com/blog/2017/07/introduction-to-genetic-algorithm/