Main Content

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 ordenador 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.

Temas relacionados