Week 4.1 - Genetic Algorithm

#8. GENETIC ALGORITHM (Ga)

AIM: To write a program to calculate Global Maxima using Genetic Algorithm, using MATLAB.

OBJECTIVE:

Write a code in MATLAB to optimise the stalagmite function and find the global maxima of the function.

• With Unbounded inputs.(Case1)
• With Bounded inputs.(Case2)
• With Bounded inputs with increased population.(Case3)

THEORY:

1. Introduction to optimization:

Optimization is the process of making something better. In any process, we have a set of inputs and a set of outputs.

Set of Inputs ==>> Process ==>> Set of Outputs.

Optimization refers to finding the values of inputs in such a way that we get the “best” output values. The definition of “best” varies from problem to problem, but in mathematical terms, it refers to maximizing or minimizing one or more objective functions, by varying the input parameters.

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

As explained above we need to choose an optimization algorithm to perform the Optimization process, Genetic Algorithm is one of it.

Genetic Algorithms(GAs) are commonly used to generate high-quality solutions to optimization and search problems by relying on biologically inspired operators such as mutation, crossover and selection. The Genetic Algorithm in MATLAB always minimizes the function.

There are five important features of GA:

• Fitness Function represents the main requirements of the desired solution of a problem (i.e., cheapest price, shortest route, most compact arrangement, etc.). This function calculates and returns the fitness of an individual solution. The Fitness function used here is the Stalagmite Function.

The Stalagmite Function in this model will help us to generate local minima and maxima.

• Encoding possible solutions to a problem are considered as individuals in a population. If the solutions can be divided into a series of small steps (building blocks), then these steps are represented by genes and a series of genes (a chromosome) will encode the whole solution. This way different solutions to a problem are represented in GA as chromosomes of individuals.
• The selection defines the way individuals in the current populations are selected for reproduction. There are many strategies for that (e.g., roulette-wheel, ranked, tournament selection, etc). but usually the individuals which are more fit are selected.
• The crossover operator defines how chromosomes of parents are mixed in order to obtain genetic codes of their offspring. This implements the inheritance property (offspring inherit genes of their parents).
• The mutation creates random changes in the genetic codes of the offspring. This is needed to bring some random diversity into the genetic code. In some cases, GA cannot find the optimal solution without a mutation operator (local maximum problem).

2. THE GENETIC ALGORITHM:

Nature has always been a great source of inspiration to all mankind.

Genetic Algorithms (GAs) are search based algorithms based on the concepts of natural selection and genetics. GAs are a subset of a much larger branch of computation known as Evolutionary Computation.

GAs were developed by Jhon Holland and his students and colleagues at the University of Michigan, most notably David E.Goldberg and has since been tried on various optimization problems with a high degree of success.

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.

BASIC STRUCTURE:

ADVANTAGES OF GAs:

GAs have various advantages which have made them immensely popular. These includes –

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

APPLICATIONs OF GA:

Genetic Algorithms are primarily used in optimization problems of various kinds, but they are frequently used in other application areas as well.

In this section, we list some of the areas in which Genetic Algorithms are frequently used. These are-

• Optimization- Genetic Algorithms are most commonly used in optimization problems wherein we have to maximize or minimize a given objective function value under a given se of constraints. The approach to solve Optimization problems has been highlighted throughout the tutorial.
• Economics- GAs are also used to characterize various economic models like the cobweb model, game theory equilibrium resolution, asset pricing, etc.
• Neural Networks- GAs are also used to train neural networks, particularly recurrent neural networks.
• Parallelization- GAs also have very good parallel capabilities, and prove to be very effective means in solving certain problems, and also provide a good area of research.
• Image Processing- GAs also used for various digital image processing (DIP) tasks as well like dense pixel matching.
• Vehicle routing Problems- With multiple soft time windows, multiple depots and a heterogeneous fleet.
• Scheduling applications- GAs are used to solve various scheduling problems as well, particularly the time tabling problem.
• Machine Learning- as already discussed, genetics based machine learning (GBML) is a niche area in machine learning.
• Robot Trajectory Generation- GAs have been used to plan the path which a robot arm takes by moving from one point to another.
• Parametric Design of Aircraft- GAs have been used to design aircrafts by varying the parameters and evolving better solutions
• DNA Analysis- GAs have been used to determine the structure of DNA using spectrometric data about the sample.
• Multimodal Optimization- GAs are obviously very good approaches for multimodal optimization in which we have to find multiple optimum solutions.
• Traveling salesman problem and its applications- GAs have been used to solve the TSP, which is a well-known combinatorial problem using novel crossover and packing strategies.

ADVANCED APPLICATIONs OF GA:

Constrained Optimization Problems:

Constrained Optimization problems are those optimization problems in which we have to maximize or minimize a given objective function value that is subject to certain constraints. Therefore, not all results in the solution space are feasible, and the solution space contains feasible regions as shown in the following image:

In such a scenario, crossover and mutation operators might give us solutions which are infeasible. Therefore, additional mechanisms have to be employed in the GA when dealing with constrained Optimization Problems.

Some of the most common methods are-

• Using penalty functions which reduces the fitness of infeasible solutions, preferably so that the fitness is reduced in proportion with the number of constraints violated or the distance from the feasible region.
• Using repair functions which take an infeasible solution and modify it so that the violated constraints get satisfied.
• Not allowing infeasible solutions to enter into the population at all.
• Use a special ‘representation or decoder functions’ that ensures feasibility of the solutions.

PROGRAM FOR THE STALAGMITE FUNCTION:

MATHEMATICAL EQUATIONs:

The above function is defined in the stalagmite function in MATLAB :

%Stalagmite_function.
function [f]=stalagmite(input_vector) %stalagmite function with inputs as input_vector which contains the x and y variables.  
x=input_vector(1);
y=input_vector(2);

f1=[sin(5.1*pi*x+0.5)]^6;
f2=[sin(5.1*pi*y+0.5)]^6;
f3=exp(-4*log(2)*((x-0.0667)^2)/0.64);
f4=exp(-4*log(2)*((y-0.0667)^2)/0.64);
f=-(f1*f2*f3*f4);  %The Negative sign denotes the inverse of the Stalagmite function and is added in order to find the Maximum value, as GA always gives the Minimum value. 
end

The format for writing Genetic Algorithm in MATLAB:

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

1. ‘x’ is the local minima point.
2. ‘fun’ is the function to be called. (in our case, it’s the stalagmite function.)
3. ‘nvars’ indicates the no of variables (2)
4. ‘A’ and ‘b’ are used to indicate any kind inequalities that exist in the function.
5. ‘Aeq’ and ‘Beq’ also denotes the
6. ‘lb’ is lower bound.
7. ‘ub’ is upper bound.
8. ‘nonlcon’ gives a two vectors representing inequalities and equalities.
9. ‘option’ is used to perform additional operations like increasing population size. This is done with the help of “optimoptions”.

CODE EXPLANATIONs /PROCEDURE:

Start programming in MATLAB with these three commands, as all the previous calculations are erased.

Clear all: for clears all the data stored in the workspace previously.

Close all: for closes all the previous figures and plots.

clc: for clears the command window.

Case1:

1. In case1 we will be just be applying the Genetic Algorithm and see how the program performs without ‘bounded’.

So in the beginning we are providing the ‘x’ & ’y’ inputs using the ‘linspace’ command and the ‘num_cases’ which is the iteration number. Since x & y are both a 1D array, we using the ‘meshgrid’ command to form a 2D array represents by ‘xx’ & ‘yy’.

2. Then ‘for’ loop will run for the length of the xx & yy, The input function is a row vector with 2 columns which we are assigning using ‘input_vector(1) and (2).

The ‘stalagmite’ function here will help us in finding the local maxima and minima. This loop is used entirely for the plotting of the 3D Graph, so that we can easily understand the working. The ‘stalagmite’ function is call into main program.

We already know that ‘ga’ will only find the Global minima (i.e.) using the ‘stalagmite’ function it can only find the lowest value. So we need to make a small change in the final step of the function so that ‘ga’ will be able to find the Global maxima so we will be introducing a “ – “ inverse sign to ‘f’ so that ‘ga’ can find the Global maxima.

3. For the case1, we will be running the Genetic Algorithm with ‘Unbounded’ (i.e., without lower & upper bound) and the default population 50 (since ‘ga’ is an iterative solver the loop is fun for 50 loops)

The inputs have two values the x & y coordinates of the ‘f_opt’. we can see that the ‘stalagmite’ function is used and the variable two are inputted. The ‘x_opt’ is the x value from the input and ‘y_opt’ is the y value.

And we will be calculating the time taken using the ‘tic’ & ‘toc’ commands.

4. We will be creating two plots so we will be applying the ‘subplot’ command.

The ‘surfc’ is used to view the 3D plot of points xx, yy, -f, here the -f is to represents the plot in the positive axis.

‘hold on’ is used to views all the plots.

‘shading interp’ is used so that the 3D plot is more representable.

‘plot3’ is used to plot all the values ‘x_opt’ ,’y_opt’ & ‘-f_opt’ in the 3D plot and the second ‘subplot’ only views the ‘-f_opt’ in a 2D plot.

Case2:

5. Since we are able to see the Surface graph from the case1, we can assume where the Maximum will be hence so we will be directing the algorithm to search in that region.

Only this region of the code will be modified in the case2.

Here, we are giving the upper and lower bounds value (0,0) & (.6, .6). we are instructing the algorithm that the maximum will be under that region.

The population for case2 will be 50 which is default value.

Case3:

6. In case3 , we will be put population value 300, the higher number of the population it increases the probability of us finding the optimum function.

There are several things to kept in mind when dealing with GA population :-

• The diversity of the population should be maintained otherwise it might lead to premature convergence.
• The population size should not be kept very large as it can cause a GA to slowdown,

So in case3 the population is 300 ,we put it in ‘options’ for ‘optimoptions’ and the other values are the same as of case2. So, the time taken to run the program will be more for this case.

The ‘options’ command is used to provide the value of the population. The ‘optimoptions’ command is used to create optimization options for the ‘ga’ and the ‘population size’ ,300 is inputted.

MATLAB CODE:

for Case1:

In the case1, the behaviour of the algorithm is studied by not defining the limits. The GA runs with 'Unbounded'.

%Case 1 of iteration.(Unbounded inputs)
clear all
close all
clc

x=linspace(0,0.6,150);  % x value inputs
y=linspace(0,0.6,150);  % y value inputs
[xx,yy]=meshgrid(x,y);  % Creating a 2-D mesh
num_cases=50;           % GA runs for 50 iterations.

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

tic                % Study time count start.
for i=1:num_cases
    [inputs,f_opt(i)]= ga(@stalagmite,2);  % GA function is used to run the stalagmite data and give the optimal solutions.
    x_opt(i)=inputs(1);
    y_opt(i)=inputs(2);

end
case1_time = toc   % Study time count end.

% GA gives us Minima value, Inverse f,f_opt is taken for Maxima value.

subplot(2,1,1)
surfc(xx,yy,-f)  % Generation of Stalagmite function.
hold on
shading interp  % To bring visually smooth curve surface without grid line.
plot3(x_opt,y_opt,-f_opt,'Marker','o','MarkerSize',4,'MarkerFaceColor','r')  %plotting the optimum values with a red dot marker along the stalagmite 3D curves. 
title('Unbounded inputs')
xlabel('X-axis')
ylabel('Y-axis')
subplot(2,1,2)
plot(-f_opt)     % plot of f_opt for every iterations
xlabel('Number of iterations ---->')
ylabel('Function Max ---->')

OUTPUT:

for case1-(Unbounded inputs)

case1_time =

4.2632

In the above fig, it can be seen that since the inputs are boundless GA algorithm has mapped local maxima points outside of stalagmite .

for Case2:

here the lower and upper bounds are defined so as to know the boundaries within which the global maxima lies.

%Case 2 of iteration.(Bounded inputs)
clear all
close all
clc

x=linspace(0,0.6,150);  % x value inputs
y=linspace(0,0.6,150);  % y value inputs
[xx,yy]=meshgrid(x,y);  % Creating a 2-D mesh
num_cases=50;           % GA runs for 50 iterations.

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

tic                % Study time count start.
for i=1:num_cases

    %Objective function is stalagmite and the number of variables is 2.
    % A,b,Aeq and Beq=[], as there is no Linear equalities and inequalities constraints in this function.
    %lower boundary of variables x and y in ga is set as [0,0].
    %upper boundary of variables x and y in ga is set as [0.6,0.6].

    [inputs,f_opt(i)]= ga(@stalagmite,2,[],[],[],[],[0,0],[0.6,0.6]);  % GA function is used to run the stalagmite data and give the optimal solutions.
    x_opt(i)=inputs(1);
    y_opt(i)=inputs(2);

end
case2_time = toc   % Study time count end.

% GA gives us Minima value, Inverse f_opt is taken for Maxima value.

subplot(2,1,1)
surfc(xx,yy,-f)  % Generation of Stalagmite function.
hold on
shading interp  % To bring visually smooth curve surface without grid line.
plot3(x_opt,y_opt,-f_opt,'Marker','o','MarkerSize',4,'MarkerFaceColor','r')
title('With Bounded inputs')
xlabel('X-axis')
ylabel('Y-axis')
subplot(2,1,2)
plot(-f_opt)     % plot of f_opt for every iterations
xlabel('Number of iterations ---->')
ylabel('Function Max ---->')

OUTPUT:

case2_time =

5.9384

The above graph is more clear and optimised compared to the case1, since here the bounds were defined and we could get only the values within our range. We are now more clear on the range within where our maxima lies.

for Case3:

in case3, the population size is putted in 'options' command so as to converge to the Global maxima.

%Case 3 of iteration.(Bounded inputs with increased polulation,300)
clear all
close all
clc

x=linspace(0,0.6,150);  % x value inputs
y=linspace(0,0.6,150);  % y value inputs
[xx,yy]=meshgrid(x,y);  % Creating a 2-D mesh
num_cases=50;           % GA runs for 50 iterations.

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

% options= optimoptions('ga') / increasing the ga iteration.
options=optimoptions('ga','PopulationSize',300);

tic                % Study time count start.
for i=1:num_cases
    [inputs,f_opt(i)]= ga(@stalagmite,2,[],[],[],[],[0,0],[0.6,0.6],[],[],options);  % GA function is used to run the stalagmite data and give the optimal solutions.
    x_opt(i)=inputs(1);
    y_opt(i)=inputs(2);
end

case3_time = toc   % Study time count end.

% GA gives us Minima value, Inverse f_opt is taken for Maxima value.

subplot(2,1,1)
surfc(xx,yy,-f)  % Generation of Stalagmite function.
hold on
shading interp  % To bring visually smooth curve surface without grid line.
plot3(x_opt,y_opt,-f_opt,'Marker','o','MarkerSize',4,'MarkerFaceColor','r')
title('Bounded inputs with increased population size as 300')
xlabel('X-axis')
ylabel('Y-axis')
subplot(2,1,2)
plot(-f_opt)     % plot of f_opt for every iterations
xlabel('Number of iterations ---->')
ylabel('Function Max ---->')

OUTPUT:

for case3- (iterations=50, population size=300)

case3_time =

15.7957

In this case we are gettin the optimised value of global maxima with accurate range, since added more population size, 300 thats run time is high compared to the previous two cases.

ERRORs:

No error found , carefully tackle with syntax and variables to avoid any mistakes!

CONCLUSIONs:

In this challenge, the concept of a Genetic Algorithm is used to optimize the stalagmite function to find the Global maxima. The concept and working of genetic algorithm are studied and used in the three cases to optimize the function and find the Global maxima.

REFERENCEs:

Genetic algorithm - Wikipedia

Find minimum of function using genetic algorithm - MATLAB ga - MathWorks India

Genetic Algorithm - MATLAB & Simulink - MathWorks India

Find minimum of function using genetic algorithm - MATLAB ga - MathWorks India

(PDF) Genetic Algorithms (researchgate.net)

Genetic Algorithms - Quick Guide (tutorialspoint.com)

Genetic Algorithm - MATLAB & Simulink (mathworks.com)