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

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 set 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 for research.

• Image Processing − GAs are 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.

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.

To write code to calculate Global Maxima using Genetic Algorithm, using MATLAB.

The stalagmite function is as follows:

The above function is defined in the stalagmite function in MATLAB as shown below.

function [f]= stalagmite(input_vector) %stalagmite function with input 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 he inverse of the Stalagmite function and is added in order to find the Maximum value, as GA algorithm always gives the Minimum value.
end

The format for writing genetic algorithm in MATLAB is as follows:

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

1st iteration:
In the first iteration, the behaviour of the algorithm is studied by not defining the limits. The GA doesnot run within a particular searchspace, since we have not defined bounds.

clear all
close all
clc
x=linspace(0,0.6,150); % X value inputs
y= linspace(0,0.6,150);  % Y value inputs
% Even though search space is defined GA Algorithm donot run within this searchspace
[xx,yy]= meshgrid(x,y);

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

num_cases=50; % GA runs for 50 iterations
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);
 opt_f(i)= -f_opt(i); %Ga gives us Minima value.Inverse f_opt is taken for Maxima value.

end
study1_time = toc   % Study Time count end 

subplot(2,1,1)
hold on
surfc(xx,yy,f) %Generation of stalagmite function.
shading interp  % To bring visually smooth curve surface without mesh lines
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')
subplot(2,1,2)
plot(opt_f) %plot of opt_f for every iterations
xlabel('Number of iterations ---->')
ylabel('Function Max -->')
​

2nd iteration:
Here the lower and upper bounds are defined so as to know the boundaries within which the global maxima lies. In other words we are defining a definite space within which the global maxima is to be found.

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);

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); %stalagmite function is called for every loop and output is stored in f
 end
end

num_cases=100; % GA runs for 100 iterations
tic         % Study Time start
for i=1:num_cases;
 % Objective function is stalagmite and the number of varaibles is 2
 % A,B,Aeq and Beq = [],as there is no Linear equalities and inequalities constraints in this function
 % lower boundary of varaibles x and y in ga alogorithmn is set as [0,0]
 % upper boundary of varaibles x and y in ga alogorithmn is set as [0.6,0.6]
 [inputs,f_opt(i)]= ga(@stalagmite,2,[],[],[],[],[0,0],[0.6,0.6]);
 x_opt(i)=inputs(1);
 y_opt(i)=inputs(2);
 opt_f(i)= -f_opt(i); %Ga gives us Minima value.Inverse f_opt is taken for Maxima value.
end
study2_time = toc  % Study time end
subplot(2,1,1)
hold on
surfc(xx,yy,f) %Generating the stalagmite function.
shading interp % To bring visually smooth curve surface without mesh lines
plot3(x_opt,y_opt,f_opt,'marker','o','markersize',4,'markerfacecolor','r')
title(' With Bounded inputs')
subplot(2,1,2)
plot(opt_f) %Plotting opt_f value for every iteration
xlabel('Number of iterations ---->')
ylabel('Function Max -->')

3rd iteration:
In this iteration, the population size is increased so as to converge to the Global maxima.

clear all
close all
clc
% x and y inputs
x=linspace(0,0.6,150);
y= linspace(0,0.6,150);
[xx,yy]= meshgrid(x,y);

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

num_cases=150; % GA runs for 150 iterations

options= optimoptions('ga');
options= optimoptions(options,'PopulationSize',450);
tic  % Study Time start
for i=1:num_cases
 % Objective function is stalagmite and the number of varaibles is 2
 % A,B,Aeq and Beq = [],as there is no Linear equalities and inequalities constraints in this function
 % lower boundary of varaibles x and y in ga alogorithmn is set as [0,0]
 % upper boundary of varaibles x and y in ga alogorithmn is set as [0.6,0.6]
 % population size is defined by using options in the algorithmn
 [inputs,f_opt(i)]= ga(@stalagmite,2,[],[],[],[],[0,0],[0.6,0.6],[],options);
 x_opt(i)=inputs(1);
 y_opt(i)=inputs(2);
 opt_f(i)= -f_opt(i); %Ga gives us Minima value.Inverse f_opt is taken for Maxima value.
end

Study3_time = toc   % Study Time end
subplot(2,1,1)
hold on
surfc(xx,yy,f) %Generating the stalagmite function.
shading interp % To bring visually smooth curve surface without mesh lines
plot3(x_opt,y_opt,f_opt,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded inputs with increased population size')
subplot(2,1,2)
plot(opt_f) %Plotting opt_f value for every iteration
xlabel('Number of iterations ---->')
ylabel('Function Max -->')

ERRORS while programming:

1)

This was my first error in GA code. The error was in the GA algorthm syntax, wherein I didnot type a '[]'.

2)

While defining the inputs mentioned different sizes of input vectors x and y. The error is basically due to the mesh grid command where in the two vectors cannot be combined due to their varying sizes.

Apart from this some typos errors.

RESULTS & CONCLUSION:

The following are the results obtained on running the GA.

1st iteration: (Iterations = 50)

In the above image it can be seen that since the inputs are boundless GA algorithm has mapped local maxima points outside our stalagmite function. Also we cannot infer a particular value of global maxima from the above graph, and it is hence pointless.

The study time is very less as the ga algorithm is made only to run for 50 iterations.

2nd Iteration:(iterations = 100)

The above graph is more clear and optimised compared to the 1st iteration 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 which our maxima lies.

3rd Iteration: (iterations = 150, population size = 450)

In this case we are getting the optimised value of global maxima with accurate range, since we increased the number of iterations and population size.

Since the number of iterations and population size is increased the study time is so high compared to the previous two iterations.

Thus it can be concluded that GA gives more accurate results in case of bounded inputs and by increasing the number of iterations and population size.

It can also be infered that even if we define a particular search space for GA, the GA doesnt run inside the search space. Only in cases of bounded inputs we can get interfereable results.

REFERENCES:

1. https://www.sciencedirect.com/topics/engineering/genetic-algorithm
2. https://towardsdatascience.com/introduction-to-genetic-algorithms-including-example-code-e396e98d8bf3
3. https://en.wikipedia.org/wiki/Genetic_algorithm
4. https://in.mathworks.com/help/gads/ga.html
5. https://in.mathworks.com/help/gads/genetic-algorithm.html
6. https://in.mathworks.com/help/gads/ga.html
7. https://www.researchgate.net/publication/226462334_Genetic_Algorithms
8. https://www.tutorialspoint.com/genetic_algorithms/genetic_algorithms_quick_guide.htm
9. https://in.mathworks.com/discovery/genetic-algorithm.html