9

Necesito implementar un problema de optimización mediante Genetic Algorithm para ayudarme a determinar la distribución de unos por filas y por columnas de una matriz LDPC.

Podéis encontrar más información al respecto, así como las definiciones de la function de coste y las constantes en el siguiente texto, al final de los capítulos 7.7.2 and 7.7.3.

Siguiendo la documentación de la function ga en Mathworks descubrí algunos ejemplos que parecían ser suficientes para resolver mi problema. Más concretamente decidí seguir el siguiente y de este modo tengo dos funciones definidas en mi programa para declarer tanto la function de coste como las restricciones no lineales, respectivamente:

Función de coste

Definida en el archivo CostFunction.m.

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

Restricciones no lineales

Definidas en el archivo NonLinConstr.m.

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

Código ejecutable: establecimiento del problema de optimización

Definido en el archivo GenAlg.m.

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

Tras esto, aunque mi código consigue ejecutarse sin problema aparente, tarda demasiado en realizar todos los cálculos que necesita (de hecho, lleva corriendo durante un día entero para completar sólo dos iteraciones).

A primera vista pensé que el problema podría estar en el gran número de restricciones no lineales que he utilizado (un total de 201). Sin embargo, al cambiar el valor del parámetro divisions (el cual de hecho debería ser grande para obtener el error estimado a una buena "resolución" no se observa ninguna diferencia.

El ejemplo de Mathworks, con sólo dos parámetros que optimizar en lugar de mis 26 se ejecuta perfectamente tras cuatro iteraciones en mi ordenador. Por supuesto no estoy esperando alcanzar las mismas prestaciones para mi caso, pero sí desearía que se realizase en cuestión de minutos, no mucho más. ¿Tiene este hecho algo que ver con una limitación del propio algoritmo, hay algo raro en mi código?

1 respuesta 1

1

La función usada, GA, no es la primera vez que muestra este tipo de comportamiento, sobre todo, cuando usas tantísimas variables y condiciones.

En la ayuda inglesa, encuentro este enlace: https://es.mathworks.com/matlabcentral/answers/274996-genetic-algorithm-taking-too-long-to-optimize

Y principalmente, una fuente de optimizaciones viene a ser el usar variables persistentes dentro de tus funciones

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

Prueba a utilizar este tipo de modificadores en tus funciones y si mejora el rendimiento.

Un saludo.

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.