Week 4.1 - Genetic Algorithm

Aim ;

Write a code in MATLAB to optimise the stalagmite function and find the global maxima of the function.

Explanation ;

• Genetic Alogorithm :

The genetic algorithm is a method for solving both constrained and unconstrained optimization problems that are based on the natural selection, the process that drives biological evolution.

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

1.Selection rules - select the individual callede parents contribute to the population at the next generation.

2.Crossover rules - combine two parents to form children for the next generation.

3.Mutation rules - apply random changes to individual parents to form the children.

Genetic algorithms are primarily used in optimization problems of various kinds, they a are frequently used in other application areas as well.

The areas in which genetic algorithm are frequentlyused as listed below :

1.Optimization :

Genetic algorithms are most commonly used in optimization problems wherein we have to maximize or minimize a given objective function value under a given set of constraints.

2. Economics :

GAs are used to characterize various economic models like the cobweb model, game theory equilibrium reolution, asset pricing, etc.

3. Neutral Networks :

GAs are used to train neutral networks, particularly recurrent neutral networks.

4. Image processing :

GAs are used for various digital image processing(DIP) tasks as well as dense pixel matching

• FITNESS FUNCTION ;

The fitness function takes the solution as inout and produce the suitability of the solution as the output. The evaluate how close the solution is to be optimal solution of the desired problem.

• SYNTAX EXPALANTION ;

f_min = ga(@function,nvars,A,B,Aeq,Beq,LB,UB,nonlcon,intcon,options)

The syntax is explained as follows :

'x' is the variable to store the output of the genetic algorithm.

'fun' is the function handle to call the function.

'A' and 'B' are used to represent the linear inequalities of the function, if the linear inequalities do not exist, the can be set as empty[].

'lb' and 'ub' are used to specify the upper and the lower bounds of the variables of the function.

'nonlcon' represents the non-linear constraints.

'intcon' represents the integer constraints, such that the value of the function is an integer.

'options' used to provide the value of the default parameters used named parameters, if it is required to replace the default parameters. This is done by using the 'optimioptions'

'f_min' is the local minima point.

'nvars' indicates the no. of variables used.

Same goes with 'Aeq' and 'Beq'.

• STALAGMITE FUNCTION ;

A Stalagmite is an upward-growing mound of mineral deposits that have precipitated from water dripping onto thre floor of a cave. Most stalagmite have rounded of flattened tips.

The following is the given stalagmite function for which we need to find the global maxima.

f(x,y)=f1x.f2x.f1y.f2y

where,

f1x=[sin(5.1πx+0.5)]^6

f1y=[sin(5.1πx+0.5)]^6

f2x=exp[−4ln(2).(x−0.0667)^2/0.64]

f2y=exp[-4ln(2)_.(y-0.0667)^2/0.64]

• PROGRAM FOR STALAGMITE FUNCTION ;

function f = stalagmite(input_vector)

a=input_vector(1);
b=input_vector(2);

f1_x = [sin((5.1*pi*a)+0.5)].^6;
f1_y = [sin((5.1*pi*b)+0.5)].^6;
f2_x = exp(-4*log(2)*(((a-0.667)^2)/(0.64)));
f2_y = exp(-4*log(2)*(((b-0.667)^2)/(0.64)));

f = -(f1_x*f1_y*f2_x*f2_y);
end

• PROGRAM FOR MAIN CODE ;

clear all
close all
clc

% Defining our search space
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
num_cases = 50;
% Creating a 2Dimensional mesh
[xx yy] = meshgrid(x, y);

% Evaluate the stalagmite function
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

tic
% Study 1 - Statistical behaviour with unbounded inputs
for i = 1:num_cases
    [inputs, fopt(i)] = ga(@stalagmite,2);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2);
end
study1_time = toc;

figure(1)
subplot(2,1,1)
surfc(xx,yy,-f)
hold on
xlabel('x value')
ylabel('y value')
shading interp
plot3(xopt,yopt,-fopt,'marker','o','MarkerSize',5,'MarkerFaceColor','r')
title('Unbounded inputs')
subplot(2,1,2)
plot(fopt)
xlabel('Iterations')
ylabel('Function minimum')

tic 
% Study 2 - Statistical behaviour - with upper and lower bounds
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
study2_time = toc;

figure(2)
subplot(2,1,1)
surfc(xx,yy,-f)
hold on
shading interp
plot3(xopt,yopt,-fopt,'marker','o','MarkerSize',5,'MarkerFaceColor','r')
title('Bounded inputs')
subplot(2,1,2)
plot(fopt)
xlabel('Iterations')
ylabel('Function minimum')

% Study 3 - increasing GA iterations
options = optimoptions('ga');
options = optimoptions(options,'PopulationSize',170);

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
study3_time = toc;

figure(3)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
shading interp
plot3(xopt,yopt,-fopt,'marker','o','MarkerSize',5,'MarkerFaceColor','r')
title('Bounded inputs')
subplot(2,1,2)
plot(fopt)
xlabel('Iterations')
ylabel('Function minimum')

• PROGRAM EXPALANATION ;

1. The first code defines the stalagmite function that will be called in main function.

2. The input vectors 'x' and 'y' will be assigned with the required values in the main function.

3. Negative sign used in the last line is used to maximize the stalagmite function.

4. The main code uses the stalagmite function defined to find the global maxima using matlabs in built 'ga' function.

5. First, the search space required to execute the program is defined which varies from 0 to 0.6 with 150 divisions in between.

6. Using meshgrid command, row vectors x and y are converted into matrices xx and yy.

7. With the help of for loop, the input vectors required for stalagmite function are defined using the matrices xx and yy.

8. From here onwards, whole program is divided into three iterations and will be made to run individually.

9. In the first iteration, the behaviour of the algorithm is studied by not defining the limits.

10. In the second iteration, here the limits the lower and upper bounds are defined so as to know boundaries within which the global maxima lies.

11. In the third iteration, last step of the population size is increased so as to converge to the global maxima.

• CONCLUSION ;

The given MATLAB to optimize stalagmite function and find the global maxima function are given code then run sucessfully with plot diagram to be clear executed.