基于神经网络学习方法的单机调度问题研究

发布时间：2020-08-20 17:30

【摘要】：单机调度问题作为生产调度问题中最重要的成员之一,大量存在于现实生活中,具有广泛的应用背景。在某些情况下多机以及其他复杂调度问题通常可分解成若干个单机调度问题的求解。因此,单机调度问题的研究对于有效的利用资源、提高生产效率,具有十分重要的意义。很多单机调度问题己被证明是NP-hard问题,现有的求解方法对于解决实际调度问题仍然存在其局限性。基于学习的神经网络算法具有良好的自适应性、稳定性、自学习能力、泛化能力,在诸多领域得到了有效的应用。本文选择基于神经网络的学习算法对单机调度问题进行研究,在现有研究工作的基础上,选择Pointer Networks作为网络框架,分别采用监督学习、强化学习两种方法对算法的有效性、学习能力、泛化能力进行探究。经过验证,算法能为单机调度问题提供一个较好的近似最优解,结合所提出的滚动优化策略,在大规模问题上展现了较好的适应性。全文的主要工作归纳如下:·根据调度问题的特征选取LSTM网络构建了基于Pointer Networks的监督学习模型对单机调度问题进行建模,采用拉格朗日松弛方法构建训练所需的数据集。最后通过大量的实验仿真验证了算法的有效性,探究了算法的最优参数以及泛化能力。·为了提高算法在大规模调度问题上的泛化能力,结合上章所提出的监督学习模型,提出了一种滚动优化策略,将大规模调度问题分解为小规模调度问题进行求解。通过仿真实验证实,改进后的算法在大规模调度问题上的泛化能力得到了大幅提升。·针对监督学习算法的性能极度依赖训练数据质量的现象,将强化学习与Pointer Networks进行结合,为单机调度问题建立了一个非监督的学习模型。与本文监督学习模型进行了仿真对比,验证了算法的有效性。
【学位授予单位】：厦门大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：F49;TP18
【图文】：

拓扑结构图,时序,拓扑结构,输入门

逦ｈｔ邋＝邋ｏｔ０ｔａｎｈ邋（ｃｔ）逡逑Ｘｉ逡逑图２－４邋ＬＳＴＭ网络单元结构逡逑其中0■为非线性激活函数，取值范围（0，１），输入门、输出门、遗忘门和记忆单兀逡逑均受到当前时刻输入Ｘｔ，上一时刻的输出，以及偏置６的影响。由图及相关公式可逡逑看出当ｉｔ邋＝邋０邋（输入门关闭），／ｔ邋＝邋ｌ邋（遗忘门打开）时，记忆单元Ｃｔ的信息可一直保逡逑持。ＬＳＴＭ在时序上的拓展如图２－５所示：逡逑ｒ＾１逦＜逡逑输出层：ｙｆ逦Ｊ邋…逦＊＊？邋Ｊ逡逑ｐ邋＾邋…Ｄ．逡逑隐层：一……１逦．一－邋＼逦ｖ；＇逦＾逡逑ｓ逦ｓ逦Ａ逡逑输入层：ｘｔ逡逑时序：ｔＥ［ｌ；Ｔｘ】逦ｔ＝ｌ邋？？？逦ｔ＝ｊ邋？？？邋ｔ＝Ｔｘ逡逑图２－５邋ＬＳＴＭ时序上的拓扑结构逡逑箭头表示记忆单元存储的信息在时序上的流动方向，可以看出与ＣＮＮ和其他神经逡逑网络不同，ＬＳＴＭ在时序上进行了拓展，即ＭＬＰ邋（多层神经网络）会在时序的维度上进逡逑行延伸，ＬＳＴＭ对输入特征的处理并非一次全部输入完成，而是在每个时序上进行当前逡逑时刻的输入，这决定了邋ＬＳＴＭ可以借助当前值和历史数据更好地预测时间序列。这里我逡逑２１逡逑

网络单元,输入门,时序

其中0■为非线性激活函数，取值范围（0，１），输入门、输出门、遗忘门和记忆单兀逡逑均受到当前时刻输入Ｘｔ，上一时刻的输出，以及偏置６的影响。由图及相关公式可逡逑看出当ｉｔ邋＝邋０邋（输入门关闭），／ｔ邋＝邋ｌ邋（遗忘门打开）时，记忆单元Ｃｔ的信息可一直保逡逑持。ＬＳＴＭ在时序上的拓展如图２－５所示：逡逑ｒ＾１逦＜逡逑输出层：ｙｆ逦Ｊ邋…逦＊＊？邋Ｊ逡逑ｐ邋＾邋…Ｄ．逡逑隐层：一……１逦．一－邋＼逦ｖ；＇逦＾逡逑ｓ逦ｓ逦Ａ逡逑输入层：ｘｔ逡逑时序：ｔＥ［ｌ；Ｔｘ】逦ｔ＝ｌ邋？？？逦ｔ＝ｊ邋？？？邋ｔ＝Ｔｘ逡逑图２－５邋ＬＳＴＭ时序上的拓扑结构逡逑

时间序列,结构示意图,时序,输入门

【相似文献】