遗传算法研究及其在排课问题中的应用

随着计算机技术的飞速发展，人们已经可以让计算机完成一些过去无法想象的任务。但现代科学理论研究与实践中存在着大量与组合优化，自适应等相关的问题。使用常规方法解决这些问题，除了一些简单的情况之外，人们对于大型复杂系统的优化和自适应问题显得无能为力。 遗传算法借鉴生物界自然选择和自然遗传机制，使用群体搜索技术，尤其适用于处理传统搜索方法难以解决的复杂的和非线性的问题。经过近40年的发展，遗传算法在理论研究与实际应用中取得了巨大的成功，但相对其鲜明的生物基础，其数学基础还是相对不完善的。 本文从遗传算法的基本理论入手，针对基本遗传算法(SGA)不以概率1收敛于最优解的问题，提出了一些改进方法并对其收敛性进行证明。主要有以下几方面工作： (1)将二进制编码遗传算法的模式定理扩展到由有限整数、字母或取值个数有限的浮点数编码，或它们混合编码的遗传算法范围； (2)提出最佳个体替换策略遗传算法(RECGA)、优势群体优先策略遗传算法(SCFGA)，对遗传算法进行改进； (3)使用随机过程理论Markov链对RECGA进行了收敛性分析； (4)使用泛函分析理论压缩映射原理对SCFGA进行了收敛性分析； (5)使用遗传算法设计了解决NP类问题(排课问题)的测试程序(CAP)，并根据RECGA对算法进行改进并进行测试。 CAP测试程序的实验结果表明，使用最佳个体替换策略(REC)改进遗传算法明显地提高了算法效率。同时，对RECGA、SCFGA的收敛性证明在遗传算法研究中具有一定的理论意义。