Main Content

このページは機械翻訳を使用して翻訳されました。元の英語を参照するには、ここをクリックします。

カスタム データ型を使用したシミュレーテッド アニーリングを使用したマルチプロセッサ スケジューリング

スクリプトを開く

この例では、シミュレーテッド アニーリングを使用して、カスタム データ型を使用して関数を最小化する方法を示します。ここでは、シミュレーテッド アニーリングをカスタマイズして、マルチプロセッサ スケジューリングの問題を解決します。

マルチプロセッサ スケジューリング問題

マルチプロセッサ スケジューリング問題は、プロセッサ セット上のタスクの最適な分散を見つけることです。プロセッサの数とタスクの数が与えられます。プロセッサがタスクを完了するのにかかる時間もデータとして提供されます。各プロセッサは独立して実行されますが、一度に実行できるジョブは 1 つだけです。すべてのジョブを利用可能なプロセッサに割り当てることを「スケジュール」と呼びます。この問題の目的は、与えられたタスク セットの最短スケジュールを決定することです。

まず、simulannealbnd 関数が解決できるカスタム データ型の最適化問題の観点からこの問題を表現する方法を決定します。私たちは次のようなスキームを思いつきました。まず、各タスクを 1 からタスクの総数までの整数で表します。同様に、各プロセッサは 1 からプロセッサ数までの整数で表されます。これで、特定のジョブが特定のプロセッサでかかる時間を、「長さ」と呼ばれるマトリックスに保存できるようになりました。プロセッサ「i」がタスク「j」を完了するのにかかる時間「t」は、lengths(i,j) に格納されます。

スケジュールも同様の方法で表すことができます。特定のスケジュールでは、行 (1 からプロセッサ数までの整数) はプロセッサを表し、列 (1 からタスク数までの整数) はタスクを表します。たとえば、スケジュール [1 2 3;4 5 0;6 0 0] は、タスク 1、2、3 がプロセッサ 1 で実行され、タスク 4 と 5 がプロセッサ 2 で実行され、タスク 6 がプロセッサ 3 で実行されることを意味します。

ここで、タスクの数、プロセッサの数、および配列の長さを定義します。各行の異なる係数は、異なるプロセッサが異なる速度で動作するという事実を表しています。また、simulannealbnd への開始点入力となる「sampleSchedule」も定義します。

rng default % for reproducibility
numberOfProcessors = 11;
numberOfTasks = 40;
lengths = [10*rand(1,numberOfTasks);
           7*rand(1,numberOfTasks);
           2*rand(1,numberOfTasks);
           5*rand(1,numberOfTasks);
           3*rand(1,numberOfTasks);
           4*rand(1,numberOfTasks);
           1*rand(1,numberOfTasks);
           6*rand(1,numberOfTasks);
           4*rand(1,numberOfTasks);
           3*rand(1,numberOfTasks);
           1*rand(1,numberOfTasks)];

% Random distribution of task on processors (starting point)
sampleSchedule = zeros(numberOfProcessors,numberOfTasks);
for task = 1:numberOfTasks
    processorID = 1 + floor(rand*(numberOfProcessors));
    index = find(sampleSchedule(processorID,:)==0);
    sampleSchedule(processorID,index(1)) = task;
end

カスタムデータタイプのシミュレーテッドアニーリング

デフォルトでは、シミュレーテッド アニーリング アルゴリズムは、決定変数が double データ型であると仮定して最適化問題を解決します。したがって、後続のポイントを生成するためのアニーリング関数は、現在のポイントが double 型のベクトルであると想定します。ただし、DataType オプションが「カスタム」に設定されている場合、シミュレーテッド アニーリング ソルバーは任意のデータ型を含む最適化問題にも適用できます。任意の有効な MATLAB® データ構造を決定変数として使用できます。たとえば、simulannealbnd で「sampleSchedule」を決定変数として使用する場合、整数のマトリックスを使用してカスタム データ型を指定できます。DataType オプションを「カスタム」に設定することに加えて、新しいポイントを生成できる AnnealingFcn オプションを介してカスタムアニーリング関数も提供する必要があります。

カスタムアニーリング関数

このセクションでは、必要なカスタム アニーリング関数を作成して使用する方法を示します。マルチプロセッサ スケジューリング問題の試行点は、前述したように、プロセッサ (行) とタスク (列) のマトリックスです。マルチプロセッサ スケジューリング問題用のカスタム アニーリング関数は、ジョブ スケジュールを入力として受け取ります。次に、アニーリング関数はこのスケジュールを変更し、温度に比例した量だけ変更された新しいスケジュールを返します (シミュレーテッド アニーリングでは通常どおり)。ここでは、カスタムのアニーリング関数を表示します。

type mulprocpermute.m

function schedule = mulprocpermute(optimValues,problemData)
% MULPROCPERMUTE Moves one random task to a different processor.
% NEWX = MULPROCPERMUTE(optimValues,problemData) generate a point based
% on the current point and the current temperature

% Copyright 2006 The MathWorks, Inc.

schedule = optimValues.x;
% This loop will generate a neighbor of "distance" equal to
% optimValues.temperature.  It does this by generating a neighbor to the
% current schedule, and then generating a neighbor to that neighbor, and so
% on until it has generated enough neighbors.
for i = 1:floor(optimValues.temperature)+1
    [nrows ncols] = size(schedule);
    schedule = neighbor(schedule, nrows, ncols);
end

%=====================================================%
function schedule = neighbor(schedule, nrows, ncols)
% NEIGHBOR generates a single neighbor to the given schedule.  It does so
% by moving one random task to a different processor.  The rest of the code
% is to ensure that the format of the schedule remains the same.

row1 = randinteger(1,1,nrows)+1;
col = randinteger(1,1,ncols)+1;
while schedule(row1, col)==0
    row1 = randinteger(1,1,nrows)+1;
    col = randinteger(1,1,ncols)+1;
end
row2 = randinteger(1,1,nrows)+1;
while row1==row2
    row2 = randinteger(1,1,nrows)+1;
end

for j = 1:ncols
    if schedule(row2,j)==0
        schedule(row2,j) = schedule(row1,col);
        break
    end
end

schedule(row1, col) = 0;
for j = col:ncols-1
    schedule(row1,j) = schedule(row1,j+1);
end
schedule(row1,ncols) = 0;
%=====================================================%
function out = randinteger(m,n,range)
%RANDINTEGER generate integer random numbers (m-by-n) in range

len_range = size(range,1) * size(range,2);
% If the IRANGE is specified as a scalar.
if len_range < 2
    if range < 0
        range = [range+1, 0];
    elseif range > 0
        range = [0, range-1];
    else
        range = [0, 0];    % Special case of zero range.
    end
end
% Make sure RANGE is ordered properly.
range = sort(range);

% Calculate the range the distance for the random number generator.
distance = range(2) - range(1);
% Generate the random numbers.
r = floor(rand(m, n) * (distance+1));

% Offset the numbers to the specified value.
out = ones(m,n)*range(1);
out = out + r;

目的関数

マルチプロセッサ スケジューリング問題には目的関数が必要です。目的関数は、指定されたスケジュールに必要な合計時間 (各プロセッサがタスクに費やしている時間の最大値) を返します。そのため、目的関数では合計時間を計算できるように長さ行列も必要です。私たちはこの合計時間を最小限に抑えるよう努めます。ここで目的関数を表示します

type mulprocfitness.m

function timeToComplete = mulprocfitness(schedule, lengths)
%MULPROCFITNESS determines the "fitness" of the given schedule.
%  In other words, it tells us how long the given schedule will take using the
%  knowledge given by "lengths"

%   Copyright 2006 The MathWorks, Inc.

[nrows ncols] = size(schedule);
timeToComplete = zeros(1,nrows);
for i = 1:nrows
    timeToComplete(i) = 0;
    for j = 1:ncols
        if schedule(i,j)~=0
            timeToComplete(i) = timeToComplete(i)+lengths(i,schedule(i,j));
        else
            break
        end
    end
end
timeToComplete = max(timeToComplete);

simulannealbnd は、引数 x のみを使用して目的関数を呼び出しますが、適応度関数には引数 x と "lengths" の 2 つがあります。匿名関数を使用して、追加の引数である長さ行列の値を取得できます。1 つの入力 x を受け取り、x と "lengths" を使用して 'mulprocfitness' を呼び出す匿名関数への関数ハンドル 'ObjectiveFcn' を作成します。関数ハンドル 'FitnessFcn' が作成されると、変数 "lengths" に値が設定され、これらの値は匿名関数によって取得されます。

% lengths was defined earlier
fitnessfcn = @(x) mulprocfitness(x,lengths);

各プロセッサでタスクがかかっている時間の長さをプロットするためのカスタム プロット関数を追加できます。各バーはプロセッサを表し、各バーの異なる色のチャンクは異なるタスクを表します。

type mulprocplot.m

function stop = mulprocplot(~,optimvalues,flag,lengths)
%MULPROCPLOT PlotFcn used for SAMULTIPROCESSORDEMO
%   STOP = MULPROCPLOT(OPTIONS,OPTIMVALUES,FLAG) where OPTIMVALUES is a
%   structure with the following fields:
%              x: current point
%           fval: function value at x
%          bestx: best point found so far
%       bestfval: function value at bestx
%    temperature: current temperature
%      iteration: current iteration
%      funccount: number of function evaluations
%             t0: start time
%              k: annealing parameter 'k'
%
%   FLAG: Current state in which PlotFcn is called. Possible values are:
%           init: initialization state
%           iter: iteration state
%           done: final state
%
%   STOP: A boolean to stop the algorithm.
%

%   Copyright 2006-2015 The MathWorks, Inc.

persistent thisTitle %#ok

stop = false;
switch flag
    case 'init'
        set(gca,'xlimmode','manual','zlimmode','manual', ...
            'alimmode','manual')
        titleStr = sprintf('Current Point - Iteration %d', optimvalues.iteration);
        thisTitle = title(titleStr,'interp','none');
        toplot = i_generatePlotData(optimvalues, lengths);
        ylabel('Time','interp','none');
        bar(toplot, 'stacked','edgecolor','none');
        Xlength = size(toplot,1);        
        set(gca,'xlim',[0,1 + Xlength])
    case 'iter'
        if ~rem(optimvalues.iteration, 100)
            toplot = i_generatePlotData(optimvalues, lengths);
            bar(toplot, 'stacked','edgecolor','none');
            titleStr = sprintf('Current Point - Iteration %d', optimvalues.iteration);
            thisTitle = title(titleStr,'interp','none');            
        end
end

function toplot = i_generatePlotData(optimvalues, lengths)

schedule = optimvalues.x;
nrows = size(schedule,1);
% Remove zero columns (all processes are idle)
maxlen = 0;
for i = 1:nrows
    if max(nnz(schedule(i,:))) > maxlen
        maxlen = max(nnz(schedule(i,:)));
    end
end
schedule = schedule(:,1:maxlen);

toplot = zeros(size(schedule));
[nrows, ncols] = size(schedule);
for i = 1:nrows
    for j = 1:ncols
        if schedule(i,j)==0 % idle process
            toplot(i,j) = 0;
        else
            toplot(i,j) = lengths(i,schedule(i,j));
        end
    end
end

ただし、シミュレーテッド アニーリングでは、現在のスケジュールが必ずしもこれまでに見つかった最良のスケジュールであるとは限らないことに注意してください。これまでに発見された最適なスケジュールを表示する 2 番目のカスタム プロット関数を作成します。

type mulprocplotbest.m

function stop = mulprocplotbest(~,optimvalues,flag,lengths)
%MULPROCPLOTBEST PlotFcn used for SAMULTIPROCESSORDEMO
%   STOP = MULPROCPLOTBEST(OPTIONS,OPTIMVALUES,FLAG) where OPTIMVALUES is a
%   structure with the following fields:
%              x: current point
%           fval: function value at x
%          bestx: best point found so far
%       bestfval: function value at bestx
%    temperature: current temperature
%      iteration: current iteration
%      funccount: number of function evaluations
%             t0: start time
%              k: annealing parameter 'k'
%
%   FLAG: Current state in which PlotFcn is called. Possible values are:
%           init: initialization state
%           iter: iteration state
%           done: final state
%
%   STOP: A boolean to stop the algorithm.
%

%   Copyright 2006-2015 The MathWorks, Inc.

persistent thisTitle %#ok

stop = false;
switch flag
    case 'init'
        set(gca,'xlimmode','manual','zlimmode','manual', ...
            'alimmode','manual')
        titleStr = sprintf('Current Point - Iteration %d', optimvalues.iteration);
        thisTitle = title(titleStr,'interp','none');
        toplot = i_generatePlotData(optimvalues, lengths);
        Xlength = size(toplot,1);
        ylabel('Time','interp','none');
        bar(toplot, 'stacked','edgecolor','none');
        set(gca,'xlim',[0,1 + Xlength])
    case 'iter'
        if ~rem(optimvalues.iteration, 100)
            toplot = i_generatePlotData(optimvalues, lengths);
            bar(toplot, 'stacked','edgecolor','none');
            titleStr = sprintf('Best Point - Iteration %d', optimvalues.iteration);
            thisTitle = title(titleStr,'interp','none');            
        end
         
end

function toplot = i_generatePlotData(optimvalues, lengths)

schedule = optimvalues.bestx;
nrows = size(schedule,1);
% Remove zero columns (all processes are idle)
maxlen = 0;
for i = 1:nrows
    if max(nnz(schedule(i,:))) > maxlen
        maxlen = max(nnz(schedule(i,:)));
    end
end
schedule = schedule(:,1:maxlen);

toplot = zeros(size(schedule));
[nrows, ncols] = size(schedule);
for i = 1:nrows
    for j = 1:ncols
        if schedule(i,j)==0
            toplot(i,j) = 0;
        else
            toplot(i,j) = lengths(i,schedule(i,j));
        end
    end
end

シミュレーテッドアニーリングオプションの設定

作成したカスタム アニーリングおよびプロット関数を選択し、いくつかのデフォルト オプションを変更します。ReannealInterval は 800 に設定されています。これは、ReannealInterval の値が小さいと、ソルバーがローカルで大きな進歩を遂げ始めたときに温度が上昇するように見えるためです。また、デフォルト値ではソルバーが遅くなりすぎるため、StallIterLimit を 800 に減らします。最後に、DataType を「カスタム」に設定する必要があります。

options = optimoptions(@simulannealbnd,'DataType', 'custom', ...
    'AnnealingFcn', @mulprocpermute, 'MaxStallIterations',800, 'ReannealInterval', 800, ...
    'PlotFcn', {{@mulprocplot, lengths},{@mulprocplotbest, lengths},@saplotf,@saplotbestf});

最後に、問題情報を使用してシミュレーテッドアニーリングを呼び出します。

schedule = simulannealbnd(fitnessfcn,sampleSchedule,[],[],options);
% Remove zero columns (all processes are idle)
maxlen = 0;
for i = 1:size(schedule,1)
    if max(nnz(schedule(i,:)))>maxlen
        maxlen = max(nnz(schedule(i,:)));
    end
end
% Display the schedule
schedule = schedule(:,1:maxlen)

simulannealbnd stopped because the change in best function value is less than options.FunctionTolerance.

schedule =

    22    34    32     0     0     0     0     0
     5     0     0     0     0     0     0     0
    19     6    12    11    39    35     0     0
     7    20     0     0     0     0     0     0
    30    15    10     3     0     0     0     0
    18    28     0     0     0     0     0     0
    31    33    29     4    21     9    25    40
    24    26    14     0     0     0     0     0
    13    16    23     0     0     0     0     0
    38    36     1     0     0     0     0     0
     8    27    37    17     2     0     0     0

参考

関連するトピック