【作者】 刘秋红；

【导师】 寒枫； 王柏盛；

【作者基本信息】 华北电力大学（河北） ， 计算机技术， 2007， 硕士

【摘要】 UTP问题,即大学时间表问题。UTP问题已被证明属于NP难题。解决UTP问题有许多算法,如整数规划、图着色、进化算法等等,但这些算法对于大型复杂系统的优化效果不佳。本文汲取了近年来国内外的各种排课方法的特点,探讨了一种多方法结合的解决方案,这种方案是自适应算法、遗传算法以及分层思想的结合应用。本论文主要内容:1.应用了自适应遗传算法(AGA)。AGA主要是对基本遗传算法中交叉概率和变异概率进行自适应调整和改进。这样能更好地避免基本遗传算法出现未成熟收敛等一系列问题。2.利用了运筹学中的分层思想,缩小了求解空间。3.将二进制编码遗传算法的模式定理扩展到由有限整数、字母编码或它们混合编码的遗传算法范围。4.提出了锁定标记的思想。实验表明,本文所提出的课表编排理论对开发通用型实用排课系统具有积极的意义。更多还原

【Abstract】 UTP is the university timetable problem. It is proved that UTP belongs to the NP-hard problems. There are many algorithms to solve UTP problems, such as integer programming, and so on. However, these algorithm optimization effection to large-scale complicated system is not nice.The thesis has absorbed the various characteristics of course arrangement methods in recent years, it is discussed a union solution composed of many methods. This combined method is the combination of adaptive algorithm, genetic algorithms and application of hierarchical thinking. Main content of thesis: 1. Adaptive genetic algorithm (AGA) has applied in the thesis. AGA has carried out certainly adjustment and improvement on probability alternating and mutant probability in simple genetic algorithm mainly. Such can avoid a series of problem such as not mature convergence etc. appearing on simple genetic algorithm better. 2. Use of hierarchical thinking reduced the solution space. 3. Binary-coded genetic algorithm schema theorem will be expanded to the scope of limited integer, alphanumeric codes, or their mixed-coded genetic algorithm. 4. It proposes the Lock markings idea.The experiment is indicated that the arranging timetable theory in this thesis is of some positive significance to the development of universal practical timetable problem.更多还原