Week 4.1 - Genetic Algorithm

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 as shown in the following figure.

Optimization refers to finding the values of inouts in such a way that we get the "best" outpit values.The definition of "best" varies from problem to problem,byt in mathematical terms it refers to maximizing one or more objective functions,by varying the input parameters.

The set odf 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 solutions.The aim of optimization is to find that point or set of points in the search space.

THE GENETIC ALGORITHM:

Nature has always been a great surce of inspiration to all the mankind.Genetic algorithm(GA's) are search based algorithm based on the concepts of natural selection and genetics.GA's are a subset of a much larger branch of computatio known as Evolutionary Computation.

GA's were developed by John Hollard and his students and collegues at the University of Michigan,most notably David.EGoldberg and hassince been tired on various optimization problems with a high degree of success.

In GA's,we have a pool or a population of possible solutions to the given problem.These solutions then ungergo recombination and mutation,producing new children,and the process is repeated over various generations.Each individual is assigned a fitness value and the fitter individuals are given a higher chance to mate and yield more "fitter" individuals.This is in line with the Drawinian 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 Algorithm are sufficiently randomized in nature,but they perform much better than random local search as they exploit historical information as well.

Basic Structure:

Advantages of GA's:

GA's have various advantages which have made them immensely popualar.Thes include-

• Does not require any derivative information .
• Is faster and more efficient as compared to the traditional methods.
• Has very good parelle capabilites.
• Optimizes both continuous and discrete functions and also milti-objective problem.
• Provides a list of "good" solutions and noy 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 larege number of parameters involved.

Limitations of GA's:

Like any technique GA's also suffer from a few limitations.These include-

• GA's are not suited for all problems,especially problems which are simple and for which derivative information is avaliable.
• Fitness value is calculated repeatedly which might be computationally expensive for sme 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.

APLICATIONS OF GA's:

Genetic Algorithm are prmarily used in optimization problems of various kinds,but they are frequently use in other application areas as well.In this section,we list some of the areas in which Genetic Algorithm are frequently used.These are-

• Optimization-Gnetic Algorithm 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-GA's are also uses to characterize various economic model like cobweb model,game theory equilibrium resolution,asset pricing,etc.
• Neural Networks-GA's are also used to train neural networks,particularly recurrent neural networks.
• Parallelizations-GA's also have very good parallel capabilites,and prove to be very effective means in solving certain problems,and also provide a good area for research.
• Image Processing-GA's are used for various digital image processing tasks as well like dense pixel matching.
• Travelling Salesmen Problem and its application-GA's have been used to solve the TSP,whih is a well-known combinatorial problem using novel crossover and packing strategies.

AIM:

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

PROCEDURE:

1. The satalgmite function is defined seperately.This function is later called into the main GA program.
2. Now we define the x and y inputs using linspace command.
3. Then the input vectors are transformed into array[xx,yy] so that it can be used to evaluate functions of wo variables and plot three-dimensional mesh/surface plots.
4. 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 value x and y.
5. 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 'ga' command,which is an in-built command in MATLAB.
6. Then the total number of time the ga needs to run in defined using num_case and with help of for loop ga is made to run for each iteration and the value is stored in an array.
7. GA generally gives the minima value but we need the maxima hence we can just inverse the stalagmite function by introducing a negative sign.
8. The total study time is calculated using the 'tic' and 'toc' command at the start and end of the ga for loop respectively.
9. The results are then plotted using the surfc command and plot command.
10. GA is made to run for 3 iterations with each iteration having bounded inputs,unbounded inputs and increasing population size.

The stalagmite function is as follows:

The above function is definrd in the stalagmite function in MATLAB as shown below:

function[f]=stalagmite(input_vector)%stalagmite function with input as input_vector which contains 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
3. nvars indicates the no of variables used.
4. Aand B are used to indicate any kind inequalites that exists in the function.
5. Aeq and Beq also denotes the in equalities.
6. lb=lower bound.
7. ub=upper bound.
8. nonlcon gives a two vectors representing in equalities 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 1st iteration, the behavior of the algorithm is studied by not defining the limits.The GA does not run within a particular searchspace,since we hhave 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 do not run within this search space 
[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_case=50;% GA runs for 50 iterations
tic %Study Time count start
for i=1:num_case
    [inputs,f1_opt(i)]=ga(@stalagmite,2);% GA function is used to run the stalagmite data and give optimal solutions
    x1_opt(i)=inputs(1);
    y1_opt(i)=inputs(2);
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(x1_opt,y1_opt,f1_opt,'marker','o','markersize',5,'markerfacecolor','r') %plotting the optimum values with a red dot marker along the stalagmite 3D curves.
title('Unbounded inputs')
subplot(2,1,2)
plot(f1_opt) %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
%Even though search space is defined GA Algorithm do not run within this search space 
[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_case=100;% GA runs for 50 iterations
tic %Study Time count start
for i=1:num_case
    [inputs,f2_opt(i)]=ga(@stalagmite,2,[],[],[],[],[0,0],[0.6,0.6]);% GA function is used to run the stalagmite data and give optimal solutions
    x2_opt(i)=inputs(1);
    y2_opt(i)=inputs(2);
end

study2_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(x2_opt,y2_opt,f2_opt,'marker','o','markersize',4,'markerfacecolor','r') %plotting the optimum values with a red dot marker along the stalagmite 3D curves.
title('with bounded inputs')
subplot(2,1,2)
plot(f2_opt) %plot of opt_f for every iterations 
xlabel('Number of iterations ---->')
ylabel('Function Max --->')

3rd iteration:

In this iteration,the population size increased so as to converge to the global maxima.

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 do not run within this search space 
[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_case=150;% GA runs for 50 iterations
options=optimoptions('ga');
options=optimoptions(options,'PopulationSize',450);
tic %Study Time count start
for i=1:num_case
    [inputs,f3_opt(i)]=ga(@stalagmite,2,[],[],[],[],[0,0],[0.6,0.6],[],options);% GA function is used to run the stalagmite data and give optimal solutions
    x3_opt(i)=inputs(1);
    y3_opt(i)=inputs(2);
end

study3_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(x3_opt,y3_opt,f3_opt,'marker','o','markersize',4,'markerfacecolor','r') %plotting the optimum values with a red dot marker along the stalagmite 3D curves.
title(' bounded inputs with increased population size')
subplot(2,1,2)
plot(f3_opt) %plot of opt_f for every iterations 
xlabel('Number of iterations ---->')
ylabel('Function Max --->')

Results and Conclusion:

The following are the results obtained on running the GA.

1st iteration : (Iteration=50)

study1_time =3.5014

2nd iteration : (Iteration=100)

study2_time =9.0156

3rd iteration : (Iteration=150)

study3_time =77.2316

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

It can also be infered that even is we define a particular search space for GA, the Ga does not run inside the search space.Only in cases of bounded inputs we can interferable results.