Week 5 - Genetic Algorithm
Objective
- To write a code in MATLAB to optimise the stalagmite function and find the global maxima of the function.
- To clearly expalin the concept of genetic algorithm in your own words and also explain the syntax for ga in MATLAB in your report.
- To make sure that your code gives the same output, even if it is made to run several times.
- To make plot graphs for all 3 studies and for F maximum vs no. of iterations
Theory
Optimisation -
The process of optimisation is related to best use of data for making effective decisions based on observed points. The reliability of the decision-making process is validated and other "errors" in decision-making process can be minimised to improve the efficiency of the optimisation process. "Objective", "Variable" and "Constraints" are three main areas of consideration in any optimisation problem.
Areas of application of optimisation -
Broader application of optimisation can be found in automotive, aerospace, data mining, economic and finance markets and other industries.
Optimisation algorithm -
Some specific algorithms are written to tackle the problems of optimisation in MATLAB. Different types of optimisation algorithm are used in industry. Some of the types are described below.
Population algorithm -
The algorithm that includes set of candidate data and the generation of unique solution that can be met with the necessary condition of search space is known as population based algorithm. Some of the population based algorithms are:
1. Genetic Algorithm (GA)
2. Differential Evolution
3. Particle Swarm Optimisation
Genetic Algorithm:
Genetic Algorithm is an example of optimisation algorithm. The genetic algorithm is a method for solving both constrained and unconstrained optimization problems that is based on natural selection, the process that drives biological evolution. The method is inspired from the Darwin's theory and has been used for finding optimal solutions while using functions such as stalagmite function.
Working phases for Genetic Algorithm:
a) Start, b) Initialisation, c) Evaluation, d) Selection, e) Crossover, f) Mutation, g) Optimisation and h) Termination
Syntax of GA:
x = ga(fun, nvar, A, b, Aeq, beq, Lb, Ub, nonlcon, options)
fun = objective functions
nvar = number of variables
A,b = linear inequality constraints
Aeq, beq = linear equality constraints
Lb, Ub = Lower bounds and Upper bounds
nonlcon = Non-linear constraints
options = optimisation options
Global Maxima:
The global maxima of a given function can be considered as the largest overall value of a set or a function based on the data obtained from the entire range.
Stalagmite function:
It is an mathematical function used for optimisation and deals with finding maximum value for any given function. The shape of the function represents shapes found in the cave floor. It is often studied together with "stalactite function" which behaves in the reverse manner. The equations for the stalagmite function are given as: -
Code
//Code 1
// Code for stalagmite function
function[f] = stalagmite(inputs)
x = inputs(1);
y = inputs(2);
f1x = (sin((5.1*pi*x)+0.5)).^6;
f1y = (sin((5.1*pi*y)+0.5)).^6;
f2x = exp(-4*log(2)*(((x-0.0667).^2/0.64)));
f2y = exp(-4*log(2)*(((y-0.667).^2/0.64)));
f = -(f1x*f1y*f2x*f2y);
end
//Code 2
// Code to find out Global Maxima
clear all
close all
clc
x = linspace (0,0.6,150);
y = linspace (0,0.6,150);
%Creating a 2D mesh
[xx,yy] = meshgrid (x,y);
% Number of times the GA will run
num_case = 50;
%assingning values to inputs
for i = 1:length(xx)
for j = 1:length(yy)
inputs(1) = xx(i,j);
inputs(2) = yy(i,j);
f(i,j) = stalagmite (inputs);
end
end
%unbounded GA study, Case 1
for k = 1:num_case
[inputs,fopt(k)] = ga(@stalagmite,2);
xopt(k) = inputs(1);
yopt(k) = inputs(2);
end
tic
figure(1)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
shading interp
plot3(xopt,yopt,-fopt,'color','b','marker','o','markersize',5,'markerfacecolor','r')
title('unbounded inputs')
subplot(2,1,2)
plot(-fopt,'color','b','linewidth',1)
xlabel('iterations')
ylabel('function maximum')
study1_time = toc
%Bounded GAstudy case 2
tic
for z = 1:num_case
[inputs,fopt(z)] = ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6]);
%difines a set of of lbn and ub on the designated variable
xopt(z) = inputs(1);
yopt(z) = inputs(2);
end
study2_time = toc
figure(2)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
shading interp
plot3(xopt,yopt,-fopt,'color','b', 'marker', 'o', 'markersize', 5, 'markerfacecolor', 'r');
title('bounded inputs')
subplot(2,1,2)
plot(-fopt,'color','b','linewidth',1)
xlabel('iterations')
ylabel('function maximum')
%Bounded with population case3
options = optimoptions('ga','PopulationSize',270);
tic
for z = 1:num_case
[inputs,fopt(z)] = ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6],[],[],options);
% takes the values of options and solve ga in required population
xopt(z) = inputs(1);
yopt(z) = inputs(2);
end
study3_time = toc
figure(3)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
shading interp
plot3(xopt,yopt,-fopt,'color','b', 'marker', 'o', 'markersize', 5, 'markerfacecolor', 'r');
title('bounded inputs increased population size')
subplot(2,1,2)
plot(-fopt,'color','b','linewidth',1)
xlabel('iterations')
ylabel('function maximum')
Code Explanation
Writing scripts for objective function:
Four standard equations for used for operating the stalagmite function. It is a method of optimising the results with the help of better definition of variables and constraints. This function is one of the 'Test Function' whuch is used to validate the performance characteristics of the optimization algorithms.
Evaluating the function with the commands
'linspace' command is used to create 150 divisions of the given data(a range of 0 to 0.6). Then, 'meshgrid(x,y)' command is used to create a 2D mesh or array for including data. In order to run the program for 50 times, 'num_cases' command is used.
After that, the foor loop is created to evaluate the objective function. Using a for loop will be helpful to cover the 2D input (both x & y). For every point in xy plane stalagmite function will be called to calculate the 'f' value.
In the case 1, the values for global maxima is being found out. The use of 'fopt' for optimum conditions has been critical in this area. The main purpose of the command is to ensure better optimistion. On the other hand, @ has been used as a anonymous function.
In the case 2, the values have been generated with due specification of upper bounds and lower bounds of GA. It has generated results with greater accuracy and higher stability.
In the case 3, the population size is increased to 270 and the 'optimoption' command is used to complete the case.
'surfc': this command is used to produce a contour plot that will be applicabe for 3D geometry.
'shading interp': this command is used to achieve a clear and well defined 3D figure of the plot.
'study_time=toc....tic': this command is used for specifying and understanding running time of the program.
'marker', 'markersize', 'markerfacecolor': The commands are used to specify the bullet points as marker impression along with specifying the size of impression and colour of the marked area.
'x label' and 'y label': the marking on the x-axis and y-axis of the plot respectively are written with the help of these commands.
'plot': this command is used to generate the graph between given variables.
'hold on': this command is used to stop the generation of new figures or hold a figure until the next corresponding command appears.
Output
Output Figure 1, Title: Unbounded inputs. In this case, the upper and lower bounds of GA syntax are not defined, as a result, there is a high probability of acquiring outputs with low accuracy and unstability.
Output Figure 2, Title: Bounded inputs, In this case, upper and lower bounds of the GA syntax are defined for obtaining better optimisation results with the help of given GA program.
Output Figure 3, Title: Bounded inputs with increased population size, In this case, apart from defining the upper and lower bounds of the GA syntax, the population size is also increased to 270 for obtaining better output.