英语原文共 12 页，剩余内容已隐藏，支付完成后下载完整资料
自适应变邻域搜索算法用于求解多目标设施不等面积设施布局问题
Kazi Shah Nawaz Ripon, Kyrre Glette, Kashif Nizam Khan, Mats Hovin, Jim Torresen
摘要：
在本文中，我们报告我们的进化求解方法的调查结果不平等的地区多目标设施布局问题 (FLP) 使用变邻域搜索(VNS) 与一种自适应的方案的Pareto最优解集，所提出的最后的布局。不等面积多目标设施布局问题 FLP 包括一类极为困难和广泛适用的优化问题，在不同的领域所产生和满足真实世界的应用程序的要求。VNS是探索本地搜索方法，其基本思想是系统的邻域内的本地更改搜索。传统上，本地搜索被应用于解决方案的每一代的进化算法，和经常被批评为浪费计算时间。为了解决这些问题，提出的方法组成的与改性 1 VNS-选择本地搜索，扩展自适应本地搜索优化多目标和多目标遗传算法 (GA) 的方案。不像传统的本地搜索，提出自适应局部搜索计划自动确定VNS中是否使用了遗传算法循环。我们调查了该方法的性能与多目标基于遗传算法的方法，无需本地搜索和增强与传统的本地搜索。计算结果表明，该方法与VNS同时在大多数性，优化多个条件能更有效和可以找到接近最优布局。
1、介绍
设施布置问题 (FLP) 是为满足一个或多个目标测定最有效的物理安排大量交互，按顺序在工厂车间的制造系统设施。设施通常代表组织和的最大和最昂贵资产[1] 组织来说至关重要。设施是实体在一个专用的分配任务，并且可以包括一个部门，机床、 工作中心、 制造单元、 一台机器商店或仓库 [2]。FLP 是一个经典的计算机科学问题和已被证明是 NP 难题 [3]。布局规划在一家制造企业也是重要经济审议。一种有效的布局将帮助改善任何公司其经营业绩，可以减少达 50%的占总经营费用 [4];相反的无效的布局可以添加多达36%至物料搬运成本 [5]。每年在美国独自度过关于规划和修改设施布局 [6]估计那是一笔超过 2500 亿。
在过去几十年，大量的优化和启发式算法求解 FLP有 [7-9] 得到发展。大多数的这些方法都被称为二次分配问题 (QAP)， 特别适合于等面积设施。这些方法的主要缺点是不考虑几何约束，如大小不等的设施。这些方法往往把重点放在相对等面积设施在平面图上的位置。如果所有的设施平等的地区，或可以不改变设施之间互换，其余整体邻接或距离的关系设施，很容易提前指定有限数目的潜力这些设施占据 [10] 的站点。然而，在大多数的真实世界等面积设施的应用，是一个很糟糕的假设 [11，12]。
当布局有不同地区设施时，再也不能视为 n个设施分配 n 个不同质心的位置问题。相反，质心的位置取决于确切的配置选择，制作 QAP 配方的不等面积 FLP 面积相等的同行相比不那么听话。若要处理不等面积 FLPs，早期基于离散模型的启发式算法，划分成网格的大小相等的平面图正方形。然后，每个设施被分配给其中最接近它的总面积的平方数。虽然在概念上简单，这种方法主要是生成畸形设施 [12]。尽管如此，一些程序对复合设施形状的限制使问题更易控制和可执行。不等面积FLP方案都是针对这种情况下，有效地发现给定数目的最优安排非重叠与不等面积要求在工厂的地板上不可分割的设施。这反过来又使得 不等面积的FLP ，在很多人遇到的基本优化问题的领域制造业和服务机构。
在 FLP进行的研究大部分集中在单目标，要么定量 （基于距离） 或定性（基于邻接） 优化的布局。与之相反，实际 FLP涉及几个相互冲突的目标。因此，在定量和定性目标之间必须同时考虑得出任何可能的结论。优化布局是关于当另一个标准是最重要时，给定准则可能是一个较小可能性的候选人。在一般情况下，在 FLP中最小总物料搬运(MH) 成本通常用作优化准则。亲密关系评级、 危险的运动，安全和相似也是在 FLP的重要条件。事实上，这些定性的因素考虑了最终的布局的重大影响。此外，使用只有一个定量的目标时，标准经常调和包括 像内部知识 [13]的判断。因此，FLP 属于多目标优化问题 （MOOP）。
多目标优化是一种技术用来将几个对象同时将他们转换成一个目标。多重最佳化问题目标是要找到一套Pareto最优解[14]，这是卓越的解决方案时考虑所有目标。在多重最佳化问题上来，绝对最优解是缺席并且设计器必须选择一种解决方案，提供最有用的作为一种替代目标之间的权衡。因此，它替代了一个单一的解决方案，它是更加现实和适当生成大量的 好 的布局，这些布局满足几个设计者规定条件的设施，让决策者基于当前的需求在选择之间它们。出人意料的是，还有一点注意研究的多目标 FLP在不平等地区 FLP的情况下少得多。
最近，元启发式方法也已并广泛应用于解决大 FLP [8，9]。其中，遗传算法 (GA) 已经从理论上证明在复杂搜索共享空间提供强健的搜索 [9]。尽管GA成功应用于众多的优化问题，包括 FLP，它有一个主要应用于此类问题的限制。GA能在整个搜索空间做全球搜索，但没有办法探索搜索空间内辐合区产生的遗传算法回路。在某些情况下，它要实际执行速度太慢了。一个很成功的方式来提高GA的性能是将它与本地搜索杂交。本地搜索技术被用来改善解决方案，这个方案通过遗传算法搜索其附近探索最适合的个人和如果更好地找到一个替换它。
相对变邻域搜索 (VNS) 是近期的元启发式方法，基于系统变化的局部搜索的可能邻域内 [15，16]。与其他只使用单一的邻域搜索法的基于局部搜索方法的元启发式方法相反，当前 VNS解决方案的探索越来越远距离的街区，有关当前的解决方案，以及从这些如果存在一个更好的解决方案中跳出。在这种方式下，它保持有利特性的现任解决方案并获得有前景的邻近解决方案。通过允许使用不同邻域搜索方法，VNS可以容易地逃脱从局部最优解和全局最优解的走向。
不幸的是，到目前为止只有一点对本地搜索的多目标优化技术的研究。然后，再次与本地搜索杂交可能会降低全球搜索多目标GA的能力，需要更多的计算时间比常规的GA [17]。这是因为应用本地搜索在总体中的所有个体的搜索是计算集约化过程。因此，大部分的计算时间是在本地搜索中度过。为了克服这一弱点，一种自适应是否能将本地搜索方案用于自动控制GA循环。
虽然 GA解决FLP优势和良好的性能已被证明在文献中，却没有任何的正式解决考虑到多个目标分别使用局部搜索方法不平等地区 FLP 。它也是引人注目的，所有现有的要解决不平等地区 FLPs 的方法使用单一目标或加权总和。其结果是，Pareto最优是永远不会用于解决不等面积 FLPs。在我们以前的文章[11]，我们提出多目标遗传算法的不等面积 FLPs 使用Pareto最优 [11]，但没有任何本地搜索。在这项工作，我们建议多目标遗传算法求解不等面积 FLP 使用自适应局部搜索计划，探讨其在性能解决这类多目标的问题。建议方法呈现布局的Pareto最优解集。基于自适应局部搜索建议的方案对改性VNS与相似性系数测量 (SCM)，删除传统GA表现出的全局搜索问题。另外我们延长 1-选择集成内的局部搜索 [18]VNS框架由纳入统治策略处理不平等地区多目标的 FLPs。我们使用的非支配排序遗传算法 (NSGA 2) [19] 2 的多目标进化算法 （MOEA）。
本文是通过以下方式组织的。第 2 节列举了相关的文献。第 3 节提到Pareto-的重要性在解决 FLPs.第 4 节应用最优性证明自适应局部搜索计划，还描述了其执行情况。节 5 概述了执行的建议不平等的地区多目标的 FLP 办法。本节还包括布局施工过程和执行自适应局部搜索使用VNS。第 6节 分析结果，紧接着第 7 节得出结论。
2、相关工作
几种 FLP 办法都可用在文献中，其中主要可以分为 (i) 确切方法及 (ii)启发式和元启发式方法。确切办法的最大局限是，由于计算的难解他们不能以最佳方式解决大规模 FLP。优化算法已成功应用到小规模 FLPs，但他们需要高计算能力和广泛的内存上限能力。最近一项调查表明，现有的所取得的成果最佳的精确算法 （分支和绑定） 是温和的。在合理时间它不适合于求解 FLPs 大于 20 设施 [20]。因此，研究者们依靠的启发式算法通过庞大的搜索空间的搜索，这个搜索空间是实际的 FLPs 的代表。
Armour和 Buffa [21]给出了第一种不等面积 FLP 成对交换法的解释。自那时以来，相当几个作者也试图处理不等面积 FLPs。最近对不平等地区 FLPs 在 [1，7] 中给出的点评。Konak等人 [22]开发了一个混合的整数规划 (MIP) 制定基于灵活托架结构 (FBS)解决不等面积 FLPs ，可以在最多的 14-设施问题中找到最优解。在条款的元启发式算法，Castillo 等人 [23] 应用混合整数为解决这一问题的非线性规划。Hu和Wang [24]应用遗传算法于不平等区 FLPs 实现的最小的布局成本。Tate和Smith [10] 提出了一种基于遗传算法的模型为 FLPs 与不平等的领域和不同几何状的限制。不幸的是，所有这些方法都是优化单一的目标。在[1] 提出了一种，杂交元启发式求解 FLP 是不平等的地区。然而，它主要基于离散表示。近年来，基于遗传算法和 MIP 方法 [25]，禁忌搜索 (TS)-基于分层树表示 [26]，蚁群系统的方法(AS)-基于方法 [27] 和蚁群算法 (ACO)与基于 FBS 的方法 [28] 相结合，提出了解决基于遗传算法的方法，所有这些不平等地区类似 FLPs。方法侧重于单一的目标。在一种多目标方法解决不平等的地区 [29] 中提出了 FLP。然而，它加权和法用于处理多个目标。
3、在 FLP Pareto最优的重要性
FLPs 的典型途径优化目的只有一个：定量或定性目的。定量的目的是尽量减少的总和该产品材料的流动、 距离和运输成本，每个距离单位为每一对设施的单位。它被称为普遍材料处理 (MH) 成本。定性目标旨在将利用常用材料，人员的设施或实用程序彼此相邻的同时分离设施安全、 噪音或清洁的原因。定性目标使用关系图，以最大限度地为整体的邻接措施给定的布局。这张图表指定亲密评级 (CR) 为每个对设施。
许多研究者有质疑选择单一的标准来解决 FLPs，因为定性方法和定量方法各有适当的优点和缺点 [30] 。对定量方法的主要限制是他们认为可以量化并不考虑任何定性因素的关系。另一面，定性研究方法遭受在所有缺陷定性因素上做出的强烈的假设素，这些因素可以聚合为一个标准。此外，在MOOP中， 绝对最佳解决方案中获取满足所有目标几乎都是不可能。这是由于目标性质的冲突，这个冲突是，当另一恶化的目标出现时，只获得了一个更好的目的。在这种情况下，它是需要生成一组大约高效解决方案 — —Pareto最优解。这些解决方案是在更广泛感觉在搜索空间中没有其他的解决办法是可以优化考虑到所有的目标。因此，决策者可以根据订单或客户的要求，挑选所有特定生成解决方案的最佳解决方案。
尽管研究人员在过去的几年已经提出了方法求解 [7，9] 的多目标 FLP ，这些方法，在大多数情况下，导致加权求和函数的优化。在此方法中，使用加权的系数将多个目标加起来到一个单一的标量的目标。不切实际的加权求和方法涉及困难的提前正常化这些目标和量化权重。另外，其他的这种技术的缺点问题包括预先确定的目标，获得劣质的相对权重非支配解，指定重量的用户参与值，并在同一时间获得一个单一的解决方案。有兴趣的读者可以找到在 [30，31] 的细节。要克服这些弱点，Pareto最优已成为有效的替代。
4.选择自适应局部搜索的理由
虽然GA可以快速找到有前景的地区，同时解决可以组合优化问题，它可以从经过缓慢和过早收敛之前提供准确的解决方案。而且，GA有固有的收敛到全局最优解的困难，这个最优解在在复杂和庞大的搜索空间中具有足够的精度，这个空间在现实世界的 FLP很常见 。这是因为遗传算法的基本特征 — — 不使用先验知识和无法探讨搜索空间内收敛性由 GA 循环生成的地区。与此相反的是，本地搜索的启发式算法可以反复检查一点在附近的一组当前解决方案，如果存在一个更好的邻居替换它。因此，这两种方法之间的协同作用可以给一个家庭的混合算法，同时全球和精确。遗传算法全球范围内探讨了，域和发现一套好的初始估计，而本地搜索进一步提炼这些解决方案中为了找到最近的最佳解决方案。
但是，与本地搜索杂交常常会降低遗传算法全局搜索的能力，这是因为，本地搜索通常应用于解决方案的每一代的遗传。作为结果，本地搜索技术不得不检查大量用于寻找从每个生通过遗传操作生成的初始解中的局部最优解的解决方案。它是什么也不是，但仅仅是浪费 CPU 时间。此外，大部分的本地搜索技术在混合GA中使用设计没有任何分析他们[32] 的收敛特性。为降低计算时间花费的本地搜索和改善这些弱点应用程序的本地搜索，我们实现了自适应的局部搜索技术增强与VNS，将只搜索由遗传算法的收敛区域周围循环而不是适用于所有个体。
提出的自适应局部搜索背后的基本思想计划是，考虑遗传算法是否收敛到全局最优解。当遗传算法收敛到全局优化，解决办法是不断提高。在此情况下，本地搜索应用程序是为了节省不必要的使用的计算时间。与此相反，遗传算法的性能绝对恶化，如果它不衔接到全局最优解。最坏的打算是，如果这种情况的不断进行，它将卡住造成局部最优解在早熟收敛。局部搜索技术内的GA 循环有助于改善这种情况，因为它可以生成新有一定高的健身价值的个体像由GA产生的更高级的个体。
5.执行情况
5.1.染色体表示
该方法使用的分层树状结构 [27]表示染色体适合不等面积 FLPs。 切片树是一棵二叉树是用来表示一个分层的结构。有n个设施的 FLP，切片树由 n 个树叶和 n -
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[28941]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
