2022年群蚁算法翻译 .pdf

《2022年群蚁算法翻译 .pdf》由会员分享，可在线阅读，更多相关《2022年群蚁算法翻译 .pdf（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 离散优化求解工业布局问题的蚁群算法Y.Hani*,L.Amodeo,F.Yalaoui,H.Chen ISTIT-OSI,(CNRS 2732)Universite de Technologie de Troyes,12 rue Marie Curie BP2060,10010 Troyes cedex,France Received 26 August 2005;accepted 6 October 2006 Available online 12 January 2007 摘要本文提出了一个与局部搜索相结合的被用于布局问题中的混合蚁群优化算法-ACO_GLS。ACO_GLS 被适用于工

2、业中的情况，其被法国的铁路系统设施（SNCF）用在列车的维修中。结果表明，与实际布局相比，这种实现有近20%的改善。由于问题建模为一个二次分配问题LEM（QAP），我们将我们的方法与一些可以解决此问题的最佳启发式方法做了比较。实验结果表明，在小型实例中，ACO_GLS 算法表现更好，而对于大型实例，其计算结果依旧令人满意。关键词：布局问题；二次分配问题；蚁群优化；局部搜索1.介绍设施布局问题（FLP）是一个发现机器的很好的配置，在一个给定的设备以优化生产流程的同时最小化总成本的设备或其他资源。它对一个制造系统的性能具有重要意义。设施布局问题在很多方面都有应用，如厂房组织的应用，新的生产建设单位

3、，或设备分配。一个完整的布局描述的问题可以从（Kusiak 和 Heragu，1987)中找到。布局问题是众所周知的NP-难度（Sahni and Gonzales,1976），可以在许多经典的理论研究中发现。然而，只有少数工业布局案例在文献中被解决。应用遗传算法，希克斯（2006）提出了一个遗传算法，用于如何在一个制造单元中最小化物质运动并将其应用到资本主义工业生产的实际问题中，Lee 等人（2005）提出了一种解决多楼层设施的布局问题，包括墙壁和通道的内部结构的遗传算法。马丁（2004）提出了一个与时尚产业有关的研究课题。名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 17

4、页 -2 大量的研究已对 FLP进行论述；大部分是基于二次分配问题（QAP）。存在其他类型，诸如混合整数规划（Montreuil and Laforge，1990；montreuilet 等人，1993；Meller，1999）和图论模型（Caccetta and Kusumah,2001）。很多解 决 布 局问 题 的 方 法 是 基 于元 启发 式算 法，如遗 传 算 法（TAM，1992；Tavakkoli-Monghaddain and Shayan，1998；Lee 等人,2005），禁忌搜索（Chiang and Chiang,1998），模拟退火（Baykasog lu 等人,2

5、001;Chwif 等人 1998;Mir and Imaam,2001）和蚁群算法（Solimanpur 等人,2004;Sol-imanpur等人2005）。其他方法结合了遗传算法与模拟退火算法（Balakrishnan 等人,2003），由 Armour 等人开发工艺（1964）。为了确保得到到一个最小计算时间的全局最优解，metaheu-ristics通常包括像这样的2-opt（Lin，1965）局部搜索方法。另一种方法被称为引导本地搜索（GLS）（Voudouris,1997）选取一个本地搜索和许可前逃离局部极小值，从而保证全局收敛性。GLS系统已成功应用于旅行商问题（TSP）（Vo

6、udouris,1999）和 QAP 问题（米尔斯等，2003）。蚁群优化（ACO）是一种广泛用于解决二次分配问题的方法。首次应用是由Mani-ezzo 等人提出的（1994）。从那以后，许多应用程序问题和二次差异问题在解决方案生成、局部搜索方法和信息素更新时被提出。斯图和多里戈（1999）重申了蚁群算法求解QAP问题的方法，在执行过程中，蚁群算法是求解QAP 问题的一个很好的方法。Stutzle and Hoos（2000）研究提出的最大-最小蚁群系统算法（MMAS），只允许最佳解决方案添加Pheromo信息素，跟踪更新过程中的一条。这个绑定被用于跟踪水平，以避免过早地搜索收敛。Gambar

7、della 等人（1997）提出了一种混合蚁群算法求解QAP has-qap。它们的方法的独创性在于信息素的追踪是不用于构建解决方案，而是在本地搜索中不断修改和完善。它们提出的大多数算法对于小实例都是有效的。然而，随着问题规模的增大（即资源），它们的表现越来越差。solimanpur等人（2004）提出了一个蚁群优化算法，用于解决单元间布局问题，如QAP。它们提出了一种基于每个任务的部分贡献度计算的下限用于maniezzo（1999）的技术。由于问题的复杂性，它被限制在 30个部门内。在一个之前的研究中，antabu（泰尔比先前的研究，et al.，2001）利用蚁群算法和禁忌搜索程序，已将其

8、成功地应用于QAP 为大实例的情况（即 256 资源）。名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 17 页 -3 本文提出了一种为一个QAP方法求解一个设施规划布局问题建模。它是基于一个 GLS程序，摆脱局部极小蚁群优化方法。该方法首先被应用到一个特定的工业问题中，然后，在数量很少的情况，以及从公共库QAPLIB实例的性能下（Burkard 等人，1991），我们的测试结果与Solimanpur（2004），Gambardella（1997）和泰尔比等人（2001）相比，基本一致。本文的其余四个部分是：第二部分描述的设施布局问题和工业实例建模，如QAP。第三部分提出了蚂蚁算

9、法，和引导本地搜索程序求解QAP 等问题。第四、五部分展示建模和结果对工业问题和评估了用于一些QAPLIB实例中所提出的方法的性能。最后，第五部分得出结论。2.问题描述和制定2.1 描述这个问题来自于一个由平行铁路建立的建筑物组成的火车维修设施。每辆车基本上跨越了两个建筑物，X1和 X2专业绘画和拆卸分别如图1 所示。车辆首先在外轨被处理，其次移至内轨上，然后在结束它们的路线之前，沿着一个给定的序列移至两个建筑之间。为了解决这个问题，每一个轨道被分解成区域，称为车辆的位置，在那里进行维修任务。出口入口消毒通风专门技术收集锅炉制造修理配件重新组装电力测试刹车测试喷丸马具绘画重组的窗口绘制重量拆开

10、名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 17 页 -4 图 1 车辆路径在火车维护设施被处理的车辆分批到达，并根据其序列在不同的建筑物中行驶。它们被处理的车辆分批到达，并根据其序列在不同的建筑物中行驶。它们可以乘跨波特在一个固定的轨迹进行横向移动。一个在轨道交通允许平行的轨道运动。一些任务需要很长时间，它可以在很长的时间里占据一些位置。这些任务代表瓶颈车间。在目前车间，由于缺乏定位，经常为了让其他汽车访问全文，一些车辆必须搬出去。目前车间的布局已被证明非常制约生产线规划布局。问题是要在一个建筑中找到一个资源的布局，以便优化它们之间的生产流。图 2 建筑布局说明：1.建筑面

11、积4.循环通道2.汽车位置5.横线的运输机3.不能通过的位置6.在轨道上运输换句话说，该问题也就是在一所房子里找到一个新的资源配置，如（图2）为了优化或（最小化）所有资源之间的生产流程或设备（设施）。我们认为在将 N 种资源分配到一个建筑物的N 个站点或其上的位置上中。给定一个距离矩阵 D，其中的每个元素wD,k表示位置 K和 W 之间的距离为 k，w=1，2，.，N，一个流矩阵，其中每个元素的连接，表示一个资源i 和 j 之间的流动成本，i、j 取值为 1，2，.，N。流量成本取决于一个给定的时间范围内的资源的数量之间的行程。因为程序限制，所以考虑的问题矩阵的流量是不对称的。名师资料总结-精

12、品资料欢迎下载-名师精心整理-第 4 页，共 17 页 -5 而距离矩阵是对称的。计算距离与最小车辆数将在一栋建筑来做个交换。图3 为例，03,2）（D，13,1）（D（通过交叉位置2）和26,2）（D（通过交叉位置 1 和 5）。2.2 二次分配问题（QAP）QAP 历来用于一些假设的FLP模型。在我们的工业问题中，车辆位置的尺寸确定之间的位置和距离计算wD,k预定义的数字值。因此，它是可能将我们的问题限定为一个 QAP问题。图 3 建筑内部的距离计算的一个例子QAP首次由 koopmans和贝克曼（1957）提出，它是一个通过分配一组设备到一套位置上，以减少与此相关的成本的问题，该问题不仅

13、与距离和位置有关，也和流动有关。ijf 表示设施i和j之间的流wd,k，瓦特位置之间的距离k和 w。一个变量）（jP,i被定义为：其他情况，置如果该设备被分配到位，01j)P(i,大多数情况下，设备1i 签署地点1j 和设施2i 指定位置2j 相关的成本被认为是流动的21,fii和距离21jjD。因此，解可以写成如下形式：最小数),(),(2211i12122121jipjipdfZijji iiis.t.jijipijipj1),(,1),(,将问题建模后，我们采用基于蚁群优化的方法来解决它。1 5 2 6 3 7 4 8 名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 17

14、页 -6 3.蚁群优化算法和局部搜索算法在第一章中，我们首先提出了蚁群优化算法和一般算法。然后，我们详细描述了蚁群算法的元素适应的布局问题。我们结合蚁群算法并将其用于一个引导本地搜索中。这一方法的定义和应用程序的二次分配问题在第3.2 节有提及。完整的算法ACO_GLS 在第 3.3 节。3.1 蚁群优化蚁群算法的原理（Corne 等人，1999；Dorigo 等人，2000）是基于蚂蚁寻找食物的方式。每只蚂蚁在确定自己的路线之前都需要考虑（概率选择）所有其他的蚂蚁群体成员的信息素的踪迹，它的过程中，信息素的踪迹是一个跟踪每一只蚂蚁留下的气味的方式。这种信息素随着测试时间而蒸发，因此选择为每个

15、蚂蚁的概率随时间的变化。在许多蚂蚁的路径中，对食品的路径将人物化的痕迹，因此所有的蚂蚁信息素高的将遵循相同的路径。这种集体行为，基于共享内部记忆的所有蚂蚁殖民地之间可以适应用于下列最优化问题的解决：真正的蚂蚁搜索空间成为空间的组合问题的解决方案。源食物量成为相应的求解目标函数的评价。信息素路径成为一种自适应共享存储器。蚁群优化（ACO）的问题，因此可以被编码为寻找图中的最短路径。一个蚁群算法的第一个应用程序是旅行商问题。在一般情况下，蚁群算法适用于人工蚂蚁的概念，它可以表示为以下几个步骤：第 1 步：参数初始化。第 2 步：解决方案的构建。第 3 步：本地搜索算法。第 4 步：信息素更新规则。

16、第 5 步：返回到第 2 步，直到得到一个满意的给定的停止准则。适用于布局的蚁群算法问题是由以下要素组成：1.结构化解决方案，2.启发式信息，名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 17 页 -7 3.信息素更新，4.选择概率，5.本地搜索，6.多样化。3.1.1 解决方案的构建在该算法中，它被假定每个蚂蚁最初分配一个任务，i 到位置 j 上，记为（i，j）,然后将另一个任务分配到另一个位置k 上,如此继续，直到获得一个完整的解决方案。一个禁忌列表代表蚂蚁已经分配的一系列任务，也就是列表对（i,j）。这个列表确保所有的任务都被分配到给定的地点。任务的分配标准要考虑到分配的

17、概率与一个给定的位置，并取决于两个条件，一个与每只蚂蚁的可见度有关，另一个则与整个蚁群所存放的信息素的数量有关。3.1.2 启发式信息蚂蚁并不是完全盲目行动，它们会计算出一个给定的任务分配给某个地点的成本。这个成本考虑到流动和距离矩阵。启发式信息，也叫可见度，是一个函数的分配成本。在文献中使用的几个公式，并且每一个仅适用于一个给定的问题。关于二次分配、任务的分配取决于分配的任务。将成本与分配),(li的关系定义如下：11)()()(),(isissirslisrdfdfliC（1）其中r表示资源的下一个排列施工。其可视性表示移动的可取性，被定义为11)()()(11isissirslisrad

18、fdfn（2）在（2）中加入 1分子的的原因是为了避免被0整除。这个公式表明任务对目标函数的贡献较小将更有可能被选中。3.1.3 信息素更新信息素的更新机制可以用下面的公式表示：kkiltt)1()(ilil（3）其中）（tSIT是信息素的分配的任务，它为每只蚂蚁分配的任务i 及其地点 l的迭代相联系。当一只蚂蚁选择了该任务，数量）（til随之增加。快速收敛到局名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 17 页 -8 部最优解为大的收敛结果。最终，kkilkfitbestfit（4）表示通过蚂蚁分配的任务的跟踪级别的变化的大小。正如所见，越小的是更适合的解决方案，通过蚂蚁k

19、获得适合度 k，而越大将会使蚂蚁 k选择的路径水平越高。3.1.4 选择概率蚂蚁选择任务 i 分配到 1的位置，通过以下概率：Tabukiililililkilp)1()1(（5）其中一个有助于使整个蚂蚁（近1）和每只蚂蚁根据自己的能见度选择（近0）之间的平衡。我们注意到如果相关的信息素的数量是有意义的或假设与此相关的成本很低，那么，一个任务会被分配到一个位置。最终，具有最大概率的任务被分配到位置 l 上。3.1.5 本地搜索我们选择本地搜索的方法 2-opt 是简单的，并很好地应用于 QAP 算法中（soli-manpur等人，2004）。该方法适用于一个给定的解决方案的所有可能的排列的任务

20、。每个突变以最小的成本为出发点，选择一个局部极小值。这个过程是重复的，直到不再注意到改进为止。为了在交换过程中限制计算时间，我们做了如下简化；如果交换了置换元素i和j之间的位置，那么客观的差函数值则将是：)()()()(),(,kikjikjkjiijjjiiffddffddffddffddjijkikjikkjkijiijjjii（6）这个代数式是由 Gambard Ella 等人在 1997年提出的，他们提出了一个混合蚁群算法应用到二次分配中的问题叫做一个HAS-QAP 算法时简化的来的。本地搜索不一定导致全局最小。在大多数情况下，它收敛到局部极小。为此，引导本地搜索法（GLS）被用作“p

21、enalize”，当局部最小值发现为了收敛到全局最小。GLS 将在后面进行详细说明。名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 17 页 -9 3.1.6 多样化通过Gambardella等人（1997）使用。多元化机制被激活，如果迭代次数max_iter 期间，没有改善，最好的解决方案是检测产生。多元化经营-清除所有信息包含的信息素的信息素矩阵重新初始化和随机产生新的当前解所有的蚂蚁却一分帽子收到最好的解决方案，由搜索到目前为止。另一种可能性是删除所有信息素的路径，除了最佳的解决方案。蚁群算法我们提出了以下的一般和 2-opt 蚁群优化算法。步骤1：为所有任务和位置初始化参

22、数，步骤2：为每只蚂蚁分配任务的位置与概率P，更新信息素，如果最好的解决方案是没有改善的 max_iter 迭代，0il，但最好的解决方案，步骤3：回到步骤 2直到满足停止准则。3.2 引导本地搜索（GLS）引导本地搜索（GLS）（Mills 等人，2003）是一种元启发式算法在局部搜索算法的顶部。当给定的局部搜索算法解决局部最优，GLS 的变化目标函数，以增广目标函数增加处罚，相关的功能包含在局部最优。本地搜索，然后继续搜索使用增强目标函数。解决方案功能的选择取决于问题类型，每个特征定义必须有以下组件：1.指示功能）（siI的指示功能特点是目前在当前的解决方案或不。如果特征 FI在溶液 S和

23、0否则现在它等于 1。2.一个成本函数）（sic对美国有网络连接的成本3.一个点球ip 最初设置为 0，用来惩罚网络局部极小的发生。当本地搜索返回一个局部最小，GLS 增加功能的刑罚具有效用最大化的利用),(ifs定义如下：iiiipssIfsutil1)(c)(),(（7）这个想法的特点是为了惩罚，第一具有高成本的。GLS 采用一种增强成本函数，以引导本地搜索出本地最佳。的想法是，使当地的最昂贵的解决方案，在周名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 17 页 -10 围的搜索空间，在相同的功能是不预先发送。niiipsIsgsH1)()()(（8）其中）（sG是成本函数

24、和0K 用来改变寻找解决方案的多样化的参数。0K 较高的值会导致更多的多样化的搜索。地理中的应用他QAP 问题与以下类：即实现特征网络；iP 溶液的对应任务的分配我的位置iP。功能网络连接的成本取决于我对解决美国所有其他任务的任务相互作用。这个成本是由njijijiDfic1),(（9）的值很好的适应了 QAP 问题：41111nninjijninjijDf（10）GLS 技术在该 QAP 问题中的应用可以归纳为以下：从当前的解决方案，一个本地搜索的方法（例如使用2-opt）找到一个局部最小值，以增强成本函数。如果这个最小的成本（不增加）比发现的最低成本，它被保存为最好的解决方案。最后，具有最

25、大效用的分配将有相应的惩罚增加。所述GLSQAP算法可以被概括为如下：步骤1：计算。步骤2：最优解 =初始解 s。步骤3：相对于增强成本函数执行本地搜索2-opt，*是目前发现的解决方案具有低成本扩张。如果成本（*）成本（0S），由*代替0S。找到任务（功能）的具有最大的效用，让它成为iF；iP 为例。增加相应的处罚：步骤4：回到步骤 3，直到满足给定的停止准则。步骤5：S0找到原问题的最佳解决方案。3.3 完整的算法最后，与 GLS 的蚁群优化算法的程序如下：步骤1：初始化参数。名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 17 页 -11 步骤2：为所有蚂蚁。（a）分配任

26、务的位置与给定的分配概率，（b）执行本地搜索 GLSQAP，（c）更新信息素，（d）如果最好的办法是不到 max_iter 迭代改进，0il，但最好的解决方案。步骤3：回到步骤 2,直到满足停止准则。4.工业案例应用我们认为在建筑物的位置或汽车地点分配的资源。给定一个距离矩阵D，其中每个元素的 DK，W 表示位置 K和W 之间的距离为 k，w=1,2，,，N和一个流矩阵，其中每个元素的网络连接，表示一个资源i 和j 之间的流动成本，为ji,=1，2，,，N。我们的问题建模为一个 QAP。流量成本取决于一个给定的时间范围内的资源的数量之间的行程。在所考虑的问题，矩阵是非对称的，在流证据的限制。距

27、离矩阵是对称的。的距离计算是相关的最小数量的车辆移动的建筑物内，以使交换。模型参数：N 变量总数ijr资源j 分配到的任务 i wkD,位置W 之间的距离 k和瓦特本距离被定义为可使用的数这两个资源之间的位置,jiijrrf资源RIJ之间生产流程和。此流被评价为数字汽车两种资源之间传递的否则表示分配给位置，如果,0k1,ijkrrpij（11）否则，如果位置是,0stand1dedizeTEk（12）否则，如果是专门的位置,01kTES（13）名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 17 页 -12 为了优化生产流程，我们定义二次函数的最小化：wrkrjijkwwkrr

28、ijijjiijfpDfZ,i,（14）如果不可用的位置被排除，应添加下面约束：1:,ijkrijpk（15）kkrijpji1:,，（16）1kkTESTE（17）约束（15）和（16）是定期分配问题的标准约束。约束（17）意味着，占据了所有的位置都是专业的或标准的。5.实验结果5.1 参数该算法利用 Visual C+6实现。在奔腾 3与1.8 兆赫的处理器速度。在该算法中的四个参数：蚂蚁数量，iter_max和影响该性能的算法等。试运行我们的问题，每形成要找到合适的参数。蚂蚁数量的测试5和60之间，和的结果与常规的质量之间的折衷一致收敛时间被发现表1列出了适当的值。很好的适应与 GLS

29、程序。个体蚂蚁调查。这个值被发现支持更多的支持信息素的路径比值0.6 表明该溶液的建设通常，是接近 0.5。在我们的情况下而被发现的iter_max=10 和=0.6。对于 AN=20。当一个是固定的，这个值被发现到很好地适应与GLS 过程。表1 参数值参数值 AN 20 Alpha 0.6 iter_max 10 005.2 工业应用工业问题包括 72个地点 27不能使用，39个专业和 6个标准化位置。实际资源名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 17 页 -13 分配作为算法的初始条件。所有计算是根据一年的数据计划。车间的实际布局产生然而，425的成本，我们的算法

30、 ACO_GLS提出了一种解决方案,与改进 19.6%尊重实际布局。这意味着它收敛与一个更好的解决方案，这证明了它有能力解决工业布局问题。我们也找到了问题的精确解通过使用枚举方法，因为只有六个任务需要分配。该溶液是相同的被发现的算法。这意味着该算法收敛到最佳的解决方案这个产业问题。建议的应用程序可能是有用的未来产业案例。事实上，如上所述在问题描述中，行业正在尝试提高其性能，这意味着解决其他设施问题。此外，实例进行了测试和结果进行了比较其他车辆与其他研究。5.3 概括该算法的性能进行了测试，从库QAPLIB 实例（Burkard 等人，1991）。我们首先比较我们的算法与 HAS-QAP（Gam

31、bardella等人，1997）的方法关于蚂蚁殖民地。我们将它与 ANTabu 比较（Talbi 等人，2001），与其他基于遗传算法的方法，仿真退火，禁忌搜索或蚁群，并通过solimanpur 等人（2004）与最近提出的蚁群优化算法。该小数量的问题。表3比较的结果，所有的引用算法对于小实例的位置下降在 30和19之间。我们选择的实例包括规则和QAPLIB 不规则问题。这种差异关系有利于 QAPLIB最知名的解决方案一个百分比差距。这几乎是不可能的，相同的实验设置为以前的研究，但是，为了给计算的想法时间，平均执行时间超过 10个运行显示在表 2。表2证明了对于实例 30个任务，ACO_GLS

32、性能优于所有其他比较算法。为了推广我们的算法中的应用方法，从大量 QAPLIB 实例研究不同种类的问题。结果是表3中我们比较这些算法对一组12的实例研究，范围从 35到128个位置。大实例。曾经，我们仍能获得满意的解决方法ACO_GLS性能比 HAS-QAP 更好。如何实例。它表示（表3），我们的算法大的问题，逃离局部极小执行更复杂的本地搜索 ntabu是更好一点，所以我们可能要对于较大的实例，给出的结果所提出的 ACO_GLS算法被证明融合完美的情况下，最多40个地点作为示于表 2和3这种性能是中规中矩的工业问题，因为现实生活中的问题，通常不超过 30?40的位置。因此，这种算法将是一个非常

33、有用的工具，布局优化，在现实生活中的产业名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页，共 17 页 -14 本文案例中说明。表2 比较从 QAPLIB 选择二次分配情况的结果（最好的结果是黑体字）最优解HAS_QAP ANTabu ACO Solimanpur ACO_GLS 时间（秒）Els 19 17212548 0.923 000 4 Tai 20b 122455319 0.243 000 5 Chr 25a 3796 3.0822 0.8957 0 03 Bur 26a 5426670 000 035 Bur 26b 3817852 00.0169 0 034 Bur 2

34、6c 5426795 000034 Bur 26d 3821225 000035 Bur 26e 5386859 000034 Bur 26f 3782044 000034 Bur 26g 10117172 0000 33 Kra30a 88900 0.6299 0.2677 0035 Kra 30b 91420 0.0711 00.0153 019 Nug30 6124 0.098 0 0.013 0 3 数值表示解决方案的价值和百分比最著名值之间的平均差距。表3 比较从 QAPLIB 选择二次分配情况的结果（最好的结果是黑体字）最优解HAS_QAP ANTabu ACO_GLS 时间（秒）

35、Tai 35a 2422002 1.762 0.215 0109 Tai 35b 283315445 0.343 0.0408 0112 Tai 40a 3139370 1.989 0.442 0204 Tai 50a 4941410 2.800 0.781 1.28 228 Tai 60a 7208572 3.070 0.919 1.25 342 Tai 80a 13557864 0.663 0.663 1.53 1524 Wil 50 48816 0.061 0.008 0.01 1197 Sko42 15812 0.076 0082 名师资料总结-精品资料欢迎下载-名师精心整理-第 14

36、 页，共 17 页 -15 Sko49 23410 0.141 0.038 0.10 105 Sko56 34524 0.101 0.002 0.19 294 Sko64 48498 0.129 0.001 0.008 522 Esc 128 64-001292 六、总结在本文中，我们提出了一个强大的元启发式算法的布局问题建模为一个QAP。该算法是基于蚁群优化和引导本地搜索。GLS 利用资源的成本函数为引导本地搜索出一个局部最优解，该算法的发展是出于一个产业的案例在列车维修设施。我们把它应用到一个工业案例有六个位置，并找到最佳的解决方案。由于位置的数量在未来会增加，我们提出的蚁群算法的性能进行

37、了测试，一些测试选自文献相比，许多现有的算法问题。结果表明，性能相比，HAS-QAP，ANTabu 和Solimanpur等。蚁群算法随着位置的人数高达40的问题都可以得到我们的算法ACO_GLS。因此，ACO_GLS是最适应的算法对该工业的情况和其他适应数小于40的位置布局问题；然而，结果仍然是令人满意的，具有较大实例布局问题的。未来的工作包括对于大型实例,寻找更复杂的本地搜索，找到一个更好的结果，可以处理更复杂的约束问题的方法。参考文献Armour,G.C.,Buffa,E.S.,Vollmann，T.E.,1964.Allocating facilities with CRAFT.Har

38、vard Business Review 42,136 158.Balakrishnan,J.,Cheng,C-H.,Wong,K-F.,2003.FACOPT:a user friendly FACility layout OPTimization system.Comput Operat Res 30,16251641.Baykasouglu,Gindy,N.N.Z.,2001.A simulated anealing algo-rithm for dynamic layout problem.Computers&Operations Research 28,14031426.Burkar

39、d,R.E.,Karisch,S.,Rendel,F.,1991.QAPLIB A Quadratic Assignment Problem Library.European Journal of Operational Research 55,115-119,electronic update:http/fmtbhpl.tu-graz.ac.at/karisch/qaplib.Caccetta,L.,Kusumah,Y.S.,2001.Computational aspects of the facility layout design problem.Non-Linear Analysis

40、 7,5599 5610.Chiang,W.C.,Chiang,C.,1998.Intelligent local search strategies for solving facility layout problems with the quadratic assignment problem formulation.European Journal of Oper-ational Research 106,名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页，共 17 页 -16 457488.Chwif,L.,Barretto,M.R.P.,Moscato,L.A.,1998.

41、A solution to the facility layout problem using simulated anealing.Com-puters in industry 36,125132.Corne,D.,Dorigo,M.,Glover,F.,1999.New Ideas in Optimization.Mac Graw Hill.Dorigo,M.,Bonabeau,E.,Theraulaz,G.,2000.Ant algorithms and stimergy.Future Generation Computer Systems 16,851 871.Gambardella,

42、L.M.,Taillard,E.D.,Dorigo,M.Ant colonies for the QAP,Technical report IDISIA,1997,pp.497.Hicks,2006.A genetic algorithm tool designing manufacturing facilities in the capital goods industry,International Journal of Production Economics.Koopmans,T.C.,Beckman,M.,1957.Assignment problems and the locati

43、on of economic activities.Econometrica 25,5376.Kusiak,Heragu,S.S.,1987.The facility layout problem.Euro-pean Journal of Operational research 29,229251.Lee,K.Y.,Roh,M.I.,Jeong,H.S.,2005.An improved genetic algorithm for multi-floor facility layout problems having inner structure walls and passages.Co

44、mputers&Operations Research 32(4),879899.Lin,S.,1965.Computer solutions for the traveling selsman problem.Bell System Technology Journal 44,22452269.Maniezzo,V.,Colorni,A.,Dorigo,M.The ant system applied to the quadratic assignment problem.Technical report IRIDIA/,Universite Libre de Bruxelles,1994,

45、pp.94128.Maniezzo,V.,1999.Exact and approximate nondeterministic tree-search procedures for the quadratic assignment problem.INFORMS Journal on Computing 11,358 369.Martens,J.,2004.Two genetic algorithms to solve a layout problem in fashion industry.European Journal of Opera-tional Research 54(1),30

46、4322.Meller，R.D.,Narayanan,V.,Vance,P.H.,1999.Optimal facility layout design.Operations Research Letters 23,117127.Mills,P.,Tsang,E.,Ford,J.,2003.Applying an extended Guided Local Search to the Quadratic Assignment Problem,Annals of OR 118,121135.Mir,M.,Imaam,M.H.,2001.A hybrid optimization approach

47、 for layout design of unequal-area facilities.Computers&Industrial Engineering 39,49 63.Montreuil，Laforge，A.,1990.A modeling farmwork for integrating layout design and flow network design.Proceeding of Material Handling Research Colloquium,4358.Montreuil,B.，Venkatadri,U.,Ratliff,H.D.,1993.Generating

48、 a layout 名师资料总结-精品资料欢迎下载-名师精心整理-第 16 页，共 17 页 -17 from a design skeleton.IIE Trans 25,315.Sahni,S.,Gonzales,T.,1976.P-complete approximation problems.Journal of Associated Computer Machinery 23(5),555 565.Solimanpur,M.,Vrat,M.,Shankar,R.,2004.Ant Colony optimization algorithm to the inter-cell layo

49、ut problem in cellular manufacturing.European Journal of Operational Research 157,592606.Solimanpur,M.,Vrat,Prem,Shankar,Ravi,2005.Ant algorithm for the single row layout problem in flexible manufacturing systems.Computers&Operations Research 32(3),583598.Stutzle,T.,Dorigo,M.Aco algorithm for the qu

50、adratic assignment problem.Technical report IRIDIA/,Universite Libre de Bruxelles,1999,pp.99102.Stutzle,T.,Hoos,H.,2000.MAX-MIN ant system.Future Generation Computer Systems 16,889 914.Talbi,E.G.,Roux,O.,Fonlupt,C.,Robillard,D.,2001.Parallel ant colonies for the quadratic assignment problem.Future G