Многопроцессорное Планирование с помощью Симулированного Отжига с Пользовательским типом данных
В этом примере показано, как использовать симулированный отжиг, чтобы минимизировать функцию с помощью пользовательского типа данных. Здесь симулированный отжиг настраивается, чтобы решить многопроцессорную задачу планирования.
Многопроцессорная проблема планирования
Многопроцессорная проблема планирования состоит из нахождения оптимального распределения задач на наборе процессоров. Количество процессоров и количество задач даны. Время, потраченное, чтобы выполнить задачу процессором, также обеспечивается как данные. Каждый процессор запускается независимо, но каждый может только запустить одно задание за один раз. Мы вызываем присвоение всех заданий к доступным процессорам "расписание". Цель проблемы состоит в том, чтобы определить самое короткое расписание для данного набора задач.
Сначала мы определяем, как описать эту проблему в терминах задачи оптимизации пользовательского типа данных что simulannealbnd функция может решить. Мы придумываем следующую схему: во-первых, позвольте каждой задаче быть представленной целым числом между 1 и общее количество задач. Точно так же каждый процессор представлен целым числом между 1 и количество процессоров. Теперь мы можем сохранить количество времени, данное задание возьмет данный процессор в названных "длинах" матрицы. Количество времени "t", который процессор "i" берет, чтобы выполнить задачу "j", будет храниться в длинах (i, j).
Мы можем представлять расписание подобным образом. В данном расписании строки (целое число между 1 к количеству процессоров) будут представлять процессоры, и столбцы (целое число между 1 к количеству задач) будут представлять задачи. Например, расписание [1 2 3; 4 5 0; 6 0 0] были бы задачи 1, 2, и 3 выполняемых на процессоре 1, задачи 4 и 5 выполняемых на процессоре 2 и задача 6 выполняемых на процессоре 3.
Здесь мы задаем наше количество задач, количество процессоров и массив длин. Различные коэффициенты для различных строк представляют то, что различные процессоры работают с различными скоростями. Мы также задаем "sampleSchedule", который будет нашим входом начальной точки к simulannealbnd.
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. Однако, если 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 и "длины". Мы можем использовать анонимную функцию, чтобы получить значения дополнительного аргумента, матрицы длин. Мы создаем указатель на функцию 'ObjectiveFcn' к анонимной функции, которая берет один вход x, но вызовы 'mulprocfitness' с x и "длины". Переменные "длины" имеют значение, когда указатель на функцию 'FitnessFcn' создается так, эти значения получены анонимной функцией.
% 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
Но помните, в симулированном отжиге текущего расписания не обязательно лучшее расписание, найденное до сих пор. Мы создаем вторую пользовательскую функцию построения графика, которая отобразит нам лучшее расписание, которое было обнаружено до сих пор.
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
Симулированный Setup опций отжига
Мы выбираем пользовательский отжиг и функции построения графика, которые мы создали, а также изменяем некоторые опции по умолчанию. 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)
Optimization terminated: change in best function value 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
