Genetic algorithm analysis using MATLAB

AIM : To write a program to optimize the stalagmite function and find the global maxima of the function using MATLAB

OBJECTIVE:

• To optimize the stalagmite function and find the global maxima of the function
• To plot surface graphs for 3 different cases for `f_(max)` vs no:of iterations
• To explain the concept of genetic algorithm and also explain the syntax for ga function

THEORY

Genetic algorithm

A genetic algorithm is a method of solving optimization problems by the concept of theory of evolution proposed by Charles Darwin.It is a search-based optimization technique based on the principles of Genetics and Natural Selection.This algorithm is used to calculate the global minimum or global maximum of a function.MATLAB has an inbuilt function called 'ga' to calculate the global minimum from the function.It is frequently used to find optimal or near-optimal solutions to difficult problems which otherwise would take a lifetime to solve. It is frequently used to solve optimization problems, in research, and in machine learning.

FLOWCHART DEPECTING THE GENETIC ALGORITHM

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

1. The algorithm randomly selects members from the current population which become the parents for the next iteration.
2. The parents members of the function undergo mutations and crossovers to generate the child members of the functions.
3. These child members now become the new population of the function and new parent members are selected from this new population.
4. The process is repeated over and over again until the required value from the function is obtained or the number of generations become very high.

Stalagmite Equation

A stalagmite is a type of rock formation that rises from the floor of a cave due to the accumulation of material deposited on the floor from ceiling drippings. Stalagmites may be composed of lava, minerals, mud, peat, pitch, sand, sinter and amberat (crystallized urine of pack rats).A close identical geometrical shape can be obtained by using a mathematical function. This function should be applied to two variables in two dimensions which yields the stalagmite.

Governing equations :

• `f(x,y)=f_(1,x)*f_(2,x)*f_(1,y)*f_(2,y)`
• `f_(1,x)=(sin(5.1πx+0.5))^6`
• `f_(1,y)=(sin(5.1πy+0.5))^6`
• `f_(2,x)=exp(−4ln(2)(((x−0.0667)^2)/0.64))`
• `f_(2,y)=exp(−4ln(2)(((x−0.0667)^2)/0.64))`

Syntax for ga module

• x = ga(fun,nvars) finds a local unconstrained minimum, x, to the objective function, fun. nvars is the dimension (number of design variables) of fun.
• x = ga(fun,nvars,A,b) finds a local minimum x to fun, subject to the linear inequalities A*x ≤ b. ga evaluates the matrix product A*x as if x is transposed (A*x').
• x = ga(fun,nvars,A,b,Aeq,beq) finds a local minimum x to fun, subject to the linear equalities Aeq*x = beq and A*x ≤ b. (Set A=[] and b=[] if no linear inequalities exist.) ga evaluates the matrix product Aeq*x as if x is transposed (Aeq*x').
• x = ga(fun,nvars,A,b,Aeq,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. (Set Aeq=[] and beq=[] if no linear equalities exist.)
• x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon) subjects the minimization to the constraints defined in nonlcon. The function nonlcon accepts x and returns vectors C and Ceq, representing the nonlinear inequalities and equalities respectively. ga minimizes the fun such that C(x) ≤ 0 and Ceq(x) = 0. (Set lb=[] and ub=[] if no bounds exist.)
• x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,options) minimizes with the default optimization parameters replaced by values in options. (Set nonlcon=[] if no nonlinear constraints exist.) Create options using optimoptions.
• x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon) or x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon,options) requires that the variables listed in IntCon take integer values.
• x = ga(problem) finds the minimum for problem, where problem is a structure.
• [x,fval] = ga(___), for any previous input arguments, also returns fval, the value of the fitness function at x.
• [x,fval,exitflag,output] = ga(___) also returns exitflag, an integer identifying the reason the algorithm terminated, and output, a structure that contains output from each generation and other information about the performance of the algorithm.
• [x,fval,exitflag,output,population,scores] = ga(___) also returns a matrix population, whose rows are the final population, and a vector scores, the scores of the final population.

PROGRAM CODE

Stalagmite function

function [f] = stalagmite_func(input_vector)

x = input_vector(1);
y = input_vector(2);

f_1_x = (sin(5.1*pi*x + 0.5))^6;
f_1_y = (sin(5.1*pi*y + 0.5))^6;
f_2_x = exp(-4*log(2)*((x-0.0667)^2/0.64));
f_2_y = exp(-4*log(2)*((y-0.0667)^2/0.64));
%ga by default, returns minimum values
%hence'- ve sign' is used to return max values from ga command
[f] = -((f_1_x)*(f_2_x)*(f_1_y)*(f_2_y));        
end

Main program

clear all 
close all 
clc 

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

%values for generating the 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_func(input_vector);
end 
end

%study 1 unbounded 
for k = 1:n
    [ip1, fopt1(k)] = ga(@stalagmite_func,2);
    xopt1(k) = ip1(1);
    yopt1(k) = ip1(2);
end
figure(1)
subplot(2,1,1)
hold on 
surfc(x,y,-f)
shading interp

plot3(xopt1,yopt1, -fopt1,'marker','o','markerfacecolor','r')
xlabel('x values')
ylabel('y values')
title('unbounded plot')

figure(2)
plot(-fopt1)
xlabel('iterations')
ylabel('fopt1')
title('unbounded plot')

%study 2 bounded
for k = 1:n
    [ip2, fopt2(k)] = ga(@stalagmite_func,2,[],[],[],[],[0;0],[1;1]);
    xopt2(k) = ip2(1);
    yopt2(k) = ip2(2);
end
figure(3)
subplot(2,1,1)
hold on 
surfc(x,y,-f)
shading interp

plot3(xopt2,yopt2, -fopt2,'marker','o','markerfacecolor','r')
xlabel('x values')
ylabel('y values')
title('bounded plot')

figure(4)
plot(-fopt2)
xlabel('iterations')
ylabel('fopt2')
title('bounded plot')

%study 3 bounded
options = optimoptions('ga');
options = optimoptions(options,'populationsize',400);
for k= 1:n
    [ip3, fopt3(k)] = ga(@stalagmite_func,2,[],[],[],[],[0;0],[1;1],[],[],options);
    
    xopt3(k) = ip3(1);
    yopt3(k) = ip3(2);
    
end

figure(5)
subplot(2,1,1)
hold on 
surfc(x,y,-f)
shading interp

plot3(xopt3,yopt3, -fopt3,'marker','o','markerfacecolor','r')

figure(6)
plot(-fopt3)
xlabel('iterations')
ylabel('fopt3')

RESULTS

CASE 1

CASE 2

CASE 3

PROCEDURE

1. Input variables (x and y) were created which were one dimensional arrays of 150 equally spaced values between 0 and 0.6 using linspace command and then two dimensional matrix of these variables were created using meshgrid command.
2. Another function named stalagmite was created separately which stores the two input variables and contains equations for output and was called in main program.
3. The results from stalagmite function was stored in another variable (f) and plotted as surface usinf surfc command in MATLAB.
4. "ga" function was used to calculate the maximum value of stalagmite function, but since "ga" command gives minimum value of function provided so some changes had to be made to get desired results, so a '-' sign was used before (f) to get maximum values from "ga" command.
5. Then our code was made to iterate 50 times using 'for loop' to study the statistical behaviour of genetic algorithm with unbounded inputs,bounded inputs, bounded inputs with increasing populations and all these studies are plotted individually using subplot,plot3 and sufc command.
6. In the 1st study GA function runs for 50 iterations. Plots of the stalagmites and maximum values generated in each iteration are shown above.
7. In the 2nd study GA function is incorporated with lower and upper bounds and runs for 50 iterations. Plots of the stalagmites and maximum values generated in each iteration are shown above.
8. In the 3rd study GA function is incorporated with lower and upper bounds along with the population e. Plots of the stalagmites and maximum values generated in each iteration are shown above.

Only minor syntax errors were encountered

CONCLUSION

we were able to succesfully optimize the stalagmite function and find the global maxima of the function using the MATLAB program given above.