基于区块的两阶段进化算法在多目标车间调度中的研究

发布时间：2020-04-23 23:45

【摘要】：多目标流水车间调度问题是实际生产活动中经常应用的一类组合优化问题,其主要是在满足相关约束的条件下,对工件和加工机器进行合理地排列组合,以使最终的绩效指标整体最优化。不同于单目标车间调度问题,多目标需要同时考虑两个及两个以上的目标以使总体达到最优,大大增加了问题难度,使求解过程变得更为复杂。因此,对多目标流水车间调度进行研究具有一定的应用价值。目前求解多目标流水车间调度问题的算法很多,但是很多算法在求解大规模复杂问题时往往存在较多限制。两阶段子群遗传算法(Two PhaseSub PopulationGenetic Algorithm,TPSPGA)虽然在解的多样性上有很大的优势,但求解质量有待进一步提高。基于分解的多目标进化算法(Multi-Objective Evolutionary Algorithm based on Decomposition,MOEA/D)由于种群规模和权重向量一直不变,在解的多样性上存在不足。在进化机制方面,传统的进化方法由于交叉、变异等随机机制在后期会破坏优势解,导致解的质量下降。本文针对流水车间调度的最小化总完工时间与最小化最大流程时间两个目标,提出一种基于区块的两阶段进化算法(Block-based Two Phase Evolutionary Algorithm,BTPEA)来求解生产调度优化问题。该算法分为两个阶段,第一阶段将种群分为若干个子群体,对每个子群体权重赋值,第二阶段将子群体重新合并成一个大群体,采用且比雪夫分解策略对群体分解。该算法的进化机制是通过若干代的传统遗传算产生较优子代,借鉴蚂蚁信息素浓度的思想对子代建立位置信息素矩阵和相依信息素矩阵并根据两矩阵挖掘区块,将区块与非区块重组形成人工染色体。最后对染色体进行重组,提高染色体的质量并使用二元竞赛法保留优势染色体。为了比较的算法的求解性能,使用Taillard标准实例对BTPEA、TPSPGA、MOGA/D、NSGA-II、SPEA-II等多种算法测试,并对测试结果进行分析。在解的分布上,BTPEA均处于图的最左下方,即都取得了较优的解。在D1_R值上,BTPEA取得了最低值,说明了该算法在解的多样性和收敛性上具有较优的求解效果。在C指标上,在C(A,x)的值均等于1或略小于1(A表示BTPEA,X表示其它算法),证明了该算法求得的解的质量较高。在计算机的运行时间上,BTPEA的运行时间明显低于其他算法。
【图文】：

图 1.1 进化算法分类Fig. 1.1 Evolutionary algorithm classification现对目前较为经典的进化算法进行分析：1. VEGA（Vector Evaluated Genetic Algorithm）：VEGA 是由 Schaffer[56]所提出的用于求解多目标最优化问题的 Pareto 最优化，此方法是在传统遗传算法上发展而来首先将配对池分解若干个大小的子配对池，并对子配对池赋一目标i ，然后从种群取指定目标较优的染色体并复制到对应目标的子配对池中，这样不断选择，直到所子配对池都装满染色体。最后将子配对池中所有的染色体混合，进行交配、突变等法虽然提高了较优染色体被选取的机会，，但是解的多样性表现差。2. MOGA（Multi-Objective Genetic Algorithm）：MOGA 是由 Fonseca 等[58]所提出此方法主要是在每一代将种群进行分级，其中，非支配解的等级为一，其余的被支解的等级依次加一，另外还使用了适应度均分方法，在同一等级的个体均分适应度同一等级的个体具有相同的适应度。但是适应度均分方法需设定参数，增加的算法用难度。3. NSGA（Non-dominated Sorting Genetic Algorithm）：NSGA 由 Deb 等[59]于 199先提出，并于 2000 年对其改进提出一种 NSGA-II[60]。NSGA 在选择的方法上与传

Pareto前沿图
【学位授予单位】：天津理工大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：TP18;TB497

【相似文献】

相关期刊论文 前10条

1 谷峰,陈华平,卢冰原,古春生;粒子群算法在柔性工作车间调度中的应用[J];系统工程;2005年09期

2 ;工业上应用成果[J];微计算机信息;1989年04期

3 张守刚;吴龙成;王艳;纪志成;;基于分布估计算法的硫化车间调度[J];系统仿真学报;2017年09期

4 马慧民;叶健飞;;柔性车间调度与设备维护的联合优化研究[J];机械设计与制造;2015年07期

5 黄英杰;姚锡凡;;基于目标级联法和粒子群算法的柔性分布式车间调度[J];中南大学学报(自然科学版);2012年01期

6 朱良学;;遗传算法在车间调度中的应用[J];软件导刊;2007年17期

7 季娜;蔡红霞;钱晖;;基于滚动时域优化策略的玻璃深加工车间调度研究[J];工业控制计算机;2017年03期

8 高亮;高海兵;周驰;;基于粒子群优化的开放式车间调度[J];机械工程学报;2006年02期

9 谷峰;陈华平;卢冰原;;基于遗传算法的模糊柔性工作车间调度优化[J];系统工程与电子技术;2006年07期

10 谷峰;陈华平;卢冰原;;基于均匀设计的多目标遗传算法在柔性工作车间调度中的应用[J];系统工程理论方法应用;2006年06期

相关会议论文 前10条

1 谷峰;陈华平;卢冰原;;自适应多目标遗传算法在柔性工作车间调度中的应用[A];系统仿真技术及其应用（第7卷）——'2005系统仿真技术及其应用学术交流会论文选编[C];2005年

2 李桂芬;鞠彦兵;;基于仿真和遗传算法的车间调度优化方法研究[A];2006中国控制与决策学术年会论文集[C];2006年

3 魏杰;李铁克;;基于随机性参数混合免疫算法的工艺车间调度研究[A];第十一届全国自动化应用技术学术交流会论文集[C];2006年

4 陈可嘉;季平;;一种集成MRP与车间调度的混合整数规划模型[A];2006年中国运筹学会数学规划分会代表会议暨第六届学术会议论文集[C];2006年

5 张秀丽;黄越;刘念;;基于混合优化算法的多目标柔性工作车间调度[A];Proceedings of 2010 Chinese Control and Decision Conference[C];2010年

6 朱晓东;;基于TC-TPN的SMT产品制造系统车间调度[A];2008中国电子制造技术论坛论文集[C];2008年

7 张翠林;王烁;王军强;;考虑约束松弛的柔性流水调度研究[A];发展战略性新兴产业，助推新能源装备制造——2014年第四届全国地方机械工程学会学术年会暨新能源装备制造发展论坛论文集[C];2014年

8 甘屹;李胜;;蚁群算法的参数优化配置研究[A];全国先进制造技术高层论坛暨第九届制造业自动化与信息化技术研讨会论文集[C];2010年

9 刘辙;彭亮;崔广才;吴学礼;;混合遗传算法在车间调度中的应用[A];中国自动化学会全国第九届自动化新技术学术交流会论文集[C];2004年

10 姚丹;郭放;石金华;;基于混合算法的网络化制造车间调度研究[A];全国先进制造技术高层论坛暨第七届制造业自动化与信息化技术研讨会论文集[C];2008年

相关重要报纸文章 前5条

1 田晓翠邋郑瑞丹;念好质量经打好安全牌[N];人民铁道;2008年

2 通讯员 谢晓刚;信息化让设备质量管理耳聪目明[N];人民铁道;2009年

3 张立民;印刷企业创新要多角度深切入[N];中国新闻出版报;2010年

4 通讯员 朱明熹;小改造做出节支大文章[N];人民铁道;2009年

5 王继征;ERP既带来技术也带来理念[N];中国纺织报;2007年

相关博士学位论文 前10条

1 鞠全勇;智能制造系统生产计划与车间调度的研究[D];南京航空航天大学;2007年

2 金亮亮;基于网络图与工艺规划集成的车间调度建模与优化[D];华中科技大学;2016年

3 林仁;离散制造企业资源弹性约束下作业车间调度问题研究[D];西南交通大学;2016年

4 王芳;面向碳效优化的柔性流水车间调度研究[D];华中科技大学;2017年

5 李新宇;工艺规划与车间调度集成问题的求解方法研究[D];华中科技大学;2009年

6 黄云峰;车间调度和谐范式与多智能体系统情智集成的研究[D];重庆大学;2010年

7 曾强;离散制造企业批量生产车间调度智能优化研究[D];重庆大学;2010年

8 温海骏;不确定环境下再制造生产计划与车间调度集成优化研究[D];合肥工业大学;2015年

9 王桂荣;分时电价下炼钢连铸生产调度优化方法[D];山东大学;2017年

10 郭文胜;基于敏捷制造模式的虚拟车间协同作业原理与应用实践[D];四川大学;2002年

相关硕士学位论文 前10条

1 张春花;基于区块的两阶段进化算法在多目标车间调度中的研究[D];天津理工大学;2019年

2 张雪芳;基于列生成算法的柔性车间调度研究[D];浙江工业大学;2018年

3 王晶;阻塞混合流水车间调度优化研究[D];郑州大学;2019年

4 魏亮旗;基于改进人工蜂群算法的车间调度优化的研究与应用[D];安徽大学;2019年

5 公旭冉;面向双柔性多目标工作车间调度的智能算法研究[D];湖南大学;2018年

6 李浩;基于粒子群优化算法的车间调度系统的研究与设计[D];宁夏大学;2018年

7 任清华;双柔性流水车间调度及其与运输集成调度研究[D];湖南大学;2018年

8 程冰;基于群体智能算法的车间调度方法研究[D];江南大学;2018年

9 魏鑫;面向多目标优化的改进型多Agent车间调度技术研究[D];南京航空航天大学;2018年

10 杨德博;基于候鸟优化算法的开放车间调度研究[D];华中科技大学;2017年

本文编号：2638289