Determining Global Maxima of Stalagmite function using Genetic Algorithm

Aim:

To write a program to find the global maxima of the Stalagmite function using MATLAB

Theory:

A genetic algorithm is a search heuristic that is inspired by Charles Darwin’s theory of natural evolution. This algorithm reflects the process of natural selection where the fittest individuals are selected for reproduction in order to produce offspring of the next generation.

The process of natural selection starts with the selection of fittest individuals from a population. They produce offspring which inherit the characteristics of the parents and will be added to the next generation. If parents have better fitness, their offspring will be better than parents and have a better chance at surviving. This process keeps on iterating and at the end, a generation with the fittest individuals will be found.

The genetic algorithm uses three main types of rules at each step to create the next generation from the current population:

• Selection rules select the individuals, called parents, that contribute to the population at the next generation.
• Crossover rules combine two parents to form children for the next generation.
• Mutation rules apply random changes to individual parents to form children.

Syntax:

The syntax of Genetic algorithm is mentioned below:

x=ga(func,nvars)

func - Function name

nvars - Number of Variables

x = ga(fun,nvars,A,b,Aeq,beq,lb,ub)

func - Function name

nvars - Number of Variables

A- linear inequality constraints as real matrix

b- linear inequality constraints as real vector

Aeq- linear equality constraints as real matrix

beq- linear equality constraints as real vector

lb- lower boundary

ub-upper boundary

x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,options)

func - Function name

nvars - Number of Variables

A- linear inequality constraints as real matrix

b- linear inequality constraints as real vector

Aeq- linear equality constraints as real matrix

beq- linear equality constraints as real vector

lb- lower boundary

ub-upper boundary

nonlcon- Non linear constraints

options - creating optimisation options using "optimoptions".

options = optimoptions(SolverName)
options = optimoptions(SolverName,Name,Value)

Explanation of Program

With the input values x,y we created a 2D array using "meshgrid"

A stalagmite function is created in the name of "stalagmite"

For loop inserted for running upto length of x and y and the values of 2D form of X and Y to stalagmite input.

The surface plot is ploted with the (X,Y,F)

Study1 (Statistical Behaviour)

• A clock is assigned to find the time taken to run the study1
• For loop is used to run a iteration of 50 times and the output from ga function is stored in x1,y1,f1
• The syntax used here is x=ga(func,nvars)
• For getting the F-maximum value we put negative sign so a inverted plot is obtained as ga function gives a global maxima
• The plot is done wiyh output values like x1,y1 and f1 value and a subplot is made with F-maximum and Iteration.

Study2- Statistical Behaviour with upper and lower bounds

• A clock is assigned to find the time taken to run the study2
• For loop is used to run a iteration of 50 times and the output from ga function is stored in x2,y2,f2
• The syntax used here is x = ga(fun,nvars,A,b,Aeq,beq,lb,ub)
• The lower and upper boundary can be fixed to range in between if you know where is your global maxima will be nearly settle, here it is (0,0.075) for x and y, the global value of z is got in short period of time.
• For getting the F-maximum value we put negative sign so a inverted plot is obtained as ga function gives a global maxima
• The plot is done wiyh output values like x2,y2 and f2 value and a subplot is made with F-maximum and Iteration.
• Now the result obtained are more boundary conditioned.

Study3- Statistical Behaviour increasing GA iteration

• A clock is assigned to find the time taken to run the study3
• For loop is used to run a iteration of 50 times and the output from ga function is stored in x3,y3,f3
• The syntax used here is x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,options)
• The lower and upper boundary can be fixed to range in between if you know where is your global maxima will be nearly settle, here it is (0,0.075) for x and y, the global value of z is got in short period of time.
• Optimised option used to increase the number of population to get the value(if it is not mentioned it will take a value of 50).
• For getting the F-maximum value we put negative sign so a inverted plot is obtained as ga function gives a global maxima
• The plot is done wiyh output values like x3,y3 and f3 value and a subplot is made with F-maximum and Iteration.
• Now the result obtained gives the global maxima using stalagmite function

Note:

num_cases : assigned 50 number so that 'ga' can get to the minima value correctly

Population will take 170 points (here it had taken population as 170) from 1st iteration and check the fitness ie, in terms of minima value and this will be go on for the length of iteration (ie, 50) and with the 50 values we will plot the graph.

To obtain graph in proper view (ie non inverted) we given -ve value to the 'f' at the time of plot.

Program

%GENETIC ALGORITHM
clear all
close all
clc

%inputing the values of x and y
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
num_cases = 50;
%creating the mesh values 2D array of x and y
[X,Y] = meshgrid(x,y);

for i=1:length(X)
    for j=1:length(Y)
        inputs(1)=X(i,j);
        inputs(2)=Y(i,j);
        F(i,j)= stalagmite(inputs);
    end
end

%study1- statistical behaviour
tic
for k=1:num_cases
    [inputs,f1(k)]= ga(@stalagmite,2);
    x1(k)= inputs(1);
    y1(k)= inputs(2);
end
study1_time = toc;
figure(1)
subplot(2,1,1)      %sub plot
surfc(X,Y,-F)      
shading interp;
xlabel('X');
ylabel('Y');
hold on
plot3(x1,y1,-f1,'o','MarkerSize',5,'MarkerFaceColor','#D9FFFF')  %3d plot along with the surface plot 
title('unbounded inputs');
subplot(2,1,2)        %sub plot
plot(-f1)
xlabel('No of iteration');
ylabel('function maximum');
tic
%study2- statistical behaviour with upper and lower bounds
for k=1:num_cases
    [inputs,f2(k)]= ga(@stalagmite,2,[],[],[],[],[0;0],[0.4;0.4]);
    x2(k)= inputs(1);
    y2(k)= inputs(2);
end
study2_time = toc;
figure(2);
subplot(2,1,1)            %sub plot
surfc(X,Y,-F)
shading interp;
xlabel('X');
ylabel('Y');
hold on
plot3(x2,y2,-f2,'o','MarkerSize',5,'MarkerFaceColor','#D9FFFF')     %3d plot along with the surface plot 
title('Bounded inputs');
subplot(2,1,2)
plot(-f2)
xlabel('No of iteration');
ylabel('function maximum');

%study3- statistical behaviour increasing GA iteration

options=optimoptions('ga');
options=optimoptions('ga','PopulationSize',170);
for k=1:num_cases
    [inputs,f3(k)]= ga(@stalagmite,2,[],[],[],[],[0;0],[0.075;0.075],[],[],options);
    x3(k)= inputs(1);
    y3(k)= inputs(2);
end
study3_time = toc;
figure(3);
subplot(2,1,1)          %sub plot
surfc(X,Y,-F)
shading interp;
xlabel('X');
ylabel('Y');
hold on
plot3(x3,y3,-f3,'o','MarkerSize',5,'MarkerFaceColor','#D9FFFF')  %3d plot along with the surface plot 
title('Increasing GA Iteration');
subplot(2,1,2)
plot(-f3)
xlabel('No of iteration');
ylabel('function maximum');

Function Structure:

function[F] = stalagmite(inputs)
x=inputs(1);
y=inputs(2);
A= (sin((5.1*pi*x)+0.5))^6 ; 
B= (sin((5.1*pi*y)+0.5))^6 ;  
C=exp(-4*log(2)*((x-0.0667)^2/0.64));
D=exp(-4*log(2)*((y-0.0667)^2/0.64));
F= -(A*B*C*D);   %-ve sign is given to get maxima value
end

Output

Study-1

Study-2

Study-3

Workspace Data:

The value of x and y for global maximum value

The time took for doing the study

Result :

Global maxima of a stalagmite function was found to be 1 at the value of (0.0668,0.668) and the output plotted with all the three studies. The graph for the Fmaximum vs No: of iteration is plotted and noted when the population(ie ga to be iterated inside to get the result unless the different of the concecutive value is very low and to the power of 10^-3 only it will be finalise the value) was increased to a value of 170 numbers(otherwise it will take as 50) we could see the time for the study increasing to 4 times. So we can able to get an inference that if we increase the no of population then the time for the all process increases but the result will be precise.