Week 4 - Genetic Algorithm

AIM: -

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

INTRODUCTION: -

Genetic Algorithm (GA) is a search-based optimization technique based on the principles of Genetics and Natural Selection. GAs are a subset of a much larger branch of computation known as Evolutionary Computation.

In GAs, we have a pool or a population of possible solutions to the given problem. These solutions then undergo recombination and mutation (like in natural genetics), producing new children, and the process is repeated over various generations. Each individual (or candidate solution) is assigned a fitness value (based on its objective function value) and the fitter individuals are given a higher chance to mate and yield more “fitter” individuals. This is in line with the Darwinian Theory of “Survival of the Fittest”.

In this way we keep “evolving” better individuals or solutions over generations, till we reach a stopping criterion.

Genetic Algorithms are sufficiently randomized in nature, but they perform much better than random local search (in which we just try various random solutions, keeping track of the best so far), as they exploit historical information as well.

Advantages of GAs

GAs have various advantages which have made them immensely popular. These include −

• Does not require any derivative information (which may not be available for many real-world problems).
• Is faster and more efficient as compared to the traditional methods.
• Has very good parallel capabilities.
• Optimizes both continuous and discrete functions and also multi-objective problems.
• Provides a list of “good” solutions and not just a single solution.
• Always gets an answer to the problem, which gets better over the time.
• Useful when the search space is very large and there are a large number of parameters involved.

Limitations of GAs

Like any technique, GAs also suffer from a few limitations. These include −

• GAs are not suited for all problems, especially problems which are simple and for which derivative information is available.
• Fitness value is calculated repeatedly which might be computationally expensive for some problems.
• Being stochastic, there are no guarantees on the optimality or the quality of the solution.
• If not implemented properly, the GA may not converge to the optimal solution.

Basic Terminology

Population:-

The problem initiates 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 and Genes are joined into a string which yields us chromosome which is nothing but a solution .

• Chromosomes− A chromosome is one such solution to the given problem.
• Gene− A gene is one element position of a chromosome.
• Allele− It is the value a gene takes for a particular chromosome.
• Genotype− Genotype is the population in the computation space. In the computation space, the solutions are represented in a way which can be easily understood and manipulated using a computing system.
• Phenotype− Phenotype is the population in the actual real world solution space in which solutions are represented in a way they are represented in real world situations.
• Decoding and Encoding− For simple problems, the phenotype and genotype spaces are the same. However, in most of the cases, the phenotype and genotype spaces are different. Decoding is a process of transforming a solution from the genotype to the phenotype space, while encoding is a process of transforming from the phenotype to genotype space. Decoding should be fast as it is carried out repeatedly in a GA during the fitness value calculation.

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.

Selection phase:-

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

Crossover:-

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

Termination:-

Finally, the algorithm terminates if the population has converged. Then it is said that genetic algorithm has provided a set ot solution to our problem

PROCEDURE: -

Firstly, we need to define a function called STALAGMITE function which takes two inputs, namely x and y, and gives the output which is used as input for GA to optimise. The code below shows the Stalagmite function.

# CODE – 1

This code solves the functions given below:

`f_(1x ) = (sin⁡((5.1πx)+0.5) )^6`

`f_(1y) = (sin⁡((5.1πy)+0.5) )^6`

`f_(2x)= e^(((-4*log⁡(2)*((x-0.0667)^2 ))/0.64) )`

`f_(2y)= e^(((-4*log⁡(2)*((y-0.0667)^2 ))/0.64) )`

`f_(1x)`,`f_(2x)` , `f_(1y)`,`f_(2y)` are signified as Func1, Func2, Func3, Func4 in the code.

The next code uses the Genetic Algorithm to optimise the output from the stalagmite function.

# CODE -- 2

Here, X and Y are the inputs for the stalagmite function and the number of iterations is set to 50 and is determined by the variable iterations. The stalagmite function is generated in next step and is stored in Func variable.

The 1^st study is to use GA unbounded and use it to optimise the stalagmite function by finding minimum value of the function. It is made to run from 1 to iterations time and the output possible minimum function value is stored in Fun_val_1 vector and the possible location of minimum values are stored in Output_1 matrix. Output_1 has two columns with 1^st denoting x-value and 2^nd denoting y-value which is store in X_out_1 and Y_out_1 vector respectively. Using the tic-toc function the total time for optimisation is calculated and is stored in study_1_time.

The two plot is generated in single area using subplot() function. For maximising the stalagmite function the negative of Func vector is use as negative of minima is maxima. Surface plot is generated using surfc(X,Y,-Func) which plots the 3D surface plot with grids. To remove the grids we use shading interp command and we get the smooth plot. Using hold on command another plot is superimposed on the same plot and then the optimised values from GA is plotted using plot3(X_out_1,Y_out_1,-Fun_val_1,'color','b','marker','o','markersize',5,'markerfacecolor','r') command. The second portion of the subplot plots the output optimised value i.e. -Fun_val_1 per iterations.

The 2^nd study is using GA by limiting the values of its domain using upper and lower bounds. The command [Output_2, Fun_val_2(k)] = ga(@stalagmite,2,[],[],[],[],[0,0],[0.9,0.9]) limits the algorithm limit to x-domain of 0 to 0.9 and y-domain of 0 to 0.9 and the same procedure is followed as above. The time take to complete the iterations is stored in study_2_time variable using tic-toc function and finally the respective plot is generated using the process as done before.

The 3^rd study is using GA using bounding and also limiting the Population size. Using optimoptions command the Population size is specified for the function ga using the command optimoptions(@ga,'PopulationSize',400) in the specified format and is stored in options variable. Using the command [Output_3, Fun_val_3(k)] = ga(@stalagmite,2,[],[],[],[],[0,0],[1,1],[],options) the domain as well as the population size are both limited which helps to find the optimal value accurately. The plotting is done with the same process as above and the optimisation is stored in study_3_time variable using tic-toc function.

CONCLUSION: -

Genetic Algorithm always gives the minimum value of the function. To maximise the output negative sign is used on output function values from genetic algorithm process.

Form the plot of 1^st study, we see that there are a large number of possible maximum value of the function is calculated by GA and it is difficult to determine the global maximum of all. Form plot we can also see that the X and Y values considered by GA as possible maxima lies beyond the actual X and Y domains which are not necessary. And also, the optimal values of function lies between 0 to 1 which is not a good optimisation. The time taken in this study is 3.7880 seconds.

From the plot of 2^nd study, the optimisation is much better than the previous one as the possible optimal values lies between the 4 values which is obtained by limiting the domain of calculation. The function value lies between 0.7 and 1 which is much better than the previous one but still it needs to be improved for getting global optimal value. The time taken in this study is 4.2171 seconds.

From the plot of 3^rd study, the optimisation results in only one value of X_out_3 and Y_out_3 which shows that the optimal result has been reached. The 2^nd sub plot shows that the function value lies between 0.99999985 to 0.99999977 which is almost 1. This accuracy of the result is obtained by limiting the inputs to a bounding domain and also imposing a population limit. But the simulation time has increased to 23.4651 seconds.

CODE-1

function [Func] = stalagmite(Input)
   
    P = Input(1);
    Q = Input(2);

    Func1 = (sin((5.1*pi*P)+0.5))^6;
    Func2 = (sin((5.1*pi*Q)+0.5))^6;
    Func3 = exp((-4*log(2)*((P-0.0667)^2))/(0.64));
    Func4 = exp((-4*log(2)*((Q-0.0667)^2))/(0.64));

    Func = -(Func1*Func2*Func3*Func4);

end

CODE-2

close all
clear all
clc

X = linspace(0,0.8,200);
Y = linspace(0,0.8,200);

iterations = 50;

for i = 1:length(X)
    for j = 1:length(Y)
        Input(1) = X(i);
        Input(2) = Y(j);
        Func(i,j) = stalagmite(Input);
    end
end

tic

for k = 1:iterations
    [Output_1, Fun_val_1(k)] = ga(@stalagmite,2);
    X_out_1(k) = Output_1(1);
    Y_out_1(k) = Output_1(2);
end

study_1_time = toc

figure(1)
subplot(3,1,1:2)
surfc(X,Y,-Func)
shading interp
hold on
plot3(X_out_1,Y_out_1,-Fun_val_1,'color','b','marker','o','markersize',5,'markerfacecolor','r')
xlabel('X values')
ylabel('Y values')
title('Unbounded Inputs')
hold off

subplot(3,1,3)
plot(-Fun_val_1,'color','b','linewidth',2)
xlabel('Number of Iterations')
ylabel('Function Values')

tic

for k = 1:iterations
    [Output_2, Fun_val_2(k)] = ga(@stalagmite,2,[],[],[],[],[0,0],[0.9,0.9]);
    X_out_2(k) = Output_2(1);
    Y_out_2(k) = Output_2(2);
end

study_2_time = toc

figure(2)
subplot(3,1,1:2)
surfc(X,Y,-Func)
shading interp
hold on
plot3(X_out_2,Y_out_2,-Fun_val_2,'color','b','marker','o','markersize',5,'markerfacecolor','r')
xlabel('X values')
ylabel('Y values')
title('Bounded Inputs')
hold off

subplot(3,1,3)
plot(-Fun_val_2,'color','b','linewidth',2)
xlabel('Number of Iterations')
ylabel('Function Values')

options = optimoptions(@ga,'PopulationSize',400);

tic

for k = 1:iterations
    [Output_3, Fun_val_3(k)] = ga(@stalagmite,2,[],[],[],[],[0,0],[1,1],[],options);
    X_out_3(k) = Output_3(1);
    Y_out_3(k) = Output_3(2);
end

study_3_time = toc

figure(3)
subplot(3,1,1:2)
surfc(X,Y,-Func)
shading interp
hold on
plot3(X_out_3,Y_out_3,-Fun_val_3,'color','b','marker','o','markersize',5,'markerfacecolor','r')
xlabel('X values')
ylabel('Y values')
title('Bounded Inputs with Population Limit')
hold off

subplot(3,1,3)
plot(-Fun_val_3,'color','b','linewidth',2)
xlabel('Number of Iterations')
ylabel('Function Values')