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