Optimization of a genetic algorithm in Matlab

Question:

I need to implement an optimization problem using Genetic Algorithm to help me determine the distribution of ones by rows and by columns of an LDPC matrix.

You can find more information about it, as well as the definitions of the cost function and the constants in the following text, at the end of chapters 7.7.2 and 7.7.3 .

Following the documentation for the ga function in Mathworks I discovered a few examples that seemed to be enough to solve my problem. More specifically, I decided to follow the following and in this way I have two functions defined in my program to declare both the cost function and the non-linear constraints, respectively:

Cost function

Defined in the CostFunction.m file.

function y = CostFunction(l)
D = 26; % Dimension of the parameter vector l to be optimized
L = D/2;
y = (sum(l((L+1):D)./(1:L)))/(sum(l(1:L)./(1:L)));
end

Nonlinear constraints

Defined in the NonLinConstr.m file.

function [c, ceq] = NonLinConstr(l)

syms x;
L = 13;
R = 13;
D = L+R;

X = x.^(0:(R-1));
R = l(L+1:D)*transpose(X);

error = 0.485;
divisions = 200;
rate = 0.5;

Aj = zeros(1, divisions);
rho = zeros(1, divisions);
xj = zeros(1, divisions);

for j=1:1:divisions
    xj(j) = error*j/divisions;
    rho(j) = subs(R,x,1-xj(j));
    Aj(j) = 1 - rho(j);
end

c = zeros(1, length(xj));
lambda = zeros(1, length(Aj));
for j = 1:1:length(xj)
    lambda(j) = sum(l(2:L).*(Aj(j).^(1:(L-1))));
    c(j) = error*lambda(j) - xj(j);
end
ceq = [];
% ceq = (sum(l((L+1):D)./(1:R)))/(sum(l(1:L)./(1:L))) - (1-rate);
% For some reason I can't explain, the line above does not seem to work out.
end

Executable code: setting the optimization problem

Defined in the GenAlg.m file.

clear;clc
tic
L = 13;
R = 13;
D = L+R;

options = optimoptions(@ga,'MutationFcn',@mutationadaptfeasible,'Display','iter');

ObjectiveFunction = @CostFunction;
nvars = D;    % Number of variables

A = [];
B = [];
Aeq = [0, ones(1,L-1), zeros(1,L); 0, ones(1,R-1), zeros(1,L)];
beq = [1;1];
LB = zeros(1,D);   % Lower bound
UB = [0 ones(1,L-1) 0 ones(1,R-1)];  % Upper bound
ConstraintFunction = @NonLinConstr;
IntCon = [];
[x, fval] = ga(ObjectiveFunction,nvars,A,B,Aeq,beq,LB,UB,ConstraintFunction, [], options);
toc

After this, although my code manages to run without any apparent problem, it takes too long to perform all the calculations it needs (in fact, it has been running for a whole day to complete only two iterations).

At first glance I thought that the problem could be in the large number of non-linear constraints that I have used (a total of 201). However, changing the value of the divisions parameter (which in fact should be large to get the estimated error at good "resolution" does not show any difference.

The Mathworks example, with only two parameters to optimize instead of my 26, runs perfectly after four iterations on my computer. Of course I am not expecting to achieve the same benefits in my case, but I would like it to be done in a matter of minutes, not much more. Does this fact have something to do with a limitation of the algorithm itself, is there something weird in my code?

Answer:

The function used, GA, is not the first time that it shows this type of behavior, especially when you use so many variables and conditions.

In the English help, I find this link: https://en.mathworks.com/matlabcentral/answers/274996-genetic-algorithm-taking-too-long-to-optimize

And mainly, a source of optimizations is to use persistent variables within your functions

http://es.mathworks.com/help/matlab/ref/persistent.html

Try using this type of modifier in your functions and if it improves performance.

All the best.

Scroll to Top