Week 5 - Genetic Algorithm

A genetic algorithm (GA) is a method for solving both constrained and unconstrained optimization problems based on a natural selection process that mimics biological evolution. The algorithm repeatedly modifies a population of individual solutions. At each step, the genetic algorithm randomly selects individuals from the current population and uses them as parents to produce the children for the next generation. Over successive generations, the population "evolves" toward an optimal solution.

You can apply the genetic algorithm to solve problems that are not well suited for standard optimization algorithms, including problems in which the objective function is discontinuous, nondifferentiable, stochastic, or highly nonlinear.

The genetic algorithm differs from a classical, derivative-based, optimization algorithm in two main ways, as summarized in the following table.

Classical Algorithm	Genetic Algorithm
Generates a single point at each iteration. The sequence of points approaches an optimal solution.	Generates a population of points at each iteration. The best point in the population approaches an optimal solution.
Selects the next point in the sequence by a deterministic computation.	Selects the next population by computation which uses random number generators.

 

The genetic algorithm uses three main type of rules to create the next population from the present selected populations.

1. Selection rules selects individuals and called parents. That contributes to the populations for the next generation.
2. Crossover rules combines the two parents to form a child.
3. Mutation rules apply random changes to individual parents to form children.

The basic steps in creating a genetic algorithm is as follows.

1. The algorithm creates a random initial population at the beginning.
2. Then to creates the new population. Algorithm sets the scores to the individuals based upon their fitness values and converts them in to the more meaning full arrangements.
3. Based upon these data, algorithm selects the individuals called parents.
4. Then the algorithm produces the children from the parents. Children are produced either by the random changes of mutation in the parents. Or by the combining the vector entries in the parents called cross over.
5. In this way the algorithm replaces the current population be the new generation children.
6. The algorithm stops when it reaches one of the specified factors, such as time, fitness number, generation, function tolerance, constrained tolerances. Etc.

STALAGMITE FUNCTION:  Stalagmite function is a mathematical model which is used to find out the local minima and maxima. It is three-dimensional function. It has a lot of local minima or maxima, and one global maxima or minima. The name stalagmite is actually a type of rock formation generally in the lime caves. Which are formed due to the accumulation of material deposits on the floor from the ceiling drippings.

 

Syntax for defining GA(Genetic Algorithm).

The ‘ga’ syntax in matlab used to find the minimum function using genetic algorithm. There are several syntax of ‘ga’. We can change the syntax based upon the problem.

1 ‘ga’ Syntax.

X = ga(fun,nvars)

Where

X = Variables

.fun = Function file name.

.nvars = Numbers of variables.

2 ‘ga’ Syntax.

X = ga(fun,nvars,A,B,Aeq,Beq,lb,bu)

Where

A,B = Linear inequality constraints.

Aeq,Beq = Linear equality constraints.

Lb,ub = Lower & Upper bound.

If there are no linear inequality and equality constraints, then A,B,Aeq,Beq, are set to be ‘[ ]’.

3 ‘ga’ Syntax.

X = ga(fun,nvars,A,B,Aeq,Beq,lb,ub,nonlcon,IntCon,options)

Where

.nonlcon = Nonlinear constraints.

.IntCon = Integer Values.

Options = Optimization options.

If there are no Nonlinear constraints and Integer values, the nonlcon and Intcon are set to ‘[ ]’.

 

function [f] = stalgamite(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); % Negative sign is given to the final out put, because we need the

                   % inverted stalagmite plot which gives the function maxima.

 

end

 

 

 

Now we can start the ‘ga’ Main code.

clear all

close all

clc

 

x = linspace(0,0.6,150);

y = linspace(0,0.6,150);

n = 50;

[xx,yy] = meshgrid(x,y);

%f = stalgamite(x,y);

for i = 1:length(x);

    for j = 1:length(y);

  input_vector(1) = xx(i,j);

  input_vector(2) = yy(i,j);

  f(i,j) = stalgamite(input_vector);

    end

end

figure(12)

surfc(xx,yy,-f);

shading interp

[inputs, fval] = ga(@stalgamite, 2)

% Study 1 : Statistical Behaviour.

 

tic

for i = 1:n;

    [inputs,fopt(i)] = ga(@stalgamite, 2);

    xopt(i) = inputs(1);

    yopt(i) = inputs(2);

end

study1_time = toc

 

figure(1)

subplot(2,1,1)

hold on

surf(xx,yy,-f)

shading interp

xlabel('x- axis')

ylabel('y-axis')

title('Statistical Behaviour with Unbound inputs')

plot3(xopt,yopt,-fopt,'Marker','o','MarkerFaceColor','b','MarkerSize',5);

subplot(2,1,2)

plot(-fopt)

xlabel('No. of Iteration')

ylabel('Function Maximum')

 

% Study 2 - Statistical Behaviour with upper & lower bound

 

tic

for i = 1:n;

    [inputs, fopt(i)] = ga(@stalgamite,2,[],[],[],[],[0;0],[1;1]);

    xopt(i) = inputs(1);

    yopt(i) = inputs(2);

end

study2_time = toc

 

figure(2)

subplot(2,1,1)

hold on

surf(xx,yy,-f)

shading interp

xlabel('X-axis')

ylabel('Y-axis')

title('Statistical Behaviour with upper & lower bounds')

plot3(xopt,yopt,-fopt,'Marker','o','MarkerSize',5,'markerfacecolor','b')

subplot(2,1,2)

plot(-fopt)

xlabel('No. Of iteration')

ylabel('Function Maximum')

 

% Study 3 - Statistical Behaviour with Increasing Iteration Of GA

 

options = optimoptions('ga')

options = optimoptions(options,'PopulationSize',300);

 

tic

for i = 1:n

    [inputs, fopt(i)] = ga(@stalgamite,2,[],[],[],[],[0;0],[1;1],[],[],options);

    xopt(i) = inputs(1)

    yopt(i) = inputs(2)

end

 

study3_time = toc

 

figure(3)

subplot(2,1,1)

hold on

surf(xx,yy,-f)

shading interp

xlabel('X-axis')

ylabel('Y-axis')

title('Statistical Behaviour with increasing iterations')

plot3(xopt,yopt,-fopt,'Marker','o','MarkerSize',5,'markerfacecolor','b')

subplot(2,1,2)

plot(-fopt)

xlabel('No. Of iteration')

ylabel('Function Maximum')

 

Code Summery.

1. Code starts with the clear all, close all, and clc command.
2. Clear all command used to clear all the variables in the work space.
3. Close all command closes all the plots and figures are opened recently.
4. ‘clc’ Command used to clear the command window.
5. Then the ‘x’, ‘y’ array is defined using the linspace command to create the 1*150 array.
6. A 2D mesh of ‘x’, ‘y’ array is created using meshgrid command.
7. Numbers of iterations for the code to run is defined 50
8. To evaluate the stalagmite function ‘for’ loop is used where ‘i’ is initialized. And for every value of ‘i’ another ‘for’ loop is used to initialized, ‘j’.
9. As we get the input vector xx, yy of the stalagmite function. We can plot this data if needed.
10. We have to obtain the 3 result for the ‘ga’
11. In first study the maximum value of the function is found out with out no limitation, no bound.
12. This is done by the inbuilt function of ‘ga’ in matlab. X = ga(fun,nvars)
13. We have used ‘tic’ & ‘toc’ command to record the time to execute the ‘ga’ function for the n = 50 iteration.
14. After that we had plot the output, using the ‘surf’ command.
15. To neglect the grid line on the plot. We had used the inbuilt command ‘shading interp’.
16. Plot 3 command is used to plot coordinates in the 3D space.

plot3(xopt,yopt,-fopt,'Marker','o','MarkerSize',5,'markerfacecolor','b')

14. The result of the above case will be different for each time we run the program. To get the same value each time, we need to restrict the program within the specific bound (Upper bound and lower bound). The code is same as the study no 1. But the basic difference is that the ‘ga’ syntax. We had provided the upper bound and lower bound limits. ga(@stalgamite,2,[],[],[],[],[0;0],[1;1]);
15. After plotting the data of study no. 2. We did find that the results are not same every time the program terminates. A solution for this is that to increase the no. of cases or iterations.
16. In the study no. 3, we had increased the no. of iteration to 300. We had used the inbuilt syntax of

options = optimoptions('ga')

options = optimoptions(options,'PopulationSize',300);.

17. The syntax of ‘ga’ contains ‘option’ term and the rest of the code is as same as the study no 1,2.

 

 

Study no 1: Statistical Behaviour with unbound limits.

In the above plot, it can be observed how the random sampling of the genetic algorithm generates the new optimum values for the function every time the code run. Large no of blue dots shows values of co-ordinates of x, y. varies each time iteration runs.

 

Study no 2: Statistical Behaviour with Upper and lower bound.

In above results, the numbers of blue dots is less as compared to the previous one. This is the result of providing the upper and lower bound to the function.

 

Study no 3: Statistical Behaviour with increasing iterations.

In this study, the numbers of the iterations is increased to the 300 to converge and find out the global maxima of the function. Here we can see only one blue dot on the stalagmite function and that is the required global maxima point.

 

There are no major errors, i get while coading. Some errors i got, Which discription is given below; 

01. one error came while coading. It was that, i had used the plot command in place of 'plot 3' command. 

02. Second error is that, while programing the function command. I had used sind and cosd in place of sin or cos. That's why i am getting a plane plot. Not a stalagmite plot. 

https://in.mathworks.com/discovery/genetic-algorithm.html

https://in.mathworks.com/help/gads/how-the-genetic-algorithm-works.html

https://in.mathworks.com/help/gads/some-genetic-algorithm-terminology.html