使用自定义数据类型的模拟退火的多处理器调度
此示例显示如何使用模拟退火来最小化使用自定义数据类型的函数。这里，模拟退火被定制以解决多处理器调度问题。
多处理器调度问题
多处理器调度问题包括在一组处理器上查找任务的最佳分发。给出了处理器的数量和任务数量。通过处理器完成任务所需的时间也被提供为数据。每个处理器独立运行，但每个处理器一次只能一次运行一个作业。我们称为可用处理器的所有作业的分配是“计划”。问题的目标是确定给定的任务集的最短时间表。
首先，我们确定如何在自定义数据类型优化问题方面表达此问题simulannealbnd功能可以解决。我们提出以下方案：首先，让每个任务由1到1之间的整数和任务总数表示。类似地，每个处理器由1之间的整数和处理器的数量表示。现在，我们可以存储给定作业将在称为“长度”的矩阵上的给定处理器上的时间量。处理器“i”需要完成任务“j”的时间量将存储在长度（i，j）中存储。
我们可以以类似的方式代表一个时间表。在给定的计划中，行（1到10个处理器之间的整数）将表示处理器和列（1到TASK的整数）将表示任务。例如，时间表[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 *兰德(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”以便通过匿名函数捕获这些值时，变量“长度”具有值。
以前定义％长度fitnessfcn = @（x）mulprocfitness（x，长度）;
我们可以添加一个定制的绘图函数来绘制任务在每个处理器上占用的时间长度。每个条代表一个处理器，每个条上不同颜色的块代表不同的任务。
类型mulprocplot.m.
函数stop = mulprocplot（〜，优化值，标志，长度）％mulprocplot plotfcn用于samultiprocessordemo％stop = mulprocplot（选项，优化值，标志），其中优化值是一个％结构，其中包含以下字段：％x：当前点％fval：functionx％bestx的价值：最佳点到目前为止最佳选择效率最佳：功能值在最佳温度：当前温度％迭代：当前迭代％funccount：函数评估数量％t0：开始时间％k：退火参数'k'％％标志：调用PlotFCN的当前状态。可能的值为：％init：初始化状态％erer：迭代状态％dode：最终状态%% stop：boolean停止算法。%% 2006-2015 MathWorks，Inc.持久性闪烁insitle％#ek stop = false;切换标志案例'init'set（gca，'xlimmode'，'manual'，'zlimmode'，'manual'，...'Alimmode'，'手册'）titlestr = sprintf（'当前点 - 迭代％d'，OptimValues.Ceration）;thistitle = title（titlestr，'interp'，'none'）;toplot = i_generyplotdata（优化值，长度）;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
但请记住，在模拟退火时，目前的时间表不一定是到目前为止发现的最佳时间表。我们创建了第二种自定义绘图功能，将显示到我们到目前为止发现的最佳计划。
类型mulprocplotbest.m.
函数stop = mulprocplotbest（〜，OptimValues，标志，长度）％mulprocplotbest plotfcn用于samultiprocessordemo％stop = mulprocplotbest（选项，优化值，标志），其中OptimValues是具有以下字段的％结构：％x：当前点％fval：函数x％bestx的价值：最佳点到目前为止最佳选择效率最佳：功能值在最佳温度：当前温度％迭代：当前迭代％funccount：函数评估数量％t0：开始时间％k：退火参数'k'％％标志：调用PlotFCN的当前状态。可能的值为：％init：初始化状态％erer：迭代状态％dode：最终状态%% stop：boolean停止算法。%% 2006-2015 MathWorks，Inc.持久性闪烁insitle％#ek stop = false;切换标志案例'init'set（gca，'xlimmode'，'manual'，'zlimmode'，'manual'，...'Alimmode'，'手册'）titlestr = sprintf（'当前点 - 迭代％d'，OptimValues.Ceration）;thistitle = title（titlestr，'interp'，'none'）;toplot = i_generyplotdata（优化值，长度）;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，因为默认值使求解器太慢。最后，我们必须设置数据类型“自定义”。
选项= Optimoptions（@simulannealbnd，'数据类型'那'风俗'那......'Annealingfcn'，@mulprocpermute，“MaxStallIterations”, 800,“ReannealInterval”，800，......“PlotFcn”，{{@ multiprocplot, length}，{@ multiprocplotbest, length}，@saplotf，@saplotbestf});
最后，我们通过问题信息调用模拟退火。
schedule = simulannealbnd（fitnessfcn，sampleschedule，[]，[]，选项）;%删除零列(所有进程都是空闲的)maxlen = 0;为了i = 1：大小（时间表，1）如果Max (nnz(schedule(i，:)))) maxb0 maxlen = Max (nnz(schedule(i，:)));结尾结尾％显示计划Schedule =计划（：，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
也可以看看
相关的话题
- 算法设置
- 如何模拟退火工程
- 在并行处理中最小化MakEspan(优化工具箱)
你也可以从以下列表中选择一个网站:
