关键词:
柔性作业车间调度
遗传算法
差分进化算法
交叉变异操作
摘要:
车间调度问题是制造执行系统中最为关键的一环,是当今制造业发展环境下的一个研究热点。良好的车间调度能使企业的生产资源得到最大程度的优化,并能有效确保车间能有条不紊地运转。作为传统作业车间调度问题(Job shop Scheduling Problem,JSP)的扩展,柔性作业车间调度问题(Flexible Job shop Scheduling Problem,FJSP)更符合实际的生产车间。在目前众多解决FJSP问题的算法中,遗传算法应用最为广泛,但传统的遗传算法存在一些缺陷,而差分进化算法能够弥补这些不足,并将各自的优势最大程度的发挥出来,因此本文提出一种自适应遗传差分进化算法(Adaptive Genetic Algorithm Differential Evolution,简称AGA-DE)来解决FJSP问题,主要研究内容如下:首先,在进行种群初始化时,它的优劣直接影响到算法的执行效率及算法整体的优劣。因此为了解决由于随机初始化而导致的种群质量低下的问题,本文对传统的种群初始化方法进行改进,在随机生成初始种群之后,利用轮盘赌策略筛选群体,这样在保障初始种群多样性、初始种群随机性基础上能提升初始种群的质量,加快算法收敛速率。其次,由于遗传算法更倾向于通过交叉来获得全局最优解,而差分进化算法更倾向于通过变异来提升局部搜索能力,并且多数基因的交叉、变异概率都是固定的数值且这些数值的选取比较困难,容易造成算法的局部最优,也会降低收敛速率。因此,本文提出改进的自适应交叉、变异概率公式,使交叉、变异概率的值会因为个体和种群适应度值的改变而呈现出对应的线性变化。在此基础上对交叉和变异概率值进行调节,从而改造进化过程中的交叉方式和变异方式,不仅能提升算法全局搜索能力,同时还能加快算法收敛速度。再次,在后期进化过程中,遗传算法容易出现早熟、陷入局部最优等问题,为了有效解决上述问题,弥补遗传算法的不足之处,本文采用一种基于实数编码的局部收敛判定指标,并通过自适应差分进化搜索,快速找到并快速跳出局部最优解。该指标能够在进化后期实时追踪到算法的收敛趋势,判断算法是否过早收敛,如果算法达到了局部最优,这时遗传算法的交叉和变异几乎没有作用,要及时跳出局部区域搜索,就要执行带有差分变异算子的差分进化算法产生新个体,其中缩放因子的值可以根据种群的进化生成而自适应地改变,采用自适应的缩放因子可以大大减少求解过程的复杂度,提高求解效率,并且加快算法的收敛速度。最后,在运用测试函数测试改进算法有效性的基础上,将改进算法应用于柔性作业车间调度问题的经典算例,对不同算法仿真的结果进行比较分析,论证该方法在最大完工时间、收敛速度等方面的优越性,验证了改进算法的可行性和有效性,并将改进算法运用于实际案例证明算法存在的现实意义。