群蚁算法翻译

1离散优化求解工业布局问题的蚁群算法Y.Hani*,L.Amodeo,F.Yalaoui,H.ChenISTIT-OSI,(CNRS2732)Universite´deTechnologiedeTroyes,12rueMarieCurieBP2060,10010Troyescedex,FranceReceived26August2005;accepted6October2006Availableonline12January2007摘要本文提出了一个与局部搜索相结合的被用于布局问题中的混合蚁群优化算法--ACO_GLS。ACO_GLS被适用于工业中的情况，其被法国的铁路系统设施（SNCF）用在列车的维修中。结果表明，与实际布局相比，这种实现有近20%的改善。由于问题建模为一个二次分配问题LEM（QAP），我们将我们的方法与一些可以解决此问题的最佳启发式方法做了比较。实验结果表明，在小型实例中，ACO_GLS算法表现更好，而对于大型实例，其计算结果依旧令人满意。关键词：布局问题；二次分配问题；蚁群优化；局部搜索1.介绍设施布局问题（FLP）是一个发现机器的很好的配置，在一个给定的设备以优化生产流程的同时最小化总成本的设备或其他资源。它对一个制造系统的性能具有重要意义。设施布局问题在很多方面都有应用，如厂房组织的应用，新的生产建设单位，或设备分配。一个完整的布局描述的问题可以从（Kusiak和Heragu，1987)中找到。布局问题是众所周知的NP-难度（SahniandGonzales,1976），可以在许多经典的理论研究中发现。然而，只有少数工业布局案例在文献中被解决。应用遗传算法，希克斯（2006）提出了一个遗传算法，用于如何在一个制造单元中最小化物质运动并将其应用到资本主义工业生产的实际问题中，Lee等人（2005）提出了一种解决多楼层设施的布局问题，包括墙壁和通道的内部结构的遗传算法。马丁（2004）提出了一个与时尚产业有关的研究课题。2大量的研究已对FLP进行论述；大部分是基于二次分配问题（QAP）。存在其他类型，诸如混合整数规划（MontreuilandLaforge，1990；montreuilet等人，1993；Meller，1999）和图论模型（CaccettaandKusumah,2001）。很多解决布局问题的方法是基于元启发式算法，如遗传算法（TAM，1992；Tavakkoli-MonghaddainandShayan，1998；Lee等人,2005），禁忌搜索（ChiangandChiang,1998），模拟退火（Baykasoglu等人,2001;Chwif等人1998;MirandImaam,2001）和蚁群算法（Solimanpur等人,2004;Sol-imanpur等人2005）。其他方法结合了遗传算法与模拟退火算法（Balakrishnan等人,2003），由Armour等人开发工艺（1964）。为了确保得到到一个最小计算时间的全局最优解，metaheu-ristics通常包括像这样的2-opt（Lin，1965）局部搜索方法。另一种方法被称为引导本地搜索（GLS）（Voudouris,1997）选取一个本地搜索和许可前逃离局部极小值，从而保证全局收敛性。GLS系统已成功应用于旅行商问题（TSP）（Voudouris,1999）和QAP问题（米尔斯等，2003）。蚁群优化（ACO）是一种广泛用于解决二次分配问题的方法。首次应用是由Mani-ezzo等人提出的（1994）。从那以后，许多应用程序问题和二次差异问题在解决方案生成、局部搜索方法和信息素更新时被提出。斯图和多里戈（1999）重申了蚁群算法求解QAP问题的方法，在执行过程中，蚁群算法是求解QAP问题的一个很好的方法。StutzleandHoos（2000）研究提出的最大-最小蚁群系统算法（MMAS），只允许最佳解决方案添加Pheromo信息素，跟踪更新过程中的一条。这个绑定被用于跟踪水平，以避免过早地搜索收敛。Gambardella等人（1997）提出了一种混合蚁群算法求解QAPhas-qap。它们的方法的独创性在于信息素的追踪是不用于构建解决方案，而是在本地搜索中不断修改和完善。它们提出的大多数算法对于小实例都是有效的。然而，随着问题规模的增大（即资源），它们的表现越来越差。solimanpur等人（2004）提出了一个蚁群优化算法，用于解决单元间布局问题，如QAP。它们提出了一种基于每个任务的部分贡献度计算的下限用于maniezzo（1999）的技术。由于问题的复杂性，它被限制在30个部门内。在一个之前的研究中，antabu（泰尔比先前的研究，etal.，2001）利用蚁群算法和禁忌搜索程序，已将其成功地应用于QAP为大实例的情况（即256资源）。3本文提出了一种为一个QAP方法求解一个设施规划布局问题建模。它是基于一个GLS程序，摆脱局部极小蚁群优化方法。该方法首先被应用到一个特定的工业问题中，然后，在数量很少的情况，以及从公共库QAPLIB实例的性能下（Burkard等人，1991），我们的测试结果与Solimanpur（2004），Gambardella（1997）和泰尔比等人（2001）相比，基本一致。本文的其余四个部分是：第二部分描述的设施布局问题和工业实例建模，如QAP。第三部分提出了蚂蚁算法，和引导本地搜索程序求解QAP等问题。第四、五部分展示建模和结果对工业问题和评估了用于一些QAPLIB实例中所提出的方法的性能。最后，第五部分得出结论。2.问题描述和制定2.1描述这个问题来自于一个由平行铁路建立的建筑物组成的火车维修设施。每辆车基本上跨越了两个建筑物，X1和X2专业绘画和拆卸分别如图1所示。车辆首先在外轨被处理，其次移至内轨上，然后在结束它们的路线之前，沿着一个给定的序列移至两个建筑之间。为了解决这个问题，每一个轨道被分解成区域，称为车辆的位置，在那里进行维修任务。出口入口消毒通风专门技术收集锅炉制造修理配件重新组装电力测试刹车测试喷丸马具绘画重组的窗口绘制重量拆开4图1车辆路径在火车维护设施被处理的车辆分批到达，并根据其序列在不同的建筑物中行驶。它们被处理的车辆分批到达，并根据其序列在不同的建筑物中行驶。它们可以乘跨波特在一个固定的轨迹进行横向移动。一个在轨道交通允许平行的轨道运动。一些任务需要很长时间，它可以在很长的时间里占据一些位置。这些任务代表瓶颈车间。在目前车间，由于缺乏定位，经常为了让其他汽车访问全文，一些车辆必须搬出去。目前车间的布局已被证明非常制约生产线规划布局。问题是要在一个建筑中找到一个资源的布局，以便优化它们之间的生产流。图2建筑布局说明：1.建筑面积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。流量成本取决于一个给定的时间范围内的资源的数量之间的行程。因为程序限制，所以考虑的问题矩阵的流量是不对称的。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）提出，它是一个通过分配一组设备到一套位置上，以减少与此相关的成本的问题，该问题不仅与距离和位置有关，也和流动有关。ijf表示设施i和j之间的流wd,k，瓦特位置之间的距离k和w。一个变量）（jP,i被定义为：其他情况，置如果该设备被分配到位，01j)P(i,大多数情况下，设备1i签署地点1j和设施2i指定位置2j相关的成本被认为是流动的21,fii和距离21jjD。因此，解可以写成如下形式：最小数),(),,(2211i12122121jipjipdfZijjiiiis.t.jijipijipj1),(,,1),(,将问题建模后，我们采用基于蚁群优化的方法来解决它。1526374863.蚁群优化算法和局部搜索算法在第一章中，我们首先提出了蚁群优化算法和一般算法。然后，我们详细描述了蚁群算法的元素适应的布局问题。我们结合蚁群算法并将其用于一个引导本地搜索中。这一方法的定义和应用程序的二次分配问题在第3.2节有提及。完整的算法ACO_GLS在第3.3节。3.1蚁群优化蚁群算法的原理（Corne等人，1999；Dorigo等人，2000）是基于蚂蚁寻找食物的方式。每只蚂蚁在确定自己的路线之前都需要考虑（概率选择）所有其他的蚂蚁群体成员的信息素的踪迹，它的过程中，信息素的踪迹是一个跟踪每一只蚂蚁留下的气味的方式。这种信息素随着测试时间而蒸发，因此选择为每个蚂蚁的概率随时间的变化。在许多蚂蚁的路径中，对食品的路径将人物化的痕迹，因此所有的蚂蚁信息素高的将遵循相同的路径。这种集体行为，基于共享内部记忆的所有蚂蚁殖民地之间可以适应用于下列最优化问题的解决：真正的蚂蚁搜索空间成为空间的组合问题的解决方案。源食物量成为相应的求解目标函数的评价。信息素路径成为一种自适应共享存储器。蚁群优化（ACO）的问题，因此可以被编码为寻找图中的最短路径。一个蚁群算法的第一个应用程序是旅行商问题。在一般情况下，蚁群算法适用于人工蚂蚁的概念，它可以表示为以下几个步骤：第1步：参数初始化。第2步：解决方案的构建。第3步：本地搜索算法。第4步：信息素更新规则。第5步：返回到第2步，直到得到一个满意的给定的停止准则。适用于布局的蚁群算法问题是由以下要素组成：1.结构化解决方案，2.启发式信息，73.信息素更新，4.选择概率，5.本地搜索，6.多样化。3.1.1解决方案的构建在该算法中，它被假定每个蚂蚁最初分配一个任务，i到位置j上，记为（i，j）,然后将另一个任务分配到另一个位置k上,如此继续，直到获得一个完整的解决方案。一个禁忌列表代表蚂蚁已经分配的一系列任务，也就是列表对（i,j）。这个列表确保所有的任务都被分配到给定的地点。任务的分配标准要考虑到分配的概率与一个给定的位置，并取决于两个条件，一个与每只蚂蚁的可见度有关，另一个则与整个蚁群所存放的信息素的数量有关。3.1.2启发式信息蚂蚁并不是完全盲目行动，它们会计算出一个给定的任务分配给某个地点的成本。这个成本考虑到流动和距离矩阵。启发式信息，也叫可见度，是一个函数的分配成本。在文献中使用的几个公式，并且每一个仅适用于一个给定的问题。关于二次分配、任务的分配取决于分配的任务。将成本与分配),(li的关系定义如下：11)()()(),(isissirslisrdfdfliC（1）其中r表示资源的下一个排列施工。其可视性表示移动的可取性，被定义为11)()()(11isissirslisradfdfn（2）在（2）中加入1分子的的原因是为了避免被0整除。这个公式表明任务对目标函数的贡献较小将更有可能被选中。3.1.3信息素更新信息素的更新机制可以用下面的公式表示：kkiltt)1()(ilil（3）其中）（tSIT是信息素的分配的任务，它为每只蚂蚁分配的任务i及其地点l的迭代相联系。当一只蚂蚁选择了该任务，数量）（til随之增加。快速收敛到局8部最优解为大的收敛结果。最终，kkilkfitbestfit][（4）表示通过蚂蚁分配的任务的跟踪级