主要内容

使用自定义数据类型的模拟退火进行多处理器调度

打开脚本

此示例演示如何使用模拟退火来最小化使用自定义数据类型的函数。这里采用模拟退火的方法来解决多处理器调度问题。

多处理器调度问题

多处理器调度问题包括在一组处理器上寻找任务的最优分布。给出了处理器的数量和任务的数量。处理器完成任务所花费的时间也作为数据提供。每个处理器独立运行，但每个处理器一次只能运行一个作业。我们把所有作业分配给可用的处理器称为“调度”。这个问题的目标是确定给定任务集的最短进度。

首先，我们确定如何用自定义数据类型优化问题来表达这个问题simulannealbnd函数可以求解。我们提出了以下方案:首先，让每个任务用1与任务总数之间的整数表示。类似地，每个处理器由1和处理器数量之间的整数表示。现在，我们可以将给定作业在给定处理器上花费的时间存储在一个名为“长度”的矩阵中。处理器“i”完成任务“j”所花费的时间“t”将存储为长度(i,j)。

我们可以用类似的方式表示时间表。在给定的调度中，行(1到处理器数量之间的整数)将表示处理器，列(1到任务数量之间的整数)将表示任务。例如，调度[1 2 3;4 5 0;6 0 0]将是在处理器1上执行的任务1、2和3，在处理器2上执行的任务4和5，在处理器3上执行的任务6。

这里我们定义了任务数量、处理器数量和长度数组。不同行的不同系数表示不同的处理器以不同的速度工作。我们还定义了一个“samplesschedule”，它将作为我们的起始输入点simulannealbnd．

rng默认的再现率%numberOfProcessors = 11;numberOfTasks = 40;长度= [10*rand(1,numberOfTasks);7 *兰德(1、numberOfTasks);2 *兰德(1、numberOfTasks);5 *兰德(1、numberOfTasks);3 *兰德(1、numberOfTasks);4 *兰德(1、numberOfTasks);1 *兰德(1、numberOfTasks);6 *兰德(1、numberOfTasks); 4*rand(1,numberOfTasks); 3*rand(1,numberOfTasks); 1*rand(1,numberOfTasks)];%任务在处理器上的随机分布(起点)samplesschedule = 0 (numberOfProcessors,numberOfTasks);为processorID = 1 + floor(rand*(numberOfProcessors));index = find(samplesschedule (processorID，:)==0);sampleSchedule(processorID,index(1)) = task;结束

自定义数据类型的模拟退火

默认情况下，模拟退火算法在假设决策变量为双数据类型的情况下解决优化问题。因此，生成后续点的退火函数假设当前点是double类型的向量。然而，如果数据类型选项设置为“自定义”时，模拟退火求解器也可以处理涉及任意数据类型的优化问题。您可以使用任何有效的MATLAB®数据结构作为决策变量。例如，如果我们想simulannealbnd要使用“samplesschedule”作为决策变量，可以使用整数矩阵指定自定义数据类型。除了设置数据类型选项“自定义”，我们还需要提供一个自定义退火函数通过AnnealingFcn选项，可以生成新的点。

自定义退火函数

本节展示如何创建和使用所需的自定义退火函数。多处理器调度问题的一个试验点是前面讨论的处理器(行)和任务(列)的矩阵。多处理器调度问题的自定义退火函数将以作业调度作为输入。然后，退火函数将修改此调度并返回一个新的调度，该调度已按与温度成比例的量进行了更改(这是模拟退火的习惯)。这里我们展示了自定义退火函数。

类型mulprocpermute.m
mulprocpermute将一个随机任务移动到不同的处理器。% NEWX = MULPROCPERMUTE(optimValues,problemData)根据当前点和当前温度%生成一个点，版权2006 the MathWorks, Inc. schedule = optimValues.x;这个循环将生成一个距离为optimValues.temperature的邻居。它通过生成% current调度的邻居，然后生成该邻居的邻居，以此类推，直到生成足够多的邻居。for i = 1:floor(optimValues.temperature)+1 [nrows ncols] = size(schedule);Schedule =邻居(Schedule, nrows, ncols);结束  %=====================================================% 功能表=邻居(调度、nrows ncols) %的邻居产生一个邻居给定的时间表。它通过将一个随机任务移动到不同的处理器来实现。代码%的其余部分用于确保调度的格式保持不变。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;

目标函数

对于多处理器调度问题，我们需要一个目标函数。目标函数返回给定调度所需的总时间(这是每个处理器在其任务上花费的时间的最大值)。因此，目标函数还需要长度矩阵来计算总时间。我们要尽量使总时间最小化。这里我们展示了我们的目标函数

类型mulprocfitness.m
function timeToComplete = mulprocfitness(schedule, length) % mulprocfitness决定给定计划的“适合度”。换句话说，它告诉我们给定的调度将花费多长时间，使用“长度”给出的%知识版权2006 the MathWorks, Inc. [nrows ncols] = size(schedule);timeToComplete = 0 (1,nrows);当i = 1时，timeToComplete(i) = 0;如果调度(i,j)~=0 timeToComplete(i) = timeToComplete(i)+长度(i，调度(i,j));timeToComplete = max(timeToComplete);

simulannealbnd只调用一个参数的目标函数x，但我们的适应度函数有两个参数:x和“长度”。我们可以使用匿名函数来获取附加参数的值，即长度矩阵。我们为一个接受一个输入的匿名函数创建了一个函数句柄'ObjectiveFcn'x，但调用'mulprocfitness' withx和“长度”。变量“长度”在函数句柄“FitnessFcn”创建时有一个值，因此这些值由匿名函数捕获。

% length是前面定义的Fitnessfcn = @(x) mulprocfitness(x，长度);

我们可以添加一个自定义绘图函数来绘制任务在每个处理器上所花费的时间长度。每个条形图代表一个处理器，每个条形图中不同颜色的块代表不同的任务。

类型mulprocplot.m
函数停止= mulprocplot (optimvalues ~,国旗,长度)% mulprocplot PlotFcn用于SAMULTIPROCESSORDEMO %停止= mulprocplot(选项、optimvalues国旗)optimvalues %结构有以下字段:x %: % fval:当前点函数值在x % bestx:迄今为止最佳点发现% bestfval:函数值在bestx %温度:当前温度%迭代:当前迭代% funccount: % t0函数值的运算次数:开始时间% k:退火参数“k”% %国旗:调用PlotFcn的当前状态。可能值为:% init:初始化状态% iter:迭代状态% done:最终状态% % STOP:停止算法的布尔值。版权所有2006-2015 The MathWorks, Inc. persistent thisTitle %#ok stop = false;开关标志大小写'init' set(gca，'xlimmode'，'manual'，'zlimmode'，'manual'，…'alimmode'，'manual') titleStr = sprintf('当前点-迭代%d'， optimvalues.iteration);thisTitle = title(titleStr，'interp'，'none');toplot = i_generatePlotData(优化值，长度);ylabel(“时间”、“插值函数”,“没有一个”);栏(“堆叠”,如何“edgecolor”,“没有一个”); 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

但请记住，在模拟退火中，当前的调度并不一定是迄今为止发现的最佳调度。我们创建第二个自定义绘图函数，该函数将向我们显示迄今为止发现的最佳时间表。

类型mulprocplotbest.m
函数停止= mulprocplotbest (optimvalues ~,国旗,长度)% mulprocplotbest PlotFcn用于SAMULTIPROCESSORDEMO %停止= mulprocplotbest(选项、optimvalues国旗)optimvalues %结构有以下字段:x %: % fval:当前点函数值在x % bestx:迄今为止最佳点发现% bestfval:函数值在bestx %温度:当前温度%迭代:当前迭代% funccount: % t0函数值的运算次数:开始时间% k:退火参数'k' % % FLAG:调用PlotFcn的当前状态。可能值为:% init:初始化状态% iter:迭代状态% done:最终状态% % STOP:停止算法的布尔值。版权所有2006-2015 The MathWorks, Inc. persistent thisTitle %#ok stop = false;开关标志大小写'init' set(gca，'xlimmode'，'manual'，'zlimmode'，'manual'，…'alimmode'，'manual') titleStr = sprintf('当前点-迭代%d'， optimvalues.iteration);thisTitle = title(titleStr，'interp'，'none');toplot = i_generatePlotData(优化值，长度);Xlength = size(toplot,1);ylabel(“时间”、“插值函数”,“没有一个”); 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，因为默认值使求解器太慢。最后，我们必须设置数据类型“自定义”。

选项= optimoptions(@simulannealbnd，“数据类型”，“自定义”，.．.“AnnealingFcn”@mulprocpermute,“MaxStallIterations”, 800,“ReannealInterval”, 800,.．.“PlotFcn”，{{@mulprocplot，长度}，{@mulprocplotbest，长度}，@saplotf，@saplotbestf});

最后，我们用我们的问题信息调用模拟退火。

schedule = simulannealbnd(fitnessfcn,sampleSchedule，[]，[]，options);删除零列(所有进程空闲)Maxlen = 0;为I = 1:size(schedule,1)如果Max (nnz(schedule(i，:)))>maxlen maxlen = Max (nnz(schedule(i，:)));结束结束%显示时间表Schedule = Schedule (:，1:maxlen)
优化终止:最佳函数值的更改小于options.FunctionTolerance。安排= 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 30 15 10 3 0 0 0 0 0 0 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 38 36 0 0 0 0 0 1 0 0 0 0 0 8 27 37 17 2 0 0 0

另请参阅

相关的话题