Study Of Genetic Algorithms And Application In Course Arrangement Problem

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.