当前位置:首页 >> 机械/仪表 >>

求解车间调度问题的自适应混合粒子群算法


第 32 卷   11 期 第 2009 年 11 月

计             算 机 学 报
C H IN ESE J OU RNAL O F COM PU T ERS

Vol. 32 No . 11 Nov. 2009

 

求解车间调度问题的自适应混合粒子群算法

长胜  孙吉贵   欧阳丹彤   张永刚
1) 2)

1)

2)

2)

2)

( 东北大学信息科学与工程学院   沈阳   110004)

( 吉林大学计算机科学与技术学院符号计算与知识工程教育部重点实验室   长春   130012)

摘    要 针对最小完工时间的流水车间作业调度问题 ,提出了一种自适应混合粒子群进化算法 —— H PSO ,将遗 —A 传操作有效地结合到粒子群算法中 . 定义了粒子相似度及粒子能量 ,粒子相似度阈值随迭代次数动态自适应变化 , 而粒子能量阈值与群体进化程度及其自身进化速度相关 . 此外 ,针对算法运行后期进化速度慢的缺点 ,提出了一种 基于邻域的随机贪心策略进一步提高算法的性能 . 最后将此算法在不同规模的实例上进行了测试 ,并与其他几种 具有代表性的算法进行了比较 ,实验结果表明 ,无论是在求解质量还是稳定性方面都优于其他几种算法 ,并且能够 有效求解大规模车间作业问题 . 关键词   粒子群优化 ; 车间调度 ; 粒子相似度 ; 粒子能量 ; 贪心策略 中图法分类号 TP301     DOI 号 : 10. 3724/ SP. J . 1016. 2009. 02137

pends o n t he swarm evolving degree and t he particle ’ evolving speed. In order to imp rove t he s

p ropo sed algorit hm perfo rmance f urt her , a neighborhood based rando m greedy search st rategy is int roduced to overco me t he shortco ming of evolving slowly in t he later running p hase. Finally , p ropo sed efficient algorit hms. The result show s t hat t he solutio n qualit y and t he stabilit y of t he uling p ro blem.

gy ; greedy st rategy

收稿日期 :2007210218 ; 最终修改稿收到日期 :2008212210. 本课题得到国家自然科学基金重大项目 (60496320 ,60496321) 、 国家自然科学 基金 (60773097 ,60873148) 、 新世纪优秀人才支持计划项目基金 、 吉林省科技发展计划项目基金 (20060532 ,20080107) 、 吉林省青年科研 基金 (20080107 ,20080617) 及东北师范大学自然科学青年基金 (20081003) 资助 . 张长胜 , 男 ,1980 年生 , 博士研究生 , 研究方向为智能信 息处理 . 孙吉贵 ,男 ,1962 年生 ,教授 ,博士生导师 ,研究领域为自动推理 、 约束程序 . 欧阳丹彤 ( 通信作者) , 女 ,1968 年生 , 教授 , 博士生 导师 ,研究领域为基于模型的诊断 . E2mail : ouyd @jlu. edu. cn. 张永刚 ,男 ,1975 年生 ,博士 ,讲师 ,研究方向为约束程序 .

wit h t he o bjective of minimizing makespan , which co mbined t he particle swarm optimizatio n algo2 rit hm and genetic operator s toget her . The particle similarit y and particle energy are defined. The t hreshold of particle similarit y dynamically changes wit h iteratio ns and t he particle energy de2 t he p ropo sed algorit hm is tested o n different scale benchmarks and co mpared wit h t he recently H P GA bot h p recede t he ot her t wo algorit hms. It can be used to solve large scale flow shop sched2 Keywords   particle swarm op timizatio n ; flow shop scheduling ; particle similarit y ; particle ener2

Abstract   A hybrid self2adaptive algorit hm is p ropo sed to solve t he flow shop scheduling p ro blem

ZHAN G Chang2Sheng1)   SUN J i2 Gui
1) 2)

A Self2Adaptive Hybrid Particle Swarm Optimization Algorithm f or Flo w Shop Scheduling Problem
2)

( S chool of I nf ormation S cience an d Engi neeri n g , N ort heastern Uni versit y , S heny an g   110004) Colle ge of Com p uter S cience & Technolog y , J ili n Uni versit y , Chan gchun   130012)

( Key L aboratory of S y mbol Com p ut ation an d Know le d ge Engi neeri n g of t he M i nist ry of Education ,

  YAN G Dan2 To ng2)  ZHAN G Yo ng2 Gang2) OU

2138

计             算 机 学 报

2009 年

1    引 言
调度问题是很多实际流水线生产调度问题的简 化模型 ,因此其研究具有极高的理论价值和实践价 值 . 本文研究的置换流水车间作业调度问题是在满 足工件约束和机器约束条件下 , 使得最小完工时间 尽可能小 . 工件约束指每个工件在每台机器上恰好 加工一次 ,每个工件在每个机器上的加工顺序相同 ; 机器约束指每台机器在任何时刻至多加工一个工 件 ,每台机器加工的各工件的顺序相同 . 该问题一般 可以描 述为 : n 个 待加 工的 作业 J = { J 1 , J 2 , …,
J n } , 需 要 在 m 台 机 器 上 加 工 M = { M 1 , M 2 , …, M m } , 每个作业包含 m 道工序 J i = { Oi , 1 , Oi , 2 , … Oi , m } , 其中 Oi , k 代表作业 i 在机器 k 上的加工时间

为 t i k ( 1 Φ i Φ n , 1 Φ k Φ m) 的工序 . 作业 J j 的完工时 间 C j 为其最后一个工序完成时间即 C j = Cj m . 求解 目标是求得一个可行调度 , 使得加工完所有作业所 花的时间 Cmax 尽可能少 . 该问题可用如下的数学模 型表示 :
C 1 1 = tπ1 1 π

其中 , Cj k 表示工序 O j k 的完工时间 .

此问题已被证明是 N P 难度问题 [ 1 ] , 因此 , 精确

方法[ 2 ] 在合理的时间内只能求解小规模问题 , 其求 解时间随着问题规模成指数倍增长 . 而启发式算法 能够在可接受的时间内 , 使用较少的存储空间求得 问题近似最优解或最优解 , 主要分为构造启发式[ 3 ] 和元启发式两种 [ 4 ] : 构造启发式方法虽可以在较短 时间内获得调度问题的解 , 但其在构造调度的过程 中依赖根据问题局部信息设计的调度规则 , 所获得 的调度一般为局部最优解 ; 元启发式方法 , 是基于仿 生学机理的调度算法能够在可行时间内以较大概率 获得该类问题的最优解或近似最优解 , 成为求解各 种车间调度问题的有效算法 , 正受到研究者的广泛 关注 . 粒子群算法 ( PSO ) 是受鸟群觅食启发提出的一 种进化计算方法 , 其收敛速度快 、 易于实现 , 被成功 应用在多个领域中 [ 5 ] . 目前 , 应用 PSO 算法求解调

C j 1 = C j - 1 1 + tπj 1 , Π j ∈{ 2 , …, n} π π C j k = max{ C j - 1 , k , C j k - 1 } + tπj k , π π π Cmax = max Cj ,

π π C 1 k = C 1 k - 1 + tπ1 k , Π k ∈{ 2 , …, m}

   Π j ∈{ 2 , …, n} , k ∈{ 2 , …, m}

度问题的研究还很少 , 实验表明 , 在求解调度问题 时 , 它们较 GA 算法更为有效 . 但已提出的算法都存 在早熟收敛 、 易陷入局部最优 、 进化后期算法收敛速 [ 6 27 ] 度明显下降等缺点 , 主要是由于进化过程中粒 子能量不断下降 , 导致粒子进化停滞不前 , 群体多样 性过低造成的 . 为了克服这些不足 , 本文提出了一种 混合元启发式算法2A H PSO , 将 PSO 算法与 GA 算 法 [ 8 ] 结合在一起 , 利用遗传操作不断引入新的信息 指导群体的进化 . 定义了粒子相似度及粒子能量 , 粒 子相似度阈值随迭代次数动态自适应变化 , 而粒子 能量阈值与群体进化程度及其自身进化速度相关 . 使用排序策略保持群体的多样性 , 当相邻的两个粒 子的相似度大于其当前的相似度阈值时 , 对其中的 一个粒子执行变异操作 . 设计了一种基于遍历矩阵 的快速计算最小完工时间方法 . 此外 , 针对进化后期 进化速度慢的缺点 , 提出了一种基于邻域的随机贪 心策略 , 进一步提高算法的性能 . 最后 , 分析了算法 的复杂度及收敛性 , 并通过实验对比证明了算法的 有效性 .

2   HPSO 算法 A

为了使 用 PSO 算 法 求 解 调 度 问 题 , Ramesh2 kumar 提出了一种置换离散粒子群算法 [ 7 ] , 粒子在 更新过程中只交换相应位置的元素 , 而不引入新元 位置及速度 . 21 1   算法进化模型 在 PSO 算法中 , 每个粒子的行为主要受其当前 动量项 、 个体认知部分及群体认知部分的影响 . 因 此 , 传统的粒子速度公式可通过将粒子的当前速度 与其个体最优解及当前的群体最优解分别进行交叉 来取代 , 粒子的位置更新也相应地变为将粒子当前 位置与当前速度交叉求得 . 粒子速度及位置更新公 式可表示如下 : ( 1) V i ( k + 1) = V i ( k) Pgbest Pibest ( 2) X i ( k + 1) = X i ( k) V i ( k + 1) 其中符号 表示交叉操作 . 由上面的公式可以看出 , 每个粒子追随其当前个体最优解及全局最优解运 动 . 与传统的 PSO 算法一样 , 它具有快速收敛 、 计算

素 . 受其启发 , 我们将置换的思想引入到所提出的算 法中 . 对于一个含有 n 个作业的流水调度问题 , 粒子 i 的位置及速度均被表示为一个满足 alldifferent ” “ [9 ] 约束 的 n 维向量 , 即所有作业的一个全排列 , 然后 结合 GA 算法中的交叉及变异操作不断更新粒子的

11 期

张长胜等 : 求解车间调度问题的自适应混合粒子群算法

2139

简单等优点 . 但是 , 进化过程中粒子的速度会迅速逼 近零 , 即粒子的当前速度和其当前位置相同 , 使算法 易于陷入局部最优解 , 如实验部分的 A H PSO 2S 2A 算法所示 . 为此 , 本文引入了粒子能量及粒子能量阈 值的概念 . 粒子能量阈值随着迭代次数粒子的进化 速度动态自适应调整 , 使算法在进化初期具有较强 的全局搜索能力 , 在后期则侧重局部精化能力 . 定义 1.   给定粒子 Pi , 其当前位置和速度分别 为 X i , V i , 当前的个体最优位置和群体最优位置分 别为 Pibest , Pgbest . 此粒子当前所具有的能量可计算 如下 :
dim

定义 . 定义 3.   给定粒子 Pi , P j , 它们的相似度计算 如下 :
dim k =1

s ∑ ame

Pibest ( k) , Pjbest ( k) dim ,

s i m i l arit y ( Pi , P j ) =

其中 , di m 表示待加工的作业数量 . 定义 4.   设最大迭代次数 M A X G E N , 粒子相 似度阈值的取值范围为 [ s I ni , s Fi n ] , 则当迭代次数 为 cu rGen 时粒子相似度阈值定义如下 : si m i T h res hol d ( cu rGen) = ( M A X G E N - curGen 3 s ( × s I ni - s Fi n) + s Fi n ,
M A X GEN

其中 , s ame ( x , y) =

状态及群体当前最优位置相关 . 易见 ener g y ( Pi ) ∈
[ 0 , 1 ].

为最大迭代次数 , e I ni 与 e Fi n 分别代表粒子能量的 上界及下界 , 则对于给定的粒子 Pi , 其能量阈值定 义如下 :
e ner g y T h res hol d ( Pi ) =

其中 , s pee d ( P ( k) i ) = Pibest ( k) / Pibest ( k - 1 ) , e 为预 先指定的常量 , 用于控制粒子能量阈值的变化趋势 . 粒子能量阈值与群体进化程度及粒子进化速度 相关 . 可以看出 , 算法运行过程中粒子能量不断变 化 , 当粒子能量小于它当前的能量阈值时 , 对其当前 速度及位置执行变异操作如式 ( 3 ) ~ ( 4 ) 所示 , 以此 引入新的信息增加粒子能量 , 扩大其能够到达的搜 索范围 .
V i ( k) = m ut ation ( V i ( k) ) ( 3) ( 4)

少 , 全局搜索能力不断下降 , 影响群体的进化质量 ,

如实验中 A H PSO 2S 算法所示 . 由此 , 我们定义了粒 子相似度及粒子相似度阈值 , 采用排序策略保持群 体的多样性 . 粒子相似度用于度量两个粒子的相近 程度 , 根据相邻两个粒子的个体最优位置的距离

e ner g y ( Pi ) = 01 6 ×
dim k =1

j =1

s ∑ ame ( P

ibest

( j ) , Pgbest ( j ) ) +

    11 4 ×∑ ame ( X i ( k) , V i ( k) ) / ( 2 ×d i m ) , s
0, 1,

若 x=y . 若 x ≠y

粒子能量用于刻画粒子的搜索能力 , 与粒子当前

其中 s 为一常量 , 用于控制粒子相似度阈值每次变 化的幅度 . 粒子相似度阈值用于设定当前群体中粒子之间 距离的下界 , 它随迭代次数动态自适应变化 . 在算法 运行的初始阶段 , 粒子相似度阈值取值较大 , 使得粒 子在搜索空间中分布均匀 , 搜索范围扩大 ; 随着群体 的不断进化 , 相似度阈值不断减小 , 使得粒子之间能 够逐渐聚合到当前的全局最优位置 , 加强搜索最优 位置的邻域 , 进一步提高最优解的精度 . 为了保持群 体的多样性 , 在进化过程中 , 根据适应度值对群体中 的所有粒子进行排序 , 当两个相邻的粒子的相似度 小于当前的粒子相似度阈值时 , 对较差粒子的历史 最优解执行变异操作 , 如式 ( 5) 所示 . ( 5) Pibest ( k + 1 ) = m ut ation ( Pibest ( k + 1) ) 通过变异操作能够在群体中重新引入新的有用信 息 , 指导粒子搜索那些未曾搜索过的区域 , 进一步抑 制算法的早熟收敛 . 21 2   适应度计算 为了提高算法的速度 , 我们设计了一种基于遍 历矩阵的快速计算粒子适应度的方法 . 对于给定的 n 个待加工作业 , 每个作业包含 m 道工序 , 我们将调 度 S = s1 , s2 , …, s n 〉 〈 的加工时间矩阵 T 定义为 t1 , s1 t1 , s2 … t1 , s n
T = t2 , s1 t2 , s2

定义 2. 设当前迭代次数为 cu rGen , M A X G E N

 

( MA X G E N - cu rGen × spee d ( Pi ( cu rGen ) ) ) MA X G E N

e

×

 ( eI ni - eFi n) + eFi n ,

… t2 , s n

X i ( k) = m ut ation ( X i ( k) )





   以上模型在迭代过程中群体多样性会不断减

t m , s1

t m , s2

… … … tm , sn

,

其中 , si ∈J , t j k 表示作业 j 在第 k 台处理机上的加 工时间 , 1 Φ i Φ n , 1 Φ j Φ m. 算法中粒子的适应度值由最小完工时间表示 , 根据以上定义 , 通过对问题数学模型的分析 , 给定的 调度 S 对应的最小完工时间 , 可通过按照如下公式

2140

计             算 机 学 报
endif

2009 年

遍历矩阵 T 求得 :
t1 , 1 , t1 , j - 1 + t1 j , ti , j = ti - 1 , 1 + ti , 1 , ti - 1 , j + ti , j , ti , j - 1 + ti , j , i = 1,j = 1 i = 1 , j ≠1 i ≠1 , j = 1 . ti - 1 , j > ti , j - 1 ti - 1 , j < ti , j - 1

endif endfor
curGen + + ;

endwhile ret urn gB est ; end.

遍历完成后 , 新计算出的 t m , n 的值就是调度 S 的最 小完工时间 . 在我们的 A H PSO 算法中 , 群体的初始化采用 随机的方式 , 即在搜索空间中随机地产生粒子的初 始位置和初始速度 , 将每个粒子的历史最优位置设 置为其当前位置 , 并计算每个粒子当前位置所代表 调度的最小完工时间 , 将其作为粒子的适应度值 . 根 据算法的进化模型 , A H PSO 算法可描述如下 . 算法 .   H PSO . A
  begin
i niti ali ze ( pop) ; ? curGen ?= 0 ;

   : M A X FGEN 表示算法的最大迭代次数 ; curGen 及 注 pop N um 分别为当前迭代次数和群体规模 ; ran dom 表示 [ 0 , 1 ]之间的随机数 .

21 3   算法描述及分析
fo r j
? ? =

   收敛通常是指一个系统或过程达到一个稳定状 态 , 对基于群体的优化算法来说 , 算法的收敛可以根 据群体的行为来定义 [ 10 ] . 给定待求解的调度问题 Ω P , 其搜索空间 Ω, gbest ( t) ∈ 为算法在时间 t 或在 群体的第 t 次进化中求得的最优位置 . gbest 3 为 Ω 中的一个固定位置 , 收敛的定义可记为
lim gbest ( t) = gbest 3 .
t →∞

也就是说 , 如果由算法求得的 gbest 不在变化 , 那么 就说处于收敛状态 . 如果 gbest 为搜索空间的全局 最佳位置 , 则算法获得了全局最优收敛 , 否则算法陷 入局部最优位置 . 定理 1.   H PSO 算法是收敛的 . A

while curGen < M A X GE N do 1 to pop N um do
pop[ j ]. pB est ;
? pop [ j ]. v [ cu rGen + 1 ] ?= pop[ j ]. v[ cu rGen]

gB est

? pop [ j ]. x[ cu rGen + 1 ] ?= pop[ j ]. x[ cu rGen]

证明 .   将群体中的每个粒子的当前位置视为

pop[ j ]. v[ curGen + 1 ] ;

一个状态 , 则所有的粒子当前位置的集合可视为一 种状态分布 . 这种状态分布会随算法的运行而改变 . 由于 A H PSO 算法的运行具有随机性 , 其基本操作 只与当前状态有关 , 是无后效性的 , 因此可以把群体 内的个体视为一个具有不同状态的随机变量的概率 分布 . 首先证明由式 ( 1) ~式 ( 2) 构成的迭代过程是收

? pop [ j ]. f it ness ?= Cmax ( pop[ j ]. cu rrent) ;

if pop[ j ]. f it ness < Cmax ( pop[ j ]. pB est) then

?  pop[ j ]. pB est ?= pop[ j ]. cu rrent ; endif if pop[ j ]. f itness < Cmax ( gB est) then ? gB est ?= pop[ j ]. current ; endif . ? c ?= j ; while pop[ c] . f itness < pop[ c - 1 ] & &c ! =1 do sw a p ( pop[ c] , pop[ c - 1 ]) ; ? c ?= c - 1 ; endwhile endfo r ? fo r k ?= 1 to pop N um do ?  p articleEner g y ?=

敛的 . 设群体规模为 m , 问题规模为 l 群体的状态记 为 ( p1 , p2 , …, p m ) , 最佳调度为 p 3 . 所有的群体状 态构成一个 1 ×N 的行向量 , 其中 N = ( m. l) ! , 这个 行向量的每个元素由排在一起的 m 个粒子的当前 位置构成 . 可表示为
( 1) ( 1) ( 1) ( 2) ( 2) ( 2) { ( p1 , p2 , …, p m ) , ( p1 , p2 , …, p m ) , …, ( ( ( ( p1 N) , p2 N) , …, p mN) ) } ,

p a rticle Ener g y Com p uti n g ( pop[ k ]) ;

if p a rticle Ener g y <
particle Energ y T hreshol d ( pop[ k] , curGen) then

  i ncrease Pa rticle Ener g y ( pop[ k ]) ;

endif

if k ! = 1 t hen

? si mi l arit y ?=

p articleS i mi l arit y Com p uti n g ( pop[ k ]) ;

if similarit y < similarit y T hreshol d ( curGen) then
? pop[ k] . pB est ?= m utation ( pop[ k ] . pB est) ;

假设经过若干代进化后 , 达到种群最优状态 p 3 , 不 妨设其排在状态行向量的第一个分两处 , 即
( ( ( ( p1 N) , p2 N) , …, p mN) ) } ,

根据粒子的速度及位置更新公式可知 , 此时 , 处在最 优位置粒子的速度及历史最优位置均为 p 3 , 在下一 次迭代中求得的粒子当前位置不变 . 状态转移矩阵

(3) (3) (3) ( 2) ( 2) ( 2) { ( p1 , p2 , …, p m ) , ( p1 , p2 , …, p m ) , …,

11 期

张长胜等 : 求解车间调度问题的自适应混合粒子群算法

2141

可写为
C =

O ( 2 m d) . 由于在一次迭代中需要计算所有粒子的

1
C21

C22

其中 C 为随机矩阵 , 其每一行至少有一个正的元 素 , <为 N - 1 维行向量 . 显然 C 为可约随机矩阵 , 且 C21 , C22 不是零矩阵 , 根据可约随机矩阵的性质有
C
∞ ∞ = ( C 1 , 0 , …, 0) ,

其中 , C1∞ > 0 . 因为 C ∞可看作是一个状态分布 , 所以 应有
∞ C1

= 1 , 于是 C



= ( 1 , 0 , …, 0 ) , 即算法收敛到

了 p . 当算法中粒子能量小于其当前的能量阈值或粒 子的相似度大于当前相似度阈值时 , 虽然引入了变 异操作 , 但并没有改变当前已经得到的历史全局最 优位置 , 而且在以后的进化中 , 只有当得到的位置由 于此最优位置时才会被取代 , 即全局最优位置总是 朝着更好的位置进化 . 所以 , 根据定义 6 , A H PSO 算 法是收敛的 . 证毕 . 定理 2.  A H PSO 算法求得的解是一个合法 调度 . 证明 .   算法中使用的交叉及变异操作可参看 文献 [ 8 ] , 每种操作都满足 alldifferent ” “ 约束 , 都是 一个合法调度 , 即 A H PSO 算法的搜索空间是由所 有合法调度构成的 . 所以由 A H PSO 算法求得的解 必然合法 . 证毕 . ( (4 n + 定理 3. A HPSO 算法的空间复杂度为 O 2 m + 2) ?d) , 群体每次进化的最坏渐进时间复杂度 为 O ( m n d2 ) . 其中 n 为群体规模 , d 表示作业数量 , m 为处理机个数 . 证明 .   A H PSO 算法运行过程中需要存储 在 每个粒子的当前位置 、 个体最佳位置 、 上一次迭代的 个体最佳位置及速度 , 令群体规模为 n , 则它所消耗 存储空间为 O ( 4 n ?d) ; 在求解粒子适应度时还需要 存储处理时间矩阵 , 所消耗的空间为 O ( 2 m d) ; 每次 执行交叉及变异等操作时还需要一个存储新位置或 速度的空间 , 此外还需要存储一个全局最优调度 ; 所 以 H P GA 算法的空间复杂度为 O ( ( 4 n + 2 m + 2 ) ? d) . 算法运行时 , 执行一次交叉操作消耗的时间最 多为 O ( 2 d - 1 ) , 变异操作最多为 O ( d ) , 所以在 H P GA 算法的一次迭代过程中 , 由交叉或变异引起 的最坏时间复杂度为 O ( 2 n ( 2 d - 1) ) ; 计算个体能量 时 , 需要访问每个粒子 , 由此引起的时间复杂度为
O ( 2 n ?d) ; 计算相似度及相似度阈值所消耗的时间

3

也为 O ( 2 n ?d) , 求解每个粒子适应度时需要求得及 遍历 与 之 相 应 的 时 间 矩 阵 , 其 时 间 复 杂 度 为

<

适应度 , 那么需要消耗的时间就变为 O ( 2 m n d) , 并 且最坏情况下 , 在一次迭代中每个粒子都需要更新其 个体最优位置及当前位置和速度时 , 那么此时所消耗 的时间就变为 O ( 4 m n d2 ) . 当问题规模逐渐增大即
m ?n的值趋于无穷大时 , 4 m n d Ε 8 n d Ε 2 n , 所以
2

H P GA 算法的最坏时间渐进复杂度为 O ( m n d2 ) .

证毕 .

当接近最优解时 , 易于停止进化 . 为此 A H PSO 算法 中引入一种基于邻域的贪心随机搜索策略在每次迭 代过程中更新粒子的个体最优解 , 进一步提高解的 质量 , 此时将算法记作 G2A H PSO . 随机搜索策略 , 可描述如下 .
begin
? i m p rove ?= t rue ;

定义 5.   给定一个含有 n 个作业的调度问题 , 它的任意一个有效调度 π= {π , …,π } 可看作是 n 1 n 维空间中的一个点 . 通过随机选择一个作业 π , 1 Φ i 效调度 , 即 n 维空间中一个新的点 . 所有以此方式求 得的点就构成了作业 π的邻域 . i 根据以上定义 , 我们提出一种基于邻域的贪心
i Φ n , 将其插入到任意其它位置 , 可求得一个新的有 ) procedure . Negihborhood Greedy_ Insersion (π .
while ( i m p rove = t rue) do
? i m p rove ?= false ; ? i ?= ran dom ( 0 , di mension - 1) ; ? i m p rove ?= t rue ;

3  实验结果

算法求解 FSP 问题的性能的影响进行了分析 . 实验 中本文选择第二种形式的两点交叉操作 , 并分别测 试了 6 种变异操作对算法的影响 . 这 6 种变异操作 分别是近邻变异 ( M1) 、 随机交换变异 ( M2 ) 、 移位变

21 4   算法改进
endif endwhile ret urn π; end .

实验中发现 , 进化后期算法收敛速度明显下降 ,

remove t he jo b π f rom π; i π ?= best schedule obtained by inserting π in any ? ′ i po sitions of π; ) if Cmax (π ) < Cmax (π t hen ′ π ?= π ; ? ′

文献 [ 8 ] 对各种基本的遗传操作及它们对 GA

2142

计             算 机 学 报

2009 年

异 ( M3) 、 置换变异 ( M4 ) 、 逆转变异 ( M5 ) 、 / 置 逆转 换变异 ( M6) . 此外 , 还测试了粒子能量及粒子相似 度策略对算法性能的影响 . 最后在不同规模的 Tail2 liard 数据集[ 11 ] 上对 A H PSO 及 G2A H PSO 算法进 行了测试 , 并与最近提出的求解调度问题的 GA 算 法[8 ] 、 SPSOA 算法[ 7 ] 进行了比较 . 为了方便 , 实验中 A HPSO 和 G2A HPSO 算法的参数设置相同 , M A X 2 G E N = 1000 , pop N um = 60 , s = 11 40 , e = 11 35 , e I ni = 01 45 , e Fi n = 01 10 , s I ni = 01 85 , s Fi n = 01 05 . 为说明算法每次求得的最优解与已知最优解的 差距 , 我们定义了算法所求得的最优解的平均偏离度 ( Average Relative Deviatio n , A RD ) 即算法每次运 行得到的最优解与已知最优解的差的均值. 计算如下 :
T

A RD =

i =1

∑ S ol

i

- O pti m al / T ,

问题

ta005 ta010 ta020 ta030 ta050 ta060 ta070 ta080

   可以看出 A H PSO 算法的平均求解质量最佳 , 求得的最优解及平均偏离度都是最小的 . A H PSO 2S

图 1  不同规模问题上 A H PSO 、 H PSO 2S 和 A H PSO 2S 2A 算法的群体平均进化曲线 A

A HPSO 2S 2A 1250/ 12541 3/ 1277 (191 3) 1120/ 11391 2/ 1161 (311 2) 1614/ 16321 7/ 1654 (411 7) 2212/ 22401 3/ 2269 (621 3) 3190/ 32231 9/ 3245 (1581 9) 3982/ 40191 9/ 4075 (2631 9) 5342/ 53941 8/ 5429 (721 8) 5986/ 60471 4/ 6087 (2021 4)

表 1  AHPSO , AHPSO 2S 和 AHPSO 2S2A 在不同规模问题上的测试结果比较 、 括号内的值为算法在此问题上运行 10 次的平均偏离度
测试结果
A HPSO 2S 1235/ 12421 0/ 1250 (71 0) 1108/ 11081 0/ 1108 (01 0) 1599/ 16141 2/ 1631 (231 2) 2194/ 22041 4/ 2221 (261 4) 3131/ 31611 1/ 3204 (961 1) 3884/ 39171 6/ 3969 (1611 6) 5328/ 53401 2/ 5346 (181 2) 5896/ 59021 4/ 5904 (571 4)

其中 T 为针对某个问题算法的运行次数 , 它是算法 求得的最优解偏离已知最优解平均程度的指标 , 能 够反映出算法的平均求解质量 . 本文实验中每个测 试问题上各算法运行次数都为 10 , 即 T = 10 . 31 1   粒子能量及粒子相似度策略对算法性能的影响 的求解质量也明显高于 A H PSO 2S 2A 算法 . 也就是 说粒子能量及粒子相似度策略能够极大地提高算法
A HPSO 1235/ 12421 7/ 1250 (71 7) 1108/ 11081 0/ 1108 (01 0) 1598/ 16111 4/ 1618 (201 4) 2178/ 21901 3/ 2199 (121 3) 3112/ 31561 0/ 3204 (911 0) 3843/ 38721 5/ 3899 (1161 5) 5328/ 53361 6/ 5346 (141 6) 5881/ 59001 8/ 5903 (551 8)

为了测试它们在 A H PSO 算法中的作用 , 我们 比较了采用移位变异操作的 A H PSO 算法 、 HS2 A PO 2S 算法及 A H PSO 算法在不同规模问题上的求 解结果 . A H PSO 2S 2A 算法是去除粒子能量及粒子 相似度策略即迭代模型只由式 ( 1 ) ~ ( 2 ) 构成的算

法 ; A H PSO 2S 算法是去除粒子相似度策略即迭代 模型由式 ( 1) ~ ( 4 ) 构成的算法 . 表 1 为在每个问题 上各算法 10 次运行中求得的最好解 、 最优解均值 、 最差解及平均偏离度的比较结果 . 各算法在不同规 模问题上的群体平均适应度进化曲线如图 1 所示 .

11 期

张长胜等 : 求解车间调度问题的自适应混合粒子群算法

2143

的性能 . 从图 1 中明显看出 A H PSO 2S 2A 算法虽然 收敛速度快 , 但容易陷入局部最优解 , 其求解质量最 差 . 此外 , 对于小规模问题由于其解空间小 , 粒子能 够搜索到的区域几乎涵盖整个解空间 , 此时 , 粒子相 似度策略对算法性能影响不大 , 如图 1 ( a ) 所示 . 随 着问题规模增加 , 其求解空间也变得相对复杂 , 此时 排序策略能够指导粒子朝着最有希望获得更好解的
问题
ta005 ta010 ta020 ta030 ta050 ta060 ta070 ta080

表 2  采用不同变异操作的 AHPSO 算法的测试结果
测试结果
M3 1235/ 12421 7/ 1250 1108/ 11081 0/ 1108 1608/ 16111 4/ 1618 2178/ 21901 3/ 2199 3112/ 31561 0/ 3204 3843/ 38721 5/ 3899 5328/ 53401 5/ 5346 5881/ 59001 8/ 5903 M3 1235/ 12351 0/ 1235 1108/ 11081 0/ 1108 1591/ 16071 1/ 1617 2179/ 21821 8/ 2195 3091/ 31101 3/ 3131 3806/ 38391 8/ 3899 5328/ 53311 6/ 5342 5881/ 59001 8/ 5903 M3 71 7 (01 0) 01 0( 01 0) 201 4 (161 1) 121 3 (41 8) 911 0( 451 3) 1161 5( 831 8) 181 5( 91 2) 551 8( 551 8) M4 1244/ 12471 0/ 1250 1108/ 11091 2/ 1120 1591/ 16091 9/ 1629 2179/ 21841 6/ 2196 3131/ 31561 9/ 3216 3859/ 38921 1/ 3908 5342/ 53521 0/ 5386 5903/ 59141 8/ 6009 M4 1235/ 12361 8/ 1244 1108/ 11081 0/ 1108 1591/ 16061 3/ 1608 2178/ 21811 0/ 2185 3095/ 31181 9/ 3132 3797/ 38291 2/ 3861 5328/ 53291 6/ 5342 5856/ 58871 3/ 5903 M4 121 0 (11 8) 11 2 (01 0) 181 9 (151 3) 61 6( 31 0) 911 9 (531 9) 1361 1 (731 2) 301 0 (71 6) 691 8 (421 3)

问题

ta005 ta010 ta020 ta030 ta050 ta060 ta070 ta080

   从表中可以看出 , 无论是从所得到的最优解 、 最 优解均值还是最差解方 面 , 使 用变 异操 作 M3 时 A H PSO 算法的性能最佳 , 在 10 次运行中除问题 ta020 外 , 求得的最小完工时间都优于使用其它几 种变异操作时算法求得的解 . 对于 G2A H PSO 算法 来说 , 除变异操作 M 1 外 , 使用其它几种变异操作对 算法的性能影响不是很大 , 这主要是由于使用这几 种变异操作时 , 算法的全局搜索能力相差不大 , 而在 算法运行后期 , 解的质量的精化又主要依赖于贪心 随机搜索策略 . 从表 1 、 2 的对比中可以看出 , 无 表 论使用哪种变异操作 , G2A H PSO 算法求得的最优 解、 最优解均值和最差解都要明显好于 A H PSO 算
问题
ta005 ta010 ta020 ta030 ta050 ta060 ta070 ta080 M1 171 6 (61 5) 171 3 (31 8) 371 8 (191 3) 601 0 (111 9) 1571 3 (741 0) 2441 8 (1141 0) 571 5 (61 5) 1911 4 (551 8) M2 111 3 (01 8) 31 8 (01 0) 191 9 (121 6) 201 0 (31 3) 971 6 (541 8) 1501 8 (661 5) 211 2 (91 0) 591 3 (511 4)

M1 1243/ 12521 6/ 1294 1108/ 11251 3/ 1138 1614/ 16281 8/ 1654 2210/ 22381 0/ 2273 3204/ 32221 3/ 3286 3946/ 40001 8/ 4076 5342/ 53791 5/ 5422 5949/ 60361 4/ 6087 M1 1235/ 12411 5/ 1250 1108/ 11111 8/ 1127 1604/ 16101 3/ 1614 2178/ 21891 9/ 2202 3131/ 31391 0/ 3162 3849/ 38701 0/ 3899 5324/ 53281 5/ 5332 5881/ 59001 8/ 5903

M2 1235/ 12461 3/ 1250 1108/ 11111 8/ 1127 1591/ 16101 9/ 1620 2185/ 21981 0/ 2227 3131/ 31621 6/ 3191 3871/ 39061 8/ 3965 5342/ 53431 2/ 5346 5903/ 59041 3/ 5916 M2 1235/ 12351 8/ 1243 1108/ 11081 0/ 1108 1591/ 16031 6/ 1613 2178/ 21811 3/ 2189 3091/ 31191 8/ 3132 3800/ 38221 5/ 3855 5324/ 53311 0/ 5342 5881/ 58961 4/ 5903

表3  采用不同变异操作的 G2AHPSO 算法的测试结果
测试结果

表 4  AHPSO 与 GAHPSO 算法平均偏离度的比较
测试结果

区域搜索 , 进一步提高算法的性能 , 如图 1 ( b ) ~ ( d) 所示 . 31 2   局部搜索策略对算法性能的影响 为了测试局部搜索策略对算法性能的影响 , 我 们在每个测试集上采用不同变异操作的 A H PSO 及 最优解均值及最差解 , 如表 2 和表 3 所示 .
M5 1235/ 12421 8/ 1250 1108/ 11081 9/ 1111 1608/ 16111 8/ 1615 2186/ 22011 9/ 2220 3131/ 31631 8/ 3213 3884/ 39241 2/ 3985 5342/ 53551 8/ 5386 5903/ 59671 8/ 6069 M5 1235/ 12351 0/ 1235 1108/ 11081 0/ 1108 1591/ 15991 7/ 1613 2178/ 21811 2/ 2188 3092/ 31281 1/ 3146 3790/ 38251 7/ 3855 5324/ 53291 4/ 5342 5856/ 58911 7/ 5903 M5 71 8 (01 0) 01 9 (01 0) 201 8 (81 7) 231 9 (31 2) 981 8 (631 1) 1681 2 (691 7) 331 8 (71 4) 1221 8 (461 7) M6 1235/ 12401 4/ 1250 1108/ 11101 1/ 1120 1591/ 16061 1/ 1618 2183/ 21951 6/ 2207 3152/ 31761 2/ 3195 3868/ 39131 9/ 3944 5342/ 53431 0/ 5346 5903/ 59061 6/ 5924 M6 1235/ 12351 0/ 1235 1108/ 11081 0/ 1108 1591/ 15981 7/ 1608 2179/ 21811 0/ 2183 3091/ 31181 5/ 3139 3802/ 38291 1/ 3864 5322/ 53311 6/ 5342 5879/ 58981 4/ 5903 M6 51 4( 01 0) 21 1 (01 0) 151 1( 71 7) 171 6 (31 0) 1111 2 (531 5) 1571 9 (731 1) 211 0 (91 6) 611 6 (531 4)

法求得的解 . 此外 , 我们还比较了这两种算法的收敛速度 , 如 图 2 , 它显示了对于不同规模的问题 , 采用不同变异 操作时最小完工时间随迭代次数的进化曲线 . 其中 虚线 表 示 A H PSO 算 法 的 收 敛 曲 线 , 实 线 是 G2 A H PSO 算法的收敛曲线 . 显然 , G2A H PSO 算法随 迭代 次 数 收 敛 得 快 些 , 而 且 收 敛 点 的 值 也 小 于 A H PSO 算法 . 对于不同的问题 , 变异操作对算法的 收敛速度的影响也稍有不同 . A H PSO 算法与 G2A H PSO 算法在各问题上 所求得解的平均偏离度 , 如表 4 所示 , 括号内为 G2 A H PSO 算法的平均偏离度 .

G2A H PSO 算法分别运行 10 次 , 所求得的最优解 、

2144

计             算 机 学 报

2009 年

图2  不同规模问题上采用各种变异操作时 A H PSO 和 GA H PSO 算法的群体适应度进化曲线

   可以看出 , 无论是使用哪种变异操作 G2A H P2 SO 算法求得解的平均偏离度都明显小于 A H PSO 算法 求 解 的 平 均 偏 离 度 . 也 就 是 说 , G2A H PSO 算法每次求得高质量解的概率远远大于 A H PSO 算法 . 从上面的实验分析对比中可以得出 , 无论是从 求得 的 解 质 量 、 敛 速 度 还 是 平 均 偏 离 度 方 面 , 收 G2A H PSO 算法都明显优于 A H PSO 算法 . 但是 , 由 于 G2A H PSO 算法在群体进化中 , 每个粒子都要执 行贪心随机搜索过程 , 所以每次群体进化所消耗的 时间也高于 A H PSO 算法 . 在所有测试问题上 A H P2 SO 算法与 G2A H PSO 算法进化一次所消耗的时间 对比如图 3 所示 . 此外 , 由于贪心随机搜 索过 程主 要依 赖于 插 入操作求解邻域内的点 , 所以在计算这些点的适应 度时可以通过使用文献 [ 12 ]中基于插入的加速算法 可以进一步提高 G2A H PSO 算法的速度 , 但仍会 略慢于 A H PSO 算法 . 在实际应用中是否采用贪心 搜索策略 , 需要在求解质量与求解速度之间进行 权衡 .
问题 规模 最优解
1235 1108 1591 2178 3065 5322 5845 GA ta005 ta010 ta020 ta030 ta050 ta060 ta070 ta080 20 × 5 20 × 5 20 × 10 20 × 20 50 × 10 50 × 20 100 × 5 100 × 10

表 5  算法求解结果比较
SPSOA

2222

1304/ 13471 0/ 1387 1188/ 12521 4/ 1303 1702/ 17901 7/ 1852 2368/ 24531 9/ 2517 3384/ 35121 3/ 3557 4338/ 44581 2/ 4524 5409/ 56111 6/ 5688 6302/ 63951 0/ 6493

1244/ 12501 4/ 1254 1108/ 11261 0/ 1160 1600/ 16351 5/ 1674 2194/ 22431 0/ 2299 3173/ 32201 4/ 3260 3917/ 39821 5/ 4038 5342/ 53621 8/ 5389 5903/ 59591 1/ 6051

最后 , 为了进一步说明本文提出算法的有效性 , 将它们与最近提出的 GA 算法 [ 8 ] 及 SPSOA 算法 [ 7 ] 进行了比较 , 所得结果如表 5 所示 . 表中都是使用各 变异操作每个算法运行 10 次得到的最好结果 , 可以 看出在所有的测试集上无论 G2A H PSO 算法还是 A H PSO 算法所求得的最优解 、 最优解均值及最差 解都明显小于其他两种算法 , 而且 G2A H PSO 算法 能够求得问题 ta070 的最优解 5322 , 也就是说在此 问题上 G2A H PSO 具有全局收敛性 .
求解结果
A H PSO 1235/ 12401 4/ 1250 1108/ 11081 0/ 1108 1591/ 16061 1/ 1618 2178/ 21901 3/ 2199 3112/ 31561 0/ 3204 3843/ 38721 5/ 3899 5328/ 53401 5/ 5346 5881/ 59001 8/ 5903 1235/ 12351 0/ 1235 1108/ 11081 0/ 1108 1591/ 15981 7/ 1608 2178/ 21811 0/ 2185 3091/ 31101 3/ 3131 3790/ 38251 7/ 3855 5322/ 53311 6/ 5342 5856/ 58871 3/ 5903 G2A HPSO

31 3   与其他算法的比较

图3  采用变异操作 M3 时 A H PSO 和 G2A H PSO 算法求解各问题的时间对比

11 期

张长胜等 : 求解车间调度问题的自适应混合粒子群算法

2145

4    结 语
本文工作主要体现在以下几个方面 : ( 1 ) 提出 了一种求解流水调度问题的自适应混合粒子群算 法 ,将遗传操作结合到算法中 ; ( 2 ) 定义了粒子能量 及随进化程度自适应调整的粒子能量阈值 , 采用变 异操作保持粒子的搜索能力 ; ( 3 ) 引入了粒子相似 度及相似度阈值 ,并采用排序策略保持群体的多样 性 ,抑制算法的早熟收敛 ; ( 4 ) 通过使用遍历矩阵方 式快速计算一个调度的最小完工时间 ; ( 5 ) 证明了 算法的收敛性 ,分析了算法空间复杂度及迭代一次 的渐进时间复杂度 . 最后定义了衡量算法性能指标2 平均偏离度 ,将该算法在 8 个不同规模的问题上进 行了测试 ,并与当前国际文献中最近提出的两种著 名算法进行了比较 , 结果表明无论是求得的解得质 量还是算法的稳定性均明显好于这两种算法 , 加入 随机贪心搜索策略后效果更佳明显 . 下一步工作主 要集中在测试其他交叉策略对算法的影响 , 找出交 叉操作与变异操作的最佳组合 , 以及使用本文提出 的算法解决其他组合优化问题 .

[4]

flowshop s to minimize makespan. Computers and Operations Research , 2003 , 30 (12) : 19231 Research , 1990 , 47 (1) : 65274 Yang Qing2 Yun , Sun Ji2 Gui , Zhang J u2 Yang et al . A hybrid

[5]

[6]

[7]

[8]

[9]

[ 10 ]

参 考
[1 ]




[ 11 ]

Garey M , Johnson D , Set hy R. The co mplexit y of flow shop and job shop scheduling. Mat hematics of Operations Re2 tardy scheduling wit h release dates. Co mp uters & Opera2 Gangadharan R , Rajendran C. Heuristic algorit hms for search , 1976 , 1 (2) : 1172129 Valente J M S , Alves R A F S. An exact app roach to early/

[ 12 ]

[2 ]

[3 ]

Background

zatio n p roblems in real life which is N P2hard and difficult to find a satisf ying solution wit hin a limited time. How to get

  The scheduling p ro blems is a kind of impo rtant optimi2

SUN Ji2 Gui , bo rn in 1962 , Ph. D. , p rofesso r , Ph. D.

tions Research , 2005 , 32 (11) : 290522917

terest s include intelligent informatio n

p rocessing and const raint p rogramming.

1980 , Ph. D. . His current research in2

ZHANG Chang2Sheng ,

bo rn

in

gramming and auto matic reaso ning.

reasoning and model based Diagno sis

research interest s include intelligent info rmation p rocessing and const raint p rogramming.

t he best o r a satisf ying solution quickly has great significance for imp roving p roductivity and t he develop ment of society.

The t raditional optimization algo rit hms have many advanta2

supervisor. His research interest s include co nst raint p ro2 Ph. D. supervisor. His research interest s include auto matic ZHANG Yong2 G ang , bo rn in 1975 , Ph. D. . His current OUYANG Dan2Tong , born in 1968 , Ph. D. , p rofesso r ,

crete particle swarm optimization (DPSO) algorit hm for per2 ceedings of t he ICNC 2005 , Changsha , China , 3612 , 2005 : 5722581 Lian Zhi2 Gang , Gu Xing2Sheng , Jiao Bin. A similar particle swarm optimization algorit hm for permutation flowshop 10 (1) : 292127 search , 2008 , 35 (9) : 280722839 Co mp utation , 2006 , 175 (1) : 7732785 search for large scheduling p roblems. International Journal Production Econo mics , 2004 , 88 (12) : 1912203 Universit y of Pretoria , Pretoria , Sout h Af rica , 2002 shop sequencing p roblem. European Journal of Operational Pan Quan2 Ke , Tasgetiren M F , Liang Yun2Chia. A discrete Lauriere J 2L . A language and a p rogram for stating and sol2 ving co mbinatorial p roblems. Artificial Intelligence , 1978 , van den Bergh F. An analysis of particle swarm optimizers [ Ph. D. dissertation ] . Depart ment of Co mp uter Science , Taillard E. So me efficient heuristic met hods for t he flow particle swarm optimization algorit hm for t he no2wait flow2 shop scheduling p roblem. Comp uters & Operations Re2 mutation flowshop scheduling to minimize makspan/ / Pro2 scheduling to minimize makespan. Applied Mat hematics and Nearchou A C. The effect of various operators on t he genetic

duction Economics , 1993 , 32 (3) : 285290 1582165

discrete particle swarm algorit hm for open2shop problems/ /

Aldowaisan T , Allahverdi A. New heuristics for no2wait

scheduling in no2wait flowshop . International Journal of Pro2 Proceedings of t he 6t h International Conference on Simulated Evolution and Learning ( SEAL 2006) . Hefei , China , 2006 : Rameshkumar K , Suresh R K , Mohanasundaram K M. Dis2

2146

计             算 机 学 报

2009 年

ges such as good comp uting efficiency , st rong soundness and mat ure p roperty , but t hey all have insurmountable limitation p roximately best solution for a co mplex system. The p resen2 tatio n of evolutionary algorit hm gives a new idea for solving complex optimizatio n p ro blems. It has been adopted by many bility , essential parallelism and global search ability. Many p roject p ractice p roblems and can get very good optimization effect s. For many years t he main focus of research was on t he application of single metaheuristics to given p roblems. In flexibility when dealing wit h real2world and large2scale p rob2 po se algo rit hm fo r t he flow shop scheduling p roblem wit h lems. In t his work , t he aut hors combined t he generic opera2 tio ns wit h t he particle swarm optimizatio n algo rit hm and p ro2 tio n algo rit hms in which t he particle swarm optimizatio n al2 gorit hm is newer and p referable. It has been applied to many recent years , it has become evident t hat t he concent ration on tio n of concept s of different metaheuristics , called hybrid me2 taheuristic , can p rovide a more efficient behavio r and a higher a sole metaheuristic is rat her rest rictive. A skilled co mbina2 research fields because of it s intelligence , universality , sta2 researchers in o ur co unt ry have p ut forward lot s of optimiza2 t hat it is difficult or impo ssible to find t he exactly or even ap2

single objective. Based o n t he analysis for t he algorit hm , it s effectivenesses are validated by t he co mpariso ns wit h ot her existing algorit hms on benchmarks wit h different scale and difficulties. Hybrid metaheuristic is a new research area and currently enjoys an increasing interest in t he optimizatio n co mmunity since t he special issue“ Hybrid Metaheuristics” of rit hms was p ublished in 2005. The design and implementa2 questions abo ut t he design of a single metaheuristic. Choice rit hm co mpo nent s. Interactio n can take place at low2level , using f unctions f ro m different metaheuristics , but also at mated hybridization. However , t he field of hybrid metaheu2 ristics is still in it s early days. Many app roaches are p re2ma2 t hat can be generally used for optimization. So , t his work in t his paper will enrich and p ush forward t he st udies of t he re2 high2level , e. g. , using a po rtfolio of metaheuristics for auto2 International Journal of Mat hematical Modelling and Algo2

tion of hybrid metaheuristics rise p ro blems going beyond

lem of how to achieve a p roper interaction of different algo2 t ure and a substantial amount of f urt her research is necessary in o rder to develop clearly st ruct ured hybrid metaheuristics lated areas in both t heoretical and technological aspect s.

and t uning of parameters is for example enlarged by t he p rob2


相关文章:
于田县代理发表职称论文发表-初中数学作业有效性论文选...
混合遗传算法求解包含柔性工艺的作业车间调度问题 32...龙门吊与集卡协同调度问题研究 50……基于自适应蚁群...柔性调度多目标优化的混合粒子群算法研究 60……改进...
粒子群算法综述
粒子群算法就是以模拟鸟的群集智能为特征,以求解 ...群算法属于一种群体搜索方法,具有潜在的自适应性。 ...随机键表示法表示粒子的位置解决单一机器调度问题;...
非线性规划的粒子群算法
多解非线性规划问题的有效的算法,70 年代又得到...杂交和混合粒子群算法(HPSO)是受遗传算法、自然选择...根据粒子群算法提出的自适应多峰生物测定融合算法,...
开题论文
基于粒子群算法的流水车间调度问题研究摘要: 本文研究...设计 T 一种混合遗传算法求解作业车间调度问题,...“重新加温”的自适应温度调节特性,取得了良好的效果...
一种求解多目标柔性作业车间调度的改进粒子群算法
最优解,常用求解算法包括改进的混合遗传算法 0.引言 引言 [1、2] 近年来,多目标柔性作业车间调度问题 、 改进的多目标粒子群算法[3]、 存档进化粒子 [4] (...
粒子群算法实现
这是一种基于种群搜索的自适应进化计算技术,算法最初受到鸟群觅食活动规律性的...此外,H.Yoshida[4]还提出了混合编码的粒子群算法,并用其求解电压控制 问题。...
(70832)航班延误恢复调度的混合粒子群算法
提出了求 解航班延误恢复调度问题的混合粒子群算法。...解决旅行商问题[3-4]、作业车间调度问题[5-7]、...[6] 那加. 基于自适应变异的粒子群优化算法的车间...
粒子群算法在交通领域的应用
算法的求解方法是在粒子群算法中构造了路径条数维的粒子空间, 每一维对应一条...问题, 可采用各种改进的粒子群算法, 如自适应粒子群算法与混合粒 子群算法等...
利用粒子群优化算法优化柔性制造系统中的调度问题
混合粒子群算法在混流装配... 5页 5财富值 用于车间作业调度的粒子群... 5...的研究成果已被用于自动化制造系统设计及运行问题,但是还有很多问题仍然没有解 ...
文献综述
粒子群优化算法、蚁群优化算法等,为解决调度问题提供...加工时间的作业车间调度 问题进行了求解[8]郑晓伟 ...李保 王长华 熊婧 2009 年在 基于自适应蚁群算法的...
更多相关标签: