Week 4 - Genetic Algorithm

Aim : Write a code in MATLAB to optimize the stalagmite function and find the global maxima of the function.

Introduction : In computer science and operations research, a genetic algorithm (GA) is a metaheuristic inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms (EA). Genetic algorithms are commonly used to generate high-quality solutions to optimization and search problems by relying on biologically inspired operators such as mutation, crossover and selection. John Holland introduced genetic algorithms in 1960 based on the concept of Darwin’s theory of evolution; his student David E. Goldberg further extended GA in 1989.

Genetic algorithm is used to solve optimization problems across many industries like engineering, logistics and transportation. There are many optimization tools but genetic algorithm (ga) is widely used because of it’s simplicity and easy application to wide range of optimization problems.

In Natural Evolution, species evolve based on three concepts,

1. Reproduction
2. Mutation
3. Survival of fittest

Equations Used :

The Function We need to maximize is represented by,

`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)(y-0.0667)^2/0.64]`

Syntax of genetic algorithm in MATLAB :

Find minimum of function using genetic algorithm.

In matlab by default we can find minimum value of the given function using genetic algorithm optimization technique.

In This problem we have to find out Maximum of the function it can be achieved by simply multiplying (-1) to given function.

Different syntax types :

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) 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 non lcon. The function non lcon 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 non lcon=[] if no nonlinear constraints exist.) Create options using optim options.

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.

Note

When there are integer constraints, ga does not accept linear or nonlinear equality constraints, only inequality constraints.

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 exit flag, 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.

Steps of Program :

Step 1 : Coding for Stalagmite Function(Defining Stalagmite function)

function f =stalagmite(input_vector)

x = input_vector(1)

y = input_vector(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.0667)^2/0.64));

f= -(f1x*f1y*f2x*f2y); % '-VE' sign is used to get maximum of the function

end

Step 2 : Defining Input array and input vector

% Let us clear & close any previous plots or code by using these cammands.

clear all

close all

clc

%creating 1D array (Input array)

%Note : This does not define the search space for genetic algorithm

x=linspace(0,0.6,150)

y=linspace(0,0.6,150)

% No of iteration i.e., how many times should ga to be run

num_cases=50;

%creating 2D array

%use meshgrid command to get 2D array from 1D array

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

for k=1:length(xx)

for m=1:length(yy)

input_vector(1)=xx(k,m);

input_vector(2)=yy(k,m);

f(k,m)=stalagmite(input_vector);

end

end

Step 3 : Coding for optimization

%Study 1 : stastical behavior

%Use tic & toc command to note timing for optimization

tic

for k=1:num_cases;

[inputs,fopt(k)]=ga(@stalagmite,2);

xopt(k)=inputs(1);

yopt(k)=inputs(2);

end

study_time1 = toc

%plotting unbounding conditions

figure(1);

subplot(2,1,1);

surfc(xx,yy,-f);

hold on;

shading interp;

plot3(xopt,yopt,-fopt,'Marker','o','Markersize',5,'Markerfacecolor','r');

subplot(2,1,2);

plot(-fopt);

xlabel('No of iterations');

ylabel('Function maximum');

title('Unbounding Condition');

Step 4 : Coding for optimization by increasing iterations

%Study 3 : Increasing GA Iterations

figure(3);

options = optimoptions('ga');

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

tic

for k=1:num_cases

[inputs,fopt(k)]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);

xopt(k)=inputs(1);

yopt(k)=inputs(2);

end

study_time3 = toc

figure(3);

subplot(2,1,1);

surfc(xx,yy,-f);

hold on;

shading interp;

plot3(xopt,yopt,-fopt,'Marker','o','Markersize',5,'Markerfacecolor','r');

subplot(2,1,2);

plot(-fopt);

xlabel('No of iterations');

ylabel('Function maximum');

title('Increasing GA Iterations');

Body of the Program :

01. Stalagmite Function

function f =stalagmite(input_vector)
x = input_vector(1)
y = input_vector(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.0667)^2/0.64));
f= -(f1x*f1y*f2x*f2y);
end

02. Main Program for Optimization for 3 different study.

% Topic :  Write a code to optimize the stalagmite function and find the global maxima of the function.
% Let us clear & close any previous plots or code by using these cammands.
clear all 
close all
clc

%creating 1D array (Input array)
%Note : This does not define the search space for genetic algorithm
x=linspace(0,0.6,150)
y=linspace(0,0.6,150)
% No of iteration i.e., how many times should ga to be run
num_cases=50;

%creating 2D array
%use meshgrid command to get 2D array from 1D array
[xx,yy]= meshgrid(x,y)

for k=1:length(xx)
    for m=1:length(yy)
        input_vector(1)=xx(k,m);
        input_vector(2)=yy(k,m);
        f(k,m)=stalagmite(input_vector);
    end
end
%Study 1 : stastical behaviour
%Use tic & toc command to note timing for optimization.
tic
for k=1:num_cases;
[inputs,fopt(k)]=ga(@stalagmite,2);
xopt(k)=inputs(1);
yopt(k)=inputs(2);
end
study_time1 = toc
%plotting unbounding conditions
figure(1);
% Subplotting is used to divide a Single plot into multiple
subplot(2,1,1);
%Surface plotting
surfc(xx,yy,-f);
hold on;
shading interp;
% 3-D point or line plotting
plot3(xopt,yopt,-fopt,'Marker','o','Markersize',5,'Markerfacecolor','r');
subplot(2,1,2);
plot(-fopt);
% Naming X & Y co-ordinates
xlabel('No of iterations');
ylabel('Function maximum');
title('Unbounding Condition');

%Study 2 : stastical behaviour using upper and lower bonds
tic;
    for k=1:num_cases;
[inputs,fopt(k)]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
xopt(k)=inputs(1);
yopt(k)=inputs(2);
    end
study_time2 = 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');
subplot(2,1,2);
plot(-fopt);
xlabel('No of iterations');
ylabel('Function maximum');
title('bounding Condition');

%Study 3 : Increasing GA Iterations

figure(3);
options = optimoptions('ga');
options = optimoptions(options,'populationsize',170);
tic
for k=1:num_cases
[inputs,fopt(k)]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
xopt(k)=inputs(1);
yopt(k)=inputs(2);
end
study_time3 = toc
figure(3);
subplot(2,1,1);
surfc(xx,yy,-f);
hold on;
shading interp;
plot3(xopt,yopt,-fopt,'Marker','o','Markersize',5,'Markerfacecolor','r');
subplot(2,1,2);
plot(-fopt);
xlabel('No of iterations');
ylabel('Function maximum');
title('Increasing GA Iterations');

Outputs :

Study 1 : stastical behaviour - Unbouding Condition

Study Time - 48.7143 sec

Study 2 : stastical behaviour - Upper & lower bound

Study Time - 39.3513 sec

Study 3 : stastical behaviour - Increasing Number of GA iterations

Study Time - 91.7830 sec.

For (x,y) = (0.06682 0.06684) we got the function optimum value as 1. That is Maximum value for the give equation.

Errors :

01. Unrecognized function or variable 'ln'.

Problem : MATLAB consist of built in function 'log' not a 'ln'.

Action : I corrected by mistake and changed my coding to 'log' in place of 'ln'.

02. 'ga' requires Global optimization toolbox.

Problem : Global optimization toolbox is not installed in my PC.

Action : Installed Global optimization toolbox and after that run the code problem solved.

Conclusion :

• This is all about how optimize given function using MATLAB.
• Remember ga in matlab gives minimum value of the function we need to convert it into maximum value by multiplying (-1) to given function.

Referances :

• Wikipedia
• Youtube Letures on genetic algorithm
• Skill Lync