第1页 / 共14页
第2页 / 共14页
第3页 / 共14页
第4页 / 共14页
第5页 / 共14页
第6页 / 共14页
第7页 / 共14页
第8页 / 共14页
论文研究-求解随机阻塞批量流水线调度问题的改进人工蜂群算法 .pdf
中国科技论文在线
http://www.paper.edu.cn
求解随机阻塞批量流水线调度问题的改进
人工蜂群算法
韩玉艳，巩敦卫，张 勇
(中国矿业大学信息与电气工程学院，江苏徐州 221116)
摘要：针对含有随机加工时间的阻塞批量流水线调度问题，利用蒙特卡洛采样方法,将不确
定加工时间的阻塞批量流水线调度问题转化为确定阻塞批量调度问题。采用改进的人工蜂群
算法,对上述转化后的调度问题进行求解。算法中加入了和声搜索和基于插入操作的局部搜
索算子,以改进全局探索和局部开发能力。将改进的算法应用到阻塞批量调度的 24 个算例中，
仿真实验结果表明，改进的人工蜂群算法能够降低调度中的不确定因素带来的影响，产生高
质量的解。
关键字：阻塞批量调度；随机加工时间；蒙特卡洛；人工蜂群；和声搜索算子
中图分类号：TP182 文献标志码：A
An improved artificial bee colony algorithm for stochastic
blocking lot-streaming flow shop scheduling problem
(School of Information and Electrical Engineering, China University of Mining and Technology,
Han Yuyan, Gong Dunwei, Zhang Yong
Xuzhou Jiangsu 221116, China)
Abstract: For the blocking lot-streaming flow shop scheduling problem with stochastic processing
time, a method is proposed to transform it into a determinate one using Monte Carlo sampling method.
An improved artificial bee colony algorithm is developed, in which a harmony search and local search
based on insertion operators are adopted to balance the algorithm’s capability in exploration and
exploitation. The proposed algorithm is applied to 24 instances of blocking lot-streaming flow shop
scheduling problem. The experimental results show that the improved algorithm can generate solutions
with high quality and reduce the influence resulting from uncertainties.
Key works: blocking lot-streaming flow shop scheduling; stochastic processing time; Monte Carlo;
artificial bee colony; harmony search operator
在批量调度中，一个完整的工件被分割成若干小批量，每个小批量在机器上加工完毕之
后，可允许其进入下游机器上加工。批量调度具有加速生产流程、缩短生产交货期、减少制
品库存和相关成本等优点，因此被成功应用于生产制造系统、装配生产线、信息服务设施、
以及化学制造业、纺织业、塑料制造业以及半导体工业等，具有广泛的工程应用背景和重要
的理论研究价值[1-2]。根据机器之间缓冲区的个数，批量流水线调度问题可分为无限缓冲区
批量流水线调度和有限缓冲区批量流水线调度。前者不会引起工件阻塞，后者则可能会引起
工件阻塞。有限缓冲区批量流水线调度中，若机器之间无中间缓冲区，则会使加工完毕的工
件 阻 塞 在 当 前 机 器 上 。 该 类 批 量 流 水 线 调 度 问 题 被 称 为 阻 塞 批 量 流 水 线 (Blocking
Lot-streaming Flow Shop，BLSFS)调度问题。除了上述约束外，在实际的生产大环境中，还
存在各种各样的不确定因素[3-4]，例如每一道生产工序中产品的处理时间、传输时间的不确
定，以及机器故障等，这些不确定因素往往会导致生产调度方案不能按照预定的目标正常执
行。因此，在模拟过程中需要考虑这些不确定因素。
目前，求解不确定加工时间调度问题常用的方法是随机调度优化方法，该方法比较简单，
基金项目：中国博士后科学基金资助项目(2014T70557，2012M521142); 江苏省博士后科研资助计划项目
（1301009B）；江苏省普通高校研究生科研创新计划(CXZZ13_0932)
作者简介：韩玉艳（1985-），女，博士研究生，主要研究方向为优化调度理论与智能优化方法
通信联系人：巩敦卫，教授，主要研究方向为智能优化与控制，基于搜索的软件工程，dwgong@vip.163.com
-1-
中国科技论文在线
http://www.paper.edu.cn
易实现，因此得到了广泛的应用。随机调度首先根据描述调度问题参数的随机变量满足的分
布，将不确定参数转化为随机变量的特征量。在问题转化之前，应事先知道加工时间的分布
函数，如正态分布函数、指数分布函数和对数分布函数等，通过这些函数，将加工时间转化
为确定的值。
针对单机随机加工时间的流水线调度问题，文献[5]提出了单模式，双模式和混合模式
情况下的 3 个约束模型，其目的是为了找到一个-鲁棒解来减小随机性对目标函数的影响程
度。文献[6]考虑了带随机加工时间的 2 台机器流水线调度问题，将随机加工时间看作是独
立随机变量，给出了一个工件序列中相邻两工件交换位置时，期望的最大完工时间的随机性
变小的一个充分条件。文献[7]考虑了 8×8 的随机调度问题，通过 3 种已知的概率分布函数，
得到相应的加工时间，采用随机方法从搜索空间中得到 N 个较好的调度序列，然后采用进
化策略对该 N 个调度序列继续进化优化，最终选择一个最好的调度策略作为该问题的最优
解。此外，为了提高算法性能，文献[8]提出了一个基于分解的混合进化优化方法，利用最
短加工时间准则和遗传算法，最小化随机柔性流水线调度问题的最大完工时间，实验仿真证
明了所提方法优于单一的 GA 算法。
蒙特卡洛(Monte Carlo，MC)方法是一种随机模拟不确定的分析方法，其结构简单，易
于实现，能够真实地模拟实际的物理过程，因此得到了广泛的应用[9-10]。该方法的思想是，
利用计算机随机函数，产生随机数来求解某个随机变量的期望值，通过不断地模拟实验，将
随机变量的平均值作为问题的近似解，其过程主要由构造概率分布函数、抽样、建立各种估
计值 3 部分组成。文献[11]采用蒙特卡洛方法和迭代的局部搜索算法，求解带随机加工时间
的置换流水线调度问题。首先，采用蒙特卡洛方法获得一些加工时间采样值，然后，利用这
些值计算期望完工时间。实验表明，所提出的方法能够有效处理置换流水线调度问题的不确
定因素。文献[12]将每个工件在每台机器上的加工时间看作是以指数分布的随机变量，建立
了以期望最大完工时间为目标的离散数学模型，并采用基于蒙特卡洛的递归算法求解上述期
望函数，实验结果证明了该算法能够产生高质量的解。文献[13]采用分布估计算法(EDA)最
小化随机作业调度的平均期望完工时间，首先利用蒙特卡洛采样方法获得加工时间，然后建
立概率模型，学习采样产生新解。实验结果证明利用概率模型有价值的信息产生的新解，比
传统的交叉变异算法具有更好的收敛性和稳定性。
上述提到的文献的共同点是，首先，通过加工时间的概率分布函数，将不确定加工时间
转化为确定的加工时间，然后优化最大期望完工时间。但上述已有的文献仅仅考虑了最大完
工时间的期望值，未考虑加工时间的随机性对最大完工时间的影响，即未考虑随机流水线调
度问题的不确定性指标。实际生产中，对不确定流水线调度问题，除了应关心最大完工时间，
还应考虑不确定因素对目标函数的影响，力求找到一个稳定性和鲁棒性较好的最小完工时
间。鉴于此，本文基于蒙特卡洛方法，利用最大完工时间采样值的方差刻画其不确定度，并
将该方差与期望值作为两个目标函数，采用改进的人工蜂群算法优化上述两个目标。
人工蜂群算法(Artificial Bee Colony algorithm，ABC) [14]模拟了雇佣蜂、观察蜂和侦察蜂
的采蜜行为，在进化过程中，3 种蜂群通过各自的分工进行不同的活动，并不断地进行信息
的交流和共享，从而找到最优解。由于该算法参数少，易于操作，搜索速度快，因此已经成
功应用于数值优化和组合优化等问题[15-16]。文献[16]结合批量流水线调度问题的结构特性与
ABC 的优化机理，提出了离散的人工蜂群算法(Discrete Artificial Bee Colony algorithm,
DABC)，实验证明，该方法优于混合的微粒子群算法和混合的遗传算法。然而，该算法中，
雇佣蜂阶段和观察蜂阶段都采用插入和交换操作产生新解。由于两阶段采用相同的方法对当
-2-
中国科技论文在线
http://www.paper.edu.cn
前解进行重复的邻域搜索，降低了种群多样性，导致算法易陷入局部最优。
和声搜索算法(Harmony Search algorithm，HS)模拟了乐师们在音乐演奏中凭借记忆通过
反复调整乐队中各种乐器的音调，最终达到一个悦耳的和声状态的过程。文献[17]基于该现
象，提出了和声搜索算法，将各种乐器和声类比于解向量，评价类比于目标函数，和声库类
比于种群，乐曲的创作过程类比于种群的进化过程，通过随机选择音调，以及和声调节来产
生新解，再通过新解与和声库中的最差解比较，不断更新和声库。由于 HS 算法具有较强的
全局搜索能力，因此广泛应用于很多优化问题。文献[18]采用离散的和声搜索算法求解批量
流水线调度问题，仿真实验证明了算法的高效性。
鉴于和声搜索算子具有较好的全局探测能力，有助于算法跳出局部最优状态，因此本文
考虑将和声搜索算子代替雇佣蜂阶段的插入和交叉操作，提出了改进的人工蜂群算法，求解
不确定加工时间的阻塞批量流水线调度问题。
1 随机阻塞批量流水线调度问题
随机 BLSFS 调度问题具体描述为，有 n(
)个工件按照相同
的工艺路线在 m 台机器上加工。加工过程满足：(1) 相同机器上同一个工件的所有小批量加
工完毕后，下一个工件的小批量才被可以加工；(2) 一台机器只能加工一个小批量工件，一
个小批量工件只能在一台机器上加工；(3) 同一台机器的被可以加工地相邻两个批量工件之
间有等待时间；(4) 机器之间没有缓冲区；(5) 工件加工时间是不确定的；(6) 每一个工件的
所有小批量在不同机器上的加工时间是不同的，在同一机器上的加工时间相同；(7) 机器准
备时间和小批量工件运输时间包含在加工时间内。
j
( ),...,
(2),...,
{ (1),
n
( )}
一般来说，在随机 BLSFS 调度问题中，如果加工时间是随机的，相应的最大完工时间
也是随机的[7]。容易理解，针对随机目标函数，很难判断其优劣，因此，需要将随机函数转
化为确定的值来进行比较。本文假定每一个工件在每一机器上加工时间的概率分布已知，并
采 用 蒙 特 卡 洛 采 样 方 法 得 到 SP 个 加 工 时 间 采 样 值 ， 然 后 形 成 一 个 集 合 ( ),j
tP ，
P
值，能够得到 SP 个相应的最大完工时间。本文的目的是寻找一个(些)调度序列，最小化最
大完工时间的均值和方差，即：
。基于这些加工时间采样
， 1,2,...,
， 1, 2,...,
p
SP
j
( ),
,...,
,...,
p
s
p
2
p
1
m
j
( ),
j
( ),
j
( ),
j
( ),
{
}
n
t
j
,
t
t
t
t
t
min
f
1
SP
1
SP
1
s
min
f
2
C
n m w
( ),
(
,
(
n
)
p
s
n m
( ),
)
s
1,2,...,SP
，
SP
s
1
(
C
n m w
( ),
(
,
n m
( ),
(
p
s
SP 1
n
)
（1）
)
2
f
1
)
，
（2）
式中： 是所有工件序列集合； ( )n 是工件序列的最后一个工件； ( )nw 是工件 ( )n 的最后
一个小批量； 1f 是最大完工时间均值； 2f 是最大完工时间方差； ( ),
p 是工件 ( )n 在机器 m
s
n m
C
上第 s 个加工时间的采样值；
p 时，整个加工序列的
s
p
s
是加工时间取值为 ( ),
n m
( ),
j
(
)
t
n m w
( ),
(
,
n
)
完工时间。
C
n m w
( ),
(
,
(
p
s
求解过程如下：
n m
( ),
)
n
)
S
C
(1),1,1
(1),1,1
0
p
(
s
(1),1,
)
S
(1),1,1
p
s
(1),1
s
1,2,...,SP
，
（3）
-3-
中国科技论文在线
http://www.paper.edu.cn
(1), ,1
(1),
t
(1), ,1
(1),
t
)
)
t
C
S
p
(
s
(1), 1,1
p
(
s
(1), ,1
(1),
t
t
(1),
)
t
)
p
s
(1),
t
t
2,3,...
m
， （4）
j
( ),1,1
j
),1
j
( ),1,1
j
( ),1
C
) max{
j
1),1,
(
p
)
(
s
S
j
( ),1,1
j
( ),1
w
(
j
1)
)
p
(
p
s
j
( ),1
s
(
),
S
(
j
),1
j
1),2,
w
(
j
1)
(
p
s
j
( ),1
)}
j
2,3,...,
n
， （5）
j
( ), ,1
t
j
( ),
t
j
( ), ,1
t
j
( ),
t
C
) max{
(
j
( ), 1,1
p
)
(
)
s
S
j
( ), ,1
j
( ),
t
t
t
p
s
j
( ),
p
s
j
( ),
t
),
S
(
j
t
1), 1,
t
(
p
s
j
( ),
)}
t
w
(
j
1)
j
2,3,...,
n
， （6）
j m
( ),
,1
j m
( ),
j m
( ),
,1
j m
( ),
C
) max{
j m
( ),
p
)
(
s
S
j m
( ),
,1
1,1
j m
( ),
(
)
p
s
j m
( ),
p
s
j m
( ),
),
C
(
j
1),
m w
(
,
j
1)
(
p
s
j m
( ),
)}
j
t
n
2,3,...,
m
2,3,...,
，
(
(
p
s
p
s
(
(
p
s
(
p
s
(
(
p
s
p
s
(
(
p
s
p
s
t
t
S
C
S
C
S
C
S
C
(7）
S
( ),1,
j
C
S
C
S
C
j
( ),1
e
(
(
p
s
p
s
C
) max{
j
( ),1,
p
(
)
s
S
j
( ),1,
e
e
(
1
)
p
s
j
( ),1
p
s
j
( ),1
j
( ),1
j
( ),1,
e
j
( ),1
),
S
j
( ),2,
(
p
s
j
( ),1
)}
e
1
j
t e
( ), ,
j
( ),
t
(
(
p
s
p
s
C
) max{
j
t
(
), 1,
p
(
)
s
S
j
t e
( ), ,
j
( ),
t
e
(
)
t
p
s
j
( ),
p
s
(
),
j
),
t
S
j
( ), 1,
t
(
p
s
j
( ),
)}
t
e
1
j
t e
( ), ,
j
( ),
t
j
e
j
e
t
j
e
1,2,...,
2,3,...,
1,2,...,
2,3,...,
2,3,...,
1,2,...,
2,3,...,
n
w
j
( )
n
w
m
n
w
j
( )
j
( )
，
（8）
， （9）
，
（10）
j m e
( ),
,
j m
( ),
(
(
p
s
p
s
C
) max{
j m e
1,
( ),
p
)
(
s
S
(
)
p
s
j m
( ),
p
s
),
C
j m e
( ),
,
(
1
p
s
j m
( ),
)}
j m
( ),
j m e
,
( ),
S 为机器开始时间； ( ), ,
t e
j m e
( ),
,
j m
( ),
j
式中： (1),1,1
量在机器 t 上的开始时间和完工时间； ( )jw 为工件 ( )j 的批量总数。
p
s
和 ( ), ,
t e
j
( ),
C
S
(
)
(
t
j
j m
( ),
分别为工件 ( )j 的第 e 个小批
p
s
j
( ),
)
t
优 2 ，记为 1
k
2 。
(2) 如果 {1,2}
k
本文考虑了两目标阻塞批量流水线调度问题，针对多目标优化问题，下面给出几个重要
的基本概念[19]，为介绍之后的算法作铺垫。
考虑上述多目标调度优化问题的任意两个调度序列 1
(1) 如果对于
k
2
，且 ' {1,2}
f
(
1
2
{1,2}
，有
, ，且 1
2 ，可得：
f
(
)
1
2
使得
，则 1 占
)
(
)
(
)
f
f
k'
k'
k
k
使得
f
k
f
(
1
2
)
(
k
)
，且 ' {1,2}
k
f
使得 '
k
f
(
1
2
)
(
k
'
)
，则 1 与 2 互
不占优。
(3) 如果 * ，不存在 ' 使得
' ，则 * 为 Pareto 的最优解，所有 Pareto
*
最优解构成的集合称为 Pareto 最优解集，记为 *U 。
2 基本的人工蜂群算法
基本的 ABC 算法最初由文献[14]提出，该算法模拟了雇佣蜂，观察蜂和侦察蜂 3 种蜂
群的采蜜过程。ABC 算法与其他群体智能方法一样，是一个迭代的过程。首先，随机初始
化一个种群，种群中每一个解代表一个食物源；然后，这些解通过 3 种蜂群不断被更新。其
中，雇佣蜂对当前解进行邻域搜索，并将得到的新解与原解进行比较，选择适应度高的解作
为候选解；观察蜂共享雇佣蜂产生的所有候选解，并以一定的概率选择适应度较高的解，对
其采用同样的邻域搜索方法，产生新解。在整个搜索过程中，若有一个解一直没有得到改善，
则由侦察蜂随机产生一个解代替。通过上述过程的不断迭代，记录下最好的解。算法 1 给出
了 ABC 算法的具体过程。
算法 1 基本人工蜂群算法
-4-
中国科技论文在线
http://www.paper.edu.cn
输入：种群大小PS、终止条件TC。
输出：最好的解。
开始
步骤1 初始化种群。 (
for i=1 to PS
for j=1 to n
UB
(
(1),
LB
LB
x
i
x
i
x
i
)
j
j
(2),.....
x n
i
( ))
为种群中第i个解，xi(j)为第i个解的第j分量。
j
()
，
random
x j
( )
i
end for
end for
步骤2 雇佣蜂产生新解。
for i=1 to PS
for j=1 to n
x
j
new ( )
end for
end for
评价新解xnew。根据更新准则更新所选择的解，即如果xnew优于当前解xi，则将xnew赋
i ， [ 1,1]
k i
, =1,2,...,PS
r ；
,
，且 k
x j
( )
i
x j
( )
i
j
( ))
x
k
(
r
值给xi。
步骤2 观察蜂共享雇佣蜂产生的解，通过下式计算每个解的适应值所占的比率。选择比
率值最大的解，执行与步骤2相同的产生新解的方法，然后根据更新准则更新所选择的解
RP
i
fitness
PS
i
fitness
i
1
， =1,2,...,PS
i
。
i
步骤4 搜索整个种群，寻找种群中一直未更新的解，然后侦察蜂对这些未更新的解，采
用步骤1的方法，重新赋值。
如果终止条件不满足，则执行步骤2，否则结束算法。
End
算法 1 中，用 n 维的实数解 ix 代表第 i 个食物源，共有 PS 个食物源， LB j 和 UB j 分别
是第 i 个解的第 j 个分量的下界和上界值；随机函数 random() 取值为 0～1 之间的随机数；
fitnessi 为种群中第 i 个解的适应函数值； RPi 为第 i 个解的适应函数值所占的比率。
3 改进的人工蜂群算法
如前所述，已有的人工蜂群算法在求解批量流水线调度问题时，雇佣蜂和观察蜂阶段都
采用插入和交换操作产生新解。由于两阶段采用相同的方法，对邻域解进行重复的搜索，降
低了种群多样性，易导致算法陷入局部最优。和声搜索算法能够充分利用自身整个和声库的
信息，产生候选解，具有较强的全局优化能力，有助于算法跳出局部最优。鉴于此，本文采
用改进的人工蜂群(Improved Artificial Bee Colony，IABC)算法，即在雇佣蜂阶段，采用和声
搜索算子代替插入和交换操作，产生候选解。此外，算法的每一次迭代都产生许多非支配解。
由于种群规模限制，这些非支配解可能会在算法迭代过程中丢失，因此，在 IABC 算法中，
设置了一个外部储备集(External Archive set， EAs)，以保留每代搜索到的优质非支配解。
改进的算法流程图如图 1 所示。
-5-
中国科技论文在线
http://www.paper.edu.cn
图 1 改进算法流程图
3.1 雇佣蜂阶段
在求解流水线调度问题时，插入操作和交换操作已成功融入人工蜂群算法中[16]，用来
产生较高质量的邻域解。然而，现有的 DABC 算法，雇佣蜂阶段和观察蜂阶段都采用插入
和交换操作产生新解。由于两阶段采用相同的方法，可能造成很多解在相同邻域内的重复搜
索，降低了种群多样性，并使算法容易陷入局部最优。因此，在雇佣蜂阶段，本文采用具有
较好全局搜索能力的离散和声搜索算子[18,20]，产生新解。算法 2 给出了 DABC 算法的具体
过程。
U u
u
u j
u n
算法 2 雇佣蜂阶段
输 入 ： 种 群 大 小 PS 、 工 件 个 数 n 、 和 声 库 记 忆 概 率 HMCR 、 未 调 度 工 件 序 列
{ (1), (2),.. ( ),..., ( )}
输出： 雇佣蜂阶段产生的新解。
Begin
令新解 new
for i=1 to PS
；
。
将种群中第i个解 i 赋值给U；
从外部储备集中随机选择一个作为参考解
for j=1 to n1
if random()
中国科技论文在线
http://www.paper.edu.cn
else
从U 中随机选择一个工件作为 new (
end if
end for
将U中最后一个工件放入 new (
；
基于Pareto占优关系，更新 i ，如果
)j
)j
，并将其从U 和 r 中删除。
new 占优或者互不占优 i ，那么
i ，
new
并将 new 放入中，
{
new
}
。
end for
End
下面通过实例 6 5
P
5 4 2 3 1
2 1 4 3 5
3 5 2 4 1
1 3 5 2 4
2 5 4 1 3
4 3 1 2 5
给出和声搜索算子产生新个体的过程，以更清晰
地理解上述方法。假定种群中 PS=6，每个工件序列由 5 个工件组成，和声记忆库概率设置
为 0.9，新解 new
1)当 i=1 时，
。
{1,5, 2, 4,3}
(1)
，从外部储备集中随机选择一个作为参考解
。
U
1
1j ，若 random()
{5,4,2,3,1}
0.8 0.9
，则从当前种群的第 1 列中随机选择一个工件。假如
，并将工件‘3’从 U 和 r 中删除，得到
r
该工件为‘3’，因为工件‘3’ U ，则令 new (1) {3}
U
r
。
，
2j ，若 random() 0.5 0.9
，则从当前种群的第 2 列中随机选择一个工件。假如
{5,4,2,1}
(2)
{1,5,2,4}
该工件为‘3’，因为工件‘3’ U ，则需将 r 的第一个工件‘1’放入 new ，得到 new (2) {1}
将工件‘1’从U 和 r 中删除，得到 {5,4,2}
U
0.95 0.9
，则从U 中随机选择一个工件放入 new 。假如该工
{5,2,4}
r
，并
(3)
。
，
3j ，若 random()
件为‘2’，则得到 new (3) {2}
j ，若 random()
(4)
4
，并将其从U 和 r 中删除，得到 {5,4}
U
，
r
{5,4}
。
0.7 0.9
，则从当前种群的第 4 列中随机选择一个工件。假如
该工件为‘2’，因为工件‘2’ U ，则需将 r 的第一个工件‘5’放入 new 中，得到 new (4) {5}
并将工件‘5’从U 和 r 中删除，得到 {4}
r 。
U ，
{4}
，
5
(5)
j ，将 U 中最后一个工件放入 new 中，得到完整的工件序列 new
{3,1,2,5,4}
基于 Pareto 占优关系，更新 1 ，若 new 占优或者互不占优 1 ，则将 new 放入储备集，即
EAs {
。
U
2
{2,1,4,3,5}
，从外部储备集中随机选择一个作为参考解
。
}
new
2) 当 i=2 时，
。
{1,3, 4,5, 2}
(1)
r
1j ，若 random() 0.65 0.9
，则从当前种群的第 1 列中随机选择一个工件。假如
，并将工件‘1’从 U 和 r 中删除，得到
该工件为‘1’，因为工件‘1’ U ，则令 new (1) {1}
-7-
中国科技论文在线
http://www.paper.edu.cn
U
{2,4,3,5}
(2)
{3, 4,5, 2}
。
0.85 0.9
2j ，若 random()
，
r
该工件为‘5’，因为工件‘5’ U ，则令 new (2) {5}
U
，
，则从当前种群的第 2 列中随机选择一个工件。假如
，并将工件‘5’从 U 和 r 中删除，得到
r
{3, 4, 2}
{2,4,3}
(3)
。
3j ，若 random()
件为 ‘2’，则得到 new (3) {2}
j ，若 random()
(4)
4
0.95 0.9
，则从U 中随机选择一个工件放入 new 。假如该工
，并将其从U 和 r 中删除，得到 {4,3}
U
，
r
{3,4}
。
0.7
，则从当前种群的第 4 列中随机选择一个工件。假如
0.9
该工件为‘2’，因为工件‘2’ U ，则需将 r 的第一个工件‘3’放入 new 中，得到 new (4) {3}
并将工件‘3’从U 和 r 中删除，得到 {4}
r 。
U ，
{4}
，
(5)
j ，将 U 中最后一个工件放入 new 中，得到完整的工件序列 new
5
{1,5,2,3,4}
。
}
{
基于 Pareto 占优关系，更新 2 ，若 new 占优或者互不占优 1 ，则将 new 放入储备集，
EAs
同理，采用上述过程，当 i 分别为 3、4、5 和 6 时，对应地可以得到 new
{4,2,1,5,3}
{5,2,1,4,3}
{1,3,5,4,2}
。
。
new
、 new
和 new
new
{2,1,5,4,3}
、
从算法 1 和例 1 可以看出，和声搜索算子能够充分利用整个种群和非支配解信息产生不
同新解，采用基于 Pareto 占优关系更新当前解，并采用外部储备集保留每代产生的非支配解，
避免好的解丢失。
3.2 观察蜂
观察蜂可共享雇佣蜂产生的有用信息，并基于共享信息进一步进行搜索。本文随机采用
两种算子中的一种，对观察蜂共享的个体进行轻微扰动来提高算法的开发能力，以更快的速
度找到最优解[2]。
如前所述，已有的 DABC 算法，雇佣蜂和观察蜂都采用基于插入和交换的方法产生新
个体，插入和交换方法如图 2 所示。
insert( ,
p p
,
1
)
2
swap( ,
p p
2
,
1
)
(a) 插入方法 (b) 交换方法
图 2 插入和交换方法
insert( ,
如图2(a)所示)。首先，随机产生两个不同的位置p1和p2，
(1) 插入方法
p1p2 ；其次，将p1+1与p2之间的工件依次向前移动一个位置，即将p1+1位置的工件移到p1位
置，p1+2位置的工件移到p1+1位置，依次类推，将p2位置的工件移到p21位置；再其次，将原
p p
2
)
,
1
-8-
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
