В этом примере показано, как использовать симулированный отжиг, чтобы минимизировать функцию с помощью пользовательского типа данных. Здесь симулированный отжиг настраивается, чтобы решить многопроцессорную задачу планирования.
Многопроцессорная проблема планирования состоит из нахождения оптимального распределения задач на наборе процессоров. Количество процессоров и количество задач даны. Время, потраченное, чтобы выполнить задачу процессором, также обеспечивается как данные. Каждый процессор запускается независимо, но каждый может только запустить одно задание за один раз. Мы вызываем присвоение всех заданий к доступным процессорам "расписание". Цель проблемы состоит в том, чтобы определить самое короткое расписание для данного набора задач.
Сначала мы определяем, как выразить эту проблему в терминах задачи оптимизации пользовательского типа данных что 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
Мы выбираем пользовательский отжиг и функции построения графика, которые мы создали, а также изменяем некоторые опции по умолчанию. 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