Week 4 - Genetic Algorithm

Aim:- To write a MATLAB code to find the global maxima of a stalagmite function and optimize it.

Objective:-

1. To write a Matlab code to optimize a stalagmite function and to find the global maxima.
2. The explanation for the genetic algorithm and the syntax for ga in MATLAB program.

Theory:- A genetic algorithm (ga) is a method for solving both constrained and unconstrained optimization problems based on a natural selection process that mimics biological evolution. The algorithm repeatedly modifies a population of individual solutions. At each step, the genetic algorithm randomly selects individuals from the current population and uses them as parents to produce the children for the next generation. Over successive generations, the population "evolves" toward an optimal solution.

The genetic algorithm can be used to solve problems that are not well suited for standard optimization including problems where the objective function is highly nonlinear and discontinuous.

A typical genetic algorithm requires:

1.a genetic representation of the solution domain,

2.a fitness function to evaluate the solution domain.

Syntax for genetic algorithm

x = ga(fun,nvars)

x = ga(fun,nvars,A,b)

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

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

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

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

x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon)

x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon,options)

x = ga(problem)

[x,fval] = ga(___)

[x,fval,exitflag,output] = ga(___)

[x,fval,exitflag,output,population,scores] = ga(___)

Function Formula

ga syntax

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

The syntax defines a set of lower bound and upper bound on variable x. The solution is found in the range Lb<x<Ub.

x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon,options)

The syntax minimizes with the default optimization parameters replaced by values in options. (Set nonlcon=[] if no nonlinear constraints exist.)

Governing equation

F(x,y)=f1x,f1y,f2x,f2y

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

f1y=[sin(5.1`pi`y+0.5)]^6

f2x=exp[-4ln(2)((x-0.0667)^2)/0.65)]

f2y=exp[-4ln(2)((y-0.0667)^2)/0.65)]

MATLAB Code for optimization

Function code

function [f]=stalagmite(input_vector)
x=input_vector(1);
y=input_vector(2);


f_1x=(sin(5.1*pi*x+0.5))^6;
f_1y=(sin(5.1*pi*y+0.5))^6;
f_2x=exp(-4*log(2)*(x-0.0667)^2/0.64);
f_2y=exp(-4*log(2)*(y-0.0667)^2/0.64);

f=-(f_1x*f_2x*f_1y*f_2y);
end

clear all
close all
clc


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



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


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
figure(1)
surfc(xx,yy,-f)
shading interp
hold on
xlabel('x value')
ylabel('y value')
title('stalagmite')
num_cases=50;
% Study 1
tic
for i=1:num_cases
    [input, fopt(i)]=ga(@stalagmite,2);
    xopt(i)= input(1);
    yopt(i)= input(2);
end
study1_time=toc
figure(2)
subplot(2,1,1) %having multiple plots in same figure window
surfc(x,y,f)
shading interp
hold on
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','r') % to check how the ga is performing
title('unbound inputs')
subplot(2,1,2)
plot(-fopt)
xlabel('Iterations')
ylabel('Function minimum')


tic
%study 2 bound inputs

for j=1:num_cases
    [input ,fopt(j)]=ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6]);
    xopt(j)=input(1);
    yopt(j)=input(2);
end
study2_time=toc

figure(3)
subplot(2,1,1)
surfc(x,y,f)
shading interp
hold on
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','r') % to check how the ga is performing
title('Bound inputs')
subplot(2,1,2)
plot(-fopt)
xlabel('Iterations')
ylabel('Function minimum')

tic
%study 3
options=optimoptions('ga')
options=optimoptions(options,'Populationsize',200)

for l=1:num_cases
    [inputs,fopt(l)]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options)
    xopt(l)=input(1);
    yopt(l)=input(2);
end
study3_time=toc
figure(4)
subplot(2,1,1)
surfc(x,y,f)
shading interp
hold on
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','r') % to check how the ga is performing
title('Bound inputs with modified pupulation size')
subplot(2,1,2)
plot(-fopt)
xlabel('Iterations')
ylabel('Function minimum')

Code Explanation

1. First, the code for the stalagmite function is defined. The code consists of the above formulas.
2. We then write the main script. The first lines include commands to close and clear predefined variables. We then define the x and y coordinates in the form of 1 dimensional matrix
3. Using meshgrid command we get the 2D array with x and y as inputs
4. We then use a loop with the 2d array in the stalagmite function. An error will occur as for every time the code is executed, the value changes. Thus another loop is introduced in the code
5. (ga) solver is used and the code is executed.
6. Three cases are undertaken to improve the algorithm. This is done since ‘ga’ takes random values and the global maxima are calculated accordingly.
7. For case 1 global maxima for all possible iterations are evaluated in the loop. Two figures are plotted using subplot command. Surfc is used for x vs y plot and max vs iteration is plot using plot command. The value is said to be unbound.
8. For case 2 we put an upper bound and a lower bound in the ga function. The same procedure is followed for the plot.
9. For case 3 we increase the ga iterations. We do this because, after every ga iteration, the population evolves towards an optimal solution. The same procedure for plotting graphs is used.
10. Tic and tok command is used to record the time taken to sole all three cases

Plots

Case 1

Case2

Case3

Errors

1. Typing error which was rectified during code execution

2. Missing the negative sign in the function code. Thus giving error during the output as ga is used to fine minima.

References

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

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

https://in.mathworks.com/help/gads/what-is-the-genetic-algorithm.html

Conclusions

Study time for case 1= 4.1063

Study time for case 2= 4.0076

Study time for case 3 = 10.8901