Week 4 - Genetic Algorithm

GENETIC ALGORITHM

A genetic algorithm makes uses of techniques inspired by evolutionary biology such as selection, mutation, inheritance and recombination to solve a problem. The most commonly employed method in genetic algorithms is to create a group of individuals randomly from a given population. The individuals thus formed are evaluated with the help of the evaluation function provided by the programmer. Individuals are then provided with a score which indirectly highlights the fitness to the given situation. The best two individuals are then used to create one or more offspring, after which random mutations are done on the offspring. Depending on the needs of the application, the procedure continues until an acceptable solution is derived or until a certain number of generations have passed.

The following diagram depicts the steps performed by a Genetic Algorithm

• Initialize Population
• Terminate? Yes; then Step 3) No; then Step 4)
• Results
• Selection
• Crossover
• Mutation; then Step 1)

Basic Terminology:

1. Population: Subset of all the possible solutions.
2. Chromosome: One of the candidate solutions.
3. Gene: One element or property of a Chromosome.
4. Allele: Value of the gene for a particular Chromosome.

Population can be represented in two types:

1. Phenptype: Population in the computation space.
2. Genotype: Population in the real world.

Fitness Function:

It is the function that takes a candidate solution and analyzises it for its output.

Genetic Operators:

These are used to alter the composition of candidate solutions to get better solutions.

1. Selection:

Used to select good candidates. As per GA documentation in MATLAB, initial population is randomly selected using a random number generator.

2. Crossover:

Combines two good candidates to form better solutions.Two candidates are chosen randomly. A point is chosen randomly between the elements of the Chromosome, and then Crossover is done.

* Not all candidate solutions from the Initial Population are chosen.

* Randomly chosen with a Crossover probability, Pc.

* N*Pc are selected for Crossover

* Remaining are not selected.

Types of Crossover methods:

1. One-Point Crossover
2. Multi-Point Crossover
3. Uniform Crossover
4. Davis Order Crossover

3. Mutation:

It is used to alter the properties of a Chromosome. The probability for the selection of the candidates must be low Mutation is very important for the convergence of GA.

Types of Mutation methods:

1. Bit Flip Mutation
2. Swap Mutation
3. Inversion Mutation

Basic Structure of Genetic Algorithm:

1. Start with the Initial Population.
2. Select parent candidate solutions for mating.
3. Crossover, Mutation is applied to generate new candidate solutions.
4. Fitness of the new candidate solutions is determined.
5. Better candidate solutions replace the existing solutions.
6. The process repeats until the optimum solution is found.

Now Starting the program I have first created a function called get_stalagmite bypassing the input array as the argument for the variables x and y.

%Stalagmite Function for GA
function [V] = get_stalagmite(input)% Calling get_stalagmite fn by passing input array
x = input(1);
y = input(2);

      
          term1 = (sin(((5.1*pi).*x)+0.5)).^6;
          term2 = exp((((x-0.667).^2).*(-4*log(2)))./0.64);
          term3 = (sin(((5.1*pi).*y)+0.5)).^6;
          term4 = exp((((y-0.667).^2).*(-4*log(2)))./0.64);
          [V] = -((term1)*(term3)*(term2)*(term4));
           
       
end

% Maximization of Stalagmite Fn using Genetic Algorithm
clear all
close all
clc

% Defining our Search Space
x = linspace(0,0.6,150); % Store 150 values of x from 0-0.6 using linspace.
y = linspace(0,0.6,150); % Store 150 values of y from 0-0.6 using linspace.
n_cases=50; % n_cases is the number of iteration for GA.
[xx yy]=meshgrid(x,y); % Create 2D Array using Meshgrid.

%Evaluating the Stalagmite Function
for i = 1:length(xx)
    for j = 1:length(yy)
        input(1) = xx(i,j);
        input(2) = yy(i,j); % For Each value of x & y creating Row Vector
        f(i,j) = get_stalagmite(input); % This generates the data for plot.
    end
end

%Case 1: Statistical behaviour of Genetic Algorithm
tic
for k = 1:n_cases
    [Inputs, Fopt(k)] = ga(@get_stalagmite,2);
     xopt(k) = Inputs(1); %saving value of x for every iteration  in array xopt.
     yopt(k) = Inputs(2); %saving value of y for every iteration  in array yopt.
end
 
%For maximizing converting the values of the stalagmite function stored in the array Fopt to their negative values
Fopt = -Fopt;
f = -f;
Time_Study1 = toc % For study of Statistical behaviour timer is used.

%Plotting
figure(1) %Figure1 is generated.
subplot(2,1,1) % Creating 2x1 subplot.
hold on
surfc(x,y,f) % Creates a surface plot of the stalagmite fn stored in f.
shading interp
plot3(xopt,yopt,Fopt,'color','b','marker','o','markersize',5,'markerfacecolor','r');% 3D Plot is created.
title('Unbounded Inputs');
subplot(2,1,2)
plot(Fopt,'color','b','linewidth',1)
xlabel('Iterations');
ylabel('Function Maximum');

%Case2: Statistical behaviour of Genetic Algorithm with Upper and Lower Bounds
 
tic
for k = 1:n_cases    
 [Inputs2, Fopt2(k)] = ga(@get_stalagmite,2,[],[],[],[],[0;0],[1;1]);
     xopt2(k) = Inputs2(1);
     yopt2(k) = Inputs2(2);
end
 
Fopt2 = -Fopt2;
Time_Study2 = toc
figure(2)
subplot(2,1,1)
hold on
surfc(x,y,f)
shading interp
plot3(xopt2,yopt2,Fopt2,'color','b','marker','o','markersize',5,'markerfacecolor','r');
title('Unbounded Inputs');
subplot(2,1,2)
plot(Fopt2,'color','b','linewidth',1)
xlabel('Iterations');
ylabel('Function Maximum');

%Case3: Statistical behaviour of GA by increasing the number of iterations.
 
options = optimoptions('ga');
options = optimoptions(options, 'PopulationSize',200);
tic
for k = 1:n_cases
 [Inputs3, Fopt3(k)] = ga(@get_stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
     xopt3(k) = Inputs3(1);
     yopt3(k) = Inputs3(2);
end
 
Fopt3 = -Fopt3;
Time_Study3 = toc
figure(3)
subplot(2,1,1)
hold on
surfc(x,y,f)
shading interp
plot3(xopt3,yopt3,Fopt3,'color','b','marker','o','markersize',5,'markerfacecolor','r');
title('Unbounded Inputs');
subplot(2,1,2)
plot(Fopt3,'color','b','linewidth',1)
xlabel('Iterations');
ylabel('Function Maximum');
rng('default'); %Set the random numberngenerator to its default state.

Now The main Program starts with clear all, close all and clc. Assigning x and y single array which stores 150 values of x and y from 0-0.6 using linspace command.n_cases =50 it is the number iterations GA will perform. Created a 2D array using meshgrid command. Now evaluating the stalagmite function by calling the get_stalagmite function using nested for loops. Now the data is generated for the plot. Initially, to check whether the function is executing properly i run the code and I got the plot as shown below. However it was wrong after analysing the function I came to know that I have missed to put parenthesis.

Initial Fn Output

Now in this program, we have used 3 cases to better understand the behaviour of GA.

Case 1: we have simply evaluated the GA using ga syntax for 50 iterations. Now we know always minimise the function. If we want to maximise the function we have use -ve sign.

The output of the 1st case is as shown below.

Case 1 Output

Case 2 : In this case we have put the upper and lower bounds for GA.

syntax for ga is as follows

Syntax for GA: [x, fval] = ga(func,nvars,A,b,Aeq,Beq,lb,ub,nonlcon,Intcon,options)

Description of GA Syntax

• 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 or gaoptimset.
• x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon) subjects the minimization to the constraints defined in nonlcon. The function nonlcon accepts x and returns vectors representing the nonlinear inequalities and equalities respectively.

x = optimum solution

f=ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon,options)

fun - fitness function.

nvars- number of variables,

A,b= Linear inequality constraints

Aeq,beq=Linear equality constraints

lb- Lower bound(limit),

ub- Upper bound(limit),

nonlcon : Use for nonlinear constraints

IntCon : to get solution in integer.

options- To set population size minimize with non-default options

The out put of second case is as follows

Case 3: In this case, we have increased the number of iterations to 200.

The output of the third case is as follows

Case 3 Output

In the last line of the program we have used the rng function to set the random number generator to its default state.