摘要
当今，科学技术正处于多学科相互交叉和融合的时代，特别是计算机科学与技术的迅速发展，从根本上改变了人类的生产和生活。同时，随着人类生存空间的扩大以及认识与改造世界范围的拓展，人们对科学技术提出了新的和更高的要求，其中对高效的优化技术和智能计算的要求日益迫切。以神经网络、遗传算法等为代表的智能算法在各种工程领域的成功应用，激励人们从更广泛的生物或自然现象寻求启发以构造新的智能算法，来解决工程中广泛存在的复杂问题。作为新加入这个行列的蚁群算法(Ant Colony Optimization, ACO)，为复杂困难的系统优化问题提供了新的具有竞争力的求解算法。虽然蚁群算法的研究刚刚起步，但是这些初步研究已显示出蚁群算法在求解复杂问题，特别是离散优化问题方面的优越性，它是一种很有发展前景的方法。
时间表问题(Timetabling Problem, TTP)属于一类特殊的调度问题，是NP-难问题，用以解决一系列事件对时间和空间资源争夺而引起的冲突，在现实世界中有着巨大的应用价值。其中课程表的编排是时间表问题的典型应用，大多数对时间表问题的研究都是在课程时间表问题的基础上进行的。随着学校招生规模的扩大和办公信息化程度的提高，课程表自动生成已经成为越来越多学校的需求，先后产生了采用不同方法的自动排课系统。然而在实际中，教学规律对课程表编排的合理性要求，以及学校或教师对课程表编排的约束性要求又是大家共同关注的焦点。本文在对课程表问题概念模型和数学模型研究的基础上，提出了利用蚁群算法求解时间表问题的思路，并设计开发了蚂蚁排课系统。通过实验，证明了蚁群算法求解时间表问题的有效性，经过一定数量蚂蚁的优化过程，课程表编排的合理性得到了提高。
At present, technology is lying in the times of the crossing of the multi science.Especially with the rapid development of the computer's science and technology, it hasradically changed manufacture and lives of human being. At the same time, as the livingspace of human being explores and the ranges of cognizing and altering; the world extends,people are greatly requiring new and advanced technology, particularly in great need ofefficient optimization technology and intelligent calculation. Intelligent algorithm, such asNeural Network and Genetic Algorithm, applies successfully in the all kinds of engineeringfields, which stimulates people to search for enlighten to construct the new intelligentalgorithm from the biologic and natural phenomenon and to solve the problems widelyexisting in the engineering. As the Ant Colony Optimization, ACO, it affords thecompetitive algorithm for the optimizing of system. Although at the beginning of ACO, ithas shown the superiority of solving the complicated questions, especially in the dispersingoptimizing of system. It is the means of perspective.
The Timetabling Problem, is a NP-hard problem, belongs to the special schedulingproblems, which can deal with the conflict caused by scrabbling for time and spaceresource. It has great applying importance in reality. Among them, the: course table is thetypical application for Timetabling Problem. Most of problems are on the base of thecourse table. With the developing of college's recruiting and office's automatization, theautomatism of course table is in great need of many colleges. They have applied manyways to the automatism of course table. However, in reality, we all focus on the rationalityof teaching disciplinarian and restriction to the colleges and teachers. This article bringsforward the new ideas of course table in the use of ACO, and develops the Ant Tabling System, named ATS, on the base of concept model and math model. Through tests, it hasbeen proved effective that ACO is used in the course table. Through the process of usingACO, the rationality of course table has been improved.
引文
[1] 丁德路，姜云飞．基于智能规划的时间表问题研究．小型微型计算机系统，2003，24(2)：246-250．
[2] Even S, Itai A, Shamir A. On the Complexity of Timetable and Multicommodity Flow Problem [J]. SIAM Journal on Computing, 1976, 5 (4): 691-703.
[3] 熊焱，王莉，李大卫，张庆灵．大学课程表问题的模型与算法．鞍山科技大学学报，2005，28(1)：26-29．
[4] TRIPATHY A. School timetabling-a case in large binary integer linear programming[J]. Discrete Applied Math Ematics, 1984. 35(3): 313-323.
[5] 马允宜，刘志镜．图与图着色在计算机辅助排课表中的应用．西安工业学院学报，1994，14(4)：314-318．
[6] Luca Di Gaspero and Andrea Schaerf. Tabu search techniques for examination timetabling. In E. Burke and W. Erben, editors, Proceedings of PATAT 2000, volume 2079 of LNCS, Springer-Verlag, Berlin, Germany,2001. 104-117.
[7] 汪祖柱，程家兴，刘慧婷．基于遗传算法求解时间表问题．计算机工程与应用，2004，23：92-94．
[8] Fernandes C, et al. High school weekly timetabling by evolutionary algorithms. In: Proc. of the 1999 ACM symposium On Applied computing, Feb. 1999. 344-350.
[9] 刘继清，陈传波．模拟退火算法在排课中的应用[J]．武汉船舶职业技术学院学报，2003(3)；22-24．
[10] 朱红梅，梁永全，林晓霞，张勇．时间表问题的人工免疫算法研究．福建电脑，2005，7：50-51．
[11] Monfrogio A. Timetabling through constrained heuristic search and genetic algorithms [J]. Software Practice and Experience, 1996, 26(3): 251-279.
[12] 李增智，王云岚，陈靖．课程表问题的一种混合型模拟退火算法．西安交通大学学报，2003，37(4)：343-345．
[13] 任学惠，顿毅杰，管会生．一种求解TTP问题的SAGA算法．兰州理工大学学报，2006，32(1)：98-101．
[14] 李士勇，陈永强，李研．蚁算法及其应用．哈尔滨：哈尔滨工业大学出版社，2004．14-21．
[15] 张健．基于图论的高校排课系统实现．重庆师范大学学报(自然科学版)，2005，22(1)：35-38．
[16] 赵光哲．大学排课问题中的遗传算法设计．延边大学学报(自然科学版)，2006，32(1)：64-68．
[17] 江齐，兰竞．遗传算法在排课问题中的运用．重庆大学学报(自然科学版)，2005，28(1)：58-71．
[18] 王凌．智能优化算法及其应用．北京：清华大学出版社，2001．62-68．
[19] 李红，成新文．禁忌搜索与遗传算法在求解时间表问题中的对比研究．内蒙古师范大学学报自然科学(汉文)版，2003，32(4)：370-373．
[20] Bonabeau E, Dorigo M, and Theraulaz G.. Swarm intelligence: from natural to artificical systerms. New York: Oxford University Press, 1999.
[21] Blum C,and Roll A. Metaheuristics in Combinatorial Optimization:Overview and Conceptual Comparison.Technical Report TR/IRIDIA/2001-13,October 2001.
[22] 刘业政，凌海峰，杨善林．蚁群优化的研究进展及应用．合肥工业大学学报(自然科学版)，2006，29(1)：41-43．
[23] Gambardella L M, Dorigo M. Ant Q: a reinforcement learning approach to the traveling salesman problem[A]. Proceedings of the 12th International Conference on Machine Learning[C]. Tahoe City, CA: Morgan Kaufmann, 1995. 252-260.
[24] Dorigo M, Gambardella L M. Ant colony system: a cooperative learning approach to the traveling salesman problem[J]. IEEE Transactions on Evolutionary Computation, 1997, 1(1): 53-66.
[25] Stutzle T, Hoos H. The MAX-MIN ant system and local search for the traveling salesman problem[A]. IEEE International Conference on Evolutionary Co mputation and Evolutionary Programming [C]. Indianapolis, USA: IEEE Press, 1997. 309-314.
[26] Bullnheimer B, Hartl R F, Strauss C. A new rank-based version of the ant system: a computational study, Tech Rept POM-03/97[R]. Viena: Institute of Management Science, University of Vienna, Austria, 1997.
[27] 吴庆洪，张纪会，徐心和．具有变异特征的蚁群算法．计算机研究与发展．1999， 36(10)：1240-1245．
[28] 覃刚力，杨家本．白适应调整信息素的蚁群算法[J]．信息与控制，2002，31(3)：198-201．
[29] 谢剑英，王颖．一种自适应蚁群算法及其仿真研究[J]．系统仿真学报，2002，14(1)：31—33．
[30] 吴斌，史忠植．一种基于蚁群算法的TSP问题分段求解算法[J]．计算机学报，2002，24(12)：1328—1333．
[31] Dorigo M, IN Cago G. Ant colony optimization: a new meta-heuristic. [A]. Proceedings of ICEC99[C]. Washington 13(2), USA: IEEE Press, 1999. 1470-1477.
[32] 蔡自兴，徐光祐．人工智能及其应用．北京：清华大学出版社，2004．184-186．
[33] Zlochin M, Birattari M,Meuleau N, Dorigo M. Model-based search for combinatorial optimization.Technical Report TR/IRIDIA/2001-15, IRIDIA, Univerite'e Libre de Bruxelles, 2001.
[34] 张航，罗熊．蚁群优化算法的研究现状及研究展望[J]．信息与控制，2004，3：43-45．