Минимизация дорогой задачи оптимизации Используя Parallel Computing Toolbox™

Этот пример показывает, как к тому, как ускорить минимизацию дорогой задачи оптимизации с помощью функций в Optimization Toolbox™ и Global Optimization Toolbox. В первой части примера мы решаем задачу оптимизации путем выполнения функций последовательным способом, и второй частью примера мы решаем ту же проблему с помощью параллельного цикла for (parfor) функция путем выполнения функций параллельно. Мы сравниваем время, потраченное функцией оптимизации в обоих случаях.

Дорогая задача оптимизации

В целях этого примера мы решаем проблему в четырех переменных, где цель и ограничительные функции сделаны искусственно дорогими путем приостановки.

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 = [];

Минимизация Используя fmincon

Мы интересуемся измерением времени, потраченного fmincon в сериале так, чтобы мы могли сравнить его с параллельным временем.

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.905339e+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.948762e+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.799e-04    2.815e-03
   15      84   -7.180410e+00    0.000e+00    6.189e-06    3.122e-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 17.0722 seconds.

Минимизация Используя генетический алгоритм

Поскольку ga обычно берет намного больше функциональных оценок, чем fmincon, мы удаляем дорогое ограничение из этой проблемы и выполняем неограниченную оптимизацию вместо этого. Передайте пустые матрицы [] для ограничений. Кроме того, мы ограничиваем максимальное количество поколений к 15 для ga так, чтобы ga мог остановиться за разумное количество времени. Мы интересуемся измерением времени, потраченного ga так, чтобы мы могли сравнить его с параллельной оценкой ga. Обратите внимание на то, что выполнение ga требует 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('optimdemos:optimparfor:gaNotFound'));
end
                                  Best           Mean      Stall
Generation      Func-count        f(x)           f(x)    Generations
    1              100      -5.546e+05       1.483e+15        0
    2              150      -5.581e+17      -1.116e+16        0
    3              200      -7.556e+17       6.679e+22        0
    4              250      -7.556e+17      -7.195e+16        1
    5              300      -9.381e+27      -1.876e+26        0
    6              350      -9.673e+27      -7.497e+26        0
    7              400      -4.511e+36      -9.403e+34        0
    8              450      -5.111e+36      -3.011e+35        0
    9              500      -7.671e+36       9.346e+37        0
   10              550       -1.52e+43      -3.113e+41        0
   11              600      -2.273e+45       -4.67e+43        0
   12              650      -2.589e+47      -6.281e+45        0
   13              700      -2.589e+47      -1.015e+46        1
   14              750      -8.149e+47      -5.855e+46        0
   15              800      -9.503e+47       -1.29e+47        0
Optimization terminated: maximum number of generations exceeded.
Serial GA optimization takes 80.2351 seconds.

Установка Parallel Computing Toolbox

Конечное дифференцирование, используемое функциями в Optimization Toolbox к аппроксимативным производным, сделано в параллели, использующей функцию parfor, если Parallel Computing Toolbox доступен и существует параллельный пул рабочих. Точно так же ga, gamultiobj и решатели patternsearch в Global Optimization Toolbox выполняют функции параллельно. Чтобы использовать функцию parfor, мы используем функцию parpool, чтобы настроить параллельную среду. Компьютер, на котором публикуется этот пример, имеет четыре ядра, таким образом, parpool запускает четырех рабочих MATLAB®. Если уже существует параллельный пул, когда вы запускаете этот пример, мы используем тот пул; см. документацию для parpool для получения дополнительной информации.

if max(size(gcp)) == 0 % parallel pool needed
    parpool % create the parallel pool
end

Минимизация Используя параллель fmincon

Чтобы минимизировать нашу дорогую задачу оптимизации с помощью параллельной функции fmincon, мы должны явным образом указать, что наша цель и ограничительные функции могут быть оценены параллельно и что мы хотим, чтобы fmincon использовал свою параллельную функциональность по мере возможности. В настоящее время конечное дифференцирование может быть сделано параллельно. Мы интересуемся измерением времени, потраченного fmincon так, чтобы мы могли сравнить его с последовательным запущенным fmincon.

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.905339e+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.948762e+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.799e-04    2.815e-03
   15      84   -7.180410e+00    0.000e+00    6.189e-06    3.122e-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.11945 seconds.

Минимизация Используя параллельный генетический алгоритм

Чтобы минимизировать нашу дорогую задачу оптимизации с помощью функции ga, мы должны явным образом указать, что наша целевая функция может быть выполнена параллельно и что мы хотим, чтобы ga использовал свою параллельную функциональность по мере возможности. Чтобы использовать параллельный ga, мы также требуем, чтобы 'Векторизованная' опция была установлена в значение по умолчанию (т.е. 'off'). Мы снова интересуемся измерением времени, потраченного ga так, чтобы мы могли сравнить его с последовательным запущенным ga. Хотя это выполнение может отличаться от последовательного, потому что ga использует генератор случайных чисел, количество дорогих функциональных оценок является тем же самым в обоих выполнениях. Обратите внимание на то, что выполнение ga требует 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
                                  Best           Mean      Stall
Generation      Func-count        f(x)           f(x)    Generations
    1              100      -5.546e+05       1.483e+15        0
    2              150      -5.581e+17      -1.116e+16        0
    3              200      -7.556e+17       6.679e+22        0
    4              250      -7.556e+17      -7.195e+16        1
    5              300      -9.381e+27      -1.876e+26        0
    6              350      -9.673e+27      -7.497e+26        0
    7              400      -4.511e+36      -9.403e+34        0
    8              450      -5.111e+36      -3.011e+35        0
    9              500      -7.671e+36       9.346e+37        0
   10              550       -1.52e+43      -3.113e+41        0
   11              600      -2.273e+45       -4.67e+43        0
   12              650      -2.589e+47      -6.281e+45        0
   13              700      -2.589e+47      -1.015e+46        1
   14              750      -8.149e+47      -5.855e+46        0
   15              800      -9.503e+47       -1.29e+47        0
Optimization terminated: maximum number of generations exceeded.
Parallel GA optimization takes 15.6984 seconds.

Сравните последовательное и параллельное время

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')

Использование параллельной функциональной оценки через parfor повысило эффективность и fmincon и ga. Улучшение обычно лучше для дорогой цели и ограничительных функций.

Похожие темы

Для просмотра документации необходимо авторизоваться на сайте