Week 4 - Genetic Algorithm using Matlab

Aim- Write a code in MATLAB to optimise the stalagmite function and find the global maxima of the function and expalin the concept of genetic algorithm in your own words and also explain the syntax for ga in MATLAB in your report.

Theory- Genetic Algorithm is a tool used to find optimal or new-optimal solutions to contrained or unconstrained problems , so first of all we will look at about Optimization.

Optimization- It is the proceess of making something better in any process, for which we have a set of inputs and a set of outputs. Optimization refers to finding the values of inputs in such a way that we get the 'best' output values. The definition of 'best' varies from problrm to problem, but in mathematical term, it refers to maximizing or minimizing one or more objective function, by varying the input parameters. The set of all possible solutions or values which the inputs can take make the search space. In this search space, lies a point or a set of points which gives the optimal solution. The aim of optimization is to find that point or set of points in the search space.

Stalagmite Function- A Stalagmite function generally refers to the function with which we are generating values over a stalagmite kind of surface for finding out the Local and Global Maxima and Minima of tha particular given function. For this in Matlab we are using a method called 'Optimization'. It is a programming which does a selection of the best element with regard to some criterion from some set of population. Optimization is done by systematically choosing input variables from within an allowed set and computing the results of the function. In Matlab to perform Optimization we use "Genetic Algorithm" method which is a inbuid function in Matlab to find the global maxima of that stalagmite function.

Genetic Algorithm(GA)- It is a search based optimization technique based on the principles of Genetics and natural selection. It is frequently used to find optimal or new-optimal solutions to difficult problems which otherwise would take a lifetime to solve it. It is frequently used to solve optimization problems on research and in machine learning. GAs are a subset of a much larger branch of computation known as Evolutionary Computation. In GAs we have a pool or a population of possible solution to the given problem. These solutions than undergo recombination and mutation (like a natural genetics), producing neww children, and the process is repeated over various generations. Eacg individual (or candidate solution) is assigned a fitness value (based on its objective function value) and the fitter individuals are given a higher chance to mate and yiels more 'Fitter' individuals. In this way we keep 'evolving' better individuals or solutions over generations, till we reach a stopping criterion. Genetic Algorithms are sufficiently randomized in nature, but they perform much better than random local search(in which we just try various random solutions, keeping track of the best so far), as we explicit historical information as well

Syntax for 'ga' in Matlab

• x = ga(fun,nvars) %find a local unconstrained minimum, x, to the objective function, fun. nvars is the dimension (number of design variables) of func.
• x = ga(fun,nvars,A,b) %find a local minimum x to fun, subject to linear inequilities 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) %find a local minimum x to fun, subject to linear inequilities 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,Ib,ub) % Defines a set of lower and upper bounds on the design variables x, so that a solution is found in the range Ib ≤ x ≤ ub. {Set Aeq=[] and beq=[] if no linear inequalities exist}
• x= ga(fun,nvars,A,b,Aeq,beq,Ib,ub,nonlcon) % Subjects the minimization of the constraints defined in a 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 Ib=[] and ub=[] if no bounds exist}
• x = ga(fun,nvars,A,b,Aeq,beq,Ib,ub,nonlcon,options) % Minimizes the default optimization parameters replaced by values in options. {Set nonlcon=[] if no nonlinear constraints exist) Creat options using optimoptions.
• x = ga(fun,nvars,A,b,[],[],Ib,ub,nonlcon,Intcon) % or x = ga(fun,nvars,A,b,[],[],Ib,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(_)≤ % ga(___), for any previous input arguments, also returns fval, the value of the fitness function at x.
• [x,fval,exitflag,output] = ga(_) % 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.

1) x=optimum solution/variables

2) no_of_variables=Number of variables, specified as a positive integer

3) A,b= Linear inequality constraints

For example, to specify

2x1 + 2x2 ≤ 13

x1 - x2 ≤ 20

x1 + 3x2 ≤ 30

give these constraints:

A = [2,2;1,-1;1,3]

b = [13;20;30]

4) Aeq,beq=Linear equality constraints

For example, to specify

2x1 + 2x2 = 13

x1 - x2 = 20

x1 + 3x2 = 30

give these constraints:

Aeq = [2,2;1,-1;1,3]

beq = [13;20;30]

5) lb,ub

lb=Lower bounds

ub=Upper bounds

For example, to specify

1 <= x(1) <= 6

-3 <= x(2) <= 8

give these constraints:

lb=[1 -3]

ub=[6 8]

6) nonlcon : Use for nonlinear constraints (We will see this in another program)

7) IntCon : to get solution in integer.

8) options: Minimize with non default options (Refer below program)

options = optimoptions('function','Constraint',limit,);

PROGRAM IN MATLAB

A) STALAGMITE FUNCTION CODE

% STEP 3
function [f]=stalagmite(input_vector)

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


f1 = (sin(5.1*pi*x + 0.5)).^6 ;
f2 = exp(-4*log(2)*((x-0.0667).^2)./0.64) ;
f3 = (sin(5.1*pi*y + 0.5)).^6 ;
f4 = exp(-4*log(2)*((y-0.0667).^2)./0.64) ;

f = -(f1*f2*f3*f4);

end

B)PROGRAM FOR GLOBAL MAXIMA

% STEP 1
clear all
close all
clc


x = linspace(0,0.6,150);
y = linspace(0,0.6,150);


% STEP 2
% converting 1D array into 2D array

[xx yy] = meshgrid(x,y);
rep = 50;

tic

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

% STEP 4
study_time = toc

surfc(xx,yy,-f)
shading interp
xlabel('x value')
ylabel('y value')
title('STALAGMITE FUNCTION')




%------------------------------------------------------------------------

% STEP 5
% STUDY 1 UNBOUNDED

tic

for i = 1:rep
    
    [inputs,fopt(i)] = ga(@stalagmite,2);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2);
    
end

study_time1 = toc

figure(1)
subplot(2,1,1)
hold on
surfc(x,y,-f)
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 maximum')




% ----------------------------------------------------------------
% STEP 6
% STUDY 2 Bounded

tic

for i = 1:rep
    
    [inputs,fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6]);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2);
    
end

study_time2 = toc

figure(2)
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r');
title('OPTIMUM SOLUTION')
subplot(2,1,2)
plot(-fopt)
xlabel('iterations')
ylabel('function maximum')


%-----------------------------------------------------------------------
% STEP 7
% STUDY 3 Increased Initial Population

options = optimoptions(@ga)
options = optimoptions(options,'populationsize',170);


tic
for i=1:rep
    
    [inputs,fopt(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2);
    
end

study_time3 = toc

figure(3)
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r');
title('OPTIMUM SOLUTION')
subplot(2,1,2)
plot(-fopt)
xlabel('iterations')
ylabel('function maximum')

global_maxima = -fopt

RESULTS

CONCLUSION- All the explanations for the output graphs is given with the program explanation section individually.

ERRORS FACED DURING PROGRAMMING

1) A minor mistake as shown in fig in line 50 was done while using ga, in writing the stalagmite

Correction - As to correct it the stagalmite is fixed with stalagmite.

REFERENCES

https://en.wikipedia.org/wiki/Genetic_algorithm

https://in.mathworks.com/help/gads/ga.html#d120e39200

https://www.mathworks.com/discovery/genetic-algorithm.html

https://www.slideshare.net/Raktim21/genetic-algorithm-raktim