Optimization Toolbox

最新のリリースでは、このページがまだ翻訳されていません。 このページの最新版は英語でご覧になれます。

Parallel Computing Toolbox™ を使用した、時間のかかる最適化問題の最小化

この例では、Optimization Toolbox™ と Global Optimization Toolbox の関数を使用して、時間のかかる最適化問題の最小化を高速で行う方法を示します。例の前半では、関数を連続的に評価することで最適化問題を解きます。例の後半では、並列 for ループ (parfor) 機能を使用して関数を並列で評価することにより、同じ問題を解きます。最適化関数の処理にかかる時間を、両方のケースで比較します。

時間のかかる最適化問題

この例では、4 つの変数をもつ問題を解きます。一時停止することで、人為的に目的関数と制約関数の処理に時間がかかるようにします。

type expensive_objfun.m
type expensive_confun.m
function f = expensive_objfun(x)
%EXPENSIVE_OBJFUN An expensive objective function used in optimparfor example.

%   Copyright 2007-2013 The MathWorks, Inc.
%   $Revision: 1.1.8.11.2.2 $  $Date: 2014/02/12 21:04:05 $

% 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.
%   $Revision: 1.1.8.11.2.2 $  $Date: 2014/02/12 21:04:05 $

% 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 にかかる時間を測定し、並列での fmincon の評価と比較できるようにします。

startPoint = [-1 1 1 -1];
options = optimoptions('fmincon','Display','iter','Algorithm','sqp');
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);
                                                          Norm of First-order
 Iter F-count            f(x) Feasibility  Steplength        step  optimality
    0       5    1.839397e+00   1.500e+00                           3.311e+00
    1      12   -8.841073e-01   4.019e+00   4.900e-01   2.335e+00   7.015e-01
    2      17   -1.382832e+00   0.000e+00   1.000e+00   1.142e+00   9.272e-01
    3      22   -2.241952e+00   0.000e+00   1.000e+00   2.447e+00   1.481e+00
    4      27   -3.145762e+00   0.000e+00   1.000e+00   1.756e+00   5.464e+00
    5      32   -5.277523e+00   6.413e+00   1.000e+00   2.224e+00   1.357e+00
    6      37   -6.310709e+00   0.000e+00   1.000e+00   1.099e+00   1.309e+00
    7      43   -6.447956e+00   0.000e+00   7.000e-01   2.191e+00   3.631e+00
    8      48   -7.135133e+00   0.000e+00   1.000e+00   3.719e-01   1.205e-01
    9      53   -7.162732e+00   0.000e+00   1.000e+00   4.083e-01   2.935e-01
   10      58   -7.178390e+00   0.000e+00   1.000e+00   1.591e-01   3.110e-02
   11      63   -7.180399e+00   1.191e-05   1.000e+00   2.644e-02   1.553e-02
   12      68   -7.180408e+00   0.000e+00   1.000e+00   1.140e-02   5.584e-03
   13      73   -7.180411e+00   0.000e+00   1.000e+00   1.764e-03   4.677e-04
   14      78   -7.180412e+00   0.000e+00   1.000e+00   8.821e-05   1.305e-05
   15      83   -7.180412e+00   0.000e+00   1.000e+00   1.517e-06   2.894e-07

Local minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the default value of the function tolerance,
and constraints are satisfied to within the default value of the constraint tolerance.



Serial FMINCON optimization takes 18.2366 seconds.

遺伝的アルゴリズムを使用した最小化

遺伝的アルゴリズム (ga) では fmincon よりもずっと多くの関数評価が行われるため、時間のかかる制約をこの問題から取り除き、代わりに制約なしの最適化を実行します。そのために、制約として空 ([]) を渡します。また、妥当な時間内に ga が終了できるように、ga の最大世代数を 15 に制限します。ga の処理にかかる時間を測定して、並列での ga の評価と比較できるようにします。ga の実行には、Global Optimization Toolbox が必要なことに注意してください。

rng default % for reproducibility
try
    gaAvailable = false;
    nvar = 4;
    gaoptions = gaoptimset('Generations',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      f-count        f(x)           f(x)    Generations
    1            40            1.76           9.773        0
    2            60          0.5878           8.145        0
    3            80          0.3654           6.894        0
    4           100         -0.8403           2.886        0
    5           120         -0.8403           1.475        1
    6           140          -5.547           1.336        0
    7           160          -21.56          0.7224        0
    8           180          -36.56          0.3093        0
    9           200          -36.56           1.518        1
   10           220          -36.84          -11.83        0
   11           240          -47.86          -17.71        0
   12           260          -65.78          -25.83        0
   13           280          -76.25           -39.1        0
   14           300          -76.25          -56.31        1
   15           320          -78.46          -64.96        0
Optimization terminated: maximum number of generations exceeded.
Serial GA optimization takes 35.4592 seconds.

Parallel Computing Toolbox の設定

Parallel Computing Toolbox を使用でき、かつワーカーの並列プールが存在する場合、Optimization Toolbox の関数によって導関数を近似する有限差分化は、parfor 機能を使用して並列的に行われます。同様に、Global Optimization Toolbox の gagamultiobj および patternsearch の各ソルバーは、関数を並列に評価します。parfor 機能を使用するために、関数 parpool を使用して並列環境を設定します。この例のパブリッシュ先となるコンピューターには 4 つのコアがあるため、parpool は 4 つの MATLAB ワーカーを起動します。この例を実行する際に並列プールが既に存在する場合は、そのプールを使用します。詳細は、parpool のドキュメンテーションを参照してください。

if max(size(gcp)) == 0 % parallel pool needed
    parpool % create the parallel pool
end
Starting parpool using the 'local' profile ... connected to 4 workers.

ans = 

  Pool with properties:

    AttachedFiles: {0x1 cell}
       NumWorkers: 4
          Cluster: [1x1 parallel.cluster.Local]
      SpmdEnabled: 1

並列 fmincon を使用した最小化

並列の関数 fmincon を使用して時間のかかる最適化問題を最小化するには、目的関数と制約関数を並列で評価できること、そして可能であれば常に fmincon で並列機能を使用することを明示的に指定する必要があります。現在、有限差分を並列で実行できます。fmincon の処理にかかる時間を測定して、fmincon の逐次的実行と比較できるようにします。

options = optimoptions(options,'UseParallel','always');
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);
                                                          Norm of First-order
 Iter F-count            f(x) Feasibility  Steplength        step  optimality
    0       5    1.839397e+00   1.500e+00                           3.311e+00
    1      12   -8.841073e-01   4.019e+00   4.900e-01   2.335e+00   7.015e-01
    2      17   -1.382832e+00   0.000e+00   1.000e+00   1.142e+00   9.272e-01
    3      22   -2.241952e+00   0.000e+00   1.000e+00   2.447e+00   1.481e+00
    4      27   -3.145762e+00   0.000e+00   1.000e+00   1.756e+00   5.464e+00
    5      32   -5.277523e+00   6.413e+00   1.000e+00   2.224e+00   1.357e+00
    6      37   -6.310709e+00   0.000e+00   1.000e+00   1.099e+00   1.309e+00
    7      43   -6.447956e+00   0.000e+00   7.000e-01   2.191e+00   3.631e+00
    8      48   -7.135133e+00   0.000e+00   1.000e+00   3.719e-01   1.205e-01
    9      53   -7.162732e+00   0.000e+00   1.000e+00   4.083e-01   2.935e-01
   10      58   -7.178390e+00   0.000e+00   1.000e+00   1.591e-01   3.110e-02
   11      63   -7.180399e+00   1.191e-05   1.000e+00   2.644e-02   1.553e-02
   12      68   -7.180408e+00   0.000e+00   1.000e+00   1.140e-02   5.584e-03
   13      73   -7.180411e+00   0.000e+00   1.000e+00   1.764e-03   4.677e-04
   14      78   -7.180412e+00   0.000e+00   1.000e+00   8.821e-05   1.305e-05
   15      83   -7.180412e+00   0.000e+00   1.000e+00   1.517e-06   2.894e-07

Local minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the default value of the function tolerance,
and constraints are satisfied to within the default value of the constraint tolerance.



Parallel FMINCON optimization takes 11.2419 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 = gaoptimset(gaoptions,'UseParallel','always');
    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      f-count        f(x)           f(x)    Generations
    1            40            1.76           9.773        0
    2            60          0.5878           8.145        0
    3            80          0.3654           6.894        0
    4           100         -0.8403           2.886        0
    5           120         -0.8403           1.475        1
    6           140          -5.547           1.336        0
    7           160          -21.56          0.7224        0
    8           180          -36.56          0.3093        0
    9           200          -36.56           1.518        1
   10           220          -36.84          -11.83        0
   11           240          -47.86          -17.71        0
   12           260          -65.78          -25.83        0
   13           280          -76.25           -39.1        0
   14           300          -76.25          -56.31        1
   15           320          -78.46          -64.96        0
Optimization terminated: maximum number of generations exceeded.
Parallel GA optimization takes 11.5677 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')
set(gca,'XTick',[0 1])
set(gca,'XTickLabel',{'Serial' 'Parallel'})
axis([0 1 0 ceil(max([X Y]))])
title('Serial Vs. Parallel Times')

parfor による並列の関数評価を利用することで、fminconga の効率はどちらも向上しました。通常、こうした効率性の向上は、時間のかかる目的関数と制約関数により適しています。

最後に、並列プールを削除します。

if max(size(gcp)) > 0 % parallel pool exists
    delete(gcp) % delete the pool
end
Sending a stop signal to all the workers ... stopped.