【作者】 陈本庆；

【导师】 马永强；

【作者基本信息】 西南交通大学 ， 交通信息工程及控制， 2003， 硕士

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

【Abstract】 Today witnesses the rapid development of computer technology. Some tasks that were impossible in the past can be accomplished with computer. However, there are still many issues to be tackled with in modern scientific theory research and practice, with regard to Combination & Optimization and self-adaptation etc. Routine methods are quite helpful resolving simple optimization and self-adaptation problems but helpless for complicated large-scale systems.Genetic Algorithms, based on the biological mechanism of natural selection & heredity and leveraging colony searching technology, is particularly applicable for the resolution of complicated & non-linear problems intractable with traditional searching methods. For nearly 40 years’ development, Genetic Algorithms has made great achievements in both theory research and practical applications. However, its mathematical foundation is still incomplete compared with the distinctive and sound biologic foundation.This paper starts with the basic theory of Genetic Algorithms. Then, some modification methods are advanced and some convergence proofs made, aiming at the problem that the probability of Simple Genetic Algorithm (SGA) converged to optimal solution is less than 1. The major tasks include:(1) Expand the schema theorem for GA. The schema theorem with binary coding advanced by Professor Holland is expanded to limited integer, letter, floating point numbers the number of which value is limited, and their hybrid coding.(2) Put forward Replacing by the Excellent Chromosome GA (RECGA), Superiority Colony First GA(SCFGA) and improve the GA;(3) Make probability convergence analysis of RECGA using the theory of Markov Chain, Random Process;(4) Make convergence analysis of SCFGA using the principle of Contractive Mapping in functional analysis theory;(5) Design the test programs (CAP) to resolve NP problems (Course Arrangement) with GAs; Based on RECGA, modify the Arithmetic and then conduct tests.The experiment result for CAP test programs illustrates that the GeneticAlgorithms becomes more efficient being improved with REG Moreover, the convergence proofs of RECGA and SCFGA are theoretically meaningful in the research of Genetic Algorithms.更多还原