Week 4.1 - Genetic Algorithm

AIM :

⁕ To understand the concept of genetic algarithm and write a code in MATLAB to optimise the stalagmite function and find the global maxima of the function.

THEORY

INTRODUCTION TO OPTIMIZATION :

Optimization is the process of making something better. In any process we have a set inputs and set of outputs as shown in the fig

Optimization refers to finding the values of inputs in such a way that we get the "bear output values the definition of "pest varies from problem to problem, but in mathematical terms, it meters to maximizing or minimizing one or more objective function by varying the input parametern.

The set of all possible solutions or valdes which the inputs can take make up the search space in this search space lies o point or a setof points which gives the optimal solution. The aim of optimization is to find that paint or not of points in the search space.

In complex machine learning models, the performance usually depends on multiple input parameters. In order to get the optimal model, the parameters must be properly tuned. However, when there are multiple parameter variables, each ranging across a wide spectrum of values, there are too many possible configurations for each set of parameters to be tested. In these cases, optimization methods should be used to attain the optimal input parameters without spending vast amounts of time finding them.

In the diagram above, it shows the distribution of the model based on only two parameters. As evident in the example shown, it is not always an easy task to find the maximum or minimum of the curve. This is why optimization methods and algorithms are crucial in the field of machine learning.

BASIC TERMINOLOGY

Before beginning a discussion on Genetic Algorithms, it is essential to be familiar with some basic terminology which will be used throughout this tutorial.

• Population − It is a subset of all the possible (encoded) solutions to the given problem. The population for a GA is analogous to the population for human beings except that instead of human beings, we have Candidate Solutions representing human beings.

• 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.

  For example, consider the 0/1 Knapsack Problem. The Phenotype space consists of solutions which just contain the item numbers of the items to be picked.

  However, in the genotype space it can be represented as a binary string of length n (where n is the number of items). A 0 at position x represents that x^th item is picked while a 1 represents the reverse. This is a case where genotype and phenotype spaces are different.

• 

• Fitness Function − A fitness function simply defined is a function which takes the solution as input and produces the suitability of the solution as the output. In some cases, the fitness function and the objective function may be the same, while in others it might be different based on the problem.

• Genetic Operators − These alter the genetic composition of the offspring. These include crossover, mutation, selection, etc.

  

  Genetic Algorithms The most commonly used optimization strategy are Genetic Algorithms. Genetic Algorithms are based off of Darwin’s theory of natural selection. It is relatively easy to implement and there is a lot of flexibility for the setup of the algorithm so that it can be applied to a wide range of problems. FITNESS FUNCTION To start off, there must be a fitness function that measures how well a set of input parameters perform. Solutions with a higher fitness derived from a fitness function will be better than ones with a lower fitness.

  GENERATE A POPULATION

  To run a genetic algorithm, first start off with a population of individuals where each individual is a solution. The solution is represented with a set of genes where each gene in the solution is a variable within the model. Each solution is randomly generated and evaluated against the fitness function to generate a fitness score. It is very important to choose an appropriate population size. If the population size is too low, then it is much harder to explore the entire state space of the problem. If the population is too large, then it will take a very long time to process each generation as system costs for calculating fitness and generating each population will take exponentially more time to process.

  PARENT SELECTION

  Next, the population goes through a process called parent selection where the best solutions (most fit individuals) will be selected to create the next generation of solutions. There are many ways to do this, such as Fitness-Proportion Selection (FPS), Rank-Based Selection, and Tournament Selection. These methods all have their pros and cons and should be picked based on the model.

  CROSSOVER

  Once the parents have been selected, the parents undergo a process called crossover. Crossover is when two parents crossover their genes in order to create a new solution (also known as a child). This promotes exploration in the state space of the problem and potentially generates new solutions that have never been tested before.

  This is done differently based on the data types of the solutions. For solutions where the genes are represented in binary, there are methods such as 1-point crossover, n-point crossover, and uniform crossover.

  For solutions where the genes are real-valued, there are methods such as single arithmetic crossover and whole arithmetic crossover.

  Also, for permutation problems (such as the Traveling Salesman problem, etc) there are methods such as the Partially-Mapped Crossover (a.k.a. PMX), Edge crossover, Order 1 Crossover, and Cycle crossover.

  MUTATION

  After the crossover phase, the children generated goes through a mutation phase. Mutation is when each gene could potentially change according to a random probability. This allows for exploitation as the children solution will not change as drastically as during the crossover phase but will still be able to explore around the neighbourhood of its current solution.

  For binary solutions, the mutation process is relatively simple where each bit is toggled according to some mutation probability.

  For real-valued solutions, the different genes can be chosen according to some acceptable range for that variable or by adding some noise that centers around 0 and varies according to some Gaussian distribution.

  Finally, for permutation problems, there are four main methods; insert mutation, swap mutation, inversion mutation, and scramble mutation.

  SURVIVOR SELECTION

  Once the children population is created, the next stage is survivor selection. This is the stage that decides which individuals get to move on to the next generation. There are multiple ways to do this as the new generation can be selected from both the pool of parents and the pool of children. There are two main methods to select the survivors of each generation, Age-Based Selection and Fitness-Based Selection (FBS). In FBS, there is Elitism, where the most fit of every population is selected, and Genitor, where the worst fit of every population gets eliminated.

ALGRITHM REPETITION

Once the new generation is selected, this whole process repeats until the algorithm converges based off of some convergence criteria. After the whole algorithm runs, the best solution from all of the generations is returned.

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.

GOVERNING EQUATION FOR STALAGMITE FUNCTION :

MATLAB CODE FOR STALAGMITE FUNCTION

function [fmax] = stalagmite(input_vector)
x = input_vector(1);
y = input_vector(2);

f_1x = (sin((5.1*pi*x)+0.5))^6;
f_1y = (sin((5.1*pi*y)+ 0.5))^6;

f_2x = exp(-4*log(2)*((x - 0.0667)^2)/(0.64));
f_2y = exp(-4*log(2)*((y - 0.6667)^2)/(0.64));
fmax = -(f_1x*f_2x*f_1y*f_2y);
end

*****************************************************************************************

MAIN CODE FOR GENETIC ALGORITHM

close all
clear all 
clc

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

% creating a 3Dimensional 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(input_vector);
    end
end

surfc(xx,yy,-f)
shading interp

[inputs , fval] = ga(@stalagmite , 2);
xlabel('X axis')
ylabel('Y axis')

• Clear all, close all and clc represents it deletes all temporary memory, closes all plots, and clears the command window.
• We assume x and y values using the linspace command. The uses of linspace command are that if we set lower and upper limits and the number of values we need it takes random values.
• In the next step, the mesh grid command is used in order to form an array of row and column values and it is stored in xx and yy variables.
• Then, for loop command is used. It repeats the function for the length of xx and yy.
• Then in the next step, we call the stalagmite function as stalagmite(input_vector).
• In the next step, surfc command is used in order to get a plot as a surface.
• Then, shading interp command is used in order to remove the grid-like structure in the plot, and color filling is done.you can refer it in the following figure.
• In the next step, the ga command is used. In the ga command, we call the stalagmite function and we need to enter the number of variables. In our problem, we have two variables x and y so we enter it as 2.
• Then in the next step x label and y label is used in order to get a clear picture of our plot

clear all
close all 
clc
%Defining our search space 
x =linspace(0,.6,150);
y =linspace(0,.6,150);
num_case=50;
%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(input_vector);
    end
end

%case 1
tic
 for k = 1:num_case
     [inp,fval(k)] = ga(@stalagmite,2);
     x_1(k) = inp(1);
     y_1(k) = inp(2);
 end
 f = -f;
 fval = -fval;
study1_time=toc;

 figure (1)
 subplot(2,1,1)
 grid on
 surfc(xx,yy,f)
  hold on
 plot3(x_1,y_1,fval,'marker','o','markersize',5,'markerfacecolor','g')
 shading interp
 title('stalagmite plot')
 subplot(2,1,2)
 plot(fval,'color','r','LineWidth',1)
 xlabel ('X axis')
 ylabel('Y axis')

tic
 % study 2 - statistical behaviour with upper and lower bounds 
 for k = 1:num_case
     [inp2,fval2(k)] = ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6]);
     x_2(k) = inp2(1);
     y_2(k) = inp2(2);
 end

 fval2= -fval2;
 study2_time=toc;

 figure (2)
 subplot(2,1,1)
 hold on
 surfc(xx,yy,f)
 shading interp
 plot3(x_2,y_2,fval2,'marker','o','markersize',5,'markerfacecolor','g')
 
 title('bounded inputs')
 subplot(2,1,2)
 plot(fval2,'color','r','LineWidth',1)
 xlabel ('X axis')
 ylabel('Y axis')

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

% study 3 - statistical behaviour with upper and lower bounds
 %Defining our search space
tic
 for k = 1:num_case
     [inp3,fval3(k)] = ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6],[],[],options);
     x_3(k) = inp3(1);
     y_3(k) = inp3(2);
 end

 fval3= -fval3;
 study3_time=toc;

 figure (3)
 subplot(2,1,1)
  hold on
 surfc(xx,yy,f)
 
 shading interp
 plot3(x_3,y_3,fval3,'marker','o','markersize',5,'markerfacecolor','g')
 
 title('bounded inputs')
 subplot(2,1,2)
 plot(fval3,'color','r','LineWidth',1)
 xlabel ('X axis')
 ylabel('Y axis')