-
一种基于流水车间调度问题的蚁群算法
概要
蚁群
系统算法（
ACS
）
，是受自然界中真
正蚂蚁寻找食物的行为启发，而产生的的一种
新颖的模仿蚁群觅食行为的智能算法。
這篇文章第一次把蚁群系统算法引入到
n/m/P/C
m
ax
问
题，
n/m/P/C
m
ax
问题
是一个
NP-hard
先后顺序问题，
用于找到
n
个工件以相同的顺序在
m<
/p>
台
机器上加工，
n
个工件在每台机器上最优的加工顺序，使最大流程时间达到最小。为了证实
蚁群算法是
一种先进的成熟的算法，
在众所周知的
Taillard
基准测试问题集上做了计算实验，
用蚁群算法与其它的启发式算法比如
遗传算法、
模拟退火，
邻域搜索等相比较，
计算结果显
示
ACS
在
n/m/P/C
m
ax
问
题上事一种很有效的启发式算法。
1.
引言
考虑一个先后顺序问题，如下：
有<
/p>
n
个不同的工件要在
m
< br>台机器上完成加工，
每个工件在每台机器上都完成一次操作，
并且所有的工作在各个机器上运行的顺序都有一样。
在任一时刻，
< br>每台机器只能处理一个工
件，
并且一个工件只能在一台机
器上加工，
没有优先权。
目标是为了使所得调度方案的最大
完成时间最小。按照惯例，这个问题应该由
n/m/P/C
m
ax
问题指出，并且是个著名的
NP-hard
问题
[
1<
/p>
]
。
[
2
]
在过去的
40<
/p>
年中，
n/m/P/C
m
ax
问题引起了很多研究员的注意
问题最佳的方法可以
通过列举的方法获得，像穷举和分解法
[
3
]
。尽管解决
n/m/P/C
m<
/p>
ax
，这些方法会带来超高的计
算量，<
/p>
即使是对于那些中等的不是很大的问题。
为了达到实际的目的，<
/p>
经常进行分配去寻找
启发式的方法以产生最佳的解决方法并使得相
关计算费用比较少。
这就导致了许多启发式程
序的诞生发展。<
/p>
当前文献中可用的解决这个问题的启发式方法可分为两类：
初始序列的产生阶段和改进
阶段
[
4
]
。在初始序列的产生阶段中，一但工件的操
作顺序被确定，那就固定不变了，不能
[
5
?
8
]
被颠倒
.
一些关于
n/m/P/C
m
ax
问题的建设性启发在文献
中都有提到，
计算结果表明这种
NEH
[
7
]
和
SPIRIT
[
2
]
启算法方法是当前可用的最好的也是被我们所熟知的方法。另一方面，
改良型启发先以一个最初的方法启动，在用一种手段来反复的获得改良方法。在最近几年，
在这一理论上应用启发式算法已经被广泛的推广进行，
启发式算法已经成为了一种可以
在较
少的限制下应用于不同的最优化问题的相当普遍的计算结构。
实际上，
有一类算法可以随机
化改进启发式算法
[
4
]
。这一类型的方法包
括：遗传算法（
GA
）
[
10
,
11
]
，模拟退火算法（
SA
）
[
12
,
13
]
，
还有禁忌搜索
[
14
,
15
]
。
文献表明这些方法在
NP-
hard
组合优化问题上起到很大的作用。
蚁群系统算法（
ACS
）
，是
Dorigo
和
Gambardella
在
1997
年首先提出的
[
18
]
，是解决组
合优化问题的一种很新很有希望的启发式算法。在
这篇论文中，我们为
n/m/P/C
m
ax
问题编
写一个
ACS
算法。这个算法将用来和以前用的
GA
，
SA
和临近搜索算法（
NS
）
，一类由
Taillard
[
19
]
提出的基准问题将被用于这次比较。
论文的其余本分分配如下：在下一个章节，
我们介绍一下
ACS
的背景。然后我们介绍一下在第
3
节中
应用的
ACS
的描述。我们执行
n/m
/P/C
m
ax
问题的
ACS
算法是第
4
节的任务。
在
Taillard
基准问题上计算结
果并进行和其他
启发式算法的比较将在第
5
节被执行。最后，我们将在第
6
节用一个概要结束这篇文章
。
算法的背景
ACS
是蚁群优化（
ACO
）
[
20
]
的一种特殊的启发式算法，是一种解决不相关联优化问
[
21
]
题的自然的有创造力的启发式算法。第一个
ACO
系统是由
Dorigo
< br>介绍的
，被叫做蚂蚁
系统（
AS
）
，它是计算人员在研究组合优化问题的结果。蚂蚁系统的来源
是自然界中使人感
兴趣的蚂蚁觅食行为，
真实的蚂蚁可以在没有
视觉信号的情况下找到从食物源头到它们巢穴
的最短路径。
它们
通过一种带有芬芳的香精来交流关于食物来源的信息，
这一芬芳香精被叫
做信息素。
当行走时，
蚂蚁将在路过的地面上分泌信息
素而且有一定几率跟随前边的蚂蚁留
下的信息素行走。
路径上不
断增长的大量的信息素给予后来的蚂蚁很大的鼓舞，
从而使得后
来的蚂蚁会更高几率的跟随前边的蚂蚁留下的信息素行走，
因为蚂蚁经过食物源由短路径
回
到巢穴要快于那些由长路径回来的蚂蚁。
所以，
短的路径上的信息素密度将比长路径上的大，
所以，
由此推理，
这就造成了短路径是那个的信息素增长量将远远大于长路径，
从而导致了
了所有的蚂蚁都能很快的选择出短路径
决组
合优化问题
[
21
< br>]
[
18
]
。对真实蚂蚁觅食行为的描述可以被模拟用来解
：客观价值相应食物源的质量，仿真
蚂蚁搜寻实质问题的解决方法模拟
真实蚂蚁搜寻它们的环境，
适应的记忆相应信息素的踪迹。
另外，
仿真蚂蚁和和局部启发功
能相结合从而指导对适宜解进行一遍仔细的搜寻。
ACO
方法已经被成功
的应用于解决组合优化问题。
这些例子都包括：
旅行商问题
[
18
,
23
]
，
连续排序问题
[
24
]
，二次分配问题
[
25
,
26
]
，车量路径问题
[
27<
/p>
,
28
]
，行程
安排问题
[
29
,
30
]
，图表着
色问题
[
31
]
，分割问题
[
32
,
33
]
，动力系统最优化问题
[
34
]
，还有无线通讯网络问题
[
35
,
36
]
。一种
非常有效的以
ACO
为基础的启发式
ACS
将在下一节被论述。<
/p>
3.
蚁群系统
ACS
进来被用来在对称和非对称旅
行商问题上同其他启发式算法相比较，
这在表
1
中
被体现
[
18
]
。三条程序被反复提到直到一些结束条件被验证。首先，一组仿真蚂蚁被放
置在
起始节点依照某些初始化规则，
每个蚂蚁利用重复的使用随
即贪吃规则建立一条路径；
其次，
当构建自己的路径时，
每个蚂蚁也会通过使用局部更新规则更新信息素的数量在所经过的路
上
。最后，一旦所有的蚂蚁停止它们的旅程，信息素行迹被再一次利用球型更新规则改变。
在接下来我们将详细的讲述这些相关规则。
初始化信息素行迹；设置参数
循环<
/p>
/*
在这一级别每个循环被称为一个反复
*/
一群蚂蚁最初被安置在出发节点
循环
/*
在这一级别每个循环被称为一步<
/p>
*/
每个蚂
蚁再三的应用转移法则来挑选下一个节点，知道一条路径被创建
应用局部更新法则去减少所经过路径的信息素
直到
所有的蚂蚁建造起一个完全的路径
应用球型更新法则，来增加当前最通用路径的信息素，并减少
其他路径的信息素
直到
标准被验证，停止
表
1
、蚁群系统算法
3.1.
蚁群系统状态转移规则
当在
ACS
之中建立一个旅程时，蚂蚁
k
在当前节点
i
选择转移到下一个节点
j
利用状<
/p>
[
18
]
态转移
规则，由下边的方程式给出
：
j
?
{
arg
max{[
?
(
i
,
u
)
][
?
(
i
,
u
)]
?
}<
/p>
?
if
?
?
q
??
q
0
,
u
?
S
k
(
i
)
J
?
?
?
?
?
?
?
?
?
?
?
?<
/p>
?
?
?
othe
rwise
,
?
?
?
?
(
1
)
在此
?
(
i
,
u
)
是信息素的移
动踪迹
(
i
,
u
)
，启发式希求
?
< br>(
i
,
u
)
?
1
/
?
(
i
,
u
)
是节点
i
到
u
(
?
(
i
,
u
))
长度
的倒数，
S
k
(
i
)
是蚂蚁
k
在节点
i
出发所有
经过的节点的集合（去寻找可行解）
。另外，
?
是
一个参数用来测定信息素和距离相比的重要性
（
?
?
0
）
。
q
是均匀分布在
?<
/p>
0
,
1
?
之间的随机数，
。另外，
J
< br>是个随机变量，用来给出
q
0
是
测定开发和探测那个相对重要的参量（
0
?
q
0
?
1
）
蚂蚁
k
在节点
i
选择移动到节点
j
的概率，这都要
依照可能的分配所选择，这种可能性的分
配就叫做随机均衡法则，这在下面的方程式中给
出：
p
k
(
i
,
j
)
?
{
?
[
?
(
i
,
j
)][
?
(
i
,
j
< br>)]
?
?
[
?
(
i
,
j
)][
?
(
i
,
j
)]
0
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
otherwise
.
u
?
S
k
(
i
)
?
?
?
if
?
j
?
S
k
(
i
),
< br>?
?
?
?
(
2
)
当建立了它们的路线，就会在启发式信息和信息素信息的双重指引下寻找边缘路径。
方程式（
1
）和（
2
）证实了节点选择事与跟带有大量信息素的最短边缘路径相连接的，状态
转移规则就是由此产生的。每当一个蚂蚁在节点
i
不
得不选择下一个节点
j
作为目的地的时
候，就将抽取一个随机数字
q
，如果
q
?
q
0
，则最
好的边缘路径就会产生（依照方程（
1
）
）
（开发）
，否则，则依照方程式（
2
）产生一条边缘路径（探测）
。
3.2.
蚁群系统局部更新规则
当创建一条路线的时候，蚂蚁改变通过局部更新规则改变它所
经边缘路径的信息素水
[
18
]
平，如下
：
?
(
i
,
j
)
:
?
(
1
?
?
< br>)
?
(
i
,
j
)
?
?
?
0
，
局部
跟新规则的作用就是产生边缘路径的改变动力用来搅乱路线。如果蚁群蚂蚁探测
这里
?
0
是最初的信心素水平，
0
?
?
?
1
是信息素蒸发参量。
到了不同的路线，
则有很高的几率会
是它们其中的一个会发现一个和它们以前在一起在一个
狭窄的空间所发现的最好的路线相
比改善的解决方法。
每当一只蚂蚁建立了一条路线，
局部
更新规则就会减少它所经路径上的信息素，
是信息素的吸引力减少。<
/p>
因此，
在一只蚂蚁所经
路线上的节点被选
择的概率要比在其他蚂蚁所经路线的选择节点要低。
因而，
蚂蚁
比较青睐
探测没有经过的边缘路径并避免汇聚在一条共同的路径。
3.3.
蚁群系统球形更新规则
球形规则是在所有的蚂蚁都已经走
完它们自己的路线。为了定位这次搜寻，球形规则
有意的去供
应短路径上的信息素的总量，
并不断加固。
因此，
只有球形地最好的蚂蚁会发现
被允许存放信息素的运算法则当前反复应用的最
好的解决方案（也就是最短路径）
。信息素
水平将会通过下边的
公式被改变
[
18
]
< br>
其中
?
(
i
,
j
)
:
?
(<
/p>
1
?
?
)
?
(
i
,
j
)
?
?
?
?
(
i
,
j
)
，
?
?
(
i
,
j
)
?
{
(
L
gb
)
?
1
?
?
?
if
(
i
,
j
)
?
global
best
tour
,
0
?
?
?
?
?
?
otherwise
.
在上面的公式中，
?
（
0<
?
<1
）是信息素参量，
L
gb
是当前反复应用的球形地最好<
/p>
的路线的长度。
4.
< br>应有蚁群算法执行
n/m/P/C
m
ax
问题
在介绍了蚁群系统启发式算法之后，现在让我们来详细的描述一下蚁群算法在
n/m
/P/C
m
ax
问题中的运用，其中主
要问题就是把问题转换成可以用
ACS
解决的问题。
4.1.
用蚁群算法描述
n/m/P/C
m
ax
问题
n/m/P/C
m
ax
问题用
ACS
通过一个分离性图表来描述。给出一个
n/m/P/C
m<
/p>
ax
问题的实
例，我们可以把它和一个分
离性图表
G =(O,C,D)
相关联，其中
< br>O
是一组节点，
C
是一组相
连接的定向的弧，
D
是一组不定向弧。
O
代表所有的处理操作
O
< br>ij
，遵照
n
个工件行事，
C
相应于单一处理操作中优先关联，
D
描绘不同工件在机器上的约束操作。
另外，
还有一个蚁
巢
N
和一个食物源
F
两个虚拟的节点。由
N
点散发出定向箭头指向那个工件的首操作，最
后所有工作的最后操作汇聚于
F
点。所以我们现在有（
nm+2
）个节点，同一个机器上的所
有的节点，都是从两个方向同时成双成对的连接。
表
2
给出了一个
3/4/P/C
m
ax
问题实例。简单起见，所有的成对的节点箭头都省略，这
些连接机组
m
的弧
D
可以决定操作在机器上的处理次序。然后在
n/m/P/C
m
ax
问题中，所有
的工件
在每个机器上都有了一样的排列顺序，
这就足够找到第一批次序。
这时，
建立一个可
行解，则一只蚂蚁将选择到达的下一个节点
就会依照表
1
给出的状态转移规则被计算出来。
然后把被选出的节点添加到禁忌列表，再重复上边工作知道第一批的最后一个工件被处理
完。很明显，这里的禁忌列表不同于禁忌搜索。在禁忌搜索中，我们通常记录排列，但是在
禁忌列表中我们通常是用
ACS
记录节点。最后，禁忌列表给出的节点排列可以决定工件加
工顺序。现在我们可以通过有向图计算出最长路径的长度。像
ACS
算法中说明的那样，信
息素痕迹可以被计算出来并被放弃。
然而，
为得到一个更好的解决方案，
在所有的蚂蚁完成
它们的解决方案以后，
每次重复操作以后，
相邻近的的成对的操作相互交换的方法将被应用。
O
11
O
12
O
13
O
14
N
O
21
O
22
O
23
O
24
F
O
31
O
32
O
33
O
34
表
2. 3/4/P/C
m
ax
问题实例，其中各机器的弧都用不同弧线给出
4.2.
两个工件之间的长度
我们现在详细说明有向图中两点之间的长度。我们这里所用的
长度概念来源于
Palmer
方法
[8
]
，一种快速获得接近
n/m/P/C
m
ax
问题最优解的方法。改方法测量了每个工件的倾斜
指数
i
(
i
?
1
,
2
,
?
,
n
< br>)
通过下边公式
m
?
1
m
?
3
m
?
3
m
?
1
S
i
?
p
i<
/p>
,
m
?
p
i
,
m
?
1
?
?
?
p
i
,
2
?
p
i
,
1
.
2
2<
/p>
2
2
其次序是在
S
数量级的降序排列的基础上构建的，
Palmer
方法的思想是认为在处理次序中
工件有短时间到长时间的拥有强烈的处理倾
向的工件优先。
按照
Palmer
方法，
我们修正倾斜指数，
并详细说明在首批任务中节点
i
(
i
?
1
,
2
,
?
,
n
?
N
)
和节
点
u
(
u
?<
/p>
1
,
2
,
?
,
n
)
之间的长度，通过下边公式
其中
?<
/p>
(
i
,
u
)
?
1
/
?
(
i
,
u
),
?
(
i
,
u
)
?
(
m
?
1
)
p
u
,
< br>m
?
(
m
?
3
)
p
u
,
m
?
1
?
?
?<
/p>
(
m
?
3
)
p
u
,
2
?
(
m
?
3
)
p
u
,
m
?
1
?
(
m
?<
/p>
1
)
p
u
,
1
?
min
{
?
(
i
,
u
)}
?
1
(
i
?
u
).
u
应用这个函数，两点之间的节点可以通过
ACS
状态转移规则基本原理得到。实际上，我们
< br>可以直接计算通过启发式希求算法并使
ACS
只在最优解
临近搜索。
就像在通过
ACS
去搜寻<
/p>
最优解的同时，我们通过定向约束任意搜索来改进
Palmer<
/p>
方法。
5.
计算结果
研究员在时序安排上面临的一个难点就是拿他们所开发出来的
启发式算法同其他研究
员相比较，
如果测试问题的标准是可达到
的，
不同的的运算法则就会被测试问题同样严密的
比较运行。因
此我们选择
120Taillard
基准测试问题
[
19
]
作为这次研究的测
试问题。
Taillard
给出了一组未解决的
n/m/P/C
m
ax
问题包括
5
，<
/p>
10
，
20
个机
器和从
20
到
500
< br>个工作。
任意举例如下
[
19<
/p>
]
：对于在任一机器
j
< br>(
j
?
1
,
2
,
?
,
m
)
上的任一工件
i
(
i
?
1
,
2
,
?<
/p>
,
n
)
，一个整
数的
处理时间
p
ij
< br>将会由统一分配得到
[1,99]
。为使问题尽量的困难
, Taillard
将会产生许多问题实
例
,
然后为每个类型的问题选择
1
0
个看上去最难的实例
,
形成一个基本
问题组。因次，每个问
题组都会有
10
个实例，总共有
120
个实例。随后，他给每个实例配备以下信
息：任意原因产
生器的的原始资料，
最优处理的上界和下界。<
/p>
测试题目可以在
Taillard
全球网
点查找
(
网址是：
/
< br>?
eric/
)
，或者是在
OR-Library
网络站点上下载（网址是：
< br>/jeb/orlib/&
）
。
在初步试验阶段，
将测试五个蚂蚁
组（
5
，
10
，
2
0
，
50
，
1
00
）
，其中
20
将优先处理，这要应用于以后所有的研究。该篇论文的
所有试验中，所有的数字参量
都将会依据
Dorigo
[
18
]
以前的研究来设置：
?
?
0
.
1
,
?
?
2<
/p>
,
?
?
0
.
1
,
q
0
?
0
.
9
,
?
0
?
(
nUB
)
?
1
其中
UB
是最优处理的上界。当其中任一操作重复
超过
5000
或者获得了下界，则算法停止。
算法是使用
Visual
C++
编码的，并在
AMD 700 MHz
的
PC
上运行。算法实现的伪代码描
< br>述将会在附录中给出，
为了评价算法，
将会对每个实例问
题进行五次实验。
选择出最好的实
验，
然后对同一个问题组中的
10
个实例求平均值，
最后的结果在表
1
中给出，
表
1
给出了蚁群
-
-
-
-
-
-
-
-
-
上一篇：淡忘的英文网名英文网名女生带翻译
下一篇：难忘作文之难忘的经历英语作文带翻译