-
离散优化
求解工业布局问题的蚁群算法
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
被适用于工业中的情况，
其被法国的铁路系统设施
（<
/p>
SNCF
）
用在列车的维修中。结果表明
，与实际布局相比，这种实现有近
20%
的改善。由
于问题建模为一个二次分配问题
LEM
（
QAP
）
，我们将我们的方法与一些可以解决<
/p>
此问题的最佳启发式方法做了比较。实验结果表明，在小型实例中，
ACO_GLS
算
法表现更好，而对于大型实例，其计算结果
依旧令人满意。
关键词：布局问题；二次分配问题；蚁群优化；局部搜索
1.
介绍
设施布局问题（
FLP
）是一个发现机
器的很好的配置，在一个给定的设备以
优化生产流程的同时最小化总成本的设备或其他资
源。
它对一个制造系统的性能
具有重要意义。
< br>设施布局问题在很多方面都有应用，
如厂房组织的应用，
新的生
产建设单位，
或设备分配。
一个
完整的布局描述的问题可以从
（
Kusiak
< br>和
Heragu
，
1987)<
/p>
中找到。布局问题是众所周知的
NP-
难
度（
Sahni and Gonzales, 1976
）<
/p>
，
可以在许多经典的理论研究中发现。
然
而，
只有少数工业布局案例在文献中被解
决。应用遗传算法，希
克斯（
2006
）提出了一个遗传算法，用于如何在一个制造<
/p>
单元中最小化物质运动并将其应用到资本主义工业生产的实际问题中，
Lee
等
人
（
< br>2005
）
提出了一种解决多楼层设施的布局问题，
包括墙壁和通道的内部结构
的遗传算法。马丁（
2004
）提出了一个与时尚产业有关的研究课题。
1
大量
的研究已对
FLP
进行论述；大部分是基于二次分配问题（
QAP
）
。存在其
他类型，诸如混合整数规划（
Montreuil and Laforge
，
1990
；
montr
euilet
等
人，
1993
；
Meller
，
1
999
）和图论模型（
Caccetta and
Kusumah, 2001
）
。很多
解
决
布
局
问<
/p>
题
的
方
法
是
基
于
元
启
发
式
算
法
，
如
遗
传
算
法
（
TAM
，
1992
；
< br>Tavakkoli-Monghaddain
and
Shayan
，
1998
；
Lee
等人
,
200
5
）
，
禁忌搜索
（
Chiang
and
Chiang,
1998
）
，
模拟退火
（
Bayk
asog
lu
等人
,
2001;
Chwif
等人
1998;
Mir
and Imaam,
2001
）和蚁群算法（
Solimanpur
等人
, 2004; Sol-
imanpur
等人
2005
）
。其他方法结合了遗传算法与模拟退火算法（
Balakrishnan
等人
,
2003
）
，
由
Armour
等人开发工艺
（
19
64
）
。
为了确保得到到一个最小计算
时间的全局最优
解，
metaheu-ristics
通常包括像这样的
2-opt
（
Lin
，
1965
）局部搜索
方法。另
一种方法被称为引导本地搜索
（
GLS
）
（
Voudouris,1
997
）
选取一个本地搜索和许
可前逃
离局部极小值，从而保证全局收敛性。
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
程
序，
摆脱局部极小蚁群优化方法。
该方法首先被应用到一个特定
的工
业问题中，然后，在数量很少的情况，以及从公共库
QAP
LIB
实例的性能下
（
Burkard
等人，
1991
）
，
我们的测试结果与
Solimanpur
（
2004
）
，
Gambardella
（
1997
）和泰尔比等人（
2001
）相比，基本一致。
本文的其余四个部分是：
第二部分描述的设
施布局问题和工业实例建模，
如
QAP
。第三部分提出了蚂蚁算法，和引导本地搜索程序求解
QAP
等
问题。第四、
五部分展示建模和结果对工业问题和评估了用于一些
QAPLIB
实例中所提出的方
法的性能。最后，第五部分得
出结论。
2.
问题描述和制定
2.1
描述
这个问题来自于一个由平行铁路建立的建筑物组成的火车维修设施。
每辆车
基本上跨越了两个建筑物，
X1
和
X2
专业绘画和拆卸分别如图
1
所示。车辆首先
在外轨被处理，
其次移至内轨上，
然后在结束它们的路线之前，
沿着一个给定的
序列
移至两个建筑之间。
为了解决这个问题，
每一个轨道被分解成区域，
称为车辆的位置，
在那里进
行维修任务。
消毒通风
入口
出口
锅炉制造修理
配件重新组装
专门技术
重量
拆开
收集
电力测试
刹车测试
绘画
重组的窗口
喷丸
马具
3
绘制
图
1
车辆路径在火车维护设施
被
处理的车辆分批到达，并根据其序列在不同的建筑物中行驶。它们
被处理的车辆分批到达，并根据其序列在不同的建筑物中行驶
。它们可以乘
跨波特在一个固定的轨迹进行横向移动。一个在轨道交通允许平行的轨道运
动。
一些任务需要很长时间，
它可以在很长的时间里占据一些位
置。
这些任务代表瓶
颈车间。在目前车间，由于缺乏定位，经常
为了让其他汽车访问全文，一些车辆
必须搬出去。
目前车间的布
局已被证明非常制约生产线规划布局。
问题是要在一
个建筑中找
到一个资源的布局，以便优化它们之间的生产流。
图
2
建筑布局
说明：
1.
建筑面积
2.
汽车位置
4.
循环通道
5.
横线的运输机
6.
在轨道上运输
3.
不能通过的位置
换句话说，该问题也就是在一所房子里找到一个新的资源配置，如（图
2
）
为了优化或（最小化）所有资源之间的生产流程或设备（设施）
。
我们认为在将
N
种资源分配到一个建筑物的
N
个站点
或其上的位置上中。
给
定一个距离矩阵
D
，
其中的每个元素
D
k
,
w
表示位置
K
和
W
之间的距离为
k
，
w =
1
，
2
，
.
. .
，
N
，
一个流矩阵，其中每个元素的连接，表示一个资源
i
和
j
之间的流动
成本，
i
、
j
取值为
1
，
2
，
.
. .
，
N
。
流量成本取决于一个给定的时间范围内的资源的数量之间的行程。因为程序
< br>限制，所以考虑的问题矩阵的流量是不对称的。
4
而距离矩阵是对称的。计算距离与最小车辆数将在一栋建筑
来做个交换。图
?
0
，
D
（
1
,
3
）
?
1
（通过交叉位置
2
）和
D
（
2
,
6
< br>）
?
2
（通过交叉
3
为例，
D
（
2
,
3
）
< br>位置
1
和
5
）
。
2.2
< br>二次分配问题（
QAP
）
QAP
历来用于一些假设的
FLP
模型。在我们的工业问题中，车辆位置的尺
寸确定之间的位置和距离计算
D
k
,
w
预定义的数字值。
因此，
它是可能将我们的问
题限定为一个
QAP
问题。
1
2
5
6
3
4
7
8
图
3
建筑内部的距离计算的一个例子
QA
P
首次由
koopmans
和贝克曼<
/p>
（
1957
）
提
出，
它是一个通过分配一组设
备到一套位置上，以减少与此相关
的成本的问题，该问题不仅与距离和位置
有关，也和流动有关。
f
ij
表示设施
i
和
j
之间的流
d
k
,
w
，
瓦特位置之间的距离
k
和
w
。
一个变量
P
（
i
,
j
）
被定义为：
置
?
1
，
如果该设备被分配到位
P(i,
j)
?
?
0
，
其他情况
?
大多数情况下，设备
i
1
签署地点
j
1
和设施
i
2
指定位置
j
2
相关的成本被认
为是流
动的
f
i
1
,
i
2
和距离
D
j
1
j
2
。因此，解可以写成如下形式：
最小数
Z
?
?
i
1
?
?
?
i
2
j
1
j
2
f
i
1
i
< br>2
d
i
1
i
2
p
(
i
1
,
j
1
),
p
(
i
2
,
j
2
)
s.t.
?
j
,
?
i
p
(
i
,
j
)
?
1
,
?
i
,
?
j
p
(
i<
/p>
,
j
)
?
1
将问题建模后，我们采用基于蚁群优化的方法来解决它。
5
3
.
蚁群优化算法和局部搜索算法
在第一
章中，我们首先提出了蚁群优化算法和一般算法。然后，我们详
细描述了蚁群算法的元素
适应的布局问题。我们结合蚁群算法并将其用于一
个引导本地搜索中。这一方法的定义和
应用程序的二次分配问题在第
3.2
节
有提及。完整的算法
ACO_GLS
在第
3.3
节。
3.1
蚁群优化
蚁群算法的原理（
Corne
等人，
1999
；
Dorigo
等人，
2000<
/p>
）是基于蚂蚁
寻找食物的方式。每只蚂蚁在确定自己的路线之前都
需要考虑（概率选择）
所有其他的蚂蚁群体成员的信息素的踪迹，它的过程中，信息素的
踪迹是一
个跟踪每一只蚂蚁留下的气味的方式。这种信息素随着测试时间而蒸发，因
此选择为每个蚂蚁的概率随时间的变化。在许多蚂蚁的路径中，对食品的路
< br>径将人物化的痕迹，因此所有的蚂蚁信息素高的将遵循相同的路径。这种集
体行为
，
基于共享内部记忆的所有蚂蚁殖民地之间可以适应用于下列最优化
问题的解决：
真正的蚂蚁搜索空间成为空间的组合问题的解决方案。
源食物量成为相应的求解目标函数的评价。
信息素路径成为一种自适应共享存储器。
蚁群优化（
ACO
）的问题，因此可以被编码为寻找图中的
最短路径。一
个蚁群算法的第一个应用程序是旅行商问题。
<
/p>
在一般情况下，蚁群算法适用于人工蚂蚁的概念，它可以表示为以下几
个步骤：
第
1
< br>步：参数初始化。
第
2
步：解决方案的构建。
第
< br>3
步：本地搜索算法。
第
4
步：信息素更新规则。
第
5
步：返回到第
2
步，直到得到一个满意的给定的停止准则。
适用于布局的蚁群算法问题是由以下要素组成：
1.
结构化解决方案，
2.
启发式信息，
6
3.
信息素更新，
4.
选择概率，
5.
本地搜索，
6.
多样化。
3.1.1
解决方案的构建
在该算法中，它被假定每个蚂蚁最初分配一个任务，
i
到位置
j
上，记
为（
i
，
j
）
,
然后将另一个任务分配到另一个位置
k
上
,
如此继续，直到获得
一个完整的解决方案。一个禁忌列表代表蚂蚁已经分配的一系列任务，也就
是列表对（<
/p>
i,j
）
。这个列表确保所有的任务都被
分配到给定的地点。任务的
分配标准要考虑到分配的概率与一个给定的位置，并取决于两
个条件，一个
与每只蚂蚁的可见度有关，
另一个则与整个蚁群所
存放的信息素的数量有关。
3.1.2
启发式信息
蚂蚁并不是完全盲目行动
，它们会计算出一个给定的任务分配给某个地
点的成本。这个成本考虑到流动和距离矩阵
。启发式信息，也叫可见度，是
一个函数的分配成本。在文献中使用的几个公式，并且每
一个仅适用于一个
给定的问题。关于二次分配、任务的分配取决于分配的任务。将成本与
分配
(
i
,
l
)
的关系定义如下：
C
(
i
,
l
)
?
?
(
f
r
(
s<
/p>
)
i
?
d
sl
?
f
ir
(
s
)
?
d
is
)
s
?
1
i
?
1
（
1
）
其中
r
表示资源的下一个排列施工。其可视
性表示移动的可取性，
被定
义为
n
a
?
1
1
?
?
s
?
1
(
f
< br>r
(
s
)
i
?
d
sl
?
f
ir
(
s
)
?
d
is<
/p>
)
i
?
1
（
2
）
在
（
2
）
中加入
1
分子的的原因是为了避免被
0
整除。这个公式表明任务对目
标函数的贡献较小
将更有可能被选中。
3.1.3
信息素更新
信息素的更新机制可以用下面的公式表示：
k
?
il
(
t
)
?
??
il
(
t
?
1
)
?
?
?
?
il
k
（
3
）
其中
SIT
（
t<
/p>
）
是信息素的分配的任务，它为每只蚂蚁分配的任务
i
及其地点
l
的迭代相联系
。当一只蚂蚁选择了该任务，数量
?
（
随之增加。快速收敛到局
il
t
）
7
部最优解为大的收敛结果。最终，
k
?
?
il
?<
/p>
?
k
bestfit
fit
[
k
]
（
4
）
表示通过蚂蚁分配的任务的跟踪级别的变化的大小。
正如所见，
越小的是更
适合的解决方案，通过蚂蚁
k<
/p>
获得适合度
[k]
，而越大将会使蚂蚁<
/p>
k
选择的路径水
平越高。
3.1.4
选择概率
<
/p>
蚂蚁选择任务
i
分配到
< br>1
的位置，通过以下概率：
k
p
il
?
i<
/p>
?
Tabuk
?
?
?
il
?
(
1
?
?
)
?
?
il
?
(
?
?
?
il
?
(
1
?
?
)
< br>?
?
il
)
（
5
）
其中一个有助于使整个蚂蚁
（近
1
）
和每只蚂蚁根据自己的能见度选择
（近<
/p>
0
）
之间的平衡。
我们注意到如果相关的信息素的数量是有意义的或假设与此相关的
成本很低，那么，一
个任务会被分配到一个位置。最终，具有最大概率的任务被
分配到位置
< br>l
上。
3.1.5
本地搜索
我们选择本地搜索的方法<
/p>
2-opt
是简单的，
并很好地应用于<
/p>
QAP
算法中
（
soli-
manpur
等人，
20
04
）
。
该方法适用于一个给定的解决
方案的所有可能的排列的任
务。
每个突变以最小的成本为出发点
，
选择一个局部极小值。
这个过程是重复的，
< br>直到不再注意到改进为止。
为了在交换过程中限制计算
时间，我们做了如下简化；如果交换了置换
?
元
素
?
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
,<
/p>
j
?
(
d
ki
?
d
kj
)(
f
?
k
?
j
?
f
?
k
?
i
< br>)
?
(
d
ik
?
d
jk
)(
f
?
j
?
k
?
f
?<
/p>
i
?
k
)
（
6
）
这个代数式是由
Gambard
El
la
等人在
1997
年提出的，他们提
出了一个混合蚁
群算法应用到二次分配中的问题叫做一个
HAS
-QAP
算法时简化的来的。
本地搜
索不一定导致全局最小。
在大多数情况下，
它收敛到局部极小。
为此，
引导本地搜索法（
GLS
）被用作“
penalize
”
，当局部最小值发现为了收敛到全局
最小。
GLS<
/p>
将在后面进行详细说明。
8
-
-
-
-
-
-
-
-
-
上一篇：颈部解剖位置的定位[1]
下一篇：世界著名服装设计师及品牌