Genetic Algorithm

AIM: To optimise the stalagmite function and find the global maxima of the function using MATLAB.

THEORY:

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. The sequence of points approaches an optimal solution.

The following outline summarizes how the genetic algorithm works:

1. The algorithm begins by creating a random initial population.
2. The algorithm then creates a sequence of new populations. At each step, the algorithm uses the individuals in the current generation to create the next population. To create the new population, the algorithm performs the following steps:
   1. Scores each member of the current population by computing its fitness value. These values are called the raw fitness scores.
   2. Scales the raw fitness scores to convert them into a more usable range of values. These scaled values are called expectation values.
   3. Selects members, called parents, based on their expectation.
   4. Some of the individuals in the current population that have lower fitness are chosen as elite. These elite individuals are passed to the next population.
   5. Produces children from the parents. Children are produced either by making random changes to a single parent—mutation—or by combining the vector entries of a pair of parents—crossover.
   6. Replaces the current population with the children to form the next generation.
3. The algorithm stops when one of the stopping criteria is met.

SYNTAX FOR GA

x = ga(fun, nvars) finds a local unconstrained minimum, x, to the objective function, fun. ‘nvars’ is the dimension (number of design variables) of fun.

x = ga(fun, nvars,A,b) finds a local minimum x to fun, subject to the linear inequalities A*x ≤ b. ga evaluates the matrix product A*x as if x is transposed (A*x').

x = ga(fun,nvars,A,b,Aeq,beq,lb,ub) defines a set of lower and upper bounds on the design variables, x, so that a solution is found in the range lb ≤ x ≤ ub. (Set Aeq=[] and beq=[] if no linear equalities exist.)

x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,options) minimizes with the default optimization parameters replaced by values in options. (Set nonlcon=[] if no nonlinear constraints exist.) Create options using optimoptions.

Stopping Conditions for the Algorithm

The genetic algorithm uses the following conditions to determine when to stop:

• Generations — The algorithm stops when the number of generations reaches the value of Generations.
• Time limit — The algorithm stops after running for an amount of time in seconds equal to Time limit.
• Fitness limit — The algorithm stops when the value of the fitness function for the best point in the current population is less than or equal to Fitness limit.
• Stall generations — The algorithm stops when the average relative change in the fitness function value over Stall generations is less than Function tolerance.
• Stall time limit — The algorithm stops if there is no improvement in the objective function during an interval of time in seconds equal to Stall time limit.
• Stall test — The stall condition is either average change or geometric weighted. For geometric weighted, the weighting function is 1/2ⁿ, where n is the number of generations prior to the current. Both stall conditions apply to the relative change in the fitness function over Stall generations.
• Function tolerance — The algorithm runs until the average relative change in the fitness function value over Stall generations is less than Function tolerance.
• Constraint tolerance — The Constraint tolerance is not used as stopping criterion. It is used to determine the feasibility with respect to nonlinear constraints. Also, max(sqrt(eps), Constraint Tolerance) determines feasibility with respect to linear constraints.

The algorithm stops as soon as any one of these conditions is met. You can specify the values of these criteria in the Stopping criteria pane in the Optimization app. The default values are shown in the pane.

GOVERNING EQUATION:

`f(x,y)=f_x.g_x.f_y.g_y`

`f_(x )= [sin⁡(5.1πx+ 0.5) ]^6`

`f_(y )= [sin⁡(5.1πy+ 0.5) ]^6`

`g_x=exp[-4 ln⁡(2) (x-0.0667)^2/(0.64)]`

`g_y=exp[-4 ln⁡(2) (y-0.0667)^2/(0.64)]`

OBJECTIVE:

1. To optimize the stalagmite function.
2. To determine the global maxima of the function.

FUNCTION PROGRAM:

function [ fxy ] = stalagmite_func(input_vector)

x = input_vector(1);
y = input_vector(2);

fx = (sin(5.1 .* pi.* x + 0.5))^6;
fy = (sin(5.1 .* pi.* y + 0.5))^6;
gx = exp((-4).*log(2).* (((x - 0.0667)^2)/0.64));
gy = exp((-4).*log(2).* (((y - 0.0667)^2)/0.64));
fxy = -(fx.* gx.* fy.* gy); 

end

MAIN PROGRAM:

% Program to optimise the stalagmite function and find the global maxima of the function

clear all
close all
clc

% Defining our search space
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);

% Iteration count
num_cases = 50;

% Creating a 2Dimensional mesh
[xx, yy] = meshgrid(x,y);

% Study 1 Evaluating the stalagmite function

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_func(input_vector);
end
end

for i = 1:num_cases
[inputs ,fval(i)] = ga(@stalagmite_func, 2);
opt_x(i) = inputs(1);
opt_y(i) = inputs(2);
end

figure(1)
subplot(2,1,1)
surfc(xx,yy,-f)
xlabel('x value')
ylabel('y value')
hold on

%Removing gridlines on the 3D surface plot
shading interp

% Plotting
plot3(opt_x ,opt_y , -fval ,'marker','*','markersize',3)
title('Unbounded Inputs')
subplot(2,1,2)
plot(-fval)
xlabel('No of Iterations')
ylabel('Function max')


% Study 2 statistical behaviour of GA with upper and lower bounds
% Bounded inputs
for i = 1:num_cases
[inputs ,fval(i)] = ga(@stalagmite_func, 2,[],[],[],[],[0;0],[1;1]);
opt_x(i) = inputs(1);
opt_y(i) = inputs(2);
end
figure(2)
subplot(2,1,1)
surfc(xx,yy,-f)
xlabel('x value')
ylabel('y value')
hold on

%Removing gridlines on the 3D surface plot
shading interp

% Plotting
plot3(opt_x ,opt_y , -fval ,'marker','*','markersize',3)
title('Bounded Inputs')
subplot(2,1,2)
plot(-fval)
xlabel('No of Iterations')
ylabel('Function max')

% Study 3 statistical behaviour of GA by increasing the no. of iterations
options = optimoptions('ga')
options = optimoptions(options,'populationsize', 600);
for i = 1:num_cases
[inputs ,fval(i)] = ga(@stalagmite_func, 2,[],[],[],[],[0;0],[1;1],[],[],options);
opt_x(i) = inputs(1);
opt_y(i) = inputs(2);
end
figure(3)
subplot(2,1,1)
surfc(xx,yy,-f)
xlabel('x value')
ylabel('y value')
hold on
%Removing gridlines on the 3D surface plot
shading interp

% Plotting
plot3(opt_x ,opt_y , -fval ,'marker','*','markersize',3)
title('Bounded Inputs')
subplot(2,1,2)
plot(-fval)
xlabel('No of Iterations')
ylabel('Function max')

OUTPUT 1: Study 3

OUTPUT 2: Study 2

OUTPUT 3: Study 3

EXPALNATION OF THE CODE:

Initially, the stalagmite function was mentioned with appropriate governing equation.

Then, the main program is subdivided into three studies.

The first study concern with the unbounded inputs, by expanding the boundary the results can be obtained.

The second study concern with the bounded inputs provided for calculating the value of Global maxima. And in this study previously occurred problems are solved for a better output.

The third study concerns with the bounded inputs provided but with a varied population size for better optimization in order to calculate the value of Global maxima and thus it provides the exact solution.

And, at last plots for all the studies has been displayed, which provide a clear insight of results.

CONCLUSION:

The global maxima is calculated by population sizing and the plots are provided as a visual context and verifies the output.

REFERENCES:

https://www.google.com/search?ei=Z64BX6vsGuDE4-EPhYiZ6Ak&q=

http://www.mathworks.com/help/gads/examples/constrained-minimization-using-the-genetic-algorithm.html

https://www.mathworks.com/help/gads/what-is-the-genetic-algorithm.html