主要内容
使用具有自定义数据类型的模拟退火的多处理器调度
这个示例展示了如何使用模拟退火来最小化使用自定义数据类型的函数。本文针对多处理器调度问题定制了模拟退火算法。
多处理器调度问题
多处理器调度问题包括在一组处理器上寻找任务的最优分配。给出了处理器的数量和任务的数量。处理器完成一项任务所花费的时间也作为数据提供。每个处理器独立运行，但每次只能运行一个作业。我们把把所有作业分配给可用的处理器称为“调度”。问题的目标是为给定的任务集确定最短的时间表。
首先，我们决定如何用自定义数据类型优化问题来表示这个问题Simulannealbnd.功能可以解决。我们提出以下方案：首先，让每个任务由1到1之间的整数和任务总数表示。类似地，每个处理器由1之间的整数和处理器的数量表示。现在，我们可以存储给定作业将在称为“长度”的矩阵上的给定处理器上的时间量。处理器“i”需要完成任务“j”的时间量将存储在长度（i，j）中存储。
我们可以用类似的方式表示一个时间表。在给定的调度中，行(1到处理器数量之间的整数)表示处理器，列(1到任务数量之间的整数)表示任务。例如，调度[1 2 3;4 5 0;6 0 0]是在处理器1上执行的任务1、2和3，在处理器2上执行的任务4和5，在处理器3上执行的任务6。
在这里，我们定义了我们的任务数，处理器数量和长度数组。各个行的不同系数代表了不同处理器以不同的速度工作的事实。我们还定义了一个“样本成本”，这将是我们的起始点输入Simulannealbnd.．
RNG.默认的重复性的％NumberofProcessors = 11;numberoftasks = 40;长度= [10 * rand（1，numperoftasks）;7 * rand（1，numperoftasks）;2 * rand（1，numperoftasks）;5 * rand（1，numperoftasks）;3 * rand（1，numperoftasks）;4 * rand（1，Numberoftasks）;1 * rand（1，numperoftasks）;6 * rand（1，numperoftasks）; 4*rand(1,numberOfTasks); 3*rand(1,numberOfTasks); 1*rand(1,numberOfTasks)];处理器上任务的％随机分发（起点）Sampleschedule = Zeros（NumberofProcessors，Numberoftasks）;为了任务= 1：numberoftasks processorid = 1 +地面（rand *（numberofprocessors））;index = find（sampleschedule（processorid，:) == 0）;SamplesChedule（ProcessorID，索引（1））=任务;结尾
自定义数据类型的模拟退火
默认情况下，模拟退火算法求助于判断变量是双数据类型的解决问题。因此，用于生成后续点的退火功能假定当前点是类型的类型。但是，如果数据类型选项设置为“自定义”模拟退火求解器还可以在涉及任意数据类型的优化问题上工作。您可以使用您喜欢的任何有效的MATLAB®数据结构作为决策变量。例如，如果我们想要Simulannealbnd.要使用“SampleSchedule”作为决策变量，可以使用整数矩阵指定自定义数据类型。除了设置数据类型“自定义”的选项我们还需要通过此提供自定义退火功能Annealingfcn.选项可以生成新点。
定制退火功能
本节介绍如何创建和使用所需的自定义退火功能。多处理器调度问题的试验点是处理器（行）和任务（列）的矩阵，如前所述。多处理器调度问题的自定义退火函数将使作业计划作为输入。然后，退火函数将修改此计划并返回一个与温度成比例的金额更改的新计划（如模拟退火的惯常）。在这里，我们展示了我们的自定义退火功能。
类型mulprocpermute.m.
函数计划= MulProcPermute（OptimValues，问题数据）％MulProcPermute将一个随机任务移动到不同的处理器。％newx = mulprocpermute（优化值，问题文件）在当前点和当前温度％2006上生成一个基于点的％2006 The MathWorks，Inc。计划= OptimValues.x;％此循环将生成“距离”的邻居等于％OptimValues.Temperature。它通过将邻居生成到％当前时间表来实现这一点，然后为该邻居生成邻居，彼此接通，直到它产生足够的邻居。对于i = 1：楼层（优化值.Temperature）+1 [nrows ncols] =大小（时间表）;schedule =邻居（计划，nrows，ncls）;结束％=====================================================％函数计划=邻居（计划，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
函数timetocomplete = mulprocfitness（计划，长度）％mulprocfitness确定给定计划的“fitness”。换句话说，它告诉我们给定的时间表使用“长度”％版权所有2006 The MathWorks，Inc。[nrows ncls] =大小（计划）;timetocomplete =零（1，nrows）;对于i = 1：nrows timetocomplete（i）= 0;对于j = 1：ncols如果时间表（i，j）〜= 0 timetocomplete（i）= timetocomplete（i）+长度（i，schedule（i，j））;else break结束结束终端timetocomplete = max（timetocomplete）;
Simulannealbnd.只调用一个参数的目标函数x，但我们的健身函数有两个论点：x和“长度”。我们可以使用匿名功能来捕获附加参数的值，长度矩阵。我们创建一个函数处理“ObjectiveFCN”，以匿名函数进行一个输入x，但称之为“mulprocfitness”x和“长度”。当创建函数句柄‘FitnessFcn’时，变量“length”有一个值，因此匿名函数会捕获这些值。
以前定义％长度fitnessfcn = @（x）mulprocfitness（x，长度）;
我们可以添加自定义绘图功能，绘制任务在每个处理器上采用的时间长度。每个条形代表处理器，每个条的不同颜色块是不同的任务。
类型mulprocplot.m
函数停止= mulprocplot (optimvalues ~,国旗,长度)% mulprocplot PlotFcn用于SAMULTIPROCESSORDEMO %停止= mulprocplot(选项、optimvalues国旗)optimvalues %结构有以下字段:x %: % fval:当前点函数值在x % bestx:迄今为止最佳点发现% bestfval:函数值在bestx %温度:当前温度% iteration:当前迭代% funccount:函数计算次数% t0:开始时间% k:退火参数'k' % % FLAG:调用PlotFcn的当前状态。可能的值为:% init:初始化状态% iter:迭代状态% done:最终状态% % STOP:停止算法的布尔值。% % Copyright 2006-2015 The MathWorks, Inc. persistent thisTitle %#ok stop = false;切换标志案例'init'set（gca，'xlimmode'，'manual'，'zlimmode'，'manual'，...'Alimmode'，'手册'）titlestr = sprintf（'当前点 - 迭代％d'，OptimValues.Ceration）;thisTitle =标题(titleStr“插值函数”,“没有一个”);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.
函数stop = mulprocplotbest（〜，OptimValues，标志，长度）％mulprocplotbest plotfcn用于samultiprocessordemo％stop = mulprocplotbest（选项，优化值，标志），其中OptimValues是具有以下字段的％结构：％x：当前点％fval：函数x％bestx的价值：最佳点到目前为止最佳选择效率最佳：功能值在最佳温度：当前温度％迭代：当前迭代％funccount：函数评估数量％t0：开始时间％k：退火参数'k'％％标志：调用PlotFCN的当前状态。可能的值为:% init:初始化状态% iter:迭代状态% done:最终状态% % STOP:停止算法的布尔值。% % Copyright 2006-2015 The MathWorks, Inc. persistent thisTitle %#ok stop = false;切换标志案例'init'set（gca，'xlimmode'，'manual'，'zlimmode'，'manual'，...'Alimmode'，'手册'）titlestr = sprintf（'当前点 - 迭代％d'，OptimValues.Ceration）;thisTitle =标题(titleStr“插值函数”,“没有一个”);toplot = i_generatePlotData(最优值，长度);Xlength =大小(如何,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因为默认值使求解器太慢。最后，我们必须设置数据类型“自定义”。
选项= Optimoptions（@simulannealbnd，“数据类型”，“自定义”，．..“AnnealingFcn”@mulprocpermute,'maxstallitions'，800，'ReannealInterval'，800，．..'plotfcn'，{{@mulprocplot，lengths}，{@ mulprocplotbest，lengths}，@ saplotf，@ saplotbestf}）;
最后，我们通过问题信息调用模拟退火。
时间= simulannealbnd (fitnessfcn sampleSchedule,[],[],选项);％删除零列（所有进程都是空闲的）maxlen = 0;为了i = 1:尺寸(时间表,1)如果MAX（NNZ（Schedule（i，i：）））> maxlen maxlen = max（nnz（schedule（i，:)））;结尾结尾%显示时间表计划=计划(:1:maxlen)
优化终止：更改最佳函数值小于options.functiontolerance。Schedule = 22 32 0 0 0 0 0 5 0 0 0 0 0 0 0 0 7 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 031 33 29 4 21 9 25 40 24 26 26 14 0 0 0 0 0 13 16 23 2 2 2 2 2 2 2 2 2 2 2 26 0 0 0 0 0 0 3 36 1 0 0 0 0 0 8 27 37 17 2 0 0 0 0
也可以看看
相关话题
您还可以从以下列表中选择一个网站：
