论文部分内容阅读
遗传算法是一种模拟生物进化过程的随机搜索算法，其自组织、自适应、自学习和种群进化能力使其适合于大规模复杂优化问题。它将问题的求解表示成“染色体”的适者生存过程，通过种群的一代代不断进化，包括复制、交叉和变异等操作，最终收敛到“最适应环境”的个体，从而求得问题的最优解或者满意解。随着计算机技术的发展，遗传算法越来越受到人们的重视，并在机器学习、模式识别、神经网络、优化控制、组合优化等领域得到了成功的应用。生产调度问题几乎在现实环境中，特别是在工业工程领域无所不在。许多制造工业提出的调度问题从本质上讲非常复杂，难以用传统优化方法求解。由于该问题表现出约束组合优化问题的所有特征，因此，调度问题成为遗传算法领域里的一个热门话题，并且成为测试新算法思想的范例。本文主要针对车间调度中典型的作业车间调度问题(Job Shop Scheduling Problem)，提出了一种适合该问题的病毒进化遗传算法。该改进算法首先从病毒个体的生成上进行了改进，其中部分病毒个体从优秀的主个体复制生成，提高了整个病毒群体的适值和感染能力，并引入了静态繁殖理论，有效的避免了问题最优解的丢失。其次，将基于优先规则的启发式方法与病毒进化遗传算法相结合，一方面通过该启发式算法来改进初始主群体的性能，另一方面让其配合病毒感染操作，调整局部搜索能力，加快进化速度，改善GA收敛慢的缺点。最后应用算法性能测试函数和标准测试集中的测试用例对改进后的算法进行了测试，结果表明算法在整体性能上有明显的提高。并且将改进后的算法用于求解实际调度问题，得到的结果是有效和可行的。