Week 4 - Genetic Algorithm

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

Theory

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. At each step, the genetic algorithm randomly selects individuals from the current population and uses them as parents to produce the children for the next generation. Over successive generations, the population "evolves" toward an optimal solution.

You can apply the genetic algorithm to solve problems that are not well suited for standard optimization algorithms, including problems in which the objective function is discontinuous, nondifferentiable, stochastic, or highly nonlinear.

Outline of the Algorithm

The following outline summarizes how the genetic algorithm works:

Initail Population

The process is begins randomly selectin a set of individuals which froms a Population.

An individual is characterized by a set of parameters known as Genes. Genes are joined into a string to form a Chromosome (solution).

In a genetic algorithm, the set of genes of an individual is represented using a string. Usually, binary values are used (string of 1s and 0s). We say that we encode the genes in a chromosome.

Fitness Function

The fitness function determines how fit an individual is (the ability of an individual to compete with other individuals). It gives a fitness score to each individual. The probability that an individual will be selected for reproduction is based on its fitness score.

Crossover

Crossover is the most significant phase in a genetic algorithm. For each pair of parents to be mated, a crossover point is chosen at random from within the genes.

For example, consider the crossover point to be 3 as shown below.

Offspring are created by exchanging the genes of parents among themselves until the crossover point is reached.

The new offspring are added to the population.

Selection

The idea of selection phase is to select the fittest individuals and let them pass their genes to the next generation.

Two pairs of individuals (parents) are selected based on their fitness scores. Individuals with high fitness have more chance to be selected for reproduction.

Mutation

In certain new offspring formed, some of their genes can be subjected to a mutation with a low random probability. This implies that some of the bits in the bit string can be flipped.

Termination

The algorithm terminates if the population has converged (does not produce offspring which are significantly different from the previous generation). Then it is said that the genetic algorithm has provided a set of solutions to our problem.

Syntax for genetic algorithm

[x,fval] = ga(func,nvars,A,B,Aeq,Beq,lb,ub,nonlcon,options)

where

func = function whoes minimum is to be find

nvars = number of variables of the function

A,B = equation of linear inequalities A*x ≤ B

Aeq,Beq = equation of linear equalities Aeq*x = Beq (Set A=[] and B=[] if no linear inequalities exist.)

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

nonlcon = The function nonlcon accepts x and returns vectors C and Ceq, representing the nonlinear inequalities and equalities respectively. ga minimizes the func such that C(x) ≤0 and Ceq(x) = 0 . (Set lb = [] and ub = [] if no bounds exist.)

options : - change default optimization parameters (Set nonlcon = [] if no nonlinear constraints exist.) Create options using optimoptions.

Stalagmite Function Equation

`f(x,y)=f_(1,x)f_(2,x)f_(1,y)f_(2,y)`

`f_(1,x)=[sin(5.1pix+0.5)]^6`

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

`f_(1,y)=[sin(5.1piy+0.5)]^6`

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

Code

clear all
close all
clc

%defining our search spacecc
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);

% creating a 2D mesh 
[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);
        f(i,j)=stalagmite(input_vector);
    end
end

% number of cases 50
num_case = 50;

tic
% Study 1 - Statistical behavior
for i=1:num_case
    [input,fval(i)]=ga(@stalagmite,2);
    x_input(i)=input(1,1);
    y_input(i)=input(1,2);
end
study1_time=toc;

figure(1)
subplot(2,1,1)
surfc(xx,yy,-f)
shading interp
hold on
plot3(x_input,y_input,-fval,'marker','o','markersize',5,'markerfacecolor','r')
title('Unbounded inputs')
subplot(2,1,2)
plot(-fval)
xlabel('Iterations')
ylabel('Function maximum')


% Study 2 - Statistical behavior - with upper and lower bounds
tic
 for i=1:num_case
    [input,fval(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6]);
    x_input(i)=input(1,1);
    y_input(i)=input(1,2);
 end
study2_time = toc;


figure(2)
subplot(2,1,1)
surfc(xx,yy,-f)
shading interp
hold on
plot3(x_input,y_input,-fval,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded inputs')
subplot(2,1,2)
plot(-fval)
xlabel('Iterations')
ylabel('Function maximum')


% Study 3 increasing GA iterattions
options = optimoptions('ga');
options = optimoptions(options,'Populationsize',250);

tic
for i=1:num_case
    [input,fval(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6],[],[],options);
    x_input(i)=input(1,1);
    y_input(i)=input(1,2);
end
study3_time=toc;

figure(3)
subplot(2,1,1)
surfc(xx,yy,-f)
shading interp
hold on
plot3(x_input,y_input,-fval,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded inputs with modified population size')
subplot(2,1,2)
plot(-fval)
xlabel('Iterations')
ylabel('Function maximum')

fprintf('Study 1 takes %f seconds\n',study1_time);
fprintf('Study 2 takes %f seconds\n',study2_time);
fprintf('Study 3 takes %f seconds\n',study3_time);
total_time = study1_time+study2_time+study3_time;
fprintf('total time is %f seconds\n',total_time);
fprintf('Max value of stalagmite function is %f\n',mean(-fval));

Code of Stalagmite Function

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

% ga always give minimum value so for max it is min of negative value
f=-f1*f2*f3*f4;

Code explanation

1. Start with close all ,clear all and clc for clearing any previous command data.
2. Defiine search space x and y by using linspace with will give 150 values between 0 to 0.6 , linespace(0,0.6,150)
3. Creat 2D mesh by meshgrid(x,y) and store the value to xx and yy.
4. Create a nested for loop for accesing each element of 2D mesh and evaluate stalagmite function.
   1. In line 1 define function name stalagmite and f is the output and input_vector is the input to the function.
   2. define each term of equation for input_vector(1) and input_vector(2)
   3. Multiply each term to get final equation .
   4. function ga always give the minimum value so for maximum value we take negative of our stalagmite function so that minimum of negative value becomes maximum
5. take num_case = 50 so that we can run ga 50 times
6. For study 1 start with tic for clock reset and then
7. Create a for loop in witch use built in function ga with stalagmite function and second input as number of variable of stalagmite function
8. Stop the clock with toc and save the time to study1_time
9. Open figure 1
10. Create 2 subplot and in first one plot stalagmite function with command surfc(xx,yy,-f) and hide the shading with shading interp
    • Use nevative of funtion output 'f' so that we can get original stalagmite function
11. hold on the first subplot and plot a 3D line with x_input and y_input and negative of values of fval for ploting original maximum value ,Use marker 'o' with size 5 and color red using command plot3(x_input,y_input,-fval,'marker','o','markersize',5,'markerfacecolor','r')
12. In the subplot 2 plot -fval and add title to it
13. For study 2 start with tic for clock reset and then
14. Create for loop in which ga run 50 time with lower and upper bound from 0 to 0.6 by using command explain in theory
15. Stop the clock with toc save the time in varibale study2_time
16. Open figure 2
17. Repeat step 10 and 12 for ploting result of study 2 in figure 2
18. For study 3 change the default population of built in function ga from 50 to 250 by using option and optimoption command
19. Reset the clock and start for loop with ga with modified polulation size of 250
20. After ending the loop save the clock timer to study3_time
21. Open figure 3
22. Repeat step 10 and 11 for ploting result of study 3 in figure 3
23. Print all the time of study by using fprintf
24. Calculate total study time and print it
25. Print the mean maximum value of the stalagmite function

NOTE:- Use command rng(0) after clc for getting same result even if the code is made to run several times.

RESULT

Study 1 - Statistical behavior

Study 2 - Statistical behavior - with upper and lower bounds

Study 3 increasing GA iterattions

Max value of stalagmite function is 1

Conclusion

The search space of ga in study 1 is beyond the range of stalagmite function beacuse of which the result is not accurate by defining the search space with lower and upper bound in study 2 it gives more accurate result by taking approximately similar time

In study 3 when we increase the default population size to 250 it will give the most accurate result but takes more time