Week 4.1 - Genetic Algorithm

                 matlab program to optimize the stalagmite function and the global maxima of the function

Genetic algorithm:

Genetic algorithm is a optimization technique it is based on evolutionary biology. It is used to obtain optimum solution from the set of many initial solutions available. It has many uses in everyday problems.

Example: In turbojet of an aircraft we can have more thrust if the temperature exiting the combustion chamber is high but if that temperature is too high than it melts turbine blades. Using genetic algoritham we may calculate optimum temperature and also best material for turbine blade. We may not always get the high thrust but the thrust we get would be optimum.

There are 4 steps in Genetic algorithm.

1.Selection

2.crossover

3.Mutation

1.Selection:  Only the fittest individual is sleected based upon the fitness value. Higher the fitness value more is its probability to be passed on to the next generation. In a pi chart the individual with highest fitness value occupies more area and hence it is more likely to be selected for next generation

2.Crossover: The fittest chosen by selection are cross overed to produce offsprings.

3.Mutation: The offsprings are then mutated and then after mutation the individual with fitness value is selected for next genearation.

 Explanation: Initially random soultions are selected and there fitness value is calculated. Out of the available solutions only the solution the produces output close to desired output is selected for next generation and is crossed over with other high fitness value solution and the offsprings are then mutated to produce the initial number of population. If the output of these population does not meet the desired output the population is then subjected to many iterations till the output converges to desired output

Flow chart of Genetic algorithm:

Syntax of genetic algorithm: 

[x,fval,exitflag,output,population,scores] = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,intcon,options)

x = function minimum

fval =the value of the fitness function at x.

exitflag =an integer identifying the reason the algorithm terminated.

output =a structure that contains output from each generation and other information about the performance of the algorithm.

population = final population

scores = the scores of the final population.

fun = function

nvars = number of design variables of the function.

A,b= Linear inequalities

Aeq,beq = Linear equalities

lb  = upper bound

up = lower bound

nonlcon =  The function nonlcon accepts x and returns vectors C and Ceq, representing the nonlinear inequalities and equalities respectively. 

intcon =  Indices of integer variables

options = To set population size

Stalagmite function :

We use these equations to create stalagmite function:

function [f] = stalagmite(input_vector)
%UNTITLED6 Summary of this function goes here
%   Detailed explanation goes here
f1x = (sin((5.1*pi*input_vector(1))+0.5)).^6;
f1y = (sin((5.1*pi*input_vector(2))+0.5)).^6;
f2x = exp((((input_vector(1)-0.0667).^2)/0.64).*(-4*log(2)));
f2y = exp((((input_vector(2)-0.0667).^2)/0.64).*(-4*log(2)));
f1= f1x*f1y*f2x*f2y;
f=-f1

end

Note : in stalagmite code we use nagetive sign because Genetic algorithm normally calculates the minimum values so we reverse the sign to reverse the values it calculates from minimum to maximum

 Main code :

plotting stalagmite and running ga to test the program:

clear all
close all
clc

x=linspace(0,0.6,150);
y=linspace(0,0.6,150);

[xx yy]=meshgrid(x,y);
tic
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
toc

surfc(xx,yy,-f);
xlabel('xvalue')
ylabel('Yvalue')
shading interp

[inputs fvalp]=ga(@stalagmite,2)
fval=-fvalp
      
        
        

Steps:

1. create values of x , y between 0 and 0.6 using command linspace

2. use meshgrid command to create solution space [xx yy]

3. create for loop inside it use input_vector to store the values of xx and yy 

4. The values stored in input_vector is than used in stalgmaite function to calculate the calues of f at i,j node i.j ,f(i,j)

5. f,xx,yy are stored in a narray whic hare than plotted.

6.use surfc(xx,yy,-f) to plot graph, we use nagetive sign because grapg usually projects downwards when when we use nagetive sign it projects upward

7. shading interp is used to hide the grid lines in the plot.

8. we use genetic algorithm on stalagmite function to calculate the maximum value and the points at which maximum occurs 

9.coordinates of points are stored in inputs and values of maximum is stored in fval

Result:

10. create get_stalagmite function using the for loop we created to find the f value

function [f] = get_stalagmite(x,y)

[xx yy] = meshgrid(x,y);
 for i=1:length(xx)
     for j=1:length(yy)
         input(1)=xx(i,j);
         input(2)= yy(i,j);
         f(i,j)=stalagmite(input);
     end
 end
end

Now we run 3 cases to calculate the maximum of the function

1. statistical aproach unbounded inputs

2. statistical aproach bounded inputs

3. increasing the number of iterations

Steps in cases :

Case 1 :

1. input the values of x and y

2. set the number of cases to 50 that is the the number of times the for loop runs

3. use get_stalagmite to find the values of f

4. use tic to start the counter

4. use for loop from 1: number of cases

5. store the values of inputs in variuables xinput and yinput

6.value of function is stored in fopt

7.toc is used at the end of for loop to note down the time taken.

7. plot surfaacec of x,y and fopt, we use -fopt in plot since the values will be nagetive as we have used -sign in stalagmite function for the values of f

8.we use plot3 to to plot the points on the peeks

9.plot the graph of -fopt,xaxis indiactes the iterations and yaxis value of -fopt

case2:

1. All the steps involved in the case 1 are followed in addition we set lowerd bounds and upper bounds of genetic algorithm under the for loop

2.we set the values of lower and upper bounds between 0 and 1 so that the values remain inside these bounds

case 3:

1. we increase the population size from 50 which is the default number to 200 so that we get the global maximum value

2. We use optimoptions and option command to set the value of population size

2. All the steps involved in case 2 are folllowed

Main code :

clear all
close all
clc

x = linspace(0,0.6,100);
y = linspace (0,0.6,100);
num_cases = 50;

[f] = get_stalagmite(x,y);

%case1 : statistical behavior unbounded inputs
tic
for i=1:num_cases
    [inputs fopt(i)] = ga(@stalagmite,2);
    xopt(i)=inputs(1);
    yopt(i)=inputs(2);
end
study_time1 = toc
figure(1)
subplot(2,1,1)
surfc(x,y,-f)
xlabel('xvalue')
ylabel('yvalue')
title('unbounded inputs')
shading interp
hold on
plot3(xopt,yopt,-fopt,'Marker','o','MarkerSize',6,'MarkerFaceColor','r')
subplot(2,1,2)
plot(-fopt)
xlabel('iterations')
ylabel('function maximum')
hold off

%case 2 statistical behavior bounded inputs
tic
for i=1:num_cases
    [inputs fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6])
    xopt(i)=inputs(1)
    yopt(i)=inputs(2)
end
study_time2 = toc

figure(2)
subplot(2,1,1)
surfc(x,y,-f)
xlabel('xvalues')
ylabel('yvalues')
title('bounded inputs')
shading interp
hold on
plot3(xopt,yopt,-fopt,'Marker','o','MarkerSize',6,'MarkerFaceColor','r')
subplot(2,1,2)
plot(-fopt)
xlabel('iterations')
ylabel('function maximum')

%case 3 increasing the number of population
options = optimoptions('ga');
options = optimoptions(options,'PopulationSize',200);
tic
for i=1:num_cases
    [inputs, fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6],[],[],options);
    xopt(i)=inputs(1);
    yopt(i)=inputs(2);
end
study_time3 = toc;
figure(3)
subplot(2,1,1)
surfc(x,y,-f)
xlabel('xvalue')
ylabel('yvalue')
title('Increasing the number of population')
shading interp
hold on
plot3(xopt,yopt,-fopt,'Marker','o','MarkerSize',6,'MarkerFaceColor','r')
subplot(2,1,2)
plot(-fopt)
xlabel('iterations')
ylabel('function maximum')

Results: 

case 1: Unbounded inputs

explanation : since the inputs are not bounded ga takes value beyond the values of x and y we have given, since the inputs are not the desired or optimum the maximum value of the function fluctuates a lot and value changed for each run.

Case 2: bounded inputs

Explanation : As we can see the case 2 is more optimized than case 1 because we have introduced bounds which limits the function to find the value between particular inputs which increases the accuracy.

Case 3: 

Explanation : As we can see the maximum value we getting is fluctuation between 0.99 and 1 which is more accurate than the case 2 as we have increased the number of initial population.

Drawback is that it increases the time taken to find the value.