一种基于遗传算法的作业车间调度问题的解决方案，陈浩哲，王晨升，作业车间调度问题(job shop scheduling problem，JSP)是复杂调度问题类型之一，有十分重要的研究意义和工程价值。本文以标准遗传算法为基础�
山国武技论文在线 针对这问题,本文提岀使用神经网络对了代适应度数据进行记录。神经网络在 记录大量数据方面拥有着巨大的优势。以单点父叉为例,我们只需要将两父代的基因输入神 经网络,再将某一交叉点所生成子代的适应度作为神经网络对应位置的输出,用此输入和输 出作为训练神经网终的数据,神经网终就能记录两父代,某一交叉点下子代的适应度。如此 遗传算法的每次迭代中都有种群数量个训练数据,而神经网络就能对这些子代适应度数据进 行记录。使用神经网络后,我们不需要用人规模的表格冇储和査找数据,只需要对网络的进 行训练,再将数据带入网络计算结果即可。 开妗 广生初始种群 解码 计算适应度 川练神经网络 是否到 达终 Y公 条件 N 近择 变异 红选取两个父 神经网络计算 子代适应度 交叉 代步数k自增1 图改走算法的流程 改进算法的流程如图一所示,改进算法的流程与传统遗传算法有点不同,其一,计算 适应度后添加了训练神经网络的步骤;其,交叉之前需要使用训练好的网络计算子代适应 度;最后,为了保证上次循环巾交叉操作和下次循环中训练网终之间种群不会发生改变,原 本放在交叉操作之后的变异操作提前到了选择操作之后。 本算法除神经网络步骤外,其他步骤与传统的遗传算法基本一致,所以,本章着重讲解 神经网络部分。要使用袒经网络首先需要决定输入和输出的形式。以的作业车间调度问 题为例,使用基于工序的编码后,一个作业车间的调度方案需要个数字表小,即一个父 代拥有个基因。而进行交叉操作需要两个父代,因此,网络需要使用两个父代作为输入 山国武技论文在线 计算了代的适应度,那么,神经网络的输入单元个数应该是 个。交叉方式选择单点 交叉,那么两个父代每个基因都可能被选为交叉点,因此对于任意两父代来说,总共有 种交叉方式,所以,神经网络的输出单元数应该是个。现在,神经网络的输入和输出 都已确定,输入时两个父代的基因,共个数字;输出对于两父代,所有交叉情况下的子 代适应度,共个数字 为了使网络记录的子代适应度与交叉点对应,需要使用二维数组记录适应度。改进算法 需要将子代适应度放入和交叉点对应的位置,原本传统遗传算法计算适应度后会将适应度放 入一个一维数组,而现在,我们需要将适应度放入一个二维数组,如表所示。横向来看 二维数组中,每行仍然只有一个适应度,且每行的适应度与原本一维数组中每行的适应度相 对应。不同的是每行适应度都多了个列标号,这是为了将适应度储存在与交叉点对应的位 置。例如,如果两父代在第个交叉点交叉后得到了适应度,就将这个适应度放入记录 适应度的二维数组中的第列。二维数组中这一行的其他数字可置为。 表存放适应度的二维数组 使用二维数组记录的适应度不能直接作为神经网终训练集的输出,因为它除上一轮交叉 位置有适应度外,其他位置均为,如果使用其作为网络训练集的输岀,就会将原本神将网 终训练的参数覆盖,导致网终不收敛,神将网络也就不能记录子代适应度了。为了使神经网 终能够记录子代适应度,我们需要将记录适应度的二维数组做一定的变换。首先我们将神经 网络训练集的输入送入神经网络,得到一行数字。这列数组是神经网络根据之前训练的结果 输出的子代适应度,命名为数组一。然后提取出二维数组中与输入对应行的适应度,命名为 数组二。将数组二中唯不为的适应度复制到数组中的对应位置,这样就完成了神经网 络训练集的输出数组二。 为确保算法对调度方法的充分探索,进行父叉操作时,算法将以一定的概率选择子代适 应度最大的位置作为交叉点,其余情况下随机选择交叉点。 仿真结果 以 问题的某次调度方案为例,该调度方案编码结果为 ,该方案的调度结果如图所示,该调度方案 的最大完成时间如横坐标所示为,且已知的最大完成时间为 现将交叉概率设置为,变异概率设置为 把算法的结果代后仍然没有改进 作为收敛条件,每步打印一次结果,将改进算法和标准遗传算法各次的运行结果进 行对比: 山国武技论文在线 3[6264 □2[546,3 M4 _1[2 M3 Mz461图 山[43匚25 调度结果 表两种算法各结果次数对比 次数个 改进后的遗传算法 标准遗传算法 最大完成时间 如表所示,改进后的遗传算法的次运行结果中,有次结果收敛于,有次 收敛于,有次收敛于;而标准遗传算法的次运行结果巾,有次结果收敛于, 有次收敛于,有次收敛于次收敛于。 图与图表明改进算法和标准遗传算法各结果次数与结果总数之闫的比例关系,由图 可知改进算法的绝大多数结果取得」问趣的最优解,且取得最优解的比例远髙于标准遗传算 法。而标准遗传算法大多数结果没有取得最优解,说明标准遗传算法存在严重的早熟问题。 在算法求解质量方面,改进算法明显优」标准遗传算法。 8 04 02 0 最大完成时间 图改达算法各结果次数与结果总数之间的比例关系 山国武技论文在线 04 030 25 c 24 015 10 005 00 最大充成时间 图标准遗传算法各结果次数与结果总数之间的比例关系 图、图和图分别说明了改进算法的结果为 和时,每次结果的达代步数 与步数的平均值。橫线的纵坐标代表步数的平局值。改进算法没有取得过结果为的解, 因为取得结果为越多,说明算法的性能就越不够理想,所以文章后续图表中的改进算法 无法展示结果为的数据。改进算法迭代步数的平均值分别为 和 2000 1500 5 第次结果(次〕 图改进算法结果为的步数平均值 第次结果次〕 图改进算法结果为的步数平均值 山国武技论文在线 第次结果(次〕 图改进算法结果为的步数平均值 图、图、图和图分别说明了改进算法的结果为 和时,每次结 果的迭代步数与步数的平均值。标准遺传算法迭代步数的平均值分别为 和。标准遗传算法迭代步数的平局值四舍五入到了个位数。 第次结果(次 图标准遗传算法结果为的步数平均值 2000 1000 第次结果【次 图标准遗传算法结果为的步数平均值 山国武技论文在线 500 1500 结果(筑) 图标准遗传算法结果为的步数平均值 第次结果(次) 图标准遗传算法结果为的步数平均值 将两算法迭代步数的平局值绘制成折线图,并展示在图中。如图所示,蓝色虚线 代衣的改进算法的平均达代步数在橙色线代茯的标准遗传算法的下方,这衣明改进算法在更 小的达代步数内收敛到了该结果。因此,相比于标准遗传算法,改进算法拥有更快的收敛速 度 00 改进算法 传统算法 1400 200 10 4 最大完成时间 图改进算法与标准遗传算法的平均迭代步数对比 山国武技论文在线 表标准遗传算法次结果 表改进算法次结果 表和表分别是标准遗传算法和改进算法的次运算结果。因为每步打印一次 结果,所以结果都已整数倍表示。 实验结果分析与评估 从求解质量的角度进行分析,我们希望算法每次运行结果都能最终收敛于最优解,即 由表可知,改进后的遗传算法的次运行结果中,有次结果收敛于,有次 收敛于,有次收敛于,没有取得过;改进算法的结果绝大多数收敛于该问题的最 优解,而没有一次收敛于较差的解 而标准遗传算法的次运行结果中,有次结 果收敛于,有次收敛于,有次收敛于次收敛于。其结果分布的较为分散, ∏大部分收敛于,只有的结果收敛于该问题的最优解。综上所述,能够明显看出在 求解质量方面,改进算法大幅优于标准遗传算法 从收敛效率的角度进行分析,我们希望算法每个结果的平均迭代步数越小越好。由图 可知,改进算法在结果为 和的达代步数平均值分别为 和 与之 相比的是,标准遗传算法结果为 和的达代步数平均值分别为 和因为改进算法没有取得过,所以我们只对、和的迭代步数平局值进 行对比。通过比较可知,改进算法每个结果的迭代步数平均值均小于标准遗传算法。综上所 述,改进算法在收敛效率方面也是由于标准遗传算法的。 结论 本文提出一直用基于遗传算法的改进算法用于解决作业车间调度问题,经过理论分析和 实践表明它在可以得到最优解或高质量的次优解,具有实用意义。相较于标准遗传算法,改 进算法不论是在求解质量还是收敛效率方面都能看到明显的提升。为进一步改进该方法的性 能,将遗传算法和神绎网络以合适的方法结合是极为有意义的硏究方向。 山国武技论文在线 致谢 感谢王晨升老师在理论研究方面与论文写作方面给子的指导; 参考文献 王波张群王飞,等 排序问题鮮空间定量分析控制与决策 韩继业排序问题的一个判别条件和一类特殊的排序问题应用数学学报 张长水阎平凡解 调度问题的神经网络方法自动化学报 张朝勇邵新宇作业车间调度理论与算法武汉华中科技大学出版社 王明蔡劲草王雷基于改进遺传算法的作业车间调度铜仁学院学报