Week 4.1 - Genetic Algorithm

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

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.

Classical Algorithm;

• Generates a single point at each iteration.
• The sequence of points approaches an optimal solution
• Selects the next point in the sequence by a deterministic computation.

Genetic Algorithm;

Generates a population of points at each iteration.

The best point in the population approaches an optimal solution.

Selects the next population by computation which uses random number generators

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

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

AIM;

To write code to calculate global maxima using genetic algorithm,using MATLAB.

Procedure:

• The stalagmite function is definedd separately. This function is later called into the main GA program.
• Then the input vector are transformed into array[xx,yy],so that it can be used to evaluate functions of two variables and plot three dimensional mesh/surface plots.
• Now the values in the different matrixes created can be put as an input into the function that we have created,by calling it.by this we can get the value of the stalagmite function at various values of x and y.
• Now since we have got the value of the function at various values,we now need to calculate the maxima value,which can be calculated using the gacommand ,which is an in-built function in MATLAB.
• Then, the total number of time the ga need to run is defined using num_cases,and with help of FOR LOOP ga is made to run for each iteration and the value is stored in an array.
• GA generally gives the minima value,but we need the maxima hence we can just inverse the stalagmite function by introducinga 'Negative Sign'
• The total study time is calculated using the 'tic' and 'toc' command at the start and end of the ga for loop respectively.
• The result are then plotted using the surfc command and plot command.
• GA is made to run for 3 iteration,with each iteration having bounded inputs, unbounded inputs and increasing population size.

The stalagmite function is as follow;

f(x,y) = f1x*f1y*f2x*f2y

f1x = (sin(5.1pix + 0.5))^6

f1y = (sin(5.1piy + 0.5))^6

f2x = exp{-4ln(2)*((x-0.667)^2/0.64)}

f2y = exp{-4ln(2)*((y-0.667)^2/0.64)}

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

STALAGMITE FUNCTION PROGRAM;

function [f] = stalagmite(input_vector)
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);
end

1st ITERATION;

In the first iteration,the behaviour of the algorithm is studied by not defining the limits. The GA doesn't run within a particular searchspace,since we have not defined bounds.

close all
clc

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 = 50

tic

%study time count start
for i = 1 : num_cases;
    [inputs , f_opt(i) ] = ga(@stalagmite,2);
    x_opt(i) = inputs(1);
    y_opt(i) = inputs(2);
    opt_f(i) = -f_opt(i);
end

study1_time = toc

subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp
plot3 (x_opt,y_Opt,opt_f,'marker','o','markersize',5,'markerfacecolor','r')
title('unbounded inputs')
subplot(2,1,2)
plot(opt_f)
xlabel('number of iteration')
ylabel('functions')

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 global maxima is to be found.

close all
clc

x=linspace(0,0.6,150);
y= linspace(00.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=100;

tic

for i=1: num_cases
    [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);
end

subplot(2,1,1)
hold on

surfc(xx,yy, f);
opt_f(i)= -f_opt(i);

study2_time = toc

shading interp
plot3(x_opt,y_opt, f_opt, 'marker', 'o', 'markersize',4,'markerfacecolor','r')
title('With Bounded inputs');
subplot (2,1,2)
plot (opt_f)
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.

close all
clc

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
options=optimoptions('ga')
options=optimoptions(options,'PopulationSize',450)

tic
%study time start

for i=1:num_cases
    [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)
end

study3_time = toc
subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp
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)
xlabel('number of iteration')
ylabel('functions')

ERRORS WHILE PROGRAMING;

1,

This was the first errror i faced here, this error occured because of i not type '[ ]'

2,

Also i face this one its form while defining the input mentioned different sizes of input vectors x and y. its occur because of meshgrid command where in two vector can't combined due to their varying sizes.

RESULTS & CONCLUSIONS;

The following are the results obtained on running the GA.

In first iteration;

study time for iteration 1 = 2.40

• In above image it can be seen that since the inputs are boundless GA algorithm has mapped local maxima poiints outside our stalagmite function.
• The study time is very less as the ga algorithm is made only torun for 50 iterations

IN SECOND ITERATION;

STUDY TIME ITERATION 2 = 6.09

• 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.
• The study time ifor ga algorithm is made to run for 100 iteration.

IN THIRD ITERATION;

STUDY TIME FOR 3 = 52.36

• In this case we are getting the optimised value of global maxima with accurate range,since we incresed the number of iteration and population size.
• since the number of iteration and population size is increased the study time is so high compared to the previous two iteration
• The study time for ga algorith is made to run for 150 iteration.

Conclude;

• Thus it can be concluded that Ga gives more accurate result in case of bounded inputs and by increasing the number of iteration 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 case of bounded inputs we can get interfereable results.