一种基于混合决策树的调度知识获取算法

摘要：提出了一种基于混合决策树的调度知识获取算法。将模拟退火算法融入遗传算法中，作为一种具有自适应变概率的变异操作，构成一种混合优化方法。利用这种混合方法求解在不同调度目标下制造系统的最优特征子集，同时确定控制决策树规模的最优参数；使用决策树评价混合方法中染色体编码的适应度，在得到不同调度目标下的最优特征子集和最优决策树参数后，生成调度知识。仿真实验结果表明，该算法在性能上优于其他算法。

关键词:调度知识； 特征选取； 遗传算法； 模拟退火算法； 决策树

适应调度是一种较好的生产调度方法，能够根据当前系统的工作状态及调度目标选择使用合适的调度规则[1]。它具有动态调度能力，非常适合生产系统复杂、生产过程随机干扰因素较多的制造系统。调度知识实现了从生产状态到调度规则的映射，是决定适应调度系统性能的关键因素。机器学习是目前获取调度知识的主要技术之一，它从仿真数据(训练样本)中学习调度知识，并将其以隐含或显式的方式表示。

如何利用机器学习技术，高效快捷地获取调度知识以适应日益复杂的生产要求，吸引了大量学者对此进行研究。彭观等人[2]和chen等人[3]利用人工神经网络(artificial neural network，ann)表示和学习调度知识。这充分利用了ann的学习能力、复杂非线性映射能力和并行运算能力，但其主要问题是神经网络隐含的知识表示方式不能增加决策者对调度问题的认识，也无法评价其隐含推理过程的正确性。park等人[1]、arzi等人[4]和孙容磊等人[5]则应用归纳学习技术推导调度知识。wwW.11665.coM该技术使用ifthen规则或决策树(decision tree, dt)的形式表示学习到的调度知识，但是如果结构复杂，将导致对应的调度知识过分凌乱，使决策者难以理解。

caskey[6]和shiue等人[7]将多种机器学习技术相结合，构成了不同的知识学习与表示混合方法，并取得了引人注目的成果。其中研究的热点之一是使用遗传算法等亚启发式算法优化决策树，使之简洁，并解决过度拟合问题。schmitt等人[8]指出由于难以控制ga的收敛，致使ga容易发生“早熟”现象，而且ga中控制参数的确定过多地依赖经验，缺乏严谨的科学理论依据。这些因素会影响决策树的优化质量和知识库的性能。为此，本文对ga进行改进，将模拟退火算法融入ga中，作为ga中具有自适应变概率的变异算子。称这种混合优化方法为gasa。gasa不仅增强了进化能力，而且在某种程度上减小了对经验参数的依赖。笔者使用gasa求解不同调度目标下制造系统的最优特征子集，并确定控制决策树规模的最优参数。dt用于评价gasa求解过程中染色体编码的适应度，在获取到最优特征子集和最优参数后生成调度知识。

表4和5的结果间接验证了gasa混合方法对选取的特征子集和dt的参数优化结果的合理性。使用过多的特征会导致训练样本的过度拟合，降低调度知识的泛化能力；使用过少的特征将影响学习能力，降低调度知识的分类能力。与ga方法相比，显然gasa能够以突出的优势减小这两种情况发生的概率。gasa也使得本文算法有效地控制了决策树的规模，相应地减少了最优规则的搜索时间。这说明gasa将两种不同搜索机制相结合，不仅减少了对经验参数的依赖，而且大大改善了搜索质量。

5结束语

构建性能优良的调度知识库能够使适应调度系统快速响应日益复杂的生产要求，制定出实时的调度策略。本文提出了一种混合决策树的调度知识获取算法。利用gasa混合优化方法求解在不同调度目标下的制造系统的近似最优特征子集，以及控制dt规模的最佳参数；使用dt评价gasa求解过程中染色体编码的适应度，在得到最优特征子集和最优参数后，生成调度知识。仿真结果表明，本文提出的算法与多种算法相比，性能非常优秀。

参考文献:

[1]park s c, raman n, shaw m j. adaptive scheduling in dynamic flexible manufacturing systems: a dynamic rule selection approach [j]. ieee transactions on robotics and automation, 1997,13(4):486-502.

[2]彭观,陈统坚,欧阳惠芳. 基于神经网络的fms 动态调度决策[j].华南理工大学学报：自然科学版, 1998,26(6):60-64.

[3]chen c c, yih y, wu y c. autobias selection for learningbased scheduling systems [j]. international journal of production research, 1999,37(9):1987-2002.

[4]arzi y, iaroslavitz l. operating an fmc by a decisiontreebased adaptive production control system [j]. international journal of production research, 2000,38(3):675-697.

[5]孙容磊,熊有伦,杜润生,等. 规则调度的迭代优化[j]. 计算机集成制造系统,2002,8(7): 546-550.

[6]caskey r c. a manufacturing problem solving environment combing evaluation, search, and generation methods [j]. computer in industry, 2001,44:175-187.

[7]shiue y r, guh r s. the optimization of attribute selection in decision treebased production control systems [j]. international journal of advanced manufacturing technology,2005,28(7):737-746.

[8]schmitt l m, nehaniv c l, fujii r h. linearanalysis of genetic algorithms [j]. theoretical computer science, 1998,200(1-2): 101-134.

[9]kim h, koehler g j. theory and practice of decision tree induction [j]. omega,1995,23(6):637-652.

[10]wang ling, zheng dazhong. an effective hybrid optimization strategy for jobshop scheduling problems [j]. computers & operations research, 2001,28:585-596.

[11]montazeri m, wassenhore l n van. analysis of scheduling rules for an fms [j]. international journal of production research, 1990,28(4):785-802.