Week 4 - Genetic Algorithm

• Selections means select the individuals, called parents, that contribute to the population at the next generation.
• Crossover means combining two parents to form children for the next generation.
• Mutation is to apply random changes to individual parents to form children.

Genetic Algorithm generates a population for each iteration. The best points in the intial population converge towards the optimal solution.

Terminology-

1.Fitness Function-It is the function that needs to be optimized. It is also called the objective function.

2.Individual-Any point to which you can apply the fitness function.The value of the fitness function for an individual is its score.

3.Population and Generation-It is an array of individuals,ie,set of initial data.In each iteration,the algorithm produces a new set of computations on the current population.Each successive population is called a new generation.

4.Parents and Children-The genetic algorithm performs computations on the current set of individuals called the parents,producing a new set of individuals ,called children.

WORKING OF THE ALGORITHM-

1.Algorithm begins by generating a new initial population.

2.It then creates a sequence of new populations.At each step,the algorithm uses the individuals in the current population to perform computations and produce the new population. The steps involved are-

3.Fitness Value is computed for each individual of the current population.

4.The fitness values computed are scaled into a more usable range of values,called expectation values.

5.The parents are then chosen on the basis of their expectation values.

6.Children are produced from parents in 2 ways- Mutation-by making random changes to a single parent,or by combining the vector entries of a pair of parents -crossover.

7.Some individuals directly survive to the next generation, they are called elite individuals. They have high fitness values.

8.The current population is replaced with the new formed children to form the next generation.

STALAGMITE FUNCTION-

A stalagmite is a type of speleothem that rises from the floor of a limestone cave due to the dripping of mineralized solutions and the deposition of calcium carbonate. A mathematical model has been formed to represent these formations. It is as follows-

'ga' Function syntax in MATLAB-

• General Syntax- x=ga(func,nvars)- finds a local unconstrained minimum, x, to the objective function,func .nvars is the dimension (number of design variables) of func.
• Modified Syntax- x=ga(func,nvars,A,b,Aeq,Beq,beq,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. Other values are set to empty,or '[]', if no linear inequalities exist.
• x=ga(func,nvars,A,b,Aeq,Beq,beq,lb,ub,nonlcon,options)- Same as above, except that the minimization is performed with the parameters replaced by the values in 'options'. 'options' are created using optimoptions() funtion.
• [x,fval]=ga(_)- We can make the function return 2 values instead of only 1 optimal value. fval is the value of the fitness function atx,for the input arguments.

WORKFLOW/STEPWISE EXPLANATION-The given formulae for the stalagmite function are written as a function. When called it returns the value calculated after passing the required inputs to the stalagmite function. Since we are interested in finding the maximum value of the function, we negate the final value of the function returned.Otherwise,we end up finding the minimum value ,instead of the maximum value.

In the main program, we generate random values for x and y, using the linspace() command.Values for the stalagmite function are generated using a nested loop running through the values of x and y.The values are passed as arguments to the stalagmite function,which calculates the value and stores it in the matrix f.

We perform the optimization of the function 3 times to compare and contrast the values obtained.In the first study,we perform an unbounded optimization. Default values for the ga function are used,no parameters are modified.The arguments passed to ga() function are the stalagmite function handle and the number of variables,which is 2 here.The function performs the optimization and returns the optimum x and y value as well the the optimal value of the fitness function.The x and y values are stored in input1 while the optimum fitness function value is stored in fopt1. This is repeated for a fixed number of iterations,here=50, to make the value converge to the optimal solution.We then proceed to plot the obtained values.A surface or contour plot is done using the surfc() command. Using surfc(),we plot the original x and y values along with the stalagmite function values,ie,x,y and f.On this same plot,we also use the plot3() command to plot the obtained optimal values of x,y and the fitness function value.This shows the range of the maximum values obtained. In a different figure window, we plot the optimal function values against the number of iterations,to see how the value obtained changes in each iteration.We see that in this unbounded plot,since there are no parameters like the selection pool or upper and lower bounds which have been changed, the results obtained are not accurate.The maximum value obtained keeps changing with each iteration as is evident from the graph.

The results obtained in study1 can be modified to get better results in study2. Here process remains the same , the only difference being that we change the upper and lower bounds in which the function performs the optimization.We specify the lower bound as [0;0] and upper bound as [1;1]. This means that the solution is found in the specified range of 0 to 1. This gives a more accurate solution as we are limiting the region in which the optimization has to be performed. As seen from the graphs,the result obtained is not as haphazard as the first study,but is improved. There is still some variation in the maximum value obtained.The solution is further refined in study3.

In study3, to further improve the accuracy of the solution,we alter the population size.By default the population size for ga() function is 50.If the population size is too small,the function ends up calculating the local maxima instead of the global maxima. So here in study3,we increase the initial population size.This is done by passing the 'options' argument to the ga() function,after specifying the upper and lower bounds.The options are then changed using the optimoptions() function. 'options=optimoptions(options,'populationsize',200)' this command is used to change the default population size from 50 to 200. The disadvantage is that the computation takes a much longer time,becuse there is a much larger population to be evalualted.The solution obtained,is however,much cleaner and gives an almost accurate optimal value for the fitness function,with very little variation as seen from the graph.

CODE(MAIN PROGRAM)-

clear all 
close all 
clc 
%% Program to optimise and find maximum value of stalagmite function 

%Inputs 
x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
n=50;

%Values for generating stalagmite function 
for i=1:length(x)
    for j=1:length(y)
        input_vector(1)=x(i);
        input_vector(2)=y(j);
        f(i,j)=stalagmite(input_vector);
   end
end

%% Study 1-Unbounded 
for k=1:n
    [input1 fopt1(k)]=ga(@stalagmite,2);
    xopt1(k)=input1(1);
    yopt1(k)=input1(2);
end

%Plot
figure(1)
subplot(2,1,1)
surfc(x,y,-f) %3D Contour plot
shading interp 
hold on 
plot3(xopt1,yopt1,-fopt1,'marker','o','markerfacecolor','r'); %Plotting Computed values 
xlabel('X Values');
ylabel('Y Values');
title('Unbounded Plot');
subplot(2,1,2)
plot(-fopt1); %Plotting optimal fitness function values against iterations
xlabel('Iterations');
ylabel('fopt1');
title('Unbounded Plot');

%% Study 2-Bounded 
for k=1:n
    [input2 fopt2(k)]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
    xopt2(k)=input2(1);
    yopt2(k)=input2(2);
end

%Plot 
figure(3)
subplot(2,1,1);
surfc(x,y,-f);
shading interp 
hold on 
plot3(xopt2,yopt2,-fopt2,'marker','o','markerfacecolor','r');
xlabel('X Values');
ylabel('Y Values');
title('Bounded Plot 1');
subplot(2,1,2);
plot(-fopt2);
xlabel('Iterations');
ylabel('fopt2');
title('Bounded Plot');

%% Study 3-Bounded
options=optimoptions('ga');
options=optimoptions(options,'populationsize',200);
for k=1:n
    [input3 fopt3(k)]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
    xopt3(k)=input3(1);
    yopt3(k)=input3(2);
end

%Plot
figure(5)
subplot(2,1,1);
surfc(x,y,-f) 
shading interp 
hold on 
plot3(xopt3,yopt3,-fopt3,'marker','o','markerfacecolor','r');
xlabel('X Values');
ylabel('Y Values');
title('Bounded Plot 2');
subplot(2,1,2);
plot(-fopt3);
xlabel('Iterations');
ylabel('fopt3');

STALAGMITE FUNCTION-

function sf=stalagmite(input_vector)
a=input_vector(1);
b=input_vector(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));

sf=-(f1*f2*f3*f4)
end

RESULTS/PLOTS-

1. Study 1-

2.Study 2-

3.Study 3-

REFERENCES-

1. mathworks.com/documentation

2. medium.com-Introduction to Genetic Algorithm