资源描述：
《群蚁算法翻译》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、离散优化求解工业布局问题的蚁群算法Y.Hani*,L.Amodeo,F.Yalaoui,H.ChenISTIT-OSI,(CNRS2732)Universite´deTechnologiedeTroyes,12rueMarieCurieBP2060,10010Troyescedex,FranceReceived26August2005;accepted6October2006Availableonline12January2007摘要本文提出了一个与局部搜索相结合的被用于布局问题中的混合蚁群优化算法--ACO_GLS。
2、ACO_GLS被适用于工业中的情况，其被法国的铁路系统设施（SNCF）用在列车的维修中。结果表明，与实际布局相比，这种实现有近20%的改善。由于问题建模为一个二次分配问题LEM（QAP），我们将我们的方法与一些可以解决此问题的最佳启发式方法做了比较。实验结果表明，在小型实例中，ACO_GLS算法表现更好，而对于大型实例，其计算结果依旧令人满意。关键词：布局问题；二次分配问题；蚁群优化；局部搜索1.介绍设施布局问题（FLP）是一个发现机器的很好的配置，在一个给定的设备以优化生产流程的同时最小化总成本的设备或其他资源。它对
3、一个制造系统的性能具有重要意义。设施布局问题在很多方面都有应用，如厂房组织的应用，新的生产建设单位，或设备分配。一个完整的布局描述的问题可以从（Kusiak和Heragu，1987)中找到。布局问题是众所周知的NP-难度（SahniandGonzales,1976），可以在许多经典的理论研究中发现。然而，只有少数工业布局案例在文献中被解决。应用遗传算法，希克斯（2006）提出了一个遗传算法，用于如何在一个制造单元中最小化物质运动并将其应用到资本主义工业生产的实际问题中，Lee等人（2005）提出了一种解决多楼层设施的布
4、局问题，包括墙壁和通道的内部结构的遗传算法。马丁（2004）提出了一个与时尚产业有关的研究课题。页脚大量的研究已对FLP进行论述；大部分是基于二次分配问题（QAP）。存在其他类型，诸如混合整数规划（MontreuilandLaforge，1990；montreuilet等人，1993；Meller，1999）和图论模型（CaccettaandKusumah,2001）。很多解决布局问题的方法是基于元启发式算法，如遗传算法（TAM，1992；Tavakkoli-MonghaddainandShayan，1998；Lee等
5、人,2005），禁忌搜索（ChiangandChiang,1998），模拟退火（Baykasoglu等人,2001;Chwif等人1998;MirandImaam,2001）和蚁群算法（Solimanpur等人,2004;Sol-imanpur等人2005）。其他方法结合了遗传算法与模拟退火算法（Balakrishnan等人,2003），由Armour等人开发工艺（1964）。为了确保得到到一个最小计算时间的全局最优解，metaheu-ristics通常包括像这样的2-opt（Lin，1965）局部搜索方法。另一种方法
6、被称为引导本地搜索（GLS）（Voudouris,1997）选取一个本地搜索和许可前逃离局部极小值，从而保证全局收敛性。GLS系统已成功应用于旅行商问题（TSP）（Voudouris,1999）和QAP问题（米尔斯等，2003）。蚁群优化（ACO）是一种广泛用于解决二次分配问题的方法。首次应用是由Mani-ezzo等人提出的（1994）。从那以后，许多应用程序问题和二次差异问题在解决方案生成、局部搜索方法和信息素更新时被提出。斯图和多里戈（1999）重申了蚁群算法求解QAP问题的方法，在执行过程中，蚁群算法是求解QAP
7、问题的一个很好的方法。StutzleandHoos（2000）研究提出的最大-最小蚁群系统算法（MMAS），只允许最佳解决方案添加Pheromo信息素，跟踪更新过程中的一条。这个绑定被用于跟踪水平，以避免过早地搜索收敛。Gambardella等人（1997）提出了一种混合蚁群算法求解QAPhas-qap。它们的方法的独创性在于信息素的追踪是不用于构建解决方案，而是在本地搜索中不断修改和完善。它们提出的大多数算法对于小实例都是有效的。然而，随着问题规模的增大（即资源），它们的表现越来越差。solimanpur等人（200
8、4）提出了一个蚁群优化算法，用于解决单元间布局问题，如QAP。它们提出了一种基于每个任务的部分贡献度计算的下限用于maniezzo（1999）的技术。由于问题的复杂性，它被限制在30个部门内。在一个之前的研究中，antabu（泰尔比先前的研究，etal.，2001）利用蚁群算法和禁忌搜索程序，已将其成功地应用于QAP为大实例的情况
