作业车间调度[1]一直是智能制造和人工智能领域的热门研究课题，在制造业[2]、项目调度[3]等不同行业中有很多应用．但车间调度面临着车间环境的动态性和不确定性的挑战(例如机器故障、任务取消)，这给传统的优化技术(如数学规划和元启发式方法)带来了计算困难．相反，调度规则却可以应对复杂的动态车间环境变化，同时对即将到达车间的不可预测事件做出反应，因此在求解动态作业车间调度问题[4]中广泛采用调度规则．文献[5]认为人工设计的调度规则已经不能满足复杂的作业车间环境状态，所以许多研究者通过遗传规划[6]智能设计生成调度规则的方法，成功获得了比人工设计更好的调度规则．然而当基于遗传规划进化生成有效调度规则时，最关键的就是选择有效的特征终端集(车间功能)以减少搜索空间的复杂性，但并不是所有终端集都有用，不相关的终端集将扩大搜索空间．例如文献[7]描述，遗传规划搜索空间大小为|F|2D-1|T|2D(F和T分别为函数和终端集数量，D为最大树深度)；因此，为了减小遗传规划搜索空间，提高搜索效率，可以通过减少特征终端集的数量来实现[8]．但遗传规划进化生成调度规则的训练时间仍然很长，尤其是当处理大型制造系统问题时，求解时间从数小时到数天．为了更好解决这一问题，文献[9]提出了一种基于遗传规划搜索历史数据和规则相似性度量的代理模型．实验结果表明，基于简化模型的代理辅助遗传规划优于传统的遗传规划，并且收敛速度也更快．受上述研究的启发，本研究将重点分析基于简化模型的代理辅助遗传规划中的特征选择，通过代理模型减少训练时间，特征选择减少终端集数量，提高搜索效率以获得更好的测试性能．其主要任务是将最小化平均流程时间作为调度优化目标，应用基于简化模型的代理辅助遗传规划方法[10]，而不是规则相似性度量的代理模型来降低适应度评估的复杂性，从而提高特征选择算法的效率．同时介绍了代理模型如何提高算法的高效性，并给出了仿真实验中算法的参数设置，从测试性能、规则长度和训练时间分析该代理模型在特征选择中的有效性．1 动态作业车间调度1.1　问题描述在动态作业车间调度问题中，设车间中有m台机器，n个待加工工件；工件i(i=1,2,…,n)有j道工序Ji=(Ji1,Ji2,…,Jij)，当工件i的第j道工序Jij根据一定的工艺顺序在指定的机器mij上加工时，所需的加工工时为tij；工件i以某种分布形式动态随机到达车间的时间为ai，工件i的交货期为di． 动态作业车间调度问题满足以下假设．假设1 从零时刻开始，所有的机器都是可运行的．假设2 当工件的一道工序完工时，立即送到下一台机器处理其下一道工序(传输时间忽略不计)．假设3 每台机器同一时刻只能处理一道工序．假设4 调度是非抢占式的，一旦一道工序在机器上开始处理，将不能被其他操作中断．假设5 在任何给定的时间内，一个工件的不同工序不能一起加工．1.2　超启发式遗传规划的调度规则利用遗传规划的自动化启发式设计能够实时生成调度规则，以应对复杂车间环境变化(如新作业的到来)，并根据车间信息做出决策．在车间决策队列中，当一台机器处于空闲状态时，对在机器上等待的多个待加工工件，应用调度规则来计算其优先级，选择优先级最高的工件进行处理．例如，在最短处理时间规则中，处理时间最短的工件具有最高优先级．近年来，应用机器学习和优化方法使设计过程实现自动化成为一种流行趋势[11]，所提出的方法通常被称为超启发式算法，它们自动选择或生成启发式算法来解决NP难的搜索问题．超启发式遗传规划和遗传算法类似，都是利用达尔文生物进化的思想，随机产生初始种群(种群中的每个个体都是基于树的表现形式)，对每个个体进行适应度评估，计算适应度值，并进行比较；再经过选择、交叉和变异等遗传操作，进行多次迭代，得到近似最优解．与元启发式算法不同，遗传规划的个体不是具体解的值，而是在启发式空间中搜索得到的解决问题的调度规则或算法．在动态作业车间调度问题[12]中，遗传规划被证明是非常有用的．因此，本研究选择遗传规划作为进化调度规则的超启发式框架．1.3　特征选择效率文献[8]提出的特征选择方法能够选择有效的关键终端集，从而提高遗传规划在动态作业车间调度问题中的测试性能．但是该方法须要用不同的随机种子多次运行遗传规划来提取不同的好的调度规则，非常耗时(在Intel(R) Core(TM) i9-9900K CPU @3.60 GHz上获得30条最佳规则需要大约45 h)，因而在实际生产中不适用．本研究通过利用代理模型降低适应度评估的复杂性来缩短遗传规划训练过程，使训练规则的时间大大减少．2 代理模型评估的特征选择算法2.1　特征选择算法原始模型适应度φΙ(g(x))定义为实例集Ι上的平均归一化目标值，如下式所示，φΙ(g(x))=1|Ι|∑I∈Ιf(S(g(x);I))f^(I)，(1)式中：x为特征向量，xi∈x表示一个特征；g(x)为调度规则的优先级函数；I为一个作业车间调度实例集；S(g(x);I)为将g(x)应用于实例I的原始模型获得的时间表；f(S)为目标值；φΙ(g(x))为g(x)在原始模型实例集Ι上的适应度．理想情况下，f^(I)是最佳参考目标值，但最佳值通常是未知的，故将其设置为某些参考规则的目标值．根据文献[8]中所描述的特征选择方法，分别定义原始模型和代理模型中特征xi到优先级函数g(x)的贡献ζΙ(xi;g(x))和ζH(Ι)(xi;g(x))，即：ζΙ(xi;g(x))=φIg(x\xi)-φI(g(x))；(2)ζH(Ι)(xi;g(x))=φH(I)g(x\xi)-φH(I)(g(x))，(3)式中x\xi表示从特征向量x中删除特征xi．这两个贡献就是在两种模型中，从g(x)中删除xi前后的适应度值之差．差值为正值表示删除xi后，新的调度规则将导致更差的性能；相反，负值表示xi对g(x)产生负贡献，而将其删除性能会更好；若ζΙ(xi;g(x))=0和ζH(Ι)(xi;g(x))=0，则xi无贡献，不影响性能．根据式(2)和(3)，定义特征xi的相关性χω(xi)，以优化不同作业车间场景ω下生成的调度规则．如果一个特征xi有更好的相关性，那么它将在车间场景中做出更多贡献．因此，χω(xi)的定义是基于遗传规划对最佳规则的贡献[8]，其贡献是基于30条最佳规则在删除特征前后平均归一化目标值的差值，每个特征的相关性值为30次独立运行中贡献值的中值．2.2　特征选择的预处理特征选择遗传规划(feature selection-genetic programming，FS-GP)和特征选择代理遗传规划(feature selection-surrogate genetic programming，FS-SGP)的框架包括三个阶段．在第一阶段，对所有特征终端集的遗传规划进行30次独立运行，以获取30条最佳规则；在第二阶段，基于30条最佳规则计算每个特征xi的相关性χω(xi)，并选择相关性大于0的特征来形成新的关键终端集x*；在第三阶段，再次运行使用新的终端集x*的遗传规划来获取新规则．为了区分特征选择后的遗传规划，提出完整终端集遗传规划(entire terminal-genetic programming，ET-GP)和完整终端集代理遗传规划(entire terminal-surrogate genetic programming，ET-SGP)．2.3　代理模型适应度评估是遗传算法进化的驱动力，不同模型直接影响着评估效率．面对复杂的作业车间环境，其适应度评估的计算量非常大，为了提高适应度评估的效率，常用代理模型来实现这一目标．对于动态作业车间调度问题，文献[10]中提出的代理模型能够发现最佳规则，其中HalfShop代理模型的评估精度最高．因此，根据文献[10]中的参数信息设置，将优先级函数g(x)在代理模型上的适应度φH(I)(g(x))定义为实例集Ι上的平均归一化目标值，φH(I)(g(x))=1|Ι|∑I∈Ιf(S(g(x);H(I)))f^(H(I)), (4)式中S(g(x);H(I))为将g(x)应用于实例I的代理模型获得的时间表．式(4)与式(1)的不同之处在于将原始模型替换为HalfShop代理模型．2.3.1　代理辅助遗传规划算法应用代理辅助遗传规划求解动态作业车间调度问题算法的流程如图1所示．10.13245/j.hust.238587.F001图1代理辅助遗传规划算法流程图代理辅助遗传规划采用Ramped-half-and-half生成方法随机初始化种群，并对每条规则进行适应度评估．若生成的最佳规则具有比当前最佳规则更好的训练性能，则更新当前最佳规则．若满足停止条件(即代理辅助遗传规划中的最大遗传代数)，则代理辅助遗传规划将停止；否则，保留精英个体，通过选择、交叉和变异等遗传操作创建中间种群．与原始种群相比，更大的中间种群规模增加了种群的多样性，同时也提供了获得更好规则的机会．中间种群中所有规则的适应度通过代理模型进行评估．2.3.2　适应度评估本研究提出的代理模型的目标是降低原始模型适应度评估的复杂性，并且保持其精度水平在可接受范围内．该代理模型的设计策略是通过减少机器数量和预热作业数来降低原始模型的复杂性．由于模型的简化使其在统计上不准确(由少量的重复和偏差引起)，因此代理模型不能提供原始车间的绝对性能(例如最小化平均流程时间)．所以，应该证明的是基于原始模型绝对性能的规则a优于规则b，则代理模型也应证明a优于b，即相对性能．该算法在不同阶段使用了三种类型的适应度函数：适应度φΙ(g(x))是利用原始模型获得的真实适应度(绝对性能)，φH(I)(g(x))是利用代理模型获得的估计适应度，适应度φΙ(g*(x))是规则g*(x)在特定世代中的性能．由于仿真成本昂贵，使用大量的仿真来获得适应度是不切实际的，因此每代只使用一次仿真来进化规则获得φΙ(g*(x))．在基于最佳适应度φΙ(g*(x))生成中间种群后，利用代理模型进行新生成的规则的适应度评估．这三个适应度函数评估算法虽然复杂，但更有效．3 仿真实验设计在动态作业车间调度问题仿真实验中，选择常用的车间场景[12]，该场景以最小化平均流程时间为调度目标．仿真实验案例的参数设置为车间有10台机器，工件数量为4 000个，考虑到车间状态的稳定性和仿真实验的有效性，在每次仿真实验开始时将使用1 000个工件进行预热．工件到达车间的过程服从泊松分布，即工件按照指数分布间隔时间动态到达车间．每个工件的工序数从离散均匀分布DU[2，10]中随机产生，每道工序的加工处理时间服从离散均匀分布DU[1，49]，每道工序的候选加工机器以无放回抽样方式从10台机器中随机产生．同时利用机器利用率为0.80，0.85，0.90，0.95进行测试．缺失表示每个作业的工序数在2和10之间随机抽取，完全则表示所有作业的工序数为10．3.1　参数设置在实验中，采用文献[13]中的时不变终端集，遗传规划算法可以在更短的时间内得到更好的调度规则，终端集包含：当前队列的工序数NIQ，当前队列的作业WIQ，机器的等待时间MWT，工序的加工时间TP，下一道工序的加工时间TNP，工序的等待时间TOW，下一个机器的等待时间TNW，作业的剩余时间WKR，剩余的工序数NOR，下一个队列中的作业WINQ，下一个队列中的工序数量NINQ，相对流量到期日DRFD，相对到期日DRD，作业权重λ，系统时间TIS，松弛时间TSL．确定遗传规划算法中的函数集，其中{+，-，*，/}是4个最基本的运算符，以及规则中常见的函数，如“min”和“max”(返回最小值和最大值)．如图2所示为“2TP+WINQ+TNP”调度规则的遗传规划树，其是最小化平均流程时间的有效调度规则，即是式(1)和(4)的参考目标值．该参考调度规则是两倍的工序加工时间，并添加了下一个队列中的作业和下一道工序的加工处理时间，由Rajendran和Holthaus手动制定并在文献[14]中提出，是手动开发的具有代表性的最佳规则．该遗传规划树的表达形式为(+(*2TP)+(WINQTNP))．10.13245/j.hust.238587.F002图2“2TP+WINQ+TNP”的遗传规划树遗传规划的其他参数采用标准参数设置，种群大小设置为1 024，最大迭代次数为51，交叉率为0.85，变异率为0.1，复制率为0.05，树的最大深度为8，利用锦标赛选择法选择遗传到下一代的个体，算法由ECJ平台实现．3.2　特征相关性首先，根据不同车间场景和给定目标得出各个特征的相关性，其相关性在2.1节定义．根据定义，相关性与平均归一化目标值直接关联，所以表1和表2中的特征相关性数值结果均无量纲．表1和表2显示了不同车间场景中动态作业车间调度特征终端集中相关性大于0的特征，该特征可以实现最小化平均流程时间．从表1和表2中可以看出TP，TNP，WINQ和NINQ这4个终端集都有大于0的相关性，其他没有列出的特征终端集的相关性几乎为0，表明它们至少在一半时间内对最佳规则没有做出任何贡献．10.13245/j.hust.238587.T001表1原始训练集上30次独立运行ET-GP的特征相关性实验利用率工序数TPTNPWINQNINQ10.80缺失0.141 10.038 40.042 40.000 220.85缺失0.156 60.056 50.062 30.001 830.90缺失0.167 90.084 70.099 20.001 240.95缺失0.185 80.113 10.131 60.001 650.80完全0.136 50.039 30.044 00.001 160.85完全0.146 70.057 00.064 20.000 970.90完全0.161 10.082 60.095 80.001 180.95完全0.173 50.122 10.149 30.003 910.13245/j.hust.238587.T002表2代理训练集上30次独立运行ET-SGP的特征相关性实验利用率工序数TPTNPWINQNINQ10.80缺失0.148 70.029 80.041 40.000 320.85缺失0.170 70.043 50.057 80.002 730.90缺失0.191 40.063 40.087 10.002 840.95缺失0.197 50.083 80.118 40.004 050.80完全0.146 90.031 90.041 70.001 760.85完全0.162 70.044 10.059 80.000 470.90完全0.177 80.062 10.086 30.001 780.95完全0.189 90.095 10.128 60.003 4从表1和表2中特征选择结果可以看出原始模型和代理模型能得到相似的特征集，同时文献[14]已经表明，TP+WINQ规则可最大程度减少平均流程时间，所以其特征相关性最高；2TP+WINQ+TNP规则类似于TP+WINQ规则，也能很好地优化调度目标，所以TNP的特征相关性次之；对于NINQ规则来说，与WINQ规则有一定的相似性，所以其特征相关性最小．3.3　测试性能在通用性方面，需要的是代理模型进化生成的调度规则在测试实例上的相对性能，即若基于原始模型的绝对性能的规则a优于规则b，则代理模型还应证明a优于b，从而说明代理模型不仅可以得到和原始模型一样的性能，而且代理模型大大提高了训练效率.表3给出了不同车间场景下，特征选择前后进化规则在测试实例上的性能，用平均归一化目标值表征，并显示了在不同车间场景下30次独立运行的平均归一化目标值的均值和方差．对于原始模型和代理模型车间场景，将参考值设置为“2TP+WINQ+TNP”规则的目标值，并分别对特征选择前后的结果之间进行了α=0.05的Wilcoxon符号秩检验．该方法作为一种常见的非参数对检验，是一种快速有效的检测方法．在数值结果测试中，若目标算法优于比较算法，则记为R+，否则记为R-．一般来说，R+数越大，目标算法的优势越大．在全部的实验场景中，FS-GP和FS-SGP的平均归一化目标值的均值和方差分别明显小于ET-GP和ET-SGP，即FS-GP和FS-SGP的测试性能明显优于ET-GP和ET-SGP，这表明仅选择遗传规划中的关键特征集就可以显著提高遗传规划进化规则的测试性能．10.13245/j.hust.238587.T003表3不同车间场景的测试性能(x¯±s)实验利用率工序数ET-GPFS-GPET-SGPFS-SGP10.80缺失0.967 6±0.001 30.964 8±0.000 80.970 8±0.003 10.965 8±0.001 220.85缺失0.954 4±0.002 20.949 9±0.001 20.959 5±0.004 90.951 6±0.001 830.90缺失0.944 7±0.003 80.937 7±0.002 20.953 4±0.008 30.940 3±0.003 440.95缺失0.926 9±0.005 90.917 7±0.003 10.942 2±0.015 80.921 8±0.004 850.80完全0.970 0±0.001 60.967 0±0.000 90.973 4±0.003 40.968 0±0.001 360.85完全0.958 4±0.002 20.953 9±0.001 20.963 8±0.005 50.955 4±0.002 070.90完全0.946 1±0.003 40.939 8±0.001 70.955 4±0.009 40.942 1±0.002 980.95完全0.922 7±0.006 50.913 3±0.002 70.940 9±0.019 70.917 1±0.004 63.4　规则长度实验中通过计算最佳规则的长度(即函数集和终端集组成的调度规则数量)、叶子(终端数)的均值来分析规则．表4给出了最小化平均流程时间的动态作业车间场景中，通过原始模型和代理模型的30次独立运行获得的最佳规则的长度、叶子的均值．与期望相同，代理模型比原始模型获得了更简单的规则，在最佳规则的长度、叶子的均值上都有更低的值．10.13245/j.hust.238587.T004表4两个模型30次独立运行获得的最佳规则的长度、终端数的均值实验场景最佳规则长度终端数ET-GP45.338.27ET-SGP34.036.10FS-GP50.203.97FS-SGP45.273.87图3也表明对在原始模型和代理模型上30次独立运行中获得的每一代规则长度的平均值而言，代理模型都比原始模型更小．10.13245/j.hust.238587.F003图330次独立运行中规则长度的平均值3.5　运行效率由于本研究的主要目标之一是提高特征选择的效率，因此对计算时间进行分析，图4给出了标准遗传规划在原始模型训练集和HalfShop代理模型训练集上的30次独立运行的计算时间．仿真实验结果表明：相较于原始模型，使用代理模型之后的特征选择效率有了明显的提升；对ET-GP而言，原始模型多次独立运行的时间均值为2 572 s，代理模型为570 s，运行时间减少了77.80%；原始模型最长运行时间为3 380 s，代理模型为564 s，运行时间减少了83.30%．对FS-GP而言，原始模型多次独立运行的时间均值为2 766 s，代理模型为684 s，运行时间减少了75.30%；原始模型最长运行时间为3 365 s，代理模型为678 s，运行时间减少了79.90%．从数值结论来看，本文方法用于提高特征选择的效率是有效的，可以大幅度缩减模型运行时间．10.13245/j.hust.238587.F004图430次独立运行时间(以平均流程时间表示)从图4中可以看出，使用代理模型的训练时间比原始模型的训练时间要少得多．在原始训练集中，车间队列有2 000个作业和500个预热作业，每个作业有10道工序，因此有2 500×10=2.5×104个决策点，每个决策点对应一道工序．在HalfShop代理训练集中，车间队列只有500个作业和100个预热作业，每个作业有5道工序，则仅有600×5=3 000个决策点，可见代理模型决策点数远少于原始模型，因此使用HalfShop代理模型进行适应度评估可以提高特征选择的效率，仿真结果也证实了这样的结论．4 结语本研究提出了利用代理模型降低适应度评估的复杂性来减少遗传规划训练过程的时间，提高特征选择算法的效率．实验结果表明：通过验证使用代理模型特征选择前后的相对性能，基于简化模型的代理辅助遗传规划算法是有效的．未来进一步研究代理模型如何应对更复杂的实际环境，且在这种情况下仍然有效，但须要在遗传规划中使用更通用和更强大的搜索机制，如协同进化和多树遗传规划[15-16]．此外，将进一步提高特征选择的准确性，并且在更多的作业车间场景验证算法的有效性，如最小化最大制造时间、最小化平均迟到时间等．