Definición de un problema de optimización mediante algoritmo genetico
Publicado por Aitor (49 intervenciones) el 09/02/2017 18:32:02
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 (http://read.pudn.com/downloads144/ebook/626798/Differential%20Evolution_A%20Practical%20Approach%20to%20Global%20Optimization.pdf).
Siguiendo la documentación de la function ´ga´ en Mathworks descubrí algunos ejemplos (https://de.mathworks.com/help/gads/examples/constrained-minimization-using-the-genetic-algorithm.html?prodcode=ML) 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.
Restricciones no lineales
Definidas en el archivo NonLinConstr.m.
Código ejecutable: establecimiento del problema de optimización
Definido en el archivo GenAlg.m.
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...? Alguien puede ayudarme?
Muchas gracias de antemano y que tengáis todos un buen día!
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 (http://read.pudn.com/downloads144/ebook/626798/Differential%20Evolution_A%20Practical%20Approach%20to%20Global%20Optimization.pdf).
Siguiendo la documentación de la function ´ga´ en Mathworks descubrí algunos ejemplos (https://de.mathworks.com/help/gads/examples/constrained-minimization-using-the-genetic-algorithm.html?prodcode=ML) 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.
1
2
3
4
5
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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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.
endCódigo ejecutable: establecimiento del problema de optimización
Definido en el archivo GenAlg.m.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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...? Alguien puede ayudarme?
Muchas gracias de antemano y que tengáis todos un buen día!
Valora esta pregunta
0