(模式识别与智能系统专业论文)蚁群优化的理论模型及在生产调度中的应用研究.pdf_第1页
(模式识别与智能系统专业论文)蚁群优化的理论模型及在生产调度中的应用研究.pdf_第2页
(模式识别与智能系统专业论文)蚁群优化的理论模型及在生产调度中的应用研究.pdf_第3页
(模式识别与智能系统专业论文)蚁群优化的理论模型及在生产调度中的应用研究.pdf_第4页
(模式识别与智能系统专业论文)蚁群优化的理论模型及在生产调度中的应用研究.pdf_第5页
已阅读5页,还剩137页未读 继续免费阅读

(模式识别与智能系统专业论文)蚁群优化的理论模型及在生产调度中的应用研究.pdf.pdf 免费下载

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

浙江大学博士学位论文 摘要 本文从蚁群优化算法理论模型角度以及在生产调度问题中的应用角度开展 了如下研究: 定义了蚁群算法考虑结点模式和弧模式信息素分布的解构造图,并把蚁群算 法的解构造过程形象为蚂蚁在解构成元素组成的解构造图上按照分布在弧或者 结点上的信息素指引进行概率性旅行的问题,并提出了蚁群算法基于解构造图的 解空间参数化概率分布模型并在此模型上提出了蚁群算法的统一框架。 基于解空间参数化概率分布模型,首先提出了一个以概率l 收敛于最优解的 解空间概率分布的迭代更新过程,然后提出了通过最小化不同分布问的交互熵距 离以及蒙特卡洛采样来逼近此迭代过程的最小交互熵信息素更新规则,接着分别 给出了弧模式以及结点模式信息素分布模型下的最小交互熵等式。本章还提出了 一种全局归一化的的蚂蚁种子信息素更新规则,该规则能保证分布在整个解构造 图上的信息素的总量保持恒定,同时解决了信息素初始化的问题以及消除了解质 量函数的量纲对算法性能的影响。然后定义了一种特殊的解构造图一矩阵解构 造图,并提出了f l o w s h o p 问题的矩阵解构造图模型,同时针对矩阵解构造图提 出了局部归一化的蚂蚁种子信息素更新规则,该规则能保证分布在矩阵解构造图 每一行结点上的信息素总量保持恒定。此外,还定义了无约束矩阵解构造图,并 证明了无约束矩阵解构造图的局部归一化蚂蚁种子信息素更新规则为最小交互 熵信息素更新规则。本章最后提出了解决并行机调度问题的蚁群算法,该算法把 并行机调度问题映射为无约束矩阵解构造图,并在算法的信息素更新过程中应用 了无约束矩阵解构造图的局部归一化蚂蚁种子信息素更新规则,与其他几个高性 能算法的仿真对比试验证明这种方法是非常有效的。 把组合优化问题描述为一个多阶段序列决策问题,并对蚁群优化算法中解构 造过程所对应的有限状态马尔科夫决策过程用强化学习理论的框架进行描述,同 时说明了所有蚁群算法均满足强化学习理论中基于马尔科夫状态的不完全信息 的广义策略迭代算法框架。此外在强化学习的理论框架内说明了a s 算法是一种 基二于蒙特卡洛方法的强化学习算法,a c s 和a n t q 算法是一种蒙特卡洛方法与 瞬时差分方法在形式上相结合的强化学习算法。本文还在蚁群算法中引入强化学 习的资格迹理论并提出了一个新颖的基于资格迹的蚁群优化算法a n t ( 2 ) ,该算 法实现了蒙特卡洛方法与瞬时差分方法的数学意义上结合,并能使蚂蚁获得的延 迟强化信号及时地在其旅行路径上反向传播。 摘要 提出了f l o w s h o p 问题的一个局部归“一化蚂蚁种子算法a c o _ n o r m ,一个引 入停滞状态脱离机制以及信息素踪迹限制机制的a c os t a g 算法和一个基于资 格迹的a n t q ( 2 ) 算法。算法还提出了一种基于d a n n e n b r i n g 方法的启发式信息。 仿真试验表明,信息素的结点模式总体优于弧模式;启发式信息能较大改进算法 性能;a c os t a g 算法的信息素踪迹更新过程中的停滞状态脱离机制以及信息 索踪迹限制机制能帮助蚂蚁跳出局部最优解;此外a n t q ( 2 ) 算法的资格迹机制 能大大改进采用弧模式解构造图的蚁群算法性能。给出了f l o w s h o p 问题的几种 培于关键路径的邻域结构,并把蚁群算法与邻域搜索相结合构成混合算法,与其 他算法在t a i l l a r d 流水作业调度测试问题集上的比较试验表明,混合算法性能更 优。 提出了混合中间存储策略下多产品间歇生产过程调度问题的一种完成时间 算法,该算法考虑了产品传输时间,与产品生产顺序有关的设备准备时间,中问 存储清洗时间以及中间存储“双传输”对完成时间的影响。采用a c on o r m 和 a c os t a g 算法用于解决多产品间歇生产过程的优化调度问题。还提出了一种 改进的基于d a n n e n b r i n g 方法的启发式信息。仿真试验表明,启发式信息能较大 改进算法性能。为加速算法的收敛,蚁群算法与邻域搜索相结合构成混合算法, 用一些测试问题对本章算法进行试验评价,试验结果表明本章提出的方法的有效 性。 利用受控赋时p e t r i 网对柔性生产线调度中的离散事件建模,在由p e t r i 网仿 真运行获得调度性能评价的基础上,采用两级递阶进化优化方法求解柔性生产过 程的优化调度问题,即由蚁群优化方法优化加工路径,然后对蚁群在信息素指引 下所构造的加工路径,由遗传算法优化在同一机器上加工的作业排序。在蚁群算 法解构造过程中提出了一种有效的启发式信息。测试问题的求解结果说明了算法 的有效性。 提出了一种a c o b a t c h 算法,用于解决有限批量流水线分批与优化调度问 题。在考虑与批处理顺序相关的批处理设备准备时间和产品批在处理设备间的传 输时间基础上,提出了无中间存储策略( n i s ) 和零等待存储策略( z w ) 下流 水作业工序流程的仿真模型和基于此模型的完成时间算法。一组6 0 个仿真测试 问题的求解结果说明了算法的有效性。 关键词:蚁群优化;进化计算;生产调度;组合优化;参数化概率模型; 强化学习;邻域搜索;并行机调度;f l o w s h o p ;多产品间歇生产流水线 混合中间存储策略;柔性j o b s h o p ;受控赋时p e t r i 网;有限批量流水线 浙江大学博士学位论文 l l i a b s t r a c t t h ep h e r o m o n e b a s e dp a r a m e t e r i z e dp r o b a b i l i s t i cm o d e lf o rt h ea c oa l g o r i t h m i sp r e s e n t e da st h es o l u t i o nc o n s t r u c t i o ng r a p ht h a tt h ec o m b i n a t o r i a lo p t i m i z a t i o n p r o b l e mc a nb em a p p e do i l b a s e do nt h e s o l u t i o nc o n s t r u c t i o ng r a p h ,t h eu n i f i e d f r a m e w o r ko f t h ea c o a l g o r i t h m i sp r e s e n t e d a ni t e r a t i v e u p d a t ep r o c e d u r eo ft h e s o l u t i o n sd i s t r i b u t i o ni nt h ep r o b l e m s p r o b a b i l i s t i cm o d e li sp r o p o s e d ,t h a t w i l l c o n v e r g et o t h eo p t i m a ls o l u t i o n sw i t h p r o b a b i l i t yo n e ,t h e nt h em i n i m u mc r o s s e n t r o p yp h e r o m o n eu p d a t er u l ei sp r o p o s e d t o a p p r o x i m a t et h e i t e r a t i v e u p d a t ep r o c e d u r eb ym i n i m i z i n gt h ec r o s s - e n t r o p y d i s t a n c ea n dm o n t e - c a r l os a m p l i n g t h eg l o b a ln o r m a l i z e da n t s s e e dp h e r o m o n e u p d a t er u l ei sp r e s e n t e dt oe n s u r et h a tt h es u m o ft h ep h e r o m o n ed i s t r i b u t e do v e rt h e c o n s t r u c t i o ng r a p hi sac o n s t a n t , i na d d i t i o n ,t h en o r m a l i z e dm e c h a n i s ms o l v e st h e p r o b l e mo fp h e r o m o n ei n i t i a l i z a t i o na n da v o i d st h e i n f l u e n c eo ft h es c a l eo ft h e q u a l i t yf u n c t i o no ft h es o l u t i o n t h el o c a ln o r m a l i z e da n t s - s e e dp h e r o m o n eu p d a t e r u l ef o rt h em a t r i xs o l u t i o nc o n s t r u c t i o ni sp r e s e n t e dt oe n s u r et h a tt h es u n lo ft h e p h e r o m o n e d i s t r i b u t e do v e rar o wo f t h en o d e si nt h ec o n s t r u c t i o ng r a p hi sac o n s t a n t , a n di tc a nb ep r o v e dt h a tf o rt h en o n - c o n s t r a i n e dm a t r i xc o n s t r u c t i o ng r a p h , t h el o c a l n o r m a l i z e da n t s - - s e e dp h e r o m o n e u p d a t er u l ei sar n i n i m u mc r o s s e n t r o p yp h e r o m o n e u p d a t er u l e a sa ne x a m p l e ,t h ep a r a l l e lm a c h i n es c h e d u l i n gp r o b l e m i sm a p p e do na n o n - c o n s t r a i n e dm a t r i xc o n s t r u c t i o ng r a p h ,a n daa c o a l g o r i t h mi sp r o p o s e d t os o l v e t h ep a r a l l e lm a c h i n es c h e d u l i n gp r o b l e m c o m p a r i s o nw i t ho t h e rb e s t p e r f o r m i n g a l g o r i t h m ,t h ea l g o r i t h mw ep r o p o s e d i sv e r ye f f e c t i v e t h ef i n i t ed e t e r m i n i s t i cm a r k o vd e c i s i o np r o c e s sc o r r e s p o n d i n gt ot h es o l u t i o n c o n s t r u c t i o n p r o c e d u r e o fa c oa l g o r i t h mi si l l u s t r a t e di nt h e t e r m i n o l o g y o f r e i n f o r c e m e n t l e a r n i n g ( r 1 0t h e o r y t h e a c oa l g o r i t h m sa r ef i r e di n t ot h e f r a m e w o r ko f g e n e r a l i z e dp o l i c yi t e r a t i o n ( g p i ) i n r lb a s e do n i n c o m p l e t e i n f o r m a t i o no f t h em a r k o vs t a t e f u r t h e r m o r e ,w es h o wt h a tt h ep h e r o m o n e u p d a t ei n t h ea c sa n da n t qa l g o r i t h mi sb a s e do nt h em cm e t h o d so rs o m ef o r m a l i s t i c c o m b i n a t i o no fm cm e t h o d sa n dt dm e t h o d s w ep r o p o s ean o v e la c o a l g o r i t h m , a n t ( 旯) a l g o r i t h m ,b a s e do n t h ee l i g i b i l i t yt r a c e ,t h ea l g o r i t h mu n i f i e st h et dm e t h o d a n dm cm e t h o d m a t h e m a t i c a l l y , a n dc a n m a k et h ed e l a y e dr e i n f o r c e m e n tc a nb eb a c k p r o p a g a t e d i nt i m e s e v e r a ln o v e la c o a l g o r i t h m sa r ep r e s e n t e df o rf l o w s h o ps c h e d u l i n gp r o b l e m f h e r ea r e :a c on o r m a l g o r i t h mw h i c ha p p l i e st h el o c a ln o r m a l i z e da n t s - s e e d na b s t r a c t p h e r o m o n eu p d a t e r u l ef o rt h em a t r i xs o l u t i o n c o n s t r u c t i o n ;t h ea c o s t a g a l g o r i t h mw h i c hi s c h a r a c t e r i z e d b yt h es t a g n a t i o ns t e p o u tm e c h a n i s ma n dt h e p h e r o m o n et r a i l l i m i tm e c h a n i s m ;t h e a n t 一烈五) a l g o r i t h m w h i c hi sb a s e do n e l i g i b i l i t yt r a c e ak i n do f h e u r i s t i ci n f o r m a t i o nb a s e do n t h ed a n n e n b r i n g a p p r o a c h i s i n t r o d u c e di nt h ep r o c e d u r eo fs o l u t i o nc o n s t r u c t i o n t h ee x p e r i m e n ts h o w st h a tt h e s t a g n a t i o ns t e po u tm e c h a n i s m a n dt h ep h e r o m o n et r a i ll i m i tm e c h a n i s mc a n h e l pa n t s s t e p p i n go u to fs t a g n a t i o na n dt h eh e u r i s t i ci n f o r m a t i o ni sv e r ye f f e c t i v e ,i na d d i t i o n , t h e e l i g i b i l i t y t r a c em e c h a n i s mi n a n t q ( i ) a l g o r i t h mc a ng r e a t l yi m p r o v et h e p e r f o r m a n c eo fa l g o r i t h mb a s e do ns o l u t i o nc o n s t r u c t i o ng r a p hi na r cm o d e t h el o c a l s e a r c hp r o c e d u r eb a s e do ns e v e r a lc r i t i c a lb l o c kb a s e dn e i g h b o r h o o ds t r u c t u r ei s h y b r i d w i t h a c o s t a ga l g o r i t h m ,c o m p a r i s o n s w i t ho t h e r w e l l - p e r f o r m e d a l g o r i t h m so n t a i l l a r d sb e n c h m a r k p r o b l e m ss h o w t h a tt h eh y b r i da l g o r i t h mp e r f o r m s b e t t e r a c o m p l e t i o nt i m ea l g o r i t h mf o rt h em u l t i p r o d u c tb a t c hs c h e d u l i n gp r o b l e mi n m i x e di n t e r m e d i a t e s t o r a g e ( m i s ) p o l i c y i s p r o p o s e d t h e t r a n s f e r t i m e , s e q u e n c e - d e p e n d e n ts e t u pt i m eo f e q u i p m e n t , a n dt h ee f f e c to f d o u b l et r a n s f e r r i n ga r e c o n s i d e r e di nt h e a l g o r i t h m b a s e d o nt h i s c o m p l e t i o n t i m e a l g o r i t h m ,t h e a c o s t a ga n da c o n o r ma l g o r i t h m sa r ea p p l i e df o rt h eo p t i m a ls c h e d u l i n go f m u l t i p r o d u c tb a t c hp r o c e s s e s am o d i f i e dd a n n e n b r i n gh e u r i s t i ci si n t r o d u c e di nt h e p r o c e d u r eo fs o l u t i o nc o n s t r u c t i o n i na d d i t i o n , a c oa l g o r i t h mi sh y b r i dw i t hl o c a l s e a r c ht oi m p r o v et h ep e r f o r m a n c e c o m p u t a t i o n a le x p e r i m e n t sd e m o n s t r a t et h a tt h e h y b r i da l g o r i t h m i sv e r ye f f i c i e n t 。 ac o n t r o l l e dt u n e dp e t r i - n e ti su s e di nt h i sp a p e rt om o d e ld i s c r e t ee v e n t si nt h e p r o d u c t i o ns c h e d u l i n go f f l e x i b l ep r o d u c t i o nl i n e s t h i sm o d e li ss y n t h e s i z e db yt h e p r o c e s s f l o ws u b n e t ,t h el t s o u r c es u b n e ta n dt h es c h e d u l i n gs u b n e tb ym e a n so f s y n c h r o n o u s c o m m o nt r a n s i t i o ni n t e r c o n n e c t i o n a h i e r a r c h i c a l e v o l u t i o n a r y o p t i m i z a t i o na p p r o a c ht of l e x i b l ej o b s h o ps c h e d u l i n gp r o b l e m si sp r o p o s e db a s e do b t h es i m u l a t i o ne v a l u a t i o nv i at h ep e t r i - n e tm o d e l t h e p r o c e s s i n gr o u t eo f t h ej o b si s o p t i m i z e db ya na n tc o l o n yo p t i m i z a t i o n ( a c o ) a p p r o a c h ,a n d ,o nt h eb a s i so ft h e o p t i m a lp r o c e s s i n gr o u t e ,ag e n e t i ca l g o r i t h mi sp r o p o s e dt oo p t i m i z et h es e q u e n c eo f t h eo p e r a t i o n sp r o c e s s e do ne a c hm a c h i n e a ne f f e c t i v ef o r mo fh e u r i s t i ci n f o r m a t i o n i si n t r o d u c e di nt h e p r o c e d u r eo f s o l u t i o nc o n s t r u c t i o n ab e n c h m a r k p r o b l e ms o l v i n g r e s u l ti n d i c a t e st h a tt h ep r o p o s e d a l g o r i t h mi sv e r ye f f e c t i v e a p h e r o m o n e n o r m a l i z e da c oa l g o r i t h m ,a c o - b a t c h ,i sp r e s e n t e df o rt h e s i z e l i m i t e db a t c hf l o w - l i n e sb a t c h i n ga n ds c h e d u l i n gp r o b l e m w i t h c o n s i d e r i n gt h e 浙江赶学博士学位论文 v b a t c h e s - - s e q u e n c e - - d e p e n d e n ts e t u pt i m eo ft h eb a t c hp r o c e s s i n gm a c h i n e sa n dt h e b a t c ht r a n s f e rt i m e ,t h es i m u l a t i o nm o d e la n d c o m p l e t i o n t i m ea l g o r i t h mb a s e do nt h e m o d e lw a s p r e s e n t e df o rt h es t o r a g es 订a t e g yo f n oi n t e r m e d i a t es t o r a g e ( h i s ) a n dz e r o w a i t i n gt i m e ( z w ) i nt h ep r i n c i p l eo f t h ea c o ,w e p r o p o s e dt h ep r e s e n t a t i o no f t h e p h e r o m o n e ,t h es t r a t e g yo fs o l u t i o nc o n s t r u c t i o n ,p h e r o m o n eu p d a t i n ga n dl o c a l s e a r c hf o rt h en i s z wf l o w - l i n e s b a t c h i n ga n ds c h e d u l i n gp r o b l e m c o m p a r i s o n s w i t ho t h e ra l g o r i t h m so nt h ee x t e n d e dt a l l l a r d sb e n c h m a r k p r o b l e m ss h o wt h a to u r a l g o r i t h m i sv e r ye f f i c i e n t k e y w o r d s :a n t c o l o n yo p t i m i z a t i o n ;e v o l u t i o n a r y c o m p u t a t i o n ;p r o d u c t i o n s c h e d u l i n g ;c o m b i n a t i o n a lo p t i m i z a t i o n ;p a r a m e t e r i z e d p r o b a b i l i s t i cm o d e l ; r e i n f o r c e m e n t l e a r n i n g ;l o c a ls e a r c h ;p a r a l l e l m a c h i n e s c h e d u l i n g ;f l o w s h o p ; m u l t i p r o d u c tb a t c hs c h e d u l i n g ;m i x e di n t e r m e d i a t es t o r a g ep o l i c y ;f l e x i b l ej o b s h o p ; c o n t r o l l e dt i m e d p e a i - n e t ;s i z e ,l i m i t e db a t c hf l o w - l i n e 塑兰垄兰堡主兰堡堕墨 一! 旦 致谢 值此论文完成之际,我由衷地感谢导师吴铁军教授三年来对我的培养。在这 三年学习和科研工作中,吴教授给予了我悉心的指导,并提供了良好的学习科研 环境。导师渊博的知识,敏捷的思维,严谨的治学态度,踏实的科研和工作作风 尤其是敬业精神为我树立了榜样。导师对知识孜孜以求的精神将时刻激励着我。 在攻读博士学位期间,智能所和控制系的老师和同学也同样给予我许多帮 助,在与他们的讨论中我受到了许多有益的启发,在此表示感谢。同时还要特别 感谢控制系2 0 0 0 秋博士生班的同学,他们的帮助和鼓励给予了我前进中的动力。 感谢我的家人,他们多年来对我的培养和支持为我的学业提供了坚实的后盾 和精神的支持。他们对我无私的爱我将永远铭记在心。 感谢所有关心和支持我的人们! 王笑蓉 2 0 0 3 年5 月于求是园 浙江大学博士学位论文 第一章绪论 摘要 本章介绍了蚁群算法的拟生态原理和一个解决t s p 问题的算法范例,提出了蚁群算法基 于解构造图的解空间参数化概率分布模型,并在此模型上提出了蚁群算法的统一框架。此外 还把蚁群算法与其它基于种群的智能方法作了比较,并介绍了蚁群算法收敛性研究方面的成 果。本章还介绍了蚁群算法的历史和发展现状,并综述了蚁群算法在生产调度问题上的研究。 最后介绍了本文的主要研究内容和成果。 关键词:蚁群算法;解构造图;参数化概率模型;生产调度; 1 1 引言 生产调度问题在理论意义上以及在企业生产实际中都是一个非常重要的问 题,对生产调度问题的研究源于上世纪5 0 年代,是运筹学的一个重要研究分支。 然而,生产调度问题一直以来都是一种未能很好解决的理论难题,而对企业来说, 生产过程中合理的排产与调度对提高设备利用率,消除生产瓶颈,加快生产进程, 减小库存,降低成本等都起着重要的意义。生产过程中,每种产品的生产都需要 特定的生产处理设备和其它资源共同完成,生产调度的作用就是在生产过程中合 理地分配生产资源和安排产品的加工路径和加工处理顺序。典型的生产调度类型 包括单机调度,双机调度,并行机调度,流水线调度( f l o w s h o p ) 和作业调度 ( j o b s h o p ) 等。近几十年来,随着工业的发展,市场竞争的加剧和客户需求的 个性化,现代工业生产方式发生了很大变化,出现了柔性生产方式,具有中间存 储的多产品间歇生产方式,分批生产方式( 组批生产) 等,这些新的生产方式下 的生产调度问题成为理论界新的研究热点。绝大部分调度问题不但约束复杂,而 且属于组合爆炸的n p - h a r d 问题。调度问题的传统的解决方法,如分支定界法, 混合整数线性规划( m i l p ) ,混合整数非线性规划( m 烈l p ) 等数学规划方法在 虽然在理论上能获得最优解,但受到问题维数的制约往往无法满足实际要求。 近年来,人们提出了各种智能算法,如模拟退火( s a ) ,遗传算法( g a ) , 禁忌搜索算法( t s ) 等来解决调度问题,虽然不能保证获得最优解,但在问题 维数较大时也能够在可行时间内找到问题的满意解。这些智能方法无论是理论研 究还是应用研究都空前活跃( 尹文君等,2 0 0 1 ) 。同时,一些新的自然启发式方法 ( m e t a - h e u r i s t i c ) 也逐渐发展起来。意大利学者d 删g o ,m a n i e z z o & c o l o m i ( 1 9 9 1 ) 第一章绪论 受蚁群觅食行为( f o r a g i n gb e h a v i o r ) 中的基于信息素( p h e r o m o n e ) 的间接通讯 机制的启发,提出了一种蚂蚁算法( a n ta l g o r i t h m ) ,并应用该算法求解旅行商 u 题( t s p ) 获得了很好的效果。在上世纪9 0 年代后期,这种算法逐渐引起了 很多研究者的注意,并对算法作了各种改进或应用于其它更为广泛的领域,取得 了一些令人鼓舞的成果。为了给这些算法提供个统一的描述框架,d o r i g o 等研 究者( d o r i g o & d ic a r o ,1 9 9 9 ;d o r i g o ,d ic a r o & g a m b a r d e l l a ,1 9 9 9 ;d o r i g o , b o n a b e a u & t h e r a u l a z ,2 0 0 0 ) 提出了称为蚁群优化( a n tc o l o n yo p t i m i z a t i o n a c o ) 的算法框架,所有符合蚁群优化描述框架的蚂蚁算法都可称之为蚁群优化 算法( a c o a l g o r i t h m ) ,或简称为蚁群算法。研究发现,蚁群优化方法在解决离 散组合优化问题方面有着良好的性能。具有n p h a r d 性的生产调度问题作为组合 优化领域的一个研究热点,也是蚁群算法的一个重要研究方向。 蚁群算法和遗传算法等进化算法均是基于种群的自然启发式方法,q u i n l a n ( 1 9 9 3 ) 把机器学习领域的自然启发式方法分为两类:基于实体( i n s t a n c e - b a s e d ) 方+ 法以及基于模型( m o d e l b a s e d ) 的方法。遗传算法等基于实体的方法用当前的 解或解的种群本身来产生新的候选解,而蚁群算法可以看作一种基于模型的搜索 方法,它通过一个解空间的参数化概率分布模型来产生候选解,此模型的参数用 以前产生的解来进行更新,使得在新模型上的搜索能集中在高质量的解搜索空间 内( 对蚁群算法而言,模型的参数就是信息素) 。蚁群算法较遗传算法等基于实 体的算法而言,其优点是学习的知识分布在解构成元素上,或者说学习的是解构 成元素与这些元素装配在一起后形成的解的质量之间存在的相关关系,而遗传算 法虽然也能隐含地学习构造块( b u i l d i n gb l o c k ) 的知识但这种学习有时是不可靠 的。此外,蚁群算法较其它进化计算方法而言,具有能方便的处理约束条件,能 方便的利用问题启发式信息的优点。 蚁群算法发展至今,虽然很多研究者运用蚁群算法在很多领域获得了成功, 同时人们也出于不同的考虑提出了各种不同版本的蚁群算法,然而绝大部分是经 验性的试验研究,就算法理论来说,缺乏必要的理论框架,及相关理论基础和依 据,对蚁群算法工作机理的认识还停留在拟生态的角度,缺乏必要的数学模型来 进行描述和分析,这在很大程度阻碍了算法的发展。建立蚁群算法的理论模型, 并在模型基础上提出改进的算法,或对原有算法进行机理分析以及将这些算法推 f “到更为复杂的贴近实际的问题上将对蚁群算法的发展起到积极的推进作用。 本文的一个重要研究内容就是为蚁群算法建立理论模型,并在理论模型的基 础上对蚁群算法的工作机理进行分析,此外在机理分析的基础上对蚁群算法的几 个主要组成部分( 如解构造过程,信息素更新过程) 进行改进以及提出新的更有 理论依据,性能更有保证的算法。本论文的前三章就是在这个方面开展研究。 在建立蚁群算法的理论模型,并基于此模型提出算法性能更有理论依据的新 浙江大学博士学位论文 的蚁群算法之外,如何应用蚁群算法于生产调度领域是本文的另一个主要研究内 容。判断一种新的方法的有效性总要把其付诸于实践,象遗传算法等更早出现的 自然启发式方法已经广泛应用于生产调度领域,而蚁群算法在生产调度领域的研 究成果非常有限,到目前为止,所研究的问题绝大部分均是经典的理论问题,即 使是这些经典问题的研究也还有很多不足之处。同时,研究如何利用蚁群算法来 解决一些更为实际的生产调度问题,不仅对于蚁群算法的发展具有积极的推动作 用,同时也为解决生产调度问题提供了一个新的很有前景的方法。 本论文从蚁群算法于生产调度中的应用角度就以下三个方面进行研究:一是 研究生产调度问题本身,比如对生产过程建模,提出求取调度性能指标的递归计 算方法或p e t r i 网仿真方法以及分析调度解空间分布的特点,并提出更为高效的 问题解空间的邻域结构;二是研究如何建立与所研究问题相对应的蚁群算法信息 素模型,信息素模型的信息素参数与由此模型产生的解的质量间的相关程度将决 定算法的总体性能:三是研究在给定算法信息素模型下,如何获得蚁群算法可利 用的有效的基于问题启发式信息;三是改进算法中的解构造规则,信息素更新规 则,或者与诸如邻域( 局部) 搜索等算法相结合得到混合的蚁群算法以提高算法 性能。 1 2 蚁群算法基本原理 蚁群算法是受到对真实蚁群行为的研究的启发而提出的。生物学研究表明一 群互相协作的蚂蚁能够找到食物源和巢之间的最短路径,而单只蚂蚁则不能。生 物学家经过大量细致观察研究发现,蚂蚁个体之间是通过一种称之为信息素的物 质进行信息传递的。蚂蚁在运动过程中,能够在它所经过的路径上留下该种物质, 而且蚂蚁在运动过程中能够感知这种物质,一条路上的信息素踪迹越浓,其它蚂 蚁将以越高的概率跟随此路径,从而该路径上的信息素踪迹会被加强,因此,由 大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象:某一路径上走过 的蚂蚁越多,则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种间 接的通信机制达到协同搜索食物最短路径的目的。下面我们引用d o r i g o , m a n i e z z o & c o l o m i ( 1 9 9 1 ) 所举的例子来具体说明蚁群系统的原理: 如图1 1 所示,假设蚂蚁以1 单位长度单位时间的爬行速度往返于食物源a 和巢e ,其中d 为距离,每过个单位时间各有3 0 只蚂蚁离开巢和食物源( 图 1 1 ( a ) ) 。 第一章绪论 ( a ) 各有3 0 只准备离开b 和d ( b ) 各有1 5 只选择c 和f ( c ) 2 0 只选择c ,1 0 只选择f 图1 1蚁群觅食行为示意图 假设t = 0 时,有3 0 只蚂蚁在点b 和点d ( 图1 1 ( b ) ) 。由于此时路上无信息 索,蚂蚁就以相同的概率走2 条路中的一条,因而1 5 只蚂蚁选择往c ,其余1 5 只选择往f 。t = 1 时,经过c 的路径被3 0 只蚂蚁爬过,而路径b f 和d f 只被 1 5 只蚂蚁爬过,从而b c d 上的信息素踪迹的浓度是b f d 的2 倍。此时,又有 3 0 只蚂蚁离开b ( 和d ) ,于是各有2 0 只蚂蚁选择往c ,另外l o 只蚂蚁选择往f , 这样更多的信息素被留在更短的路径b c d 上,这个过程一直重复,短路径b c d i 二的信息素踪迹的浓度以更快的速度增长,越来越多的蚂蚁选择这条短路径。 通过上例可知蚂蚁觅食协作方式的本质是:信息素踪迹越浓的路径,被选 中的概率越大,即路径概率选择机制;路径越短,在上面的信息紊踪迹增长得 越快,即信息素更新机制;蚂蚁之间通过信息素进行通信,即协同工作机制。 以上介绍了蚁群算法拟生态学意义上的原理,蚁群优化算法正是受到这种生 态学现象的启发,并运用于求解优化问题。蚁群算法的机理可以抽象为以下过程: 在蚁群优化算法中,作为分布智能体( d i s t r i b u t ea g e n t ) 的人工蚁( a r t i f i c i a l a n t s ) 的行为可以如下描述:一群人工蚁相互协作在问题的解空间中搜索好的解, 这些人工蚁按照人工信息素踪迹( a r t m c i a lp h e r o m o n et r a i l s ) 和基于问题的启发 式信息的指引在问题空间移动以构造问题的解。在此,信息素( p h e r o m o n e ) 类 似于一种分布式的长期记忆,这种记忆不是局部地存在于单个的人工蚁,而是全 局地分布在整个问题空间。当人工蚁在问题空间中移动时,他们在其经过的路径 上留下信息素踪迹,这些踪迹反映了人工蚁在问题空间觅食( 即构造好的解) 过 程中的经历。换句话说,信息素在蚁群的协作和通讯中起到一种间接媒介的作用, 研究社会型生物种群的学者称这种媒介为协同机制s t i g m e r g y ( d o r i g o ,m a n i e z z o & c o l o m i ,1 9 9 l ;d o r i g o ,b o n a b e a u & t h e r a u l a z ,2 0 0 0 ) 。人工蚊群在解空间中 步一步地移动从而构造问题的解,同时,他们根据解的质量在其路径上留下相 应浓度的信息素,蚁群中的其他蚂蚁倾向于沿着信息素浓的路径前进,同样这些 蚂蚁也将在这段路径上留下自己的信息素,这就形成了一种自催化强化学习 浙江大学博士学位论文 ( a u t o c a t a l y t i cr e i n f o r c e m e n tl e a r n i n g ) 机制,也就是正反馈( p o s i t i v ef e e d b a c k ) 。 这种正反馈机制将指引蚁群找到高质量的问题解,在此意义上,蚁群算法是一种 基于蒙特卡洛方法的强化学习算法。 除人工蚁的觅食行为外,蚁群优化算法还包括另外两个机制:信息素挥发 ( p h e r o m o n e t r a i l e v a p o r a t i o n ) 和后台行为( d a e m o n a c t i o n s ) ( d o r i g o & d i c a r o , 1 9 9 9 ) 。遗忘

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论