自适应差分进化算法解决多目标有限缓冲车间调度问题研究

发布时间：2017-07-27 04:01

  本文关键词：自适应差分进化算法解决多目标有限缓冲车间调度问题研究

  更多相关文章： 自适应 多目标 差分进化 流水车间调度 缓冲区 次解保留

【摘要】：流水车间调度问题(flow shop scheduling problem,FSSP)是优化组合问题的一个重要分支,对该问题的研究有利于实现有限资源的优化配置和合理利用。但因该问题为NP-hard(non-deterministic polynomial-hard),人工智能算法如今正逐渐代替数学方法,并取得了一定的成果。FSSP有多种类型,而带有限缓冲的FSSP(FSSP with limited buffers,FSSPWLB)因更接近实际生产状况而受到广泛重视,对缓冲大小的探讨在实际生产应用中也具有重要的经济价值。此外,求解多目标FSSP,可帮助决策者制定折中策略,在满足客户需求的前提下实现经济最大化等其他生产指标。因此研究多目标带有限缓冲的FSSP就显得尤为重要。差分进化(differential evolution,DE)算法因其良好的特性而大量运用于连续问题优化中。该算法的参数对所优化的问题具有敏感性,通常要根据反复实验的结果或经验来设置,因此造成计算资源的额外开销,同时受到先验经验的制约。于是对自适应差分进化算法的研究不断涌现,其应用领域也不断拓宽。在使用DE对FSSPWLB进行优化时,因其测试实例规模不同,更需要自适应机制的参与。综上所述,本文提出了一种自适应差分进化算法及其若干变体,来解决多目标FSSPWLB。目前看来,使用自适应差分进化算法优化多目标FSSPWLB尚属首例。首先,本文使用最大顺序值(largest order value,LOV)规则完成DE个体与工件排序的映射,为设计合理的自适应机制,分析了DE个体、工件排序以及目标值差异之间的关系,研究参数F和CR对目标值的影响。在此基础上提出了一种参数CR的自适应差分进化算法,以适应对算法不同的搜索需求。同时为保证初始种群的质量,使用启发式算法构造了两个特殊个体。其次,为加强算法局部搜索性能,除选择插入算子(Insert)外,还设计了一种基于概率模型的局部搜索算子(local search based on probability model,LSbPM),目的在于挖掘非支配解集中的优质子序列信息,并加以利用。引入次解保留概念,将其嵌入Insert中,保留多次插入过程中产生的次解,充分运用搜索结果,在一定程度上补偿随即抛弃被支配解而造成的计算浪费。接着,为验证本文所提出算法的各项性能的优劣,设计了其他两种变体,分别去除了LSbPM算子和次解保留机制,三种算法分别记为MPADE1、MPADE2和MPADE3,且与HDE做对比。选取三种不同基准集中的12个实例,以多项评价指标为参考,通过实验对比三种算法与HDE。实验表明,次解保留机制在算法中发挥了重要作用,使得MPADE1和MPADE3在性能上超越MPADE2和HDE。而LSbPM的效果并不理想,只有在评价次数较大时才能起到改善作用。整体来说,MPADE3是最好的算法,能够获得更多的非支配解,保证其质量,在分布性上也比其他算法好。最后,MPADE3用以研究与HDE收敛特性的差别,并分析不同缓冲区容量对FSSPWLB优化结果的影响。实验结果表明,MPADE3具有较快的收敛速度和较好的分布性。缓冲区在加工过程中具有重要作用,且所优化目标值的提升与缓冲区容量的增长不成正比,而是逐渐放缓的,这一结论可为机器配置提供指导。
【关键词】：自适应 多目标 差分进化 流水车间调度 缓冲区 次解保留
【学位授予单位】：郑州大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP18;TB497
【目录】：

• 摘要4-6
• Abstract6-11
• 1 绪论11-18
• 1.1 研究背景及意义11-13
• 1.2 国内外研究现状13-16
• 1.3 论文的主要工作及章节安排16-18
• 2 差分进化算法发展18-28
• 2.1 差分进化算法18-20
• 2.2 多目标自适应差分进化算法20-26
• 2.2.1 多目标优化问题（MOP）20-25
• 2.2.2 多目标自适应差分进化算法25-26
• 2.3 本章小结26-28
• 3 有限缓冲流水车间调度28-37
• 3.1 数学模型28-30
• 3.2 目标函数30-32
• 3.3 测试基准集32-33
• 3.4 解的表示33-36
• 3.5 缓冲区大小36
• 3.6 本章小结36-37
• 4 自适应差分进化算法设计37-60
• 4.1 PADE算法设计38-46
• 4.1.1 差分进化个体、工件序列与目标值的关系39-41
• 4.1.2 排序多样性41-45
• 4.1.3 参数自适应机制45-46
• 4.2 MPADE算法实现及流程46-54
• 4.2.1 种群初始化46-47
• 4.2.2 局部搜索47-52
• 4.2.3 非支配解集更新52
• 4.2.4 算法流程52-54
• 4.3 MPADE算法性能测试54-59
• 4.3.1 参数设置54
• 4.3.2 多目标优化评价指标54-55
• 4.3.3 实验结果与分析55-59
• 4.4 本章小结59-60
• 5 基于MPADE3的特定分析60-64
• 5.1 收敛性分析60-61
• 5.2 缓冲区影响研究61-63
• 5.3 本章小结63-64
• 6 结论与展望64-66
• 6.1 论文总结64
• 6.2 工作展望64-66
• 参考文献66-73
• 致谢73-74
• 个人简历、在学期间发表的学术论文与研究成果74

【相似文献】

中国期刊全文数据库 前10条

1 王艳宜;;改进差分进化算法及其应用[J];机械设计与研究;2010年05期

2 张鹏;;基于差分进化的混合地面等待优化策略[J];桂林航天工业高等专科学校学报;2012年03期

3 宁桂英;周永权;;一种求解二重积分的差分进化算法[J];哈尔滨理工大学学报;2013年02期

4 王惠卿;;结合机械设计约束处理的差分进化算法[J];电子制作;2013年13期

5 蔡亮;杨启文;岳兴汉;;一种基于混合差分策略的改进差分进化算法[J];河海大学常州分校学报;2007年04期

6 谭跃;谭冠政;;混沌局部搜索策略的差分进化算法[J];重庆工学院学报(自然科学版);2009年05期

7 万东;;差分进化算法研究及其应用[J];科学技术与工程;2009年22期

8 乔英;高岳林;江巧永;;一种新局部搜索策略的差分进化算法[J];太原理工大学学报;2011年04期

9 曲福恒;胡雅婷;杨勇;谷欣超;;改进差分进化算法及其在模糊聚类分析中的应用[J];长春理工大学学报(自然科学版);2011年04期

10 黄林峰;;基于离散差分进化算法的多维0/1背包问题求解[J];硅谷;2012年20期

中国重要会议论文全文数据库 前10条

1 陆丝馨;肖健梅;王锡淮;;基于改进差分进化算法的舰船电网重构[A];第二十九届中国控制会议论文集[C];2010年

2 楼洋;李均利;陈刚;;基于个体排序的差分进化算法[A];'2010系统仿真技术及其应用学术会议论文集[C];2010年

3 张倩;李海港;;多目标问题的差分进化算法研究[A];2009年中国智能自动化会议论文集（第一分册）[C];2009年

4 裴振奎;刘真;赵艳丽;;差分进化算法在多目标路径规划中的应用[A];中国运筹学会模糊信息与模糊工程分会第五届学术年会论文集[C];2010年

5 刘国帅;杨侃;陈静;周景舒;周冉;郑姣;;差分进化算法在三峡电站厂内经济运行中的应用[A];中国水文科技新发展——2012中国水文学术讨论会论文集[C];2012年

6 刘潇;桂卫华;王雅琳;王晓丽;阳春华;;一种改进的多目标差分进化算法研究[A];中国自动化学会中南六省（区）2010年第28届年会·论文集[C];2010年

7 赵娟;蔡涛;邓方;杨红伟;;基于改进差分进化算法的脉冲控制方法[A];中国自动化学会控制理论专业委员会B卷[C];2011年

8 袁沈坚;顾幸生;;基于差分进化的膜计算优化算法[A];上海市化学化工学会2010年度学术年会论文集（自动化专题）[C];2010年

9 姜立强;郭铮;刘光斌;;差分进化算法缩放因子取值策略研究[A];2007'仪表，自动化及先进集成技术大会论文集（二）[C];2007年

10 倪惠康;杜文莉;钱锋;;基于改进差分进化算法的PID参数优[A];2009年中国智能自动化会议论文集（第一分册）[C];2009年

中国博士学位论文全文数据库 前10条

1 孙浩;差分进化多目标优化算法及其在铝热连轧轧制规程中应用[D];燕山大学;2015年

2 陈盈果;面向任务的快速响应空间卫星部署优化设计方法研究[D];国防科学技术大学;2014年

3 谢宇;差分进化的若干问题及其应用研究[D];南京理工大学;2015年

4 丁青锋;基于元胞自动机的差分进化算法及其在通信系统中的应用研究[D];上海大学;2015年

5 贾东立;改进的差分进化算法及其在通信信号处理中的应用研究[D];上海大学;2011年

6 刘荣辉;多阶段自适应差分进化算法及应用研究[D];东华大学;2012年

7 郭鹏;差分进化算法改进研究[D];天津大学;2012年

8 王旭;改进差分进化算法及其在可逆逻辑综合中的应用[D];东华大学;2013年

9 董明刚;基于差分进化的优化算法及应用研究[D];浙江大学;2012年

10 王天意;大地电磁迭代有限元与改进差分进化正反演算法研究[D];中国地质大学(北京);2015年

中国硕士学位论文全文数据库 前10条

1 高静;量子差分进化算法在油田开发中的应用研究[D];浙江大学;2015年

2 万婧;基于离散微粒群算法和混合差分进化算法的复杂生产调度问题求解[D];昆明理工大学;2015年

3 张转;基于差分进化算法的混凝土德拜模型的研究[D];长安大学;2015年

4 江华;差分进化算法的改进及其在K-means聚类算法中的应用[D];华中师范大学;2015年

5 周志刚;基于差分进化算法的信用风险度量模型研究[D];华中师范大学;2015年

6 任甜甜;差分进化算法在反演问题中的研究与应用[D];新疆大学;2015年

7 杨洋;基于差分进化的模糊C-均值聚类算法研究[D];电子科技大学;2015年

8 王丹;基于辅助函数的自适应差分进化算法研究[D];西安电子科技大学;2014年

9 刘家华;基于进化计算的轧制生产过程操作优化算法与系统开发[D];东北大学;2013年

10 王旦平;圆形对称振子阵列天线基于差分进化算法的综合[D];西安电子科技大学;2014年

，

本文编号：579656