论文部分内容阅读
车间作业调度问题(Job Shop Problem,JSP)是一类典型的NP-hard问题,已被证明在多项式时间内得不到最优值。遗传算法(Genetic Algorithm,GA)作为一种通用的优化算法,在求解JSP中得到了广泛的应用。在求解JSP时,GA显示出很强的适用性,但GA的优化性能对遗传参数(尤其是交叉率和变异率)的依赖性很强,不合适的参数往往会使得GA的优化性能大打折扣。在寻求GA的最优参数方面,已有不少深入的研究,但这些研究往往从工程背景和工程应用展开,鲜有从GA基础数学模型入手的。为了更好地解决问题,对传统的遗传算法加以改进,将一些启发式的思想融合于算法之中,成为目前研究的热点。本文分别应用病毒遗传算法和单亲遗传算法来求解车间作业调度问题。针对遗传算法求解的早熟和收敛速度慢等问题,设计了一种新的改进型病毒进化遗传算法IVEGA(Improved Virus Evolutionary Genetic Algorithm,IVEGA),从横向和纵向同时搜索解空间;并在进化过程中分别建立主群体优秀染色体知识库和病毒优秀个体知识库,引入学习机制,避免了优秀解的丢失;其次,定义了一种基于整数的编码机制,既避免了进化过程中产生无效染色体的问题,也便于解空间和染色体空间的转换,大大地加快了对问题全局近似最优解的搜索速度。根据11个典型的JSP对比实验,证明了该算法对于求解JSP的有效性。考虑到传统遗传算法(TGA)在求解组合优化问题时,其优化性能对遗传参数(尤其是交叉率和变异率)的依赖性强,并且会出现“早熟收敛”现象等问题,设计了一种新的基于整数编码的单亲遗传算法IPGA(Integer Coded Partheno Genetic Algorithm,IPGA)。在进化过程中只产生单个个体群,取消了以往传统遗传算法的交叉操作,在一条染色体上进行变异操作,同时也继承了传统遗传算法遗传迭代等特性,大大地增加了遗传算法的搜索效率。对3个不同规模的FT类问题的仿真结果表明算法具有收敛速度快、优化结果好等优点。