摘要
UTP问题,即大学时间表问题。UTP问题已被证明属于NP难题。解决UTP问题有许多算法,如整数规划、图着色、进化算法等等,但这些算法对于大型复杂系统的优化效果不佳。
本文汲取了近年来国内外的各种排课方法的特点,探讨了一种多方法结合的解决方案,这种方案是自适应算法、遗传算法以及分层思想的结合应用。本论文主要内容:1.应用了自适应遗传算法(AGA)。AGA主要是对基本遗传算法中交叉概率和变异概率进行自适应调整和改进。这样能更好地避免基本遗传算法出现未成熟收敛等一系列问题。2.利用了运筹学中的分层思想,缩小了求解空间。3.将二进制编码遗传算法的模式定理扩展到由有限整数、字母编码或它们混合编码的遗传算法范围。4.提出了锁定标记的思想。
实验表明,本文所提出的课表编排理论对开发通用型实用排课系统具有积极的意义。
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.
引文
[1]Even S, Ital A Shamir A. On the complexity of timetable and multicommodity flow problems [J] . SIAM Journal on Computing, 1976, 5(4): 691-703
[2]Cook, S. A.,"The mean-field theory of a Q-state neural network model" Journal of Physics A,vol.22, No. 12, June 21, 1989, pp.2057-2068;
[3]Tripathy A. School timetabling--a case in large binary integer linear programming [J] Discrete Applied Mathematics, 1984, 35(3): 313-323
[4]Burk E K, Ellen an D G, Weare R. F. A university timetabling system based on graph coloring and constraint manipulation [J]. Journal of Research on Computing in Education, 1994, 27(1):1-18
[5]Kowalczyk R. Combining constraint programming and evolutionary algorithms in constrained decision optimization problem s [A]Proceeding of the 1997 International Conference on Neutral Information Processing and Intelligent Information Systems[C]Dunedin, New Zealand: 1997. 826-829
[6]Sigeru O. Incorporating Constraint Propagation in Genetic Algorithm for University Timetable Planning [M]. Engineering Applications of Artificial Intelligence, 1999. 241-253
[7]Colorni A, Dorigo M , Maniezzo V. Genetic algorithm and highly constrained problems: the timetable case[J]. Lecture Notes in Computer Science, 1991, (496): 55-59
[8]Colorni A, Dorigo M , Maniezzo V. Meta-heuristics for high school timetabling[J]Computational Optimization and Applications, 1998, (9): 275-298
[9]Paechter B, Luchian H, Petruic M. Two solutions to the general timetable problem using evolutionary methods[A]Proceedings of the 1’International Conference on Evolutionary Computation[C]Orlando, USA: IEEE Press,1994. 300-305
[10]Burke E K, New all J P. A phased evolutionary approach fox the timetableproblem [A] Proceedings of the 1997 International Conference on Neural Information Processing and Intelligent Information Systems[C].1997. 1038-1041
[11] 遗传算法—理论应用与软件实现.王小平,曹立明著. 西安.西安交通大学出版社.2001.1 ISBN 7-5605-1448-0 中国版本图书馆 CIP 数据核字(2001)第 079562 号
[12]遗传算法用于 NP 完全问题的求解. 杨青,马军. 1.山东公安专科学校,山东济南 250014;2.山东大学计算机系,山东济南 250100
[13]基于遗传算法的多目标问题求解方法.游进军,纪昌明,付湘,1.中国水利水电科学研究院水资源研究所,北京 100044;2.武汉大学水利水电学院,湖北武汉 430072
[14]基于遗传算法的大学课程表问题研究.熊焱,李大卫,王莉,张庆灵.1.鞍山科技大学理学院,辽宁鞍山 114044;2.东北大学理学院,辽宁沈阳110006
[15]多目标优化问题中一种改进的遗传算法.杨金明,吴捷,钟丹虹.华南理工大学电力学院,广东广州 510640
[16]遗传算法研究及其在排课系统中的应用.陈本庆.西南交通大学.2003 硕士
[17]遗传算法在高校排课管理中应用的研究. 范玉玲.山东师范大学.2004硕士
[18]排课的遗传算法.梁立,徐敏,高丽金.云南师范大学计算机科学与信息技术学院,云南昆明 650092
[19]约束满足问题的一类权值学习算法.张千里.福州大学 2001 硕士
[20]基于认知的空间拓扑关系表示与推理.皇甫涛.重庆大学 2004 硕士