论文部分内容阅读
车间作业调度问题(JSP)是许多实际问题的简化模型。寻找求解JSP问题的有效途径是调度和优化领域的重要课题。但是车间作业调度问题是NP难解问题,寻找具有多项式复杂度的算法几乎是不可能的。遗传算法是一种全局随机搜索算法,已经广泛的用于求解JSP问题。它把JSP问题的可行解通过编码从问题的解空间转化到遗传算法能够处理的搜索空间。GA的遗传算子操作能够通过交叉或变异父个体生成新个体的方式来从解空间中搜寻最优解。GA通过交换父个体中的基因片段或改变某些基因来进化进而完成搜索。如果在进化过程中,我们能够尽可能的保留父个体中具有较高适应度的优秀基因片段,并将其遗传到下一代中,那么GA可以在最有希望的解空间中搜索,进而可以提高搜索效率。本文中,我们通过用遗传算法对一个JSP实例多次求解,得到大量最优染色体编码串。经过认真分析,总结出代表问题特性的一些概念属性,并给出一个新的概念分级方法。基于这些属性及分类方法,应用数据挖掘算法从这些最优染色体编码串中学习知识,得到多组调度规则,仿真表明,这些调度规则可以有效的调度作业。调度规则也代表了这些最优染色体共有的特征。如果进化过程中在这些特征刚刚出现的时候,我们能够识别出来并将其遗传到后代个体中,显然可以改善后代种群的质量,进而可以提高搜索效率。在最后部分,借鉴上述思想求解具有操作柔性的车间调度问题。根据问题的特点,我们使用共生机制改进了遗传算法并将其集成到一个学习框架中。提出了相应的编码解码方法和一组自适应概率函数并改进了学习框架,使其在进化过程中可以学习染色体的优秀特征。我们把调度问题分为两个子问题,分别生成两个不同类的种群,相互影响,共同进化,将两个种群中的最优染色体结合起来解码则可以得到最优调度。进化过程中,学习模块可以不断从当前种群的适应度最高的一些染色体中学习其优秀特征,并指导后代个体的进化。最后我们给出了仿真实验,结果表明这种方法在解的质量上有一定程度的提高。