Genetic Algorithm

Genetic Algorithm

1. AIM : To understand the cocept of Genetic Algorithm.

2. OBJECTIVE :

• Code the stalagmite function in MATLAB.
• Optimize stalagmite function and find the global maxima of the function.
• Study 3 cases of options of Genetic Algorithm ‘ga’ in MATLAB.

3. THEORY :

3.1 Genetic Algorithm : Genetic algorithms are randomized search algorithms that have been developed in an effort to imitate the mechanics of natural selection and natural genetics. Genetic algorithms operate on string structures, like biological structures, which are evolving in time according to the rule of survival of the fittest by using a randomized yet structured information exchange. Thus, in every generation, a new set of strings is created, using parts of the fittest members of the old set. The main characteristics of a genetic algorithm are as follows:

1. The genetic algorithm works with a coding of the parameter set, not the parameters themselves.
2. The genetic algorithm initiates its search from a population of points, not a single point.
3. The genetic algorithm uses payoff information, not derivatives.
4. The genetic algorithm uses probabilistic transition rules, not deterministic ones.

3.1.1 What are henetic algorithms used for?

Genetic algorithms are commonly used to generate high-quality solutions to optimization and search problems by relying on biologically inspired operators such as mutation, crossover and selection.

3.1.2 How does the Genetic Algorithm Work?

In Genetic algorithm (GA), 'n' values form the function/problem are randomly selected (n is the population size). The values are selected after being sorted from the best to the worst ones first ('best' condition is subjected to the need). The GA selects the best and rejects the other values. Now, each selected value is mutated (n-1) times, i.e., some randomness is added to the values. Then, the mutated values are again checked against the minimum criteria condition. This iteration is continued up to the number of iterations decided.

1. Fitness function : It is the function that GA is trying to optimize.
2. Population of chromosome : It is the numerical values that represent all the solutions to the function. The selection operator chooses some of the chromosomes (with replacement) for reproduction based on probability distribution. fitter the chromosome more likely it is to be selected.
3. Cross over : This operator swaps in random a subsequence of two of the chosen chromosomes to create two offspring. Usually each chromosome is converted into binary code and then cross over is done from one parent chromosome into another.
4. Mutation : Mutation operator randomly flips individual bits in the new chromosomes.

GA flow chart –

3.2 Stalagmite function : It is a mathematical model that actually helps us to generate local minimas and local maximas.

The stalagmite function is a function with 4 components:

• sine components in each of the axis direction
• normal Gaussian distribution in each of the axis direction .

The stalagmite function is given theoretically as:

4. BODY OF CONTENT :

Stalagmite function code:

% for calling a stalagmite function
function[f] = stalagmite_function(input_vector)
x1 = input_vector(1);
y1 = input_vector(2);

f1_x = (sin((5.1*pi*x1)+0.5))^6;      % term 1
f1_y = (sin((5.1*pi*y1)+0.5))^6;      % term 2

f2_x = exp((-4*log(2)*(x1-0.0667).^2)/0.64);       % term 3
f2_y = exp((-4*log(2)*(y1-0.0667).^2)/0.64);       % term 4

f = -(f1_x*f1_y*f2_x*f2_y);     %-ve sign for finding global maximum

end

Code for finding the Global Maxima of the Stalagmite function:

% Program to find the global maxima using genetic algorithm
clear all
close all
clc

% Defining our search space
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
num_cases = 50;      %number of iterations to run ga (i.e. 50)
%to create 2-Dimensional mesh
[xx,yy] = meshgrid(x,y);

% for loop for evaluating or calling 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_function(input_vector);
    end
end

% Iterations of genetic algorithm
tic
% Study 1 - statistical behaviour
for i = 1:num_cases
    [inputs, fopt(i)] = ga(@stalagmite_function,2);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2);
end
toc

%plotting results
figure(1)
subplot(2,1,1)
hold on
surfc(x,y,-f)
hold on
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('Genetic Algorithm Unbounded Inputs')
subplot(2,1,2)
plot(-fopt)
xlabel('Iterations')
ylabel('Function Maximum')


tic
%Study 2 - statistical behaviour - with upper and lower bounds
for i = 1:num_cases
    [inputs,fopt(i)] = ga(@stalagmite_function,2,[],[],[],[],[0;0],[1;1]);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2);
end
study2_time = toc;

%plotting
figure(2)
subplot(2,1,1)
hold on
surfc(x,y,-f)
hold on
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded inputs')
subplot(2,1,2)
plot(-fopt)
xlabel('Iterations')
ylabel('Function maximum')


%study 3 - increasing GA iterations
options = optimoptions('ga');
options = optimoptions(options,'populationsize',280);

tic
for i = 1:num_cases
[inputs,fopt(i)] = ga(@stalagmite_function,2,[],[],[],[],[0;0],[1;1],[],[],options);
xopt(i) = inputs(1);
yopt(1) = inputs(2);
end
study_time3 = toc;
%plotting
figure(3)
subplot(2,1,1)
hold on
surfc(x,y,-f)
hold on
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded inputs with modified population size')
subplot(2,1,2)
plot(-fopt)
xlabel('Iterations')
ylabel('Function maximum')

STEPS :

1. Firstly we used linspace command to create 150 values from 0 to 0.6.
2. We used meshgrid command to evaluate the function of two variables and three dimensional plots.
3. We used the stalagmite function for different iterations.
4. We used the ga function to define the stalagmite function for various iterations.
5. We measured the time for each of 50 iterations and the optimum value is obtained.

5. OUTPUTS :

6. CONCLUSION :

In this report, we studied the genetic algorithm, how it has been constructed from the theory of evolution considering all the factors of reproduction at each stage that can lead to better production of the off-springs in our case the data and hence give better results. The genetic algorithm for a particular case study has been applied several times as each time we would get a new result as the algorithm selects the initial population at random. These small and tiny changes can lead to drastic variations in the computation of the minimum. In some cases, it may give local minima and in some, it may give global. For problems with less number of independent variables, it is not much of a problem as they can be verified in the manual calculations and the visualizations. However, for an engineering level optimization problem with several independent variables, it is a must to select the conditions of the genetic algorithm properly to give accurate convergence results.