このページは機械翻訳を使用して翻訳されました。最新版の英語を参照するには、ここをクリックします。
カスタムデータ型によるシミュレーテッド アニーリングを用いたマルチプロセッサ スケジューリング
この例では、シミュレーテッド アニーリングを使用して、カスタム データ型を使用して関数を最小化する方法を示します。ここでは、シミュレーテッド アニーリングをカスタマイズして、マルチプロセッサ スケジューリングの問題を解決します。
マルチプロセッサスケジューリング問題
マルチプロセッサ スケジューリングの問題は、プロセッサ セット上のタスクの最適な分散を見つけることです。プロセッサの数とタスクの数が与えられます。プロセッサによるタスクの完了に要した時間もデータとして提供されます。各プロセッサは独立して実行されますが、一度に実行できるジョブは 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 オプションを 'custom' に設定することに加えて、新しいポイントを生成できる 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
