智能混合优化策略及其在流水作业调度中的应用
第 38卷 第 8期
2004年 8月
西 安 交 通 大 学 学 报
J OURNAL OF XI AN J IAOTONG UNIVERSITY
Vo1．38 № 8
Aug． 2004
智 能混合优化 策略及 其在 流水 作业调 度 中的应用
冯远静 ，冯祖仁 ，彭勤科
(西 安交通 大 学 系统 工程 研究 所 ，710049，西 安 )
摘要：通过结合蚁群算法(ACO)的并行搜索结构和模拟退火算法(SA)的概率突跳性 ，提 出了一种有效的混
合优化策略，并将该策略应用于流水作业调度问题 (FSP)．在该策略 中，蚁群 系统的一个周游路线为模拟退
火算法提供 了一系列初始解，在每个退火温度上进行抽样准则检验并产生新解，然后更新信息激素；蚁群算
法再利用模拟退火算法产生的新解进行并行搜 索．同时，根据此策略构建并 实现 了针对 FSP问题求解的具
体混合算法．仿真结果表明，混合算法弥补了 ACO易陷入局部最优和 SA搜索效率较低的缺点，增强了全局
搜 索能力，在求解 FSP调度问题的性能上也优于其他算法．
关键词：蚁群算法；模拟退火算法；混合优化算法；流水作业调度
中图分类号 ：TP278 文献标识码：A 文章编号：0253—987X(2004)08—0779—04
Intelligent Hybrid Optimization Strategy and Its Application to
Flow-Shop Scheduling
Feng Yuanjing，Feng Zuren，Peng Qinke
(Systems Engineering Institute，Xi an Jiaotong University，Xi an 710049，China)
Abstract：By combining the parallel searching structure of ant colony optim ization (ACO)with the proba—
bilistic j umping property of simulated annealing(SA)，an effective hybrid optimization strategy was devel—
oped，and applied to flow-shop scheduling problems (FSP)． In the hybrid strategy，a cycle course of the
ant system can provide effective initial solutions for SA ，and SA generates new solutions based on the me—
tropolis criterion at each temperature，then the ant system updates pheromone trails and proceeds with par—
allel searching through reusing the new solutions from SA．M eanwhile，the hybrid algorithm for flow—shop
scheduling problems was created and realized on the basis of the hybrid strategy． W ith some benchmark
FSP problem s，the simulation results show that the method compensates the deficiency of ACO that is easy
to be run into local optimum and SA that has lower efficiency，and strengthen the global search ability．
Comparing with other algorithms for solving FSP，the proposed method has better performance．
Keywords：ant colony optimization；simulated annealing；hybrid optimization algorithm ；flow-shop
scheduling
流水作业调 度问题 (FSP)是许多 实际流 水线生
产 调度 问题 的简化模型 ，是一种典 型 的 NP难题_1j．
FSP问题 的有 效 求解 方 法 通 常 可 以分 为 构 造 型 和
改进 型方法．在过去 的几 年 ，人们 对利用改进 型方法
求解 FSP问题进 行 了大量 的研究 ，比如 模拟 退火算
法 (SA)[ 、禁 忌 搜 索[ 、遗 传 算 法l4j和 蚁 群 算 法
(ACO)[5-93
．
在随机搜索算 法 中，ACO是 一种有效 的
求解方法 ，但对 于大 规模 的 FSP调度 问题 ，它不 可
避免地陷人 了局 部最 优[6,7,10]．相 对 于 ACO，SA 的
概率 突跳性 可 以逃 避局部 最优[9j，但 由于 串行 搜索
结构使其搜 索效率较 低．本文 通过 合理 地 结合 这两
种搜索算法 的特性 ，提 出了一种有效 的混合优化策
收稿 日期 ：2003—10—29． 作者简介 ：冯远静(1977~)，男，博士生；冯祖仁 (联系人)，男 ，教授 ，博士生导师． 基金项 目：
国家 自然 科学 基 金 资助项 目(60175015)；国 家“211工 程 ”资助 项 目．
维普资讯 http://www.cqvip.com
西 安 交 通 大 学 学 报 第 38卷
略 ，并通过 基 于典 型 FSP问题 的仿 真 ，证 明 了所 提
算法 的有效性．
智能混合优化算法
1．1 混合优化算法的基本思想
ACO是模拟蚁 群从 蚁 巢 到 目的地 寻 找最 短 路
径 的并行搜 索 算法 ．SA 是 模 拟 物理 退 火 过 程 的 一
种算 法 ，通 过 赋予 搜索 过程 一 种时 变且 最终 趋 于 0
的概率突跳性 ，从而有效避 免 了局部极小．如果 两者
相结 合 ，其性 能 的互补性 主要 体现在 以下几 个方面．
(1)结合 性 的搜 索 机制．ACO 和 SA 均 是基 于
概率 机制 的随机 优化 算法 ，其 中 ：ACO是 基 于群 体
搜索 的算法 ，收敛 速度很 快 ，但 由于信息激 素更新能
力有 限 ，所 以经 常会 出现“早熟 ”现象 ；SA 通 过抽 样
稳 定准则产生新 解 ，并 由退 火温度控制搜 索过程 ，从
而有效避免 了局部 最优[1 ．两者在 机制 上 的结合 有
利 于丰富优化 中的搜 索行 为 ，同时 可增强 全局 和 局
部 意义下 的搜索 能力和效率．
(2)互 补 性 的 优 化 结 构．SA 采 用 串 行 优 化 结
构 ，ACO采用并 行 搜 索 ，两 者 结合 可 使 SA 成 为并
行 SA，从而提 高优化性 能．同时 ，SA 的概率 突跳性
可增 强蚁群的信息激素 更新能力．
(3)结合性 的历史信 息搜 索 操作．SA在 状 态产
生和接受 算子时仅 留一 个解 ，缺乏冗 余 和历 史信 息
搜索[1 ，蚁群 的信 息激 素保 留 了历史 信 息搜 索．两
者结合 有利于丰富优 化 过程 中 的邻域 搜 索结 构 ，增
强全空 间的搜 索能力．
(4)削弱参数选择 的苛 刻性 ．SA 的优 化行 为 对
退温历程 有很 强的依 赖性 ，而理 论上 的全 局 收敛 对
退温策 略的限制 条件很苛刻．ACO的搜索过 程不需
要 进 行 人 工 的调 整 ，具 有很 好 的鲁 棒 性．同时 ，SA
还 可 以平衡蚁群搜 索过程 中知识利 用与探索之 间的
关系．
1．2 算法描述
基 于上述 的 基本 思 想 ，本 文在 ACO 的 框 架基
础上引入 了 SA，提 出 了一种 有 效 的混 合 优 化 算法
(ACSA)，该算法 的流程 如图 1所示．
从 图中可 以看 到 ，ACO 为 SA提 供 了一 系列 的
初 始解 ，SA 的邻 域 搜 索 能 力 进 一 步 改 善 解 ，然 后
ACO利用 SA产 生 的 新解 再 进 行并 行 搜索 ．所 以，
ACSA 结合 了两者 的特 点 ，使各 自的搜索 能力 得 到
补充 ，弱点得 以弥补．
初始化蚁群系统，给定算法
参数，确定初温
蚁群构 造解
评价 当前蚁群 中的个体
No t
概率 地接受新个 体
： ! ／ N
。
s t
退温 操作
图 1 混合优化算法流程图
2 基于混合优化算法 的 FSP求解
2．1 解 的构 造
假设一个置换 FSP调度 问题 研 究 ／Tt台机器上
72个工件 的流水加工过程 t为工件 i在 机器 上 的
加工 时间 ， 为 机器 k上 完成 加工 工 件 i到要 加 工
下一个 工件 J时所 需 的准备 时 间 ， 为工件 i的加
工时 间 ，D 为工件 i的计 划完成 时 间．不 失一般性 ，
另设各 工件按 1～ 个 机器 的顺序进 行加工 ，令 7r一
( ， ，? ， )为所 有工 件 的一个 排 序 ，则 调度 的 目
标是寻找一个 排序 ，使 工件 的完成 时间最短．
在 ACSA 中 ，蚂蚁 的信息激 素采 用与 解 的属性
有关 的数值 r 来表示 ，即工件 i在 加工 序列 中的第
J个位 置的期 望 程 度．每个 人 工蚁 从 一 个 虚 构 的起
始结点 (初 始作业 )出发 ，然后依次 选择后续的作业 ，
一 步一步地构 造出一 条完 全路 径 (解 序 列)．在 构造
路径 的每一 步 ，蚂蚁 k从结 点 i移动 到相 邻结 点 S，
结点 S表示将被插入处 理序列 ／l" 一( 1，0"2，? ， ，)的
下一个作业 ，S的选 择按 照 伪 随 机 比例 状 态 迁 移规
则进 行[ ]，即
farg max([ (￡)] [ (￡)] )， q≤ qo
s一 ∈ (1)
【S ， q> qo
蚁群以概率 qO∈[O，1]选择结点arg max([r~(￡)] ·
lE
[ (￡) )，以概率 1～qO并按概率
维普资讯 http://www.cqvip.com
第 8期 冯 远静 ，等 ：智能 混合优 化 策略及 其在 流水 作业 调度 中的 应用
j r-r~ ( 一 (￡)==l， ￡)]。[ (￡)]p’ (一 (2)
【0，J
选择 S ．在搜 索 时 ，参 数 q。决 定 了蚁 群 的知 识 利用
与探索 两者的权重．一 味 的知识 利 用将 使搜 索很 快
地陷人局部最 优 ，而过 多的探索将影 响算法 的性能．
式 (2)中的 (￡)是 与 目标 函数 有关 的启 发式 信息 ，
口、 分别 是 控 制 信 息 激 素 和 启 发 式 信 息 值 在 概 率
p (￡)中的权重 参数．
2．2 初始温 度及温度更新 函数
个人工蚁完 成第 一次 周 游后 ，确 定周 游 最优
路径 (一次周游路径 中 目标 函数值 最小的路径 )及其
完成 时间 c ，和周 游最差路径 (一次周 游路 径 中 目
标 函数值 最 大 的路 径 )及其 完 成 时 间 c一 ．确 定 初
始温度 to一一(cw。 一cbes )／ln(po)，其 中的 P。E Eo，
1]为初始接 受概率．退温 函数采用指数退温策 略
t^=At^ ， E(0，1)为退 温 速率 ．这 种 退 温 策 略被
认 为是一种有效 的策 略[1 ，可较 好 地折 衷 、兼顾 优
化质 量和时间性能．
2．3 状态产 生函数 和状态接受 函数
在 流水作 业 调度 问题 中，状 态 的产生 可 以通 过
一 个置换来 实现 ，而置 换 的邻域 可 以表示 为 一系列
作业 的移动操作 ．本文将 互换操 作[1。]作 为算 法 的状
态产生 函数．
为 了使搜 索 过 程 能克 服 局 部 极 小 ，并 满 足 SA
算 法的对称条件 ，在 结合 互换 操作 状 态产 生 函数 的
基 础上 ，用 Metropolis抽样稳 定准 则作 为接 受 新状
态 的条件．
人 工蚁完成 一 次周 游 以后 ，为 SA 的邻 域搜 索
提供 了初始解．邻 域搜索算法描述 如下．
St印 1：在温度 ，选择人工蚁 k的周游路径 ．
Step 2：通过互换 操作 随 机产 生一 个新 的邻 域
解 ，并计算 、 的 目标 函数 值 C( )和 c( )．
Step 3：如果 min{1，expC一(c( )一C( ))／
]}~random[-O，11， 一 ；否则，转 Step 2．
Step 4：如果所有 的邻 域 解都 不能 改 善 当前解
， 或者搜索 的次数达到某 一 设定 值 ，则停 止搜 索 ；
否则 ，转 Step 2．
2．4 信息激 素的更新
在 算法 的每 一次 迭代 中 ，当整 个蚁 群 中的所有
人工蚁完成邻 域搜 索并 构造 其 问题 时 ，每个 人 工蚁
k将在经 过 的路 径 连 接 上 积 累一 定 量 的信 息 激 素
△ 一1／c~(N)，其中的c5(N)是蚂蚁 k在第 N 次
迭代时经过路径 ∥(N)完成的时间．信息激素依据
(N)一lD r (N一1)+avON (3)
更新．其 中，pE(0，1)表 示信息激 素的保 留系数 ，1一
』D表示 信息激 素的蒸 发率．
2．5 循 环终止准则
ACSA利用 两种循 环终止 准则 ，其 中 ：抽样稳 定
准则可判定 一 个 温度 下 的算法 搜 索 行 为 ，也 是 SA
切换 到 ACO 的条件．算 法终 止 原则 可 判定 优 化性
能变 化趋 势和最终优化性 能．
3 仿真结果及分析
为 了验证 ACSA 的有 效性 ，选 择 了不 同 规模 、
典型 的置换 FSP问题进 行测试．典 型的置换 FSP问
题采用 Car、Rec和 TA标 准测试 集 的部 分数据 _5]，
其 中的 Carl、Car3、Car5和 Car7作 为 简单 调度 问
题 ，其余 的作 为调 度 难 题进 行 求 解．设 置 参数 一
10，Po一0．1， 一0．9，』D一0．9，qo一0．9，并且 每个
实 例均 随机运 行 20次．用 C语 言实现上 述算法 ，运
行 环境 为 Pentium IV 2．4 GHz／256 MB RAM．
首先 ，将 ACSA 分 别 与 ACO 和 SA 的优 化性
能进行 比较 ，仿真计算结 果见表 1．从表 1可 以看
表 1 ACSA、ACO和 SA 的优 化性能 比较
标 准测 试集 ，m C— ACSA SA
e}％ t／s C e}％ t／s
AC0
Car1
Car3
Car5
Car7
Rec01
Rec07
Recl3
Recl9
Rec25
Rec31
Rec37
11，5
12．5
l0，6
7．7
20，5
20．10
20，15
30．10
30，15
50．10
75，20
0 0．35 7 038 0 0．13
0 1．25 7 312 0 0．33
0 1．15 7 720 0 0．28
0 1．12 6 590 0 0．23
1．567 5．56 1 259 6．323 2．34
1．533 7．23 1 578 9．453 3．24
1_045 8．86 1 939 4．245 4．56
2．563 14．36 2 122 3．245 8．78
3．632 21．25 2 625 7．532 14．67
1．067 59．25 3 286 5．482 18．45
6．345 145．34 5 122 8．432 56．10
1．345
2．123
0
0
2．462
4．253
5．678
2．732
5．756
6．734
11．563
0．11
0．12
0．10
0．09
0．71
1．18
1．34
2．67
3．56
4．67
12．41
注 ：n、m 表示 问题 的规模 ；c 为问题 的最 优解 ；c 为本 算法 的最优 解 ；e表 示 2O次 运行 结果 与 c一 的相 对误 差 It表 示平 均 CPU时 间．
8 2 0 0 8 6 6 9 5 1 2 ∞ 他 的 盯 船
7 7 7 6 1 1 1 2 2 3 5
8 2 0 0 7 6 0 6 5 6 4 ∞ 他 的 弘 ％
7 7 7 6 1 1 1 2 2 3 5
8 2 0 0 7 6 0 3 3 5 1 ∞ 他 弘 ％ ∞ 叭
7 7 7 6 1 1 1 2 2 3 4
维普资讯 http://www.cqvip.com
西 安 交 通 大 学 学 报 第 38卷
出 ，对于简单 实 例 ，3种 算法 都 能很 好 地 求 解 问题 ，
对于调度难 题 ，ACSA 的优 化性 能更 好．从 算 法 得
到 的问题最 优值可 以看 出，ACSA 的全局搜 索 能力
得 到 了较 大的改进 ，从 2O次运行结 果得到 的平均 相
对误差值 显 示 出 了 ACSA 的鲁 棒 性．但 是 ，ACSA
的时间性能不如 ACo和 SA的．由于 ACo本身内
在 的并行性质 ，可使得 利用 ACSA 并行 实现来 提 高
算法的速度和运行效率成为可能 ，这将是我们下一
步 的研究工作．
另外 ，我们也将 ACSA 在求 解 TA 标准 测试 问
题 ]时 的优 化性 能 与其他 几种 算法 进行 了 比较 ，结
果见表 2，其中的数据全都来源于文献[4-1．比较结
果表 明 ，ACSA 的优 化性 能更 好或 者至 少与其 他算
法相 当．
表 2 ACSA和其他算法的优化性能比较
注 ：NEH 为启 发式 算 法 ；NEH+IS为 NEH 加邻域 搜索 ；MMAS为 max-rain蚁群 算法 ；MD 为多重 下降 法 ；SAOP为改进 的 SA．
4 结 论
ACSA是 建立在蚁群 算法结构 基础上的一种 并
行搜索 算法．利用模 拟退 火 算法 的 Metropolis准 则
折衷处 理蚁群搜索 的知识 利用 与探 索 之 间 的平 衡 ，
能增 强算法在解空 间 中的探索 能力和效率．
ACSA 具有较好 的全 局优 化 度 ，其 初 值鲁 棒 性
高 ，优化结 果可靠．
对 于 复杂 优 化 问题 ，如 FSP 的 NP难题 ，单 一
机制的优化算法很难实现全局优化且效率低．结合
多种优化机制和邻域搜索结构 的 ACSA是提高全
局优化 能力和鲁棒 性 的有效 方 法 ，并 可 以在 一定 程
度上放 宽单一算法 在参数选择上 的苛刻性要求．
参考文 献 ：
[1] Garey E L，Johnson D S，Sethi R The complexity of
flow-shop and job-shop scheduling[J]．Mathematics
of Operations Research，1976，1(1)：117—129．
[2] Osman I，Potts C Simulated annealing for permuta—
tion flow-shop scheduling[J]．Omega，1989，17(6)：
551-557．
[33 Liaw C F An efficient tabu search approach for the
two-machine preemptive open shop sched uling problem
[J]．Computers& Operations Research，2003，30
(14)：2 081—2 095．
[4] Taillard K Some efficient heuristic methods for flow-
shop sequencing[J]．European Journal of Operational
Research，l990，47(1)：65～74．
[5] 王 凌著．车 间调度及其遗传算法 [M]．北京：清华
大 学 出版社 ，2003．
[6] Stutzle T．An ant approach tO the flow shop problem
[A]．European Congress On Intelligent Techniques and
So ft co mputing，Aachen，Germany，1998．
[7] Dorigo M，Cam G D．Ant colony optimization：a new
meta-heuristic[A]．Int co nf on Evolutionary Compu～
tation．Piscataway。USA，1999．
[8] 王 凌，郑大钟．一种 GASA混合优化策略 [J]．控制
理 论与 应用 ，2001，18(4)：552—554．
[9] Dorigo M，Gambardella L M Ant colony system：a
cooperative lea rn ing approach tO the traveling salesman
problem [J]． IEEE Transactions on Evolutionary
Computation，1997，1(1)：53—66．
[1O]Dorigo M，Ma njezzo V，Colorni八 Ant system：opti—
mization by a colony of cooperating agents[J]．IEEE
Tran saction on Systems． Ma n Cybernetics：B，
1996，26(1)：29—41．
[11]Stutzle T，Hoos H H．The max-min ant system and
local search for the traveling salesman problem [A]．
IEEE 4th International Conference on Evolutionary
Computation，Piscataway，USA ，1997．
fi12]Stutzle T，Hoos H H．Ma x-min ant system LJ]．Fu—
ture Ge neration co mputer Systems，2000，16(8)：889—
914．
[13]Hajek 13．Cooling schedules for optimal annealing [J]．
M athematics of Operations Resea rch， 1988， 13(2)：
311—329． (编辑 苗 凌)
维普资讯 http://www.cqvip.com
智能混合优化策略及其在流水作业调度中的应用.pdf
