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

打开脚本

这个示例展示了如何使用模拟退火来最小化使用自定义数据类型的函数。本文针对多处理器调度问题定制了模拟退火算法。

多处理机调度问题

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

首先，我们决定如何用自定义数据类型优化问题来表示这个问题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。

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

rng默认的%为了再现性numberOfProcessors = 11;numberOfTasks = 40;长度=[10 *兰德(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)];任务在处理器上的随机分布(起始点)sampleSchedule = 0 (numberOfProcessors numberOfTasks);对于task = 1:numberOfTasks processorID = 1 + floor(rand*(numberOfProcessors));指数=找到(sampleSchedule (processorID:) = = 0);sampleSchedule (processorID、索引(1))=任务;终止

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

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

自定义退火函数

本节展示如何创建和使用所需的自定义退火函数。多处理器调度问题的试验点是前面讨论过的处理器(行)和任务(列)的矩阵。多处理器调度问题的自定义退火函数将以作业调度为输入。退火函数将修改这个时间表，并返回一个与温度成比例变化的新时间表(这是模拟退火的惯例)。在这里我们显示我们的自定义退火功能。

类型mulprocpermute.m

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

mulprocfitness确定给定计划的“适合度”。换句话说，它告诉我们给定的时间表将花费多长时间，使用“长度”给出的%知识nrows timeToComplete = 0 (1);for i = 1:nrows timeToComplete(i) = 0;for j = 1:ncols if schedule(i,j)~=0 timeToComplete(i) = timeToComplete(i)+length (i,schedule(i,j));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;set(gca，'xlimmode'，'manual'，'zlimmode'，'manual'，…)'alimmode'，'manual') titleStr = sprintf('Current Point - Iteration %d'， optimvalues.iteration);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

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

类型MulprocBest.m

函数stop=mulprocplotbest（~，optimvalues，flag，length）%mulprocplotbest PlotFcn用于SAMULTIPROCESSORDEMO%stop=mulprocplotbest（选项，optimvalues，flag）其中OPTIMVALUES是一个具有以下字段的%结构：%x:当前点%fval:函数值在x%bestx:迄今为止找到的最佳点%bestfval:函数值在bestx%温度：当前温度%iteration:当前迭代%funccount:函数求值次数%t0:开始时间%k:退火参数“k%”标志：Curr调用PlotFcn的ent状态。可能的值为：%init:初始化状态%iter:迭代状态%done:最终状态%%STOP:停止算法的布尔值。%%版权所有2006-2015 the MathWorks，Inc.persistent thisTitle%#ok STOP=false；设置了开关标志case'init'（gca，'xlimmode'，'manual'，'zlimmode'，'manual'，'alimmode'，'manual'）标题栏=sprintf（'当前点-迭代%d'，'optimvalues.Iteration）；thisTitle=标题栏（标题栏，'interp'，'none'）；toplot=i_generatePlotData（optimvalues，Length）；Xlength=尺寸（toplot，1）；ylabel（'时间'，'interp'，'none'）；条（toplot，'Stacker'，'edgecolor'，'none'）；设置（gca，'xlim'，[0,1+Xlength]）如果~rem（optimvalues.iteration，100）toplot=i_generatePlotData（optimvalues，Length）；bar（toplot，'stacked'，'edgecolor'，'none'）；titleStr=sprintf（'Best Point-迭代%d'，optimvalues.iteration）；thisTitle=title（titleStr，'interp'，'none'）；终端函数toplot=i_generatePlotData（optimvalues，length）schedule=optimvalues.bestx；nrows=size（schedule，1）；%删除零列（所有进程都是空闲的）maxlen=0；对于i=1:nrows如果max（nnz（schedule（i，：）>maxlen-maxlen=max（nnz（schedule（i，：））；end-end-schedule=schedule（：，1:maxlen）；toplot=zeros（size（schedule））；[nrows，ncols]=size（schedule）；对于i=1:nrows for j=1:ncols，如果计划（i，j）=0，则顶部批次（i，j）=0；否则顶部批次（i，j）=长度（i，计划（i，j））；结束

模拟退火选项设置

我们选择已创建的自定义退火和绘图函数，并更改一些默认选项。ReannealInterval设置为800，因为ReannealInterval当求解器开始在局部取得很大进展时，似乎就会升温。我们还减少了史泰利特利米特到800，因为默认值使求解器太慢。最后，我们必须设置数据类型“习惯”。

options=options（@simulannealbnd，“数据类型”，“自定义”，．..“AnnealingFcn”@mulprocpermute,“MaxStallIterations”, 800,“ReannealInterval”, 800,．..“PlotFcn”，{{@ multiprocplot, length}，{@ multiprocplotbest, length}，@saplotf，@saplotbestf});

最后，我们将问题信息称为模拟退火。

时间= simulannealbnd (fitnessfcn sampleSchedule,[],[],选项);%删除零列(所有进程都是空闲的)maxlen = 0;对于i = 1:尺寸(时间表,1)如果Max (nnz(schedule(i，:)))) maxb0 maxlen = Max (nnz(schedule(i，:)));终止终止%显示时间表计划=计划(:1:maxlen)

优化终止:更改的最佳功能值小于选项。功能公差。安排= 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