摘要
蚁群优化(ACO)算法在国内外已经取得了很多的研究成果,也有很多应用证实了其在解决组合优化问题中的优越性,本文研究将ACO算法应用于大学课程时间表问题。
本文分析了大学课程时间表问题(UCTP)的特征和求解目标,结合已有蚂蚁算法(MMAS)的求解策略,构建了一个新的大学课程时间表问题的求解模型,相比原有的MMAS求解UCTP算法,新的计算模型充分利用启发式搜索的特征,定义了基于软限制条件的新的启发因子,并在不同规模的问题实例上进行实验,结果表明本文的MMAS算法框架可以方便地融合新的技术来提高解的质量。
鉴于任何元启发算法在解决特定问题时,都必须充分分析问题实例的特征、结合问题本身的逻辑,本文对新MMAS-UCTP算法进行了改进,对按照一般ACO准则构造出来的解进行可行化,具体采用了三种可行化技术:improve,shu?e,survive,结果表明改进后的算法质量有明显地提高。
最后,所有的蚂蚁通过共享同一信息素的方式并行构造解,实现了本课题中MMAS-UCTP算法的并行化。实验表明,并行化的结果在解的质量和运行时间方面都有很好的表现。
Ant colony algorithms have been well studied all over the world. There are a lotof successful applications which prove that ACO algorithms are good solutions to mostof the Combinational Optimization Problems. This thesis studies how to apply ACOalgotrithm to the University Timetabling Problem(UCTP).
On the basis of analyzing the properties of UCTP and the object of the prob-lem,a new computing model which combines with the max-min ant system(MMAS)algorithm is constructed. Compared with the original MMAS-UCTP, the new modeltakes more advantage of metaheuristic searching strategy and is enhanced with a newheuristic information which relies on the soft constraint violation(scv). The algorithmis implemented and tested on several problems with di?erent scales and the resultsshow that the new MMAS-UCTP can conveniently merge the new techniques, whichmay improves the solution’s quality.
It is well known that any metaheuristic algorithms should analyze the propertiesand the logic of the given problem before solving it. Here the thesis try to improve theMMAS-UCTP algorithm, i.e. to make the solutions constructed by the general ACOalgorithm feasible. Specifically speaking, the technique includes three parts named im-prove, shu?e and survive, the experiments show that the results are highly improved.
Finally, the thesis parallelize the new MMAS-UCTP algorithm by parallelizingant’s solution construction with sharing a common pheromone matrix. The experi-ments show that the final solution achieves good performance on both solution qualityand running time.
引文
[1] C.C. Gotlieb. The Construction of Class-Teacher Timetables. In C.M. Popplewell,editor, IFIP Congress 62, pages 73–77, North-Holland, 1963.
[2] T. B. Cooper and J. H. Kingston. The Complexity of Timetable ConstructionProblems. In Proceedings of the 1st International Conference on Practice andTheory of Automated Timetabling (PATAT 1995), LNCS 1153, pages 283–295.Springer-Verlag, 1996.
[3] G. Schmidt and T. Strohlein. Timetable Construction - an Annotated Bibliogra-phy. The Computer Journal, 23(4):307–316, 1979.
[4] A. Tripathy. School Timetabling - A Case in Large Binary Integer Linear Pro-gramming. Management Science, 30(12):1473–1489, 1985.
[5] A. Tripathy. Computerised Decision Aid for Timetabling - A Case Analysis. Dis-crete Applied Mathematics, 35(3):313–323, 1992.
[6] M. Dimopoulou and P. Miliotis. Implementation of a University Course andExamination Timetabling System. European Journal of Operational Research,130(1):202–213, 2001.
[7] R. Ostermann and D. D. Werra. Some Experiments with a Timetabling System.OR Spektrum, 3:199–204, 1983.
[8] G. A. Neufeld and J. Tartar. Graph Coloring Conditions for the Existence ofSolutions to the Timetable Problem. Communications of the ACM, 17(8):450–453, 1974.
[9] C. D. Wood. A Technique for Colouring a Graph Applicable to Large ScaleTimetabling Problem. Computer Journal, 12(4):317–319, 1969.
[10] M. A. S. Elmohamed, P. Coddington, and G. Fox. Comparison of Annealing Tech-niques for Academic Course Scheduling. In Proceeding of the 2nd InternationalConference on Practice and Theory of Automated Timetabling (PATAT 1997),pages 92–115, 1998.
[11] L. D. Gaspero and A. Schaerf. Tabu Search Techniques for ExaminationTimetabling. In Proceedings of the 3rd International Conference on Practice andTheory of Automated Timetabling (PATAT 2000), LNCS 2079, pages 104–117.Springer-Verlag, 2001.
[12] S. K. Mirrazavi, S. J. Mardle, and M. Tamiz. A Two-Phase Multiple ObjectiveApproach to University Timetabling Utilizing Optimization and Evolutionary So-lution Methodologies. Journal of the Operational Research Society, 54(11):1155–1166, 2003.
[13] T. B. Cooper and J. H. Kingston. The Solution of Real Instances of theTimetabling Problem. The Computer Journal, 36(7):645–653, 1993.
[14] A. Colorni, M. Dorigo, and V. Maniezzo. Metaheuristics for High SchoolTimetabling. Computational Optimization and Applications, 9(3):275–298, 1998.
[15] A. Schaerf. A Survey of Automated Timetabling. Technical report, CS-R9567,CWI, Amsterdam, Netherlands, 1995. To Appear in Artificial Intelligence Review.
[16] 朱文兴,张千里. 基于GENET的时间表问题自动求解算法. 小型微型计算机系统, 24(7):1335–1337, 2003.
[17] 唐勇,唐雪飞,王玲. 基于遗传算法的排课系统. 计算机应用, 10:93–97, 2002.
[18] 汪红星,康立山,陈毓屏. 基于演化算法的一类时间表问题的自动求解. 小型微型计算机系统, 21(5):469–471, 2000.
[19] 丁德路,姜云飞. 基于智能规划的时间表问题研究. 小型微型计算机系统,24(2):246–250, 2003.
[20] 吴金荣. 求解课程表问题的分支定界算法. 中国科学院数学与系统科学研究院,2002.
[21] M. Dorigo, V. Maniezzo, and A. Colorni. The Ant System: Optimization by aColony of Cooperating Agents. IEEE Transactions on Systems, Man and Cyber-netics, 26:29–41, 1996.
[22] S. E. Cross and E. D. Walker. Applying Knowledge-Based Planning and Schedulingto Crisis Action Planning. Morgan-Kaufmann, San Francisco, 1994.
[23] T. Stutzle and H. H. Hoos. MAX-MIN Ant System. Future Generation ComputerSystems, 16(8):889–914, 2000.
[24] 何军. 解优化问题的退火回火算法. 武汉大学学报–并行计算专刊, 1991,43-48.
[25] D. Abramson. Constructing School Timetables Using Simulated Annealing: Se-quential and Parallel Algorithms. Management Science, 17(1):98–113, 1991.
[26] 李增智,王云岚. 课程表问题的一种混合型模拟退火算法. 西安交通大学学报,37(4):343–345, 2003.
[27] 王伟,于利华. 基于贪心法和禁忌搜索的实用高校排课系统. 计算机应用,27(11):2873–2876, 2007.
[28] A. Tripathy. School Timetabling - A Case in Large Binary Integer Linear Pro-gramming. Discrete Applied Mathematics, 35(3):313–323, 1984.
[29] H. L. Fang. Genetic Algorithms in Timetabling and Scheduling. PhD thesis,Department of Artificial Intelligence, University of Edinburgh, Edinburgh, 1994.
[30] In E. Burke and B. Paechter, editors, Proceeding of the 1st International Con-ference on the Practice and Theory of Automated Timetabling. Springer-Verlag,1995.
[31] 业宁,梁作鹏. 一种基于遗传算法的TTP问题求解算法. 东南大学学报:自然科学版, 33(1):41–44, 2003.
[32] J. M. Thompson and K. A. Dowsland. A Robust Simulated Annealing BasedExamination Timetabling System. Computers Ops Res, 25(7):634–648, 1998.
[33] R. A. Valdes, E. Crespo, and J. M. Tamarit. Design and Implementation of aCourse Scheduling System Using Tabu Search. Production, Manufacturing andLogistics, European Journal of Operational Research, 137:512–523, 2002.
[34] 向阳. 推广模拟退火方法及应用. 中国科学院固体物理研究所, 2000.
[35] K. Socha, J. Knowels, and M. Sampels. A MAX-MIN Ant System for the Uni-versity Course Timetabling Problem. In M. Dorigo, G. D. Caro, and M. Sampels,editors, Proceedings of the 3rd International Workshop on Ant Algorithms (ANTS’2002), LNCS 2463, pages 1–13. Springer Verlag Berlin Heidelberg, 2002.
[36] PATA2002 Competition Website. http://www.idsia.ch/files/ttcomp2002.
[37] M. Yoshikawa, K. Kaneko, T. Yamanouchi, and M. Watanabe. A Constraint-BasedHigh School Scheduling System. IEEE Expert, 11(1):63–72.
[38] 吴小娟,吕强. 一种基于贡献的蚁群算法信息素分配策略. 微计算机信息,5(3):238–239, 2008.
[39] S. Abdullah, E. K. Burke, and B. McCollum. Using a Randomised Iterative Im-provement Algorithm with Composite Neighbourhood Structures for the Univer-sity Course Timetabling Problem. In Proceedings of the 6th Metaheuristics Inter-national Conference (MIC 05), Vienna, Austria, 2005.
[40] S. Abdullah, E. K. Burke, and B. McCollum. An Investigation of Variable Neigh-bourhood Search for University Course Timetabling. In Proceedings of the 2ndMultidisciplinary International Conference on Scheduling: Theory and Applica-tion (MISTA 2005), pages 413–427, New York, USA, July 2005.
[41] E. K. Burke, G. Kendall, and E. Soubeiga. A Tabu Search Hyperheuristic forTimetabling and Rostering. Journal of Heuristics, 9(6):451–470, 2003.
[42] E. K. Burke, B. McCollum, A. Meisels, and R. Qu. A Graph-Based Hyper Heuris-tic for Educational Timetabling Problems. European Journal of Operational Re-search, 176(1):177–192, January 2007.
[43] P. Kostuch. The University Course Timetabling Problem with a Three-phaseApproach. In E. Burke, editor, Practice and Theory of Automated Timetabling V,LNCS 3616, pages 109–125, 2005.
[44] 吴小娟,吕强. 新蚁群算法模型在大学课程时间表问题中的应用. 计算机应用与软件. 已录用待发.
[45] 吕强,高彦明,钱培德. 共享信息素矩阵:一种新的并行ACO方法. 自动化学报,33(4), 2007.
[46] 潘吉斯,吕强,王红玲. 一种并行蚁群Bayesian网络学习的算法. 小型微型计算机系统, 28(4), 2007.