Minimizar un problema de optimización costoso utilizando Parallel Computing Toolbox
En este ejemplo se muestra cómo acelerar la minimización de un problema de optimización costoso utilizando funciones de Optimization Toolbox™ y Global Optimization Toolbox. En la primera parte del ejemplo, resolvemos el problema de optimización evaluando las funciones de manera secuencial, y en la segunda parte del ejemplo, resolvemos el mismo problema utilizando la funcionalidad de bucle paralelo (parfor), evaluando las funciones en paralelo. En ambos casos, comparamos el tiempo que tarda la función de optimización.
Problema de optimización costoso
Para este ejemplo, resolvemos un problema en cuatro variables, donde las funciones objetivo y de restricción se hacen costosas artificialmente poniéndolas en pausa.
function f = expensive_objfun(x) %EXPENSIVE_OBJFUN An expensive objective function used in optimparfor example. % Copyright 2007-2013 The MathWorks, Inc. % Simulate an expensive function by pausing pause(0.1) % Evaluate objective function f = exp(x(1)) * (4*x(3)^2 + 2*x(4)^2 + 4*x(1)*x(2) + 2*x(2) + 1);
function [c,ceq] = expensive_confun(x) %EXPENSIVE_CONFUN An expensive constraint function used in optimparfor example. % Copyright 2007-2013 The MathWorks, Inc. % Simulate an expensive function by pausing pause(0.1); % Evaluate constraints c = [1.5 + x(1)*x(2)*x(3) - x(1) - x(2) - x(4); -x(1)*x(2) + x(4) - 10]; % No nonlinear equality constraints: ceq = [];
Minimizar empleando fmincon
Nos interesa calcular el tiempo que fmincon tarda en serie para poder compararlo con el tiempo en paralelo.
startPoint = [-1 1 1 -1]; options = optimoptions('fmincon','Display','iter','Algorithm','interior-point'); startTime = tic; xsol = fmincon(@expensive_objfun,startPoint,[],[],[],[],[],[],@expensive_confun,options); time_fmincon_sequential = toc(startTime); fprintf('Serial FMINCON optimization takes %g seconds.\n',time_fmincon_sequential);
First-order Norm of
Iter F-count f(x) Feasibility optimality step
0 5 1.839397e+00 1.500e+00 3.211e+00
1 11 -9.760099e-01 3.708e+00 7.902e-01 2.362e+00
2 16 -1.480976e+00 0.000e+00 8.344e-01 1.069e+00
3 21 -2.601599e+00 0.000e+00 8.390e-01 1.218e+00
4 29 -2.823630e+00 0.000e+00 2.598e+00 1.118e+00
5 34 -3.905338e+00 0.000e+00 1.210e+00 7.302e-01
6 39 -6.212992e+00 3.934e-01 7.372e-01 2.405e+00
7 44 -5.948761e+00 0.000e+00 1.784e+00 1.905e+00
8 49 -6.940062e+00 1.233e-02 7.668e-01 7.553e-01
9 54 -6.973887e+00 0.000e+00 2.549e-01 3.920e-01
10 59 -7.142993e+00 0.000e+00 1.903e-01 4.735e-01
11 64 -7.155325e+00 0.000e+00 1.365e-01 2.626e-01
12 69 -7.179122e+00 0.000e+00 6.336e-02 9.115e-02
13 74 -7.180116e+00 0.000e+00 1.069e-03 4.670e-02
14 79 -7.180409e+00 0.000e+00 7.797e-04 2.815e-03
15 84 -7.180410e+00 0.000e+00 6.368e-06 3.120e-04
Local minimum found that satisfies the constraints.
Optimization completed because the objective function is non-decreasing in
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.
Serial FMINCON optimization takes 18.2876 seconds.
Minimizar utilizando el algoritmo genético
Puesto que ga generalmente requiere muchas más evaluaciones de función que fmincon, eliminamos la restricción costosa de este problema y, en su lugar, realizamos una optimización sin restricciones. Pase matrices vacías [] para restricciones. Además, limitamos el número máximo de generaciones a 15 para ga de manera que ga pueda terminar en un tiempo razonable. Nos interesa calcular el tiempo que ga tarda de modo que podamos compararlo con la evaluación de ga en paralelo. Tenga en cuenta que para ejecutar ga se requiere Global Optimization Toolbox.
rng default % for reproducibility try gaAvailable = false; nvar = 4; gaoptions = optimoptions('ga','MaxGenerations',15,'Display','iter'); startTime = tic; gasol = ga(@expensive_objfun,nvar,[],[],[],[],[],[],[],gaoptions); time_ga_sequential = toc(startTime); fprintf('Serial GA optimization takes %g seconds.\n',time_ga_sequential); gaAvailable = true; catch ME warning(message('optim:optimdemos:optimparfor:gaNotFound')); end
Single objective optimization:
4 Variable(s)
Options:
CreationFcn: @gacreationuniform
CrossoverFcn: @crossoverscattered
SelectionFcn: @selectionstochunif
MutationFcn: @mutationgaussian
Best Mean Stall
Generation Func-count f(x) f(x) Generations
1 100 -5.546e+05 1.483e+15 0
2 147 -5.581e+17 -1.116e+16 0
3 194 -7.556e+17 6.679e+22 0
4 241 -7.556e+17 -7.195e+16 1
5 288 -9.381e+27 -1.876e+26 0
6 335 -9.673e+27 -7.497e+26 0
7 382 -4.511e+36 -9.403e+34 0
8 429 -5.111e+36 -3.011e+35 0
9 476 -7.671e+36 9.346e+37 0
10 523 -1.52e+43 -3.113e+41 0
11 570 -2.273e+45 -4.67e+43 0
12 617 -2.589e+47 -6.281e+45 0
13 664 -2.589e+47 -1.015e+46 1
14 711 -8.149e+47 -5.855e+46 0
15 758 -9.503e+47 -1.29e+47 0
Optimization terminated: maximum number of generations exceeded.
Serial GA optimization takes 81.5878 seconds.
Establecer Parallel Computing Toolbox
La diferenciación finita utilizada por las funciones en Optimization Toolbox para aproximar derivadas se realiza en paralelo utilizando la funcionalidad parfor si Parallel Computing Toolbox™ está disponible y hay un pool paralelo de workers. Lo mismo ocurre con los solvers ga, gamultiobj y patternsearch, que en Global Optimization Toolbox evalúan funciones en paralelo. Para usar la funcionalidad parfor, usamos la función parpool para configurar el entorno paralelo. El equipo en el que se publica este ejemplo tiene cuatro núcleos, por lo que parpool inicia cuatro workers de MATLAB®. Si ya hay un grupo paralelo cuando se ejecuta este ejemplo, utilizamos ese grupo; consulte la documentación de parpool para obtener más información.
if max(size(gcp)) == 0 % parallel pool needed parpool % create the parallel pool end
Minimizar empleando fmincon paralelo
Para minimizar nuestro problema de optimización costoso utilizando la función paralela fmincon, debemos indicar explícitamente que nuestras funciones objetivo y de restricción pueden evaluarse en paralelo y que queremos que fmincon utilice su funcionalidad paralela siempre que sea posible. Actualmente, la diferenciación finita se puede realizar en paralelo. Nos interesa calcular el tiempo que fmincon tarda de modo que podamos compararlo con la ejecución de fmincon en serie.
options = optimoptions(options,'UseParallel',true); startTime = tic; xsol = fmincon(@expensive_objfun,startPoint,[],[],[],[],[],[],@expensive_confun,options); time_fmincon_parallel = toc(startTime); fprintf('Parallel FMINCON optimization takes %g seconds.\n',time_fmincon_parallel);
First-order Norm of
Iter F-count f(x) Feasibility optimality step
0 5 1.839397e+00 1.500e+00 3.211e+00
1 11 -9.760099e-01 3.708e+00 7.902e-01 2.362e+00
2 16 -1.480976e+00 0.000e+00 8.344e-01 1.069e+00
3 21 -2.601599e+00 0.000e+00 8.390e-01 1.218e+00
4 29 -2.823630e+00 0.000e+00 2.598e+00 1.118e+00
5 34 -3.905338e+00 0.000e+00 1.210e+00 7.302e-01
6 39 -6.212992e+00 3.934e-01 7.372e-01 2.405e+00
7 44 -5.948761e+00 0.000e+00 1.784e+00 1.905e+00
8 49 -6.940062e+00 1.233e-02 7.668e-01 7.553e-01
9 54 -6.973887e+00 0.000e+00 2.549e-01 3.920e-01
10 59 -7.142993e+00 0.000e+00 1.903e-01 4.735e-01
11 64 -7.155325e+00 0.000e+00 1.365e-01 2.626e-01
12 69 -7.179122e+00 0.000e+00 6.336e-02 9.115e-02
13 74 -7.180116e+00 0.000e+00 1.069e-03 4.670e-02
14 79 -7.180409e+00 0.000e+00 7.797e-04 2.815e-03
15 84 -7.180410e+00 0.000e+00 6.368e-06 3.120e-04
Local minimum found that satisfies the constraints.
Optimization completed because the objective function is non-decreasing in
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.
Parallel FMINCON optimization takes 8.79291 seconds.
Minimizar utilizando el algoritmo genético paralelo
Para minimizar nuestro problema de optimización costoso utilizando la función ga, debemos indicar explícitamente que nuestra función objetivo puede evaluarse en paralelo y que queremos que ga utilice su funcionalidad paralela siempre que sea posible. Para usar el ga paralelo, también requerimos que la opción "Vectorized" se establezca en el valor predeterminado (p. ej., "off"). De nuevo, nos interesa calcular el tiempo que ga tarda de modo que podamos compararlo con la ejecución de ga en serie. Aunque esta ejecución puede ser diferente a la ejecución en serie porque ga utiliza un generador de números aleatorios, el número de evaluaciones costosas de funciones es el mismo en ambas ejecuciones. Tenga en cuenta que para ejecutar ga se requiere Global Optimization Toolbox.
rng default % to get the same evaluations as the previous run if gaAvailable gaoptions = optimoptions(gaoptions,'UseParallel',true); startTime = tic; gasol = ga(@expensive_objfun,nvar,[],[],[],[],[],[],[],gaoptions); time_ga_parallel = toc(startTime); fprintf('Parallel GA optimization takes %g seconds.\n',time_ga_parallel); end
Single objective optimization:
4 Variable(s)
Options:
CreationFcn: @gacreationuniform
CrossoverFcn: @crossoverscattered
SelectionFcn: @selectionstochunif
MutationFcn: @mutationgaussian
Best Mean Stall
Generation Func-count f(x) f(x) Generations
1 100 -5.546e+05 1.483e+15 0
2 147 -5.581e+17 -1.116e+16 0
3 194 -7.556e+17 6.679e+22 0
4 241 -7.556e+17 -7.195e+16 1
5 288 -9.381e+27 -1.876e+26 0
6 335 -9.673e+27 -7.497e+26 0
7 382 -4.511e+36 -9.403e+34 0
8 429 -5.111e+36 -3.011e+35 0
9 476 -7.671e+36 9.346e+37 0
10 523 -1.52e+43 -3.113e+41 0
11 570 -2.273e+45 -4.67e+43 0
12 617 -2.589e+47 -6.281e+45 0
13 664 -2.589e+47 -1.015e+46 1
14 711 -8.149e+47 -5.855e+46 0
15 758 -9.503e+47 -1.29e+47 0
Optimization terminated: maximum number of generations exceeded.
Parallel GA optimization takes 15.2253 seconds.
Comparar tiempo en serie y paralelo
X = [time_fmincon_sequential time_fmincon_parallel]; Y = [time_ga_sequential time_ga_parallel]; t = [0 1]; plot(t,X,'r--',t,Y,'k-') ylabel('Time in seconds') legend('fmincon','ga') ax = gca; ax.XTick = [0 1]; ax.XTickLabel = {'Serial' 'Parallel'}; axis([0 1 0 ceil(max([X Y]))]) title('Serial Vs. Parallel Times')
La utilización de la evaluación paralela de funciones mediante parfor ha mejorado la eficiencia tanto de fmincon como de ga. La mejora suele funcionar mejor para las funciones de restricción y objetivo costosas.
