Week 4.1 - Genetic Algorithm

Aim: To write a programme optimise the stalagmite function and find the global maxima of the function by using genetic algorithm.

Theory:

Genetic algorithm: Genetic algorithm was based on the principle of darwin's theory of evolution which states the survival of the fittest.

Here this algorithm is mainly used to evaluate the solution of an objective function by considering the random population. Here a fitness function is usually introduced to find the fittest of the solution. This method initially find the parent solution which is termed as the chromosomes, which inturn will udergo a fitness funtion to find the suitability of solution. Now, set of chromosomes gets mutated by the process of cross over and produce new chromosomes, which will be a combination of parent genes.where as mutation is the process of replacing random genes with another set of random genes. The rate of both cross over and mutation are controlled by cross over rate and mutation rate value. After several generation the solution value converges to a value which is regarded as the best solution.

Genetic algorithm generally find the local manima which is found to vary each time we run the programme. The consistany of this can be improved by , Increasing the population size, Assigning the boundedness, changing the mutation and crossover rate etc.

General Syntax of genetic algorithm: var_x = ga(@function,nvars,A,b,Aeq,beq,lb,ub,nonlcon,IntCon,options)

@function: The function to be alaysed to find the minima

nvars: This represents the number of the variables to be evaluated.

A,b: This shows the linear inequality constraints.

Aeq,beq: This represents the linear equalities.

lb,ub: Represents the lower and upper bound values in which the function is to evaluted.

nonlcon: This shows the non linear constraints

IntCon: This represents the integer constraints.

options: These are the options necessary for optimising the algorithm such as population size, crossover function etc to get consistent values.

Main Code:

clear all
close all
clc
%%
    x_1 = linspace(0,0.6,150);
    y_1 = linspace(0,0.6,150);
    y_a = y_1';
%To evaluate stalagmite function for values from 0 to 0.6 with 150 values
    f_1 = Stalgmite_func_1(x_1,y_a);
%%
%Case1: finding maxima without giving any constraints or boundedness value
    for cases_c_1 = 1 :100
        [input,f_c_1(cases_c_1)] = ga(@Stalgmite_func,2);
        x_c_1(cases_c_1) = input(1);
        y_c_1(cases_c_1) = input(2);
    end
    figure(1)

%plotting the results of the stalagmite function
    surfc(x_1,y_1,f_1);
    shading interp
%plotting the results of ga found at each iteration with respect to x and y values
    hold on
    plot3(x_c_1,y_c_1,f_c_1)
    xlabel('Input_x Stalagmite');
    ylabel('Input_y Stalagmite')
    zlabel('Results stalagmite')
%Plotting the results of maxima obtained with iteration.
    figure(2)
    plot(f_c_1)
    xlabel('Iterations');
    ylabel('Maxima_stalagmite')
    axis([0 100 -2 0])
    
%%
%Case2: finding maxima by assiging the value of upper and lower bounds
    for cases_c_2 = 1 :100
        [input,f_c_2(cases_c_2)] = ga(@Stalgmite_func,2,[],[],[],[],[0;0],[0.6;0.6]);
        x_c_2(cases_c_2) = input(1);
        y_c_2(cases_c_2) = input(2);
    end
    figure(3)
%plotting the results of the stalagmite function
    surfc(x_1,y_1,f_1);
    shading interp
    hold on
%plotting the results of ga found at each iteration with respect to x and y values
    plot3(x_c_2,y_c_2,f_c_2)
    xlabel('Input_x Stalagmite');
    ylabel('Input_y Stalagmite')
    zlabel('Results stalagmite')
%Plotting the results of maxima obtained with iteration.
    figure(4)
    plot(f_c_2)
    xlabel('Iterations');
    ylabel('Maxima_stalagmite')
    axis([0 100 -2 0])
    
%%    
%case3: Findin the maxima by including the population size  and the value of bounds 
option = optimoptions('ga','PopulationSize',250);
    for cases_c_3 = 1 :100
        [input,f_c_3(cases_c_3)] = ga(@Stalgmite_func,2,[],[],[],[],[0;0],[0.6;0.6],[],[],option);
        x_c_3(cases_c_3) = input(1);
        y_c_3(cases_c_3) = input(2);
    end
    
    figure(5)
%plotting the results of the stalagmite function
    surfc(x_1,y_1,f_1);
    shading interp
    hold on
%plotting the results of ga found at each iteration with respect to x and y values
    plot3(x_c_3,y_c_3,f_c_3)
    xlabel('Input_x Stalagmite');
    ylabel('Input_y Stalagmite')
    zlabel('Results stalagmite')
%Plotting the results of maxima obtained with iteration.
    figure(6)
    plot(f_c_3)
    xlabel('Iterations');
    ylabel('Maxima_stalagmite')
    axis([0 100 -2 0])

Function Code:

function [s] = Stalgmite_func(input_main)

x_f = input_main(1);
y_f = input_main(2);
term1 = (sin(5.1*pi*x_f+0.5))^6;
term2 = exp(-4*log(2)*(x_f-0.0667)^2/0.64);
term3 = (sin(5.1*pi*y_f+0.5))^6;
term4 = exp(-4*log(2)*(y_f-0.0667)^2/0.64);
s = -term1*term2*term3*term4;
end

• The programme starts with the basic initial conditions to clear the workspace, and command window.
• 'linspace' command is used to create an array of x and y values to be inputted on to the 'stalagmite' function.
• The results of the stalagmite function is storted on to a matrix 'f_1'.
• Stalagmite is a function which return a plot in the shape of a stalagmite.
• this is assigned to a seperate function which where it computes the value of the equations:

Stalagmite Function (Governing 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_{1,y} = [sin(5.1piy+0.5)]^6`

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

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

Case 1: No bounds and population size

• Now here we compute the maxima by using Genetic algorithm.
• The syntax of ga include calling the function whose minima is to be found and the no. of variables, here being the case one we do not define the population nor the bounds.
• Since the ga only returns the local minima we multiply the results of the stalagmite function with a negative sign.
• So the ga return the maximum value with a negative sign, thus the point of incident of maximum value and the vlaue itself is also stored on to an array.
• The results of stalagmite function is plotted as a 3-dimensional plot and the maximas along with their point of incidence is plotted.
• The value of Maxima is plotted with iteration to find the variation in the vlaues of msxima computed by the genetic algorithm..

Case 2: Assigning the Bounds

• Here in the case two we include the bounds which describes the domain in which the ga has to compute the maxima.
• The bounds were defined as 0 - 0.6 for both x and y. The syntax for which is shown below

 [input,f_c_2] = ga(@Stalgmite_func,2,[],[],[],[],[0;0],[0.6;0.6]);

• Introduction of this domain helps to eliminate the unwanted population which will be included to compute the maxima.
• Here also we plot the same components as in case 1.

Case 3:Assigning the Bounds and Population Size

• Here in the case two we include the bounds as in case 2, also we define the population size.
• The population size were defined as 250. The syntax for which is shown below

option = optimoptions('ga','PopulationSize',250);
[input,f_c_3] = ga(@Stalgmite_func,2,[],[],[],[],[0;0],[0.6;0.6],[],[],option);

• Defining the population size helps to include more of the value from the bounds and hence this helps to include more value.
• Increasing the population size helps to compute for find the minimum value over a large population which in turen will show approximately the global maxima when compared to the previous cases
• The plots are done as same in the previous cases.

Results:

Case 1: No bounds and population size

• From the figure it can be easily interpretted that the maxima at each iteration is found to be scattered all over the plot which depicts that the found maxima is a local maxima rather than a global one.
• This in turn can be clearly depicted from the graph of maxima stalagmite v/s iteration that the maxima just varies randomly over iterations thus make the function less consistant.

Case 2: Assigning the Bounds

• From the figure it shows that the variation of maxima with iteration has considerabily reduced with respect to case 1
• This is clearly depicted in the graph of maxima stalagmite v/s iteration where the maxima lies in between (-0.6 and -1)
• Thus almost value equal to -1 is shown which shows that the value of maxima is converging.

Case 3: Assigning the Bounds and Population Size

• At this point on defining the population size the ga really considers a large no. of population to compute the maximuma.
• thus on increasing the population size and by defining the bound the ga gets a clear picture of the domain and this will be able to compute the maxima.
• Thus from the graph of maxima stalagmite v/s iteration, the variation of the maxima value with 100 iteration is almost a constant value (considerably small variation which could be neglected) thus on defining the bounds and population size a consitant value of maxima is found.
• This maxima can be conluded as a global maxima.