В этом примере показано, как использовать смоделированный отжиг для минимизации функции с использованием пользовательского типа данных. Здесь моделируемый отжиг настраивается для решения проблемы многопроцессорного планирования.
Задача многопроцессорного планирования состоит в нахождении оптимального распределения задач на наборе процессоров. Приводится количество процессоров и количество задач. Время, необходимое для выполнения задачи процессором, также предоставляется в виде данных. Каждый процессор работает независимо, но каждый может выполнять только одно задание одновременно. Назначение всех заданий доступным процессорам мы называем «расписанием». Целью задачи является определение кратчайшего графика для данного набора задач.
Сначала мы определим, как выразить эту проблему в терминах пользовательской задачи оптимизации типа данных, которая 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 параметр имеет значение «custom», при котором моделируемый решатель отжига может также работать над задачами оптимизации, включая произвольные типы данных. В качестве переменной решения можно использовать любую допустимую структуру данных 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 и «длины». Мы можем использовать анонимную функцию для захвата значений дополнительного аргумента, матрицы длин. Мы создаем ручку функции 'ObjectiveFcn' к анонимной функции, которая берет вход того x, но вызывает «multprocfitness» с 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
Выбираем созданные пользовательские функции отжига и печати, а также изменяем некоторые параметры по умолчанию. ReannealInterval имеет значение 800, поскольку более низкие значения для ReannealInterval кажется, поднимает температуру, когда решатель начинает делать большой локальный прогресс. Мы также уменьшаем StallIterLimit 800, поскольку значение по умолчанию делает решатель слишком медленным. Наконец, мы должны установить DataType для «» custom «».
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
