kl800.com省心范文网

群蚁算法翻译


离散优化 求解工业布局问题的蚁群算法
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 被适用于工业中的情况, 其被法国的铁路系统设施 (SNCF) 用在列车的维修中。结果表明,与实际布局相比,这种实现有近 20%的改善。由 于问题建模为一个二次分配问题 LEM(QAP) ,我们将我们的方法与一些可以解决 此问题的最佳启发式方法做了比较。实验结果表明,在小型实例中,ACO_GLS 算 法表现更好,而对于大型实例,其计算结果依旧令人满意。
关键词:布局问题;二次分配问题;蚁群优化;局部搜索

1.介绍
设施布局问题(FLP)是一个发现机器的很好的配置,在一个给定的设备以 优化生产流程的同时最小化总成本的设备或其他资源。 它对一个制造系统的性能 具有重要意义。设施布局问题在很多方面都有应用,如厂房组织的应用,新的生 产建设单位, 或设备分配。 一个完整的布局描述的问题可以从 (Kusiak 和 Heragu, 1987)中找到。布局问题是众所周知的 NP-难度(Sahni and Gonzales, 1976) , 可以在许多经典的理论研究中发现。然而,只有少数工业布局案例在文献中被解 决。应用遗传算法,希克斯(2006)提出了一个遗传算法,用于如何在一个制造 单元中最小化物质运动并将其应用到资本主义工业生产的实际问题中, Lee 等 人(2005)提出了一种解决多楼层设施的布局问题,包括墙壁和通道的内部结构 的遗传算法。马丁(2004)提出了一个与时尚产业有关的研究课题。
1

大量的研究已对 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 等人, 2001; 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) (Voudouris,1999)和 QAP 问题(米尔斯等,2003) 。 蚁群优化(ACO)是一种广泛用于解决二次分配问题的方法。首次应用是由 Mani-ezzo 等人提出的(1994) 。从那以后,许多应用程序问题和二次差异问题 在解决方案生成、局部搜索方法和信息素更新时被提出。斯图和多里戈(1999) 重申了蚁群算法求解 QAP 问题的方法,在执行过程中,蚁群算法是求解 QAP 问题 的一个很好的方法。Stutzle and Hoos(2000)研究提出的最大-最小蚁群系统 算法(MMAS) ,只允许最佳解决方案添加 Pheromo 信息素,跟踪更新过程中的一 条。 这个绑定被用于跟踪水平, 以避免过早地搜索收敛。 Gambardella 等人 (1997) 提出了一种混合蚁群算法求解 QAP has-qap。它们的方法的独创性在于信息素的 追踪是不用于构建解决方案,而是在本地搜索中不断修改和完善。 它们提出的大多数算法对于小实例都是有效的。然而, 随着问题规模的增大 (即资源),它们的表现越来越差。solimanpur 等人(2004)提出了一个蚁群 优化算法,用于解决单元间布局问题,如 QAP。它们提出了一种基于每个任务的 部分贡献度计算的下限用于 maniezzo(1999)的技术。由于问题的复杂性,它 被限制在 30 个部门内。 在一个之前的研究中, antabu (泰尔比先前的研究, et al., 2001) 利用蚁群算法和禁忌搜索程序,已将其成功地应用于 QAP 为大实例的情况 (即 256 资源)。

2

本文提出了一种为一个 QAP 方法求解一个设施规划布局问题建模。 它是基于 一个 GLS 程序, 摆脱局部极小蚁群优化方法。该方法首先被应用到一个特定的工 业问题中,然后,在数量很少的情况,以及从公共库 QAPLIB 实例的性能下 (Burkard 等人,1991),我们的测试结果与 Solimanpur(2004),Gambardella (1997)和泰尔比等人(2001)相比,基本一致。 本文的其余四个部分是:第二部分描述的设施布局问题和工业实例建模,如 QAP。第三部分提出了蚂蚁算法,和引导本地搜索程序求解 QAP 等问题。第四、 五部分展示建模和结果对工业问题和评估了用于一些 QAPLIB 实例中所提出的方 法的性能。最后,第五部分得出结论。

2.问题描述和制定
2.1 描述 这个问题来自于一个由平行铁路建立的建筑物组成的火车维修设施。 每辆车 基本上跨越了两个建筑物,X1 和 X2 专业绘画和拆卸分别如图 1 所示。车辆首先 在外轨被处理,其次移至内轨上,然后在结束它们的路线之前,沿着一个给定的 序列移至两个建筑之间。 为了解决这个问题,每一个轨道被分解成区域,称为车辆的位置,在那里进 行维修任务。
消毒通风 入口 出口

锅炉制造修理 配件重新组装 专门技术 重量

拆开

收集

电力测试

刹车测试

绘画 喷丸 马具
3

重组的窗口

绘制

图 1 车辆路径在火车维护设施 被处理的车辆分批到达,并根据其序列在不同的建筑物中行驶。它们

被处理的车辆分批到达,并根据其序列在不同的建筑物中行驶。它们可以乘 跨波特在一个固定的轨迹进行横向移动。一个在轨道交通允许平行的轨道运动。 一些任务需要很长时间, 它可以在很长的时间里占据一些位置。这些任务代表瓶 颈车间。在目前车间,由于缺乏定位,经常为了让其他汽车访问全文,一些车辆 必须搬出去。 目前车间的布局已被证明非常制约生产线规划布局。问题是要在一 个建筑中找到一个资源的布局,以便优化它们之间的生产流。

图 2 建筑布局 说明: 1.建筑面积 2.汽车位置 3.不能通过的位置 4.循环通道 5.横线的运输机 6.在轨道上运输

换句话说,该问题也就是在一所房子里找到一个新的资源配置,如(图 2) 为了优化或(最小化)所有资源之间的生产流程或设备(设施) 。 我们认为在将 N 种资源分配到一个建筑物的 N 个站点或其上的位置上中。给 定一个距离矩阵 D, 其中的每个元素 Dk ,w 表示位置 K 和 W 之间的距离为 k, w = 1, 2,. . . ,N,一个流矩阵,其中每个元素的连接,表示一个资源 i 和 j 之间的流动 成本,i、j 取值为 1,2,. . . ,N。 流量成本取决于一个给定的时间范围内的资源的数量之间的行程。因为程序 限制,所以考虑的问题矩阵的流量是不对称的。
4

而距离矩阵是对称的。计算距离与最小车辆数将在一栋建筑来做个交换。图
? 0 , D( 1,3) ? 1 (通过交叉位置 2)和 D(2,6) ? 2 (通过交叉 3 为例, D(2,3)

位置 1 和 5) 。 2.2 二次分配问题(QAP) QAP 历来用于一些假设的 FLP 模型。在我们的工业问题中,车辆位置的尺 寸确定之间的位置和距离计算 Dk ,w 预定义的数字值。因此,它是可能将我们的问 题限定为一个 QAP 问题。

1

2

3

4

5

6

7

8

图 3 建筑内部的距离计算的一个例子

QAP 首次由 koopmans 和贝克曼(1957)提出,它是一个通过分配一组设 备到一套位置上,以减少与此相关的成本的问题,该问题不仅与距离和位置 有关,也和流动有关。

f ij 表示设施 i 和 j 之间的流 d k,w ,瓦特位置之间的距离 k 和 w 。 一个变量
P(i, j) 被定义为:

置 ?1, 如果该设备被分配到位 P(i, j) ? ? 其他情况 ? 0,
大多数情况下,设备 i1 签署地点 j1 和设施 i 2 指定位置 j2 相关的成本被认 为是流动的 f i1 ,i2 和距离 D j1 j2 。因此,解可以写成如下形式: 最小数 Z ? ?i
1

?? ?
i2 j1

j2

f i1i2 d i1i2 p(i1 , j1 ), p(i2 , j 2 )

s.t. ? j , ?i p (i, j ) ? 1,? i, ? j p (i, j ) ? 1 将问题建模后,我们采用基于蚁群优化的方法来解决它。

5

3. 蚁群优化算法和局部搜索算法
在第一章中,我们首先提出了蚁群优化算法和一般算法。然后,我们详 细描述了蚁群算法的元素适应的布局问题。我们结合蚁群算法并将其用于一 个引导本地搜索中。这一方法的定义和应用程序的二次分配问题在第 3.2 节 有提及。完整的算法 ACO_GLS 在第 3.3 节。

3.1 蚁群优化
蚁群算法的原理(Corne 等人,1999;Dorigo 等人,2000)是基于蚂蚁 寻找食物的方式。每只蚂蚁在确定自己的路线之前都需要考虑(概率选择) 所有其他的蚂蚁群体成员的信息素的踪迹,它的过程中,信息素的踪迹是一 个跟踪每一只蚂蚁留下的气味的方式。这种信息素随着测试时间而蒸发,因 此选择为每个蚂蚁的概率随时间的变化。在许多蚂蚁的路径中,对食品的路 径将人物化的痕迹,因此所有的蚂蚁信息素高的将遵循相同的路径。这种集 体行为,基于共享内部记忆的所有蚂蚁殖民地之间可以适应用于下列最优化 问题的解决: 真正的蚂蚁搜索空间成为空间的组合问题的解决方案。 源食物量成为相应的求解目标函数的评价。 信息素路径成为一种自适应共享存储器。 蚁群优化(ACO)的问题,因此可以被编码为寻找图中的最短路径。一 个蚁群算法的第一个应用程序是旅行商问题。 在一般情况下,蚁群算法适用于人工蚂蚁的概念,它可以表示为以下几 个步骤: 第 1 步:参数初始化。 第 2 步:解决方案的构建。 第 3 步:本地搜索算法。 第 4 步:信息素更新规则。 第 5 步:返回到第 2 步,直到得到一个满意的给定的停止准则。 适用于布局的蚁群算法问题是由以下要素组成: 1.结构化解决方案, 2.启发式信息,
6

3.信息素更新, 4.选择概率, 5.本地搜索, 6.多样化。 3.1.1 解决方案的构建 在该算法中,它被假定每个蚂蚁最初分配一个任务,i 到位置 j 上,记 为(i,j),然后将另一个任务分配到另一个位置 k 上,如此继续,直到获得 一个完整的解决方案。一个禁忌列表代表蚂蚁已经分配的一系列任务,也就 是列表对(i,j) 。这个列表确保所有的任务都被分配到给定的地点。任务的 分配标准要考虑到分配的概率与一个给定的位置,并取决于两个条件,一个 与每只蚂蚁的可见度有关, 另一个则与整个蚁群所存放的信息素的数量有关。 3.1.2 启发式信息 蚂蚁并不是完全盲目行动,它们会计算出一个给定的任务分配给某个地 点的成本。这个成本考虑到流动和距离矩阵。启发式信息,也叫可见度,是 一个函数的分配成本。在文献中使用的几个公式,并且每一个仅适用于一个 给定的问题。关于二次分配、任务的分配取决于分配的任务。将成本与分配
(i, l ) 的关系定义如下:

C (i, l ) ? ? ( f r ( s )i ? d sl ? f ir ( s ) ? d is )
s ?1

i ?1

(1)

其中r表示资源的下一个排列施工。其可视性表示移动的可取性,被定义为

na ?

1 1 ? ?s ?1 ( f r ( s )i ? d sl ? f ir ( s ) ? d is )
i ?1

(2)

在(2)中加入1分子的的原因是为了避免被0整除。这个公式表明任务对目 标函数的贡献较小将更有可能被选中。 3.1.3 信息素更新 信息素的更新机制可以用下面的公式表示:
k ? il (t ) ? ?? il (t ? 1) ? ? ?? il k

(3)

其中 SIT (t) 是信息素的分配的任务,它为每只蚂蚁分配的任务i及其地点l 的迭代相联系。当一只蚂蚁选择了该任务,数量 ?( 随之增加。快速收敛到局 il t)
7

部最优解为大的收敛结果。最终,
k ?? il ?? k

bestfit fit[k ]

(4)

表示通过蚂蚁分配的任务的跟踪级别的变化的大小。正如所见,越小的是更 适合的解决方案,通过蚂蚁k获得适合度[k],而越大将会使蚂蚁k选择的路径水 平越高。 3.1.4 选择概率 蚂蚁选择任务i分配到1的位置,通过以下概率:
k pil ?

i ?Tabuk

? ?? il ? (1 ? ? ) ??il ? (? ?? il ? (1 ? ? ) ??il )

(5)

其中一个有助于使整个蚂蚁 (近1) 和每只蚂蚁根据自己的能见度选择 (近0) 之间的平衡。 我们注意到如果相关的信息素的数量是有意义的或假设与此相关的 成本很低,那么,一个任务会被分配到一个位置。最终,具有最大概率的任务被 分配到位置l上。

3.1.5 本地搜索
我们选择本地搜索的方法2-opt是简单的, 并很好地应用于QAP算法中 (solimanpur等人,2004)。该方法适用于一个给定的解决方案的所有可能的排列的任 务。 每个突变以最小的成本为出发点, 选择一个局部极小值。 这个过程是重复的, 直到不再注意到改进为止。 为了在交换过程中限制计算时间,我们做了如下简化;如果交换了置换 ? 元 素 ? i 和 ? j 之间的位置,那么客观的差函数值则将是:
?(? , i, j ) ? (d ii ? d jj )( f ? i? i ? f ? j? j ) ? (d ij ? d ji )( f ? j? i ? f ? i? j ) ?
k ?i , j

? (d

ki

? d kj )( f ? k? j ? f ? k? i ) ? (d ik ? d jk )( f ? j? k ? f ? i? k )

(6)

这个代数式是由Gambard Ella等人在1997年提出的,他们提出了一个混合蚁 群算法应用到二次分配中的问题叫做一个HAS-QAP算法时简化的来的。 本地搜索不一定导致全局最小。 在大多数情况下, 它收敛到局部极小。 为此, 引导本地搜索法(GLS)被用作“penalize” ,当局部最小值发现为了收敛到全局 最小。GLS将在后面进行详细说明。
8

3.1.6 多样化 通过Gambardella等人(1997)使用。多元化机制被激活,如果迭代次数 max_iter期间,没有改善,最好的解决方案是检测产生。多元化经营-清除所有 信息包含的信息素的信息素矩阵重新初始化和随机产生新的当前解所有的蚂蚁 却一分帽子收到最好的解决方案,由搜索到目前为止。另一种可能性是删除所有 信息素的路径,除了最佳的解决方案。 蚁群算法 我们提出了以下的一般和2-opt蚁群优化算法。 步骤1:为所有任务和位置初始化参数, 步骤2:为每只蚂蚁分配任务的位置与概率P,更新信息素,如果最好的解决 方案是没有改善的max_iter迭代, ? il ? 0 ,但最好的解决方案, 步骤3:回到步骤2直到满足停止准则。 3.2 引导本地搜索(GLS) 引导本地搜索(GLS)(Mills等人,2003)是一种元启发式算法在局部搜索 算法的顶部。当给定的局部搜索算法解决局部最优,GLS的变化目标函数,以增 广目标函数增加处罚,相关的功能包含在局部最优。本地搜索,然后继续搜索使 用增强目标函数。 解决方案功能的选择取决于问题类型,每个特征定义必须有以下组件: 1.指示功能 I 的指示功能特点是目前在当前的解决方案或不。 如果特征FI ( i s) 在溶液S和0否则现在它等于1。 2.一个成本函数 c 对美国有网络连接的成本 ( i s) 3.一个点球 pi 最初设置为0,用来惩罚网络局部极小的发生。 当本地搜索返回一个局部最小,GLS增加功能的刑罚具有效用最大化的利用

(s, fi ) 定义如下:
util( s, f i ) ? I i ( s) c i ( s) 1 ? pi
(7)

这个想法的特点是为了惩罚,第一具有高成本的。GLS采用一种增强成本函 数,以引导本地搜索出本地最佳。的想法是,使当地的最昂贵的解决方案,在周
9

围的搜索空间,在相同的功能是不预先发送。
H ( s) ? g ( s) ? ?' ? I i ( s) ? pi
i ?1 n

(8)

其中 G(s) 是成本函数和 K 0 用来改变寻找解决方案的多样化的参数。 K 0 较高的 值会导致更多的多样化的搜索。地理中的应用他QAP问题与以下类:即实现特征 网络;Pi 溶液的对应任务的分配我的位置 Pi 。功能网络连接的成本取决于我对解 决美国所有其他任务的任务相互作用。这个成本是由

c(i, ? i ) ? ? f ij D? i? j
j ?1

n

(9)

的值很好的适应了QAP问题:

?



? ? ?
n i ?1

n j ?1

f ij ??i ?1 ? j ?1 Dij
n n

n4

(10)

GLS技术在该QAP问题中的应用可以归纳为以下: 从当前的解决方案,一个本地搜索的方法(例如使用2-opt)找到一个局部 最小值,以增强成本函数。如果这个最小的成本(不增加)比发现的最低成本, 它被保存为最好的解决方案。最后,具有最大效用的分配将有相应的惩罚增加。 所述GLSQAP算法可以被概括为如下: 步骤1:计算。 步骤2:最优解 =初始解s。 步骤3:相对于增强成本函数执行本地搜索2-opt,*是目前发现的解决方案 具有低成本扩张。 如果成本(*)<成本( S0 ),由*代替 S0 。找到任务(功能)的具有最大的 效用,让它成为 Fi ; Pi 为例。增加相应的处罚: 步骤4:回到步骤3,直到满足给定的停止准则。 步骤5:S0找到原问题的最佳解决方案。

3.3 完整的算法
最后,与GLS的蚁群优化算法的程序如下: 步骤1:初始化参数。
10

步骤2:为所有蚂蚁。 (a)分配任务的位置与给定的分配概率, (b)执行本地搜索GLSQAP, (c)更新信息素, (d)如果最好的办法是不到max_iter迭代改进,? il ? 0 ,但最好的解决 方案。 步骤3:回到步骤2,直到满足停止准则。

4.工业案例应用
我们认为在建筑物的位置或汽车地点分配的资源。给定一个距离矩阵D,其 中每个元素的DK,W表示位置K和W之间的距离为k,w = 1,2,? ,N和一个流矩 阵,其中每个元素的网络连接,表示一个资源i和j之间的流动成本,为 i, j = 1, 2,? ,N。 我们的问题建模为一个QAP。流量成本取决于一个给定的时间范围内的资源 的数量之间的行程。在所考虑的问题,矩阵是非对称的,在流证据的限制。距离 矩阵是对称的。 的距离计算是相关的最小数量的车辆移动的建筑物内, 以使交换。 模型参数: N 变量总数 资源j分配到的任务i 位置W之间的距离k和瓦特本距离被定义为可使用的数这两个资源

rij Dk ,w
之间的位置
f rij ,r ' '
i j

资源RIJ之间生产流程和。此流被评价为数字汽车两种资源之间传

递的

?1,如果rij 表示分配给位置k prij ,k ? ? 否则 ? 0, standedize d ?1,如果位置是 TEk ? ? 否则 ? 0, ?1,如果是专门的位置 TESk ? ? 否则 ? 0,
11

(11)

(12)

(13)

为了优化生产流程,我们定义二次函数的最小化:

Z ? ?????? f rij ,r ' ' ? Dk ,w ? prij ,k ? f rij ,w
i j i' j' k w
i j

(14)

如果不可用的位置被排除,应添加下面约束:

? k : ?? prij ,k ? 1
i j

(15) (16) (17)

? i,j : ? prij ,k ? 1
k

TEk ? TESk ? 1

约束(15)和(16)是定期分配问题的标准约束。约束(17)意味着,占据 了所有的位置都是专业的或标准的。

5.实验结果
5.1 参数 该算法利用Visual C++ 6实现。在奔腾3与1.8兆赫的处理器速度。在该算法 中的四个参数:蚂蚁数量, ? , max _ iter 和影响该性能的算法等。试运行我们 的问题,每形成要找到合适的参数。蚂蚁数量的测试5和60之间,和的结果与常 规的质量之间的折衷一致收敛时间被发现 表1列出了适当的值。很好的适应与GLS程序。个体蚂蚁调查。这个值被发现 支持更多的支持信息素的路径比值0.6表明该溶液的建设—通常, ? 是接近0.5。 在我们的情况下而被发现的 max _ iter = 10和 ? = 0.6。对于AN= 20。当一个是 固定的,这个值被发现到很好地适应与GLS过程。
表1 参数值 参数 AN Alpha 值 20 0.6 10

max _ iter

?0
5.2 工业应用

0

工业问题包括72个地点27不能使用,39个专业和6个标准化位置。实际资源
12

分配作为算法的初始条件。 所有计算是根据一年的数据计划。车间的实际布局产 生然而,425的成本,我们的算法ACO_GLS提出了一种解决方案,与改进19.6% 尊重实际布局。 这意味着它收敛与一个更好的解决方案,这证明了它有能力解决 工业布局问题。 我们也找到了问题的精确解通过使用枚举方法,因为只有六个任务需要分 配。 该溶液是相同的被发现的算法。这意味着该算法收敛到最佳的解决方案这个 产业问题。 建议的应用程序可能是有用的未来产业案例。事实上,如上所述在问题描述 中,行业正在尝试提高其性能,这意味着解决其他设施问题。此外,实例进行了 测试和结果进行了比较其他车辆与其他研究。 5.3 概括 该算法的性能进行了测试,从库QAPLIB实例(Burkard等人,1991)。我们 首先比较我们的算法与HAS-QAP(Gambardella等人,1997)的方法关于蚂蚁殖民 地。我们将它与ANTabu比较(Talbi等人,2001),与其他基于遗传算法的方法, 仿真退火,禁忌搜索或蚁群,并通过solimanpur等人(2004)与最近提出的蚁群 优化算法。该小数量的问题。表3比较的结果,所有的引用算法对于小实例的位 置下降在30和19之间。 我们选择的实例包括规则和QAPLIB不规则问题。 这种差异关系有利于QAPLIB 最知名的解决方案一个百分比差距。这几乎是不可能的,相同的实验设置为以前 的研究,但是,为了给计算的想法时间,平均执行时间超过10个运行显示在表2。 表2证明了对于实例30个任务,ACO_GLS性能优于所有其他比较算法。为了推 广我们的算法中的应用方法, 从大量QAPLIB实例研究不同种类的问题。结果是表 3中我们比较这些算法对一组12的实例研究,范围从35到128个位置。 大实例。曾经,我们仍能获得满意的解决方法ACO_GLS性能比HAS-QAP更好。 如何—实例。它表示(表3),我们的算法大的问题,逃离局部极小执行更复杂 的本地搜索ntabu是更好一点,所以我们可能要对于较大的实例,给出的结果所 提出的ACO_GLS算法被证明融合完美的情况下,最多40个地点作为示于表2和3这 种性能是中规中矩的工业问题, 因为现实生活中的问题,通常不超过30?40的位 置。因此,这种算法将是一个非常有用的工具,布局优化,在现实生活中的产业

13

本文案例中说明。

表2
比较从QAPLIB选择二次分配情况的结果(最好的结果是黑体字) 最优解 Els 19 Tai 20b Chr 25a Bur 26a Bur 26b Bur 26c Bur 26d Bur 26e
Bur 26f Bur 26g Kra30a Kra 30b Nug30

HAS_QAP 0.923 0.243 3.0822 0 0 0 0 0
0 0 0.6299 0.0711 0.098 0

ANTabu 0 0 0.8957 0 0.0169 0 0 0
0

ACO Solimanpur 0 0 0 0 0 0 0 0
0 0 0 0.0153 0.013

ACO_GLS 0 0 0 0 0 0 0 0
0 0 0 0 0

时间(秒) 4 5 3 35 34 34 35 34
34 33 35 19 3

17212548 122455319 3796 5426670 3817852 5426795 3821225 5386859
3782044 10117172 88900 91420 6124

0.2677 0 0

数值表示解决方案的价值和百分比最著名值之间的平均差距。 表3
比较从QAPLIB选择二次分配情况的结果(最好的结果是黑体字)
最优解 Tai 35a Tai 35b Tai 40a Tai 50a Tai 60a Tai 80a Wil 50 Sko42 2422002 283315445 3139370 4941410 7208572 13557864 48816 15812 HAS_QAP 1.762 0.343 1.989 2.800 3.070 0.663 0.061 0.076 ANTabu 0.215 0.0408 0.442 0.781 0.919 0.663 0.008 0 ACO_GLS 0 0 0 1.28 1.25 1.53 0.01 0 时间(秒) 109 112 204 228 342 1524 1197 82

14

Sko49 Sko56 Sko64 Esc 128

23410 34524 48498 64

0.141 0.101 0.129 -

0.038 0.002 0.001 0

0.10 0.19 0.008 0

105 294 522 1292

六、总结
在本文中,我们提出了一个强大的元启发式算法的布局问题建模为一个QAP。 该算法是基于蚁群优化和引导本地搜索。GLS利用资源的成本函数为引导本地搜 索出一个局部最优解, 该算法的发展是出于一个产业的案例在列车维修设施。我 们把它应用到一个工业案例有六个位置,并找到最佳的解决方案。由于位置的数 量在未来会增加, 我们提出的蚁群算法的性能进行了测试,一些测试选自文献相 比,许多现有的算法问题。结果表明,性能相比,HAS-QAP,ANTabu和Solimanpur 等。蚁群算法随着位置的人数高达40的问题都可以得到我们的算法ACO_GLS。因 此,ACO_GLS是最适应的算法对该工业的情况和其他适应数小于40的位置布局问 题;然而,结果仍然是令人满意的,具有较大实例布局问题的。 未来的工作包括对于大型实例,寻找更复杂的本地搜索,找到一个更好的结 果,可以处理更复杂的约束问题的方法。

参考文献
Armour, G.C., Buffa, E.S., Vollmann,T.E., 1964. Allocating facilities with CRAFT. Harvard 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, 1625–1641. Baykasouglu, Gindy, N.N.Z., 2001. A simulated anealing algo-rithm for dynamic layout problem. Computers & Operations Research 28,1403–1426. Burkard, 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 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

457–488. Chwif, L., Barretto, M.R.P., Moscato, L.A., 1998. A solution to the facility layout problem using simulated anealing. Com-puters in industry 36, 125–132. 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, L.M., Taillard, E.D., Dorigo, M. Ant colonies for the QAP, Technical report IDISIA, 1997, pp. 4–97. 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 location of economic activities. Econometrica 25, 53–76. Kusiak, Heragu, S.S., 1987. The facility layout problem. Euro-pean Journal of Operational research 29, 229–251. 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. Computers & Operations Research 32 (4), 879–899. Lin, S., 1965. Computer solutions for the traveling selsman problem. Bell System Technology Journal 44, 2245–2269. Maniezzo, V., Colorni, A., Dorigo, M. The ant system applied to the quadratic assignment problem. Technical report IRIDIA/,Universite Libre de Bruxelles, 1994, pp. 94–128. 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), 304–322. Meller, R.D., Narayanan, V., Vance, P.H., 1999. Optimal facility layout design. Operations Research Letters 23, 117–127. Mills, P., Tsang, E., Ford, J., 2003. Applying an extended Guided Local Search to the Quadratic Assignment Problem, Annals of OR 118, 121–135. Mir, M., Imaam, M.H., 2001. A hybrid optimization approach 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, 43–58. Montreuil,B.,Venkatadri,U., Ratliff, H.D., 1993. Generating a layout
16

from a design skeleton. IIE Trans 25, 3–15. 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 layout problem in cellular manufacturing. European Journal of Operational Research 157, 592–606. Solimanpur, M., Vrat, Prem, Shankar, Ravi, 2005. Ant algorithm for the single row layout problem in flexible manufacturing systems. Computers & Operations Research 32 (3), 583–598. Stutzle, T., Dorigo, M. Aco algorithm for the quadratic assignment problem. Technical report IRIDIA/, Universite Libre de Bruxelles, 1999, pp. 99–102. 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 Generation Computer Systems 17, 441–449. Tam, K.A., 1992. Genetic algorithms, function optimization, and facility layout design. European Journal of Operational Research 63, 322–346. Tavakkoli-Monghaddain, R., Shayan, E., 1998. Facilities layout design by genetic algorithms. Computers Industrial Engineering 35, 527–530. Voudouris, Guided Local Search for Combinatorial Optimisation Problems, Ph.D. thesis, Department of Computer Science, University of Essex, 1997. Voudouris, E., Tsang, P.K., 1999. Guided Local Search and its application to the Travelling Salesman Problem. European Journal of Operational Research 113 (2), 469–499.

17


群蚁算法翻译.doc

群蚁算法翻译_理学_高等教育_教育专区。离散优化 求解工业布局问题的蚁群算法 Y

蚁群算法外文翻译.doc

算法外文翻译 中文:起源 蚁群算法(ant colony optimization, ACO),又称蚂蚁算法...这在蚁 群中来讲就表现为,蚂蚁的行为过于僵硬,当环境变化了,蚂蚁群仍然不能...

蚁群算法蚂蚁算法中英文对照外文翻译文献.doc

蚁群算法蚂蚁算法中英文对照外文翻译文献 蚁群算法蚂蚁...首先, 你要让蚂 蚁能

群蚁算法文献综述.doc

群蚁算法文献综述_理学_高等教育_教育专区。西安理工大学本科生毕业设计(论文)文

蚁群算法与K均值算法结合翻译.doc

蚂蚁倾向于移动到信息素强度高的步道,因此,如果大量的蚂 蚁选择一个路径,这条...蚁群算法的应用的翻译 暂无评价 8页 1下载券 一种改进的粒子群和K均值......

毕业设计外文翻译-用蚁群算法在刀库索引位置的优化配置.doc

毕业设计外文翻译-用蚁群算法在刀库索引位置的优化配置 - Optimal all

毕业论文 群蚁算法模拟系统的设计与实现.doc

毕业论文 群蚁算法模拟系统的设计与实现_教育学_高等教育_教育专区。毕业论文 群蚁算法模拟系统的设计与实现 JI A N G S U 本科 UNIVERSITY 毕业论文 蚁群算法...

蚁群算法_图文.ppt

LOGO 蚁群算法 2 蚁群算法概念 2.1 蚁群算法原理 ...(i, j)上的信息量,n表示TSP规模,m为 群中...

蚁群算法_图文.ppt

蚁群算法 - 蚁群算法在车辆路径中的应用... 的能见度. ij ij ? ij 下午5时5分 9/23 2…蚁群...蚁群算法的Matlab程序 5页 1下载券 毕业论文外文翻译视频...

精 清华古文教授按古书翻译 《巧连神术》算人姓名和运气.doc

精 清华古文教授按古书翻译 《巧连神术》算人姓名和运气_临床医学_医药卫生_...群蚁附 李生道傍 花发上林 不敢说好 海青河宴 天下太平 绝无所好 发物...

2018年_图文.doc

群蚁算法翻译 暂无评价 17页 免费 2016-2020年中国旅游行业...

人力资源调度的蚁群算法模型_李松.pdf

蚁的工作循环中由第 i 只蚂蚁经过第 j 座城市所留 信息素的量及第 i 只...并且终止整个程序) END IF 3.3 蚁群算法优化 某产品中文说明书要翻译成四种文字...

2018计算机视觉分析报告.doc

可以准确识别车牌关键信息 【遥感图像解译】基于多源遥感影像进行全自动路网提取,...群蚁算法翻译 暂无评价 17页 免费 基于Android手机的室内定... 62页 2...

2017年调研课题.doc

群蚁算法翻译 暂无评价 17页 免费 中华传统文化知识 25页 2下载券 2

2018年火箭少女101成长数据纪录报告_图文.pdf

群蚁算法翻译 暂无评价 17页 免费 2018 Baidu |由 百度云 提供计

通信工程 网络技术 外文翻译 文献翻译 外文文献.doc

通信工程 网络技术 外文翻译 文献翻译 外文文献 - 外文翻译 译文题目: 在

网络市场调研_图文.ppt

房地产市场调研宝典71页 63页 5下载券 群蚁算法翻译 暂无评价 17页 免

PTA函数答案.doc

34页 免费 群蚁算法翻译 暂无评价 17页 免费 基于Android手机的

遗传算法与蚁群算法在旅行商问题中的应用.doc

遗传算法与蚁群算法在旅行商问题中的应用_IT/计算机...35 中文翻译 ......7 1.4.3 蚁群算法的应用进展以蚁群算法为代表的群智能已成为当今分布式人工智能研究的...

基于蚁群算法的点状注记智能化配置_图文.pdf

翻译性和成为一种信息传输的工具 , 是地 图 ( 包括纸质地图和屏幕地图 ) ...粒子群遗传混合算法在点... 暂无评价 5页 2.00 基于蚁群算法的资源优化...