Week 4 - Genetic Algorithm

Aim : Optimization of the Stalagmite function by using Genetic Algorithm and find the Global Maxima of the Function.

Understaning Genetic Algorithm:

1.Search Algorithm based on the Mechanics of Natural Selection & Natural Genetics. Priorities of Optimiztion to be relooked. Most Important goal for optimiztion is improvement Attainment of optimum is less important for complex systems and to get as close as an ideal solution as possible.

2.Genetic Algorithm is with Larger field called "Evolutionary computing".

3.Does not require any Derivative Information provides a list of 'Good 'Solutions not just as single solution.

4.Survival Fittest Individuals exhibits variation in appearance and behavior.

5. Those with Traits mostly fitting to the environment survive to reproduce.

6. Some of those traits are passed down from generation including mutuations to offer more variations in the future.

7. We can mirror that exact cycle in developing our search Alogorithm.

8. Mainly 5 phases in the cycle, i. Population,ii. Evaluation, iii. Selection, iv. Crossover, v. Mutuation

9. Fittness of Function is particular type of objective function used to summerize as single figure merit ,how close to given design solution is achieving the set aims.

Phases:

Selection :

It is the stage of a GA in which individual genomes are chosen from a population for later breeding .

A generic selection procedure may be implemented as follows:

The fitness of function is evaluated for each individual, providing fitness values, which are then normalized. Normalization means dividing the fitness value of each individual by the sum of all fitness values, so

that the sum of all resulting fitness values equals

Accumulated normalized fitness values are computed: the accumulated fitness value of an individual is the sum of its own fitness value plus the fitness values of all the previous individuals; the accumulated

fitness of the last individual should be 1, otherwise something went wrong in the normalization step.

A random number R between 0 and 1 is chosen.

The selected individual is the first one whose accumulated normalized value is greater than or equal to R.

Methods: a.Roulette Wheel Selection ,b.Rank Selection, c.Steady State Selection,d. Tournament Selection, e.Elitism Selection.

Crossover:

1.Cross over can be either one point or two point scheme.

2.One point crossover: Selected pair of strings is cut at some random position and their segments are swapped to form new pair of strings .

3.Two point crossover: There will be two break points in the strings that are randomly chosen.

4.At the break-point the segments of the two strings are swapped so that new set of strings are formed .

Mutuation:

1.Mutation is applied to each individually after crossover Randomly alters each gene with a small probability (generally not greater than 0.01).

2.Injects a new genetic character into the chromosome by changing at random a bit in a string depending on the probability of mutation.

3. Methods: Bit string ,flip bit, boundary,uniform Non-uniform, Gaussian, Shrink.

Choosing Terminating Criteria:

1.Stop after set of Generations .

2.Stop when the most fit solution has not changed in certain number of Generations.

3.At Predetermined generation number.

4. When reach predetermined goal.

Applications:

1.Artificial Intelligence & Robotics.

2.Automobile & Aircraft Design.

3.Air Traffic Control Systems and etc,..

Advantages:

1.It can be efficiently used to highly complex problems with multi-objectivity ,non-linerity,etc.

2.Provides not only a single best solution,but the 2nd best ,3rd best and so on as required.

3.It can incorporate with other local Search Algorithms.

Disadvantages:

1.Optimal Solutions can not be ensured.

2.Convergence of Techniques are problem oriented.

3.Sensitivity analysis should be carried out to find out the range in which the model is efficient.

4.Implementation requires good programming skills.

Programme code:

Stalagmite Function Code:

        
function f = stalagmite(inputvector)
                   a = inputvector(1)
                   b = inputvector(2) 
                   
                      f1 = (sin(5.1*pi.*a + 0.5).^6)
                      f2 = (sin(5.1*pi.*b + 0.5).^6)
                      f3 = exp((-4*log(2).*(a-0.0667).^2./0.64))
                      f4 = exp((-4*log(2).*(b-0.0667).^2./0.64))
 
                      f = -(f1*f2*f3*f4);
                      
                        end
      
        
       

% Clearing and Closing All Variables, plots, Commandline
clear all
close all 
clc

% Defining our Search Space [1D Array]
x = linspace(0,1.5,150);
y = linspace(0,1.5,150);
num_cases = 50;

% Create 2D Array
[xx,yy] = meshgrid(x,y);

% 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);   % Row Vector with 2 coloumns x and y values are put in Array 
         f(i,j) = stalagmite(input_vector); % Stalagmite function
     end
 end
 
 %study 1- statistical behavior
 
tic  % Starts a Stopwatch Timer
 for k = 1:num_cases
     [input,fopt(k)] = ga(@stalagmite,2) % Genetic Algorithm function (Function,No.of Variables)
     xopt(k) = input(1)
     yopt(k) = input(2)
 end
 time_study1 = toc % Print the Elapse time since tic was used
 figure(1)
 subplot(2,1,1) % Create the Multiple Plots in same Figure
 hold on
 surfc(x,y,-f)  
 xlabel('x value')
 ylabel('y value')
 shading interp   % Plots looks smoother
 plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','r') % 3D data points Displays
 title('Unbounded inputs')
 subplot(2,1,2)
 plot(-fopt)
 xlabel('Iterations')
 ylabel('Function minimum')
 
 % Study-2 Upper & Lower bounds
 
tic
for k = 1:num_cases
    [input,fopt(k)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
    xopt(k) = input(1);
    yopt(k) = input(2);
    
end
stydy_time = toc
figure(2)
subplot(2,1,1)
hold on
surfc(x,y,-f)
 xlabel('x value')
 ylabel('y value')
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded inputs')
subplot(2,1,2)
plot(-fopt)
xlabel('Iteration')
ylabel('Function minimum')
title('Bounded inputs')
% Study 3 increasing GA iterations
options = optimoptions('ga')
options = optimoptions(options,'populationsize',150)
tic
for k = num_cases
    
    [input,fopt(k)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options) 
    xopt(k) = input(1)
    yopt(k) = input(2)
end
study_time3 = toc
figure(3)
subplot(2,1,1)
hold on
surfc(x,y,-f)
 xlabel('x value')
 ylabel('y value')
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded inputs')
subplot(2,1,2)
plot(-fopt)
xlabel('Iteration')
ylabel('fopt')

Explanation:

1. Frist of all Programme started with clear all, close all ,clc.

2. Creates 1D Array with linpsace command in X and Y

3.Created 2D Array with Meshgrid command.

4.Evaluated of Stalagmite function by taking 2 input vectors and Stalagmite function code written seperately.

5.For loop created with no .of cases to get an optimum values for x,y, and the function.

6.Time calculated with Tic and Toc command.

7.Used Subplot command to get multiple plots in single figure.

8.Created Suface plot with surfc command.

9.Used plot 3 command to mark with particular size.

Output Results: