英语原文共 9 页，剩余内容已隐藏，支付完成后下载完整资料
通过模拟退火装箱
摘要 -将组合系统逐步建立为全局最小能量配置的过程已被称为模拟退火，统计冷却等。在过去，使用这种技术已经解决了非常大的组合优化问题。也已经表明，对于NP完全问题，这种方法能获得接近最优的解决方案。此外，这种技术适用于满足一些要求的一类问题。
本文的目的是为了说明应用于装箱问题变体的模拟退火方法的一种有效的方法。该方法的计算复杂度与输入大小呈线性关系，类似于该问题的各种众所周知的启发式方法。然而，获得的解决方案比任何启发式方法都好得多。我们考虑的bin-packing问题的特殊变体有几个实际应用，例如进程调度和批处理中的静态任务分配。在撰写本文时，我们还没有看到文献中的装箱问题的随机解决方案。
我们研究的一个显著特点是通过我们的方法获得的高质量解决方案。我们进行的大量仿真实验表明，通过随机方法获得的解决方案比那些众所周知的启发式方法获得的解决方案有着显著改进。
关键词-装箱,组合优化,全局最小值,Monte Carlo方法,NP完备性,模拟退火,统计冷却.
1.介绍
1.1装箱问题
装箱问题的经典定义包括将（可能）不同尺寸的物品列表打包成最小数量的箱子，每个箱子都有一个给定的最大容量。Coffman等人[1]对装箱问题的几种近似算法进行了很好的研究，得到了快速次优解。我们解决的经典问题的变体涉及固定数量的箱子，每个箱子具有无限容量，目标是将这些物品装入这些箱子中，以便每个箱子具有大致相同的总分配。换句话说，我们的尝试是找到最稳定的分配方式将物品分配到箱子当中。我们的问题在以下两个方面不同于经典问题。
1.容器大小不受限制，这个特殊变化背后的基本原理是这个模型在某些实际情况下是合适的。例如，在批量处理环境中，有时需要完成一定数量的(可能)不同大小的任务，给定一个固定数量的处理器。这里的主要目标是找到一个可以最大限度地减少总空闲时间的分配。
2.箱子的总数是固定的。这种变化是上述变化1的直接结果。在实际的情况下，期望可用资源以某种方式有界是合理的古典问题对箱数没有限制。
在本文的其余部分中，为了简洁起见，我们将把这个问题的变体称为装箱问题;在我们提到古典问题的地方，我们将对其进行限定，
以便明确我们所指的是哪个问题。
1.2模拟退火
模拟退火是一种通用的组合优化技术，最初在1983年由Kirkpatrick等人提出。[2]当物理系统接近热平衡和组合问题的中间阶段时，物理系统的状态之间的类比被利用来产生全球最低成本的问题解决方案。这项技术是Metropolis等人早先开发的蒙特卡罗方法的推广。[3]，并已成功用于解决旅行商问题[4]和VLSI电路中线长最小化问题[5]等优化问题。
在该技术中，利用控制参数（物理系统中的温度的模拟）以受控方式探索正在优化的组合系统的解空间，从而得到了对目标函数的连续较好的测量方法。不失一般性，我们将假设被优化的目标函数被最小化，当我们说一些状态导致比其他某个状态更好的目标函数时，我们的意思就是，该状态的目标函数的值较小。
模拟退火与迭代改进类似，这两种技术涉及改变正在优化的系统的状态并检查系统的目标函数。尽管迭代改进不允许增加目标函数的状态改变，从而迫使系统进入局部最小值，但模拟退火允许上坡运动，帮助系统爬出局部最小值并找出其他最小值，从而提高找到最小最小值的机会。通过迭代精修求得的局部最小值类似于在高温快速冷却后在物理系统中获得的亚稳态[6]，并且总体效果是淬火系统导致缺陷被冻结到结构中系统。
1.3动机和以前的工作
将模拟退火应用于装箱问题的主要动机是观察到退火对已知为NP完全的几个组合优化问题产生了非常好的解决方案。
考虑到装箱问题的解决方案空间与项目清单的大小呈指数关系，检查使用模拟退火技术解决此问题的可行性是很自然的。事实上，随着项目列表的大小变得越来越大，我们可以直观地预期退火会比贪婪的启发式执行得更好。在撰写本文时，我们尚未将这种技术应用于文献中的装箱问题。在Laarhoven等人看来，应用随机方法解决这个问题的另一个动机是：[8]退火算法的理论基础达到了一定程度的饱和水平，主要贡献将主要针对新的应用。事实上，自那时以来，退火已被用于解决各种各样的优化问题。
退火实验的典型实例包括两个重要的选择：对应于物理系统的高温和低温状态的控制参数以及改变控制参数的方法，以使系统达到最佳状态。这些关键参数的一组选择被称为退火工序。在文献中有证据表明，组合优化问题的全局最优性可以用概率1来找到，条件是退火工序满足某些条件（8-10）。
在实际应用中，例如VLSI中的电路布局，获得“良好”解决方案所需的计算资源过多。为了解决这个问题，文献中提出了几种方法。Greene等人[6]提出了一个工序，其中涉及退火而不拒绝移动。他们的方法以增加内存使用率为代价提供了显着的提速。Lam等人[5]，白[11]和黄等人。[12]提出了使退火工序有效的技术。
试图弥补退火方法所需的大量计算时间的各种方法可分为三大类 - 并行退火技术[13]，有效退火工序[5,6,11,12]和受控移动生成方法。最后一类方法通常取决于问题实例，并且不能广泛应用于组合优化。文献中较为流行的技术采用有效的退火工序，本文也描述了一个这样的工序。
2.问题的表述
我们将bin-packing问题的一个实例定义为由...组成
l.M个箱，每个箱子都有无限容量;
2.N个项目（大小） ...， ;
3.目标函数（也称为成本或能量函数）定义为
（1）
其中是分配给j个分箱的项目的大小的总和，并且是分配序列。分配序列确定每个项目分配给哪个箱。因此，每个分配序列代表了一个解决问题的可行方案。由此产生的物品分配到分箱也被称为问题（系统）的配置（状态）。是在全局最小化成本函数的每个箱的总分配。从而，
（2）
总的来说，虽然这个问题的一个特例可能不会使它本身成为这样一个完美的分配方案。 因此，存在最小化问题。
以下引理直接来自问题表述。
1.目标函数的大小不超过
目标函数的最大值是通过将项目列表中的所有项目分配到一个箱子并将其他M-1个箱子留空来获得的。这样的分配产生了一个与相同的目标函数。容易看出，其他分配可以为目标函数产生更大的值，因为现在从所有项目都已经分配好了的箱子中移动任何项目将减少目前分配到的箱子和它正在移动到的箱的目标函数
算法退火;
开始
生成随机配置C;
而要做
重复
生成新的配置
；
if
图1.用于装箱的随机算法
问题的目标是识别分配序列
(3)
因此，表示产生目标函数的全局最小值的分配序列。
3.退火算法
图1显示了装箱问题的算法。该算法从温度参数的高值开始。然后逐渐降低温度，直到算法终止时温度达到足够小的值。
在每个温度下，系统都会被扰动几次。在每个温度值下进行的一组迭代称为链。链中的迭代次数有时被称为链长。链长通常是问题大小的一小部分。我们首先注意到bin-packing问题的配置满足Strong Irreducibility [14]的性质。这直接源于观察结果，即装箱问题的配置空间是有限的，并且任何配置都可以通过移动有限数量的物品而从其他任何配置中获得。
该算法首先随机将项目分配给箱子。项目列表未按照项目的大小排序。这种分配作为退火过程的起点，将被称为系统的初始状态。为了从当前状态中获得新的状态，通过选择第4.3节中描述的两种方法之一，系统会受到干扰。计算与这个新的扰动状态相对应的目标函数的值。
然后应用Metropolis [3]标准，算法接受或拒绝新状态。如果，那么新状态将没有任何资格被接受。如果 ，那么新概率被接受
(4)
在仿真过程中，这是通过生成一个均匀分布在[0.0,1]中的随机数TJ并在r小于上面的时接受新的状态来实现的。T（4）是与物理系统中的温度类似的控制参数。当温度达到足够低的值时，在指示最近接受的配置作为找到的最佳解决方案之后，算法终止。
4.退火工序
退火工序通过定量选择三个参数来描述，即温度的起始值，温度的停止值和确定从开始到退火过程结束的温度曲线的递减函数F（t）。
从一个良好的工序中获得的退火曲线通常显示出三个广泛的感兴趣的区域—以高温为特征的高能量区域，中等能量区域和以低温为特征的低能量区域。中间能量区域是明确的并且跨越曲线的温度轴的相对较小部分。我们将把曲线的高能区所描述的系统的行为称为高温状态，并将曲线的低能区描述为低温状态。这些将在下面的章节中进一步描述。
在实际的仿真过程中，我们首先对配置空间进行探索性搜索，我们假设温度是无限的，并接受每个生成的配置。从这些数据中我们可以获得有关这个问题的基本统计量。特别地，我们感兴趣的是成本的平均值和标准偏差状态密度分布。状态信息的密度可以之后用于选择合适的起始值温度参数。
4.1高温状态
退火曲线的这个区域（以及系统的相应行为）通过接受大多数生成的状态来标记。温度参数的值非常高，以至于Metropolis标准始终得到满足。因此，这个制度的平均能量非常高。通常通过监测每个温度下的接受比率来确定起始温度必须达到多高，以获得良好的退火工序。接受比率（被接受的发生状态的比例）被任意地固定在某个较高的值，例如0.9，并且温度被增加到接受比率足够高的值。
虽然这独立于问题的方法起到了固定温度起始值的作用，但是通常它会产生太高的温度值，从而产生浪费计算资源的退火工序。对于装箱问题，引理1给出了目标函数的理论最大值。如果控制参数刚好足够高以接受具有这种最大能量的配置，则遵循该温度足够高以接受任何配置。这是我们用来达到工序的高温限制的技术。
如果是项目列表中具有最大尺寸的项目，则将单独分配到一个箱并将所有其他项目分配到另一个箱的配置具有属于最大能量配置的一个移动内的属性。这个配置的能量由下式给出
(5)
并且这个配置和最大能量配置之间的能量差（由引理1）给出
=
假设在不失一般性的情况下，只存在一个最大能量配置，只有在（仅限于在N个可能的移动中只有一个能产生最大的能量配置）。这给出了高温条件
（6）
不用说，的选择大于方程（6）所提出的选择，不会产生更好的解决方案。
退火算法在这种高温条件下产生了良好的退火曲线。根据White [11]提出的条件，Huang等人[12]建议使用高温形式的限制 其中是成本分配的标准偏差（可以从状态密度图中获得），并且可以假定高斯成本分布并选择一个足够高的温度来接受与当前配置相差几个标准偏差的配置，并以任意固定的概率来计算。通过这种方式确定高温极限而获得的解决方案的质量没有显著改善。
4.2低温状态
退火曲线的这个区域的特征在于接受新的状态，主要是如果它们得到一个目标函数更好的值。Metropolis标准主要由成本变化决定，而不是由于低温度值导致的接受概率。该曲线的平均能量接近曲线极端低温末端的全局最小值。再次，很容易看到，必须存在一个或多个配置，以限制目标函数的下侧。
文献中的几个退火工序建议，当几个计算链中溶液的质量没有明显变化时，退火过程就会停止。虽然总的来说，这是一个很好的指导原则，但问题实例可能有几个退化的低能态。在这种情况下，在低温下，配置可能会连续重复几次，而不一定是全局最小值。我们确定何时应该停止退火过程的方法考虑了系统的最低温度范围。
目标函数中的最小变化可以很容易估计。目标函数的最小值为零（理论上）。设是物品列表中尺寸最小的物品，因此，任何扰动的最小将涉及将该物品从箱子中移动到它被分配到任何其他箱子的完美分配。这产生。考虑一个分配，其中M-2个分箱的总分配为,剩余的两个分箱分别为和的总分配。在这个配置中，总共有N个可能的移动，只有一个会是完美的分配。因此,它必定是 均衡条件得到满足。这给了我们低温限制
（7）
当然，的较小选择同样适用，尽管这会浪费计算时间，因为一旦达到完美分配并且温度不高于方程（7）给出的限制，就不会接受新的配置。
4.3一代移动
退火过程中的移动表示为系统生成候选配置。根据Metropolis标准中的控制参数和随机数r，这个新的配置可能会或可能不会被接受为系统的下一个状态。通常，通过以某种方式修改系统的当前状态来生成移动。在实际模拟过程中，我们注意到两种不同类型的移动是有效的
1.将单个随机选择的物品从当前分配给它的箱中重新定位到随机选择的箱，相关的能量变化由
（8）
2.随机选择当前分配给两个不同箱的两个物品并交换它们的位置，在这种情况下能量的相关变化是
全文共9690字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[9523]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
