Week 4 - Genetic Algorithm

Aim: Writing a code in MATLAB to optimise the stalagmite function and find the global maxima of the function.

Objectives:

1. Clearly explaining the concept of genetic algorithm.
2. Explaining the syntax for ga in Matlab.

Theory:

Genetic algorithm is basically used for solving optimization problem. So, the optimization problem essentially solving the to find the optimum value. That means, find the minimum or maximum value. genetic algorithm is basically follow, the concept of genetics and evolution. Genetics is a well-known concept in biology and evolution is also an well-known concept in biology. So, these are biological concepts. So genetics and evolution is followed to solve the optimization problem then this is called the genetic algorithm and popularly it is abbreviated as GA.

The two pioneer who work to make the GA, most successful they are the two revolutionary people one is called the Gregor Johan Mendel and Charles Darwin. Gregor Johan Mendel in 1865, he proposed one revolutionary concept called the genetics and around 10 years later, Charles Darwin who proposed the concept it is called the evolution and that these two concept are merged together to solve the optimization problem which become the true I mean origin of the genetic algorithms. GA is a population based random search, this means from one population to another population we have to search for the best solution.

GA operation is concerned, those are the operation that we have mentioned is carried out by means of called the operators, those operators are basically the functions like. So, for example, encoding convergence, mating pool, fitness evolution, crossover, mutation inversion these are called operators.

II. Important terms need to clarify related with optimization problem solutions are:

1. Local optimumof an optimization problemis a solution that is optimal either maximal or minimal within a neighboring set of candidate solutions.
2. Global optimum which is the optimal solution among all possible solutions, not just those in a particular neighborhood of values.

III. Some other terminologies related with GA:

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.

IV.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.

Programmers specify the values of these criteria in the Stopping criteria

1. The GA syntax in Matlab is given by :

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 C and Ceq, representing the nonlinear inequalities and equalities respectively. ga minimizes the fun such that C(x) ≤ 0 and Ceq(x) = 0. (Set lb=[] and ub=[] if no bounds exist.)

fun = objective function

nvars = number of variables

A and B = subject to linear inequalities of the form A*x <=B

Aeq and Beq = subject to linear equalities of the form A*x = B

lb = lower bound and ub = upper bound

nonlcon = nonlinear inequalities

1. The following outline summarizes how the genetic algorithm works:
2. The algorithm begins by creating a random initial population.
3. 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.
   7. The algorithm stops when one of the stopping criteria is met.

Main Code:

clear all
close all
clc

%input arrays for x and y variables arrays
x = linspace(0,0.6,150); 
y = linspace(0,0.6,150);

[xx,yy] = meshgrid(x,y);  %% crating 2D arrays

num_case = 150; %% no. of iterations

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) = stalagmite(input_vector);   
     end
end
%study_1 %% GA runs for 150 iterations
tic               %% tic works with the toc function to measure elapsed time
for i = 1:num_case
[inputs,fopt(i)] = ga(@stalagmite,2); %% GA syntax %% 2-defines no. of variables
xopt(i) = inputs(1);    %% optimum x value stored in array   
yopt(i) = inputs(2);
end

study_time_1 = toc;   %%toc function uses the recorded value to calculate the elapsed time

figure(1)
subplot(2,1,1); 
hold on
surfc(xx,yy,f);    %%% surface plot
shading interp   %%%  varies the color in each line segment and face by interpolating the colormap index
ylabel('y data');
xlabel('x data');
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','k') %%% plot for 50 interations
title('unbounded Inputs')
subplot(2,1,2)
plot(fopt)   %% plots optimum result
xlabel('iterations')
ylabel('Function maximum')

%study 2- statistical behaviour with upper and lower bounds
tic %%
for i = 1:num_case
[inputs,fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
xopt(i) = inputs(1);
yopt(i) = inputs(2);
end
study_time_2 = toc;

figure(2)
subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp
xlabel('x data')
ylabel('y data')
plot3(xopt,yopt,fopt,'marker',o','markersize',3,'markerfacecolor','k')
title('Bounded Inputs')
subplot(2,1,2)
plot(fopt)
xlabel('Iterations')
ylabel('Function Maximum')

%study 3  %%% Changing population size
options = optimoptions('ga')
options = optimoptions(options,'populationsize',450); %% increased population size to 350
tic
for i = 1:num_case
[inputs,fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
xopt(i) = inputs(1);
yopt(i) = inputs(2);
end
study_time_3 = toc;

figure(3)
subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp
xlabel('x data')
ylabel('y data')
plot3(xopt,yopt,fopt,'marker',o','markersize',3,'markerfacecolor','k')
title('Bounded Inputs with Increased population size');
subplot(2,1,2)
plot(fopt)
xlabel('Iterations')
ylabel('Function Maximum')

max_value = [fopt];

Code for Function

function[f]=stalagmite(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);
f=1/(1+f);
end

Plots