摘要
时间表问题是运筹学领域和系统工程领域中的典型组合优化问题,是由于事件对时间和空间的资源争夺而产生的,属于NP完全类问题。大学课程表问题,作为时间表问题的一个重要组成部分,是时间表问题的研究重点,研究该类问题的解决方法和技巧,是极具理论和实际意义的。群集智能,则由于其在解决分散的、强非线性的、多变量问题中的独特优势,而得到众多研究者的重视,成为一个新的研究方向和热门课题。然而尽管群集智能在很多方面得到了应用,但在大学课程表问题这一领域,却未能得到比较好的应用。
因为上述原因,本文研究了如何基于群集智能来解决大学课程表问题,其主要贡献有:
(1)介绍了自然界中鸟群的一些栖落习性和大学课程表的一般解决步骤,然后通过模拟鸟群的栖落习性,建立了大学课程表问题的鸟群栖落模型;
(2)讨论了学校课程集、学校教室集等集合的基本属性,给出了班级课程对信息素、班级教室信息素的计算公式,并分析了它们的基本特点;
(3)根据鸟群栖落模型及班级课程对信息素、班级教室信息素的特点,得到了一种新的解决大学课程表问题的鸟群栖落算法。文中详细介绍了该算法的基本原理和基本步骤,并给出了流程图;
(4)根据鸟群栖落算法,设计了一个自动编排大学课程表的软件系统。文中介绍了该系统软件平台的选择策略、输入输出界面的设计、程序编写的基本技巧等,并给出了该系统的测试结果。
最后的测试结果表明,鸟群栖落算法是可行且有效的,大学课程表自动编排系统软件平台的选择及输入输出界面的设计,是合适且方便的。
Timetable problem is a typical problem of combined optimization in the fields of operational research and systems engineering, which belongs to NP problem. The problem usully occurs when the events dispute their space-time resources each other. University curriculum schedule problem is one of important component of the timetable problem. It becomes a highlight of timetable problems to which a lot of reseacheres have paid more attentions. Recently, more and more scholars have been focusing on swarm intelligence, because of its properties in the field of optimization. Althogh a variety of applications by swarm intelligence have been achived, the university curriculum schedule problem has not been extended, so it is of interest to study how to solve the university curriculum schedule problem based on swarm intelligence.
For the above reason, this thesis presents a modeling, algorthim and design of a software system for the university curriculum schedule problem, by using swarm intelligence. The main contributions of this thesis are listed following:
(1) The occupancy habits of a group of birds and the general steps for planning a university curriculum schedule are introduced firstly. Then, a bird occupancy model for university curriculum schedule planning is proposed with simulation of the occupancy habits of birds.
(2) Some properties of certain sets, such as university subject set and university classroom set, are discussed. The formulas for class-subject pheromore and class-classroom pheromore are given and their basic properties are derived.
(3) According to the model and the conditions of university timetable problems and the properties of class-subject pheromore and class-classroom pheromore, an algorithm for automatic planning of university timetable is presented, which can automatically plan timetables and consider the problem of deadlocks by coordination when the plan is in progress. The basic principle and general steps of the algorithm are introduced with its flow chart.
(4) In order to implement the proposed algorithm, a software system is
designed for university curriculum schedule problem, and its selecting strategy of software platform and the design of input-output interface are also introduced. Furthermore, the algorithm is programmed.
Finally, the testing result shows that the proposed algorithm for automatic planning of university timetable is feasible and effective. The design of the software system is of convenience.
引文
[1]Garey M R,Johnson D S.Computer and Intractability:A Guide to the Theory of NP Completeness[M].San francisco:W H Freeman Co,1979.
[2]刘飞.大学考试时间表问题的算法研究.鞍山市:鞍山科技大学硕士学位论文.2004.
[3]Carter M.W.,Laporte,G..Recent developments in practical examination Timetabling.In:(Burke,Ross,1996),pp.3-21.
[4]Carter M.W.,Laporte G..Recent developments in practical course timetabling.In:(Burke,Carter,1998),pp.3-19.
[5]Schaerf A.Local search techniques for large high school timetabling problems.IEEE Transactions on Systems,Man and Cybernetics Part A:Systems and Humans,1999,129(4):368-377.
[6]A.Colorni,M.Dorigo and V.Maniezzo.Metaheuristics for high school timetabling.Computational Optimization and Applications.1998.9,pp.275-298.
[7]李明.一个基于智能化搜索的排课表演算法及其client/server实现,现代计算机,1997.59,21-22.
[8]洪力奋.基于人工智能原理的大学课表编排模型.合肥工业大学学报(自然科学版).1999.22(4),101-104.
[9]周建新,王科俊等.课表编排专家系统.计算机应用.2000,20(5),76-78.
[10]陈洁.学校教务部门排课问题的数学模型及算法.管理信息系统.1999.3.53-56.
[11]董艳云,钱晓群,张宇舒.基于课元相关运算的高校排课算法.甘肃交通大学学报.1998.33(6),670-673.
[12]F.Luan and X.Yao.Solving real-world lecture room assignment problems by genetic algorithms.Complexity International,An Electronic Journal of Complex System Research,1996.3,pp.87-90.
[13]D.Safaai and O.Sigeru.Incorporating constraint propagation in genetic algorithm for university timetable planning.Engineering Applications of Artificial Intelligence.1999.35(2),pp.241-253.
[14]张春梅,行飞.用自适应的遗传算求解大学课表安排问题.内蒙古大 学学报(自然科学版).2002.33(4),459-464.
[15]张春梅,行飞,梁治安.课表的多指标数学模型及解决办法.[J]内蒙古大学学报(自然科学版).2004,35(2):139-144.
[16]M.Wright.School Timetabling using Heuristic Search.J.Opnl.Rcs.Soc,47(3),pp.347-357,1996.
[17]A.Hertz.Finding a feasible course schedule using tabu search.Discrete Applied Mathematics.35(2),pp.250-270,1992.
[18]A.Abramson.Constructing school timetables using simulated annealing:Sequential and Parallel Algorithms.Management Science,37(1),pp.98-113,1991.
[19]吴金荣.关于大学课程表问题的研究.运筹与控制.2002.11(6),66-71.
[20]吴金荣.求解课程表问题的分支定界算法.运筹与管理,2002,11(17).
[21]魏平,熊伟清.计算机辅助课表编排技术的研究[J].甘肃工业大学学报,1997,23(4):76-81.
[22]熊伟清,魏平,赵杰煜.用遗传算法求解时间表问题[J].微电子学与计算机,2002.
[23]王祜民,赵致格.排课表问题中的分组优化决策算法[J].控制与决策,1999,14(2):109-114.
[24]王祜民,赵致格.时间表问题中的定额匹配算法[J].清华大学学报,1998,38(6):8-11.
[25]熊焱,李大卫,王莉.大学课程表问题的模型与算法[J].鞍山科技大学学报.2005,2:26-29.
[26]朱冠宇,王乘,席大春.利用遗传算法求解中学课表安排问题[J].计算机工程与应用,2004,27:215-218.
[27]夏鹭平.利用人工智能原理实现大学课程表调度.微电子学与计算机,1992年,第10期,46.
[28]郭方铭等.采用增强学习算法的排课模型.计算机工程与设计,24卷,11期,2003,125.
[29]郑新春,柴佩琪.遗传算法在课程表优化组合问题中的应用(J).清华大学学报(自然科学版),1998.38(S2):114-117.
[30]Marco Dorigo,Vittorio Maniezzo,Alberto Colorni.The ant system:Optimization by a colony of cooperating agents[J].IEEE Transaction on Systems,1996,26(1):1-261.
[31]Colorni A,Dorigo M,Maniezzo V.Distributed Optimization by Ant Colonies[C].Proceeding Of The First European Conference Artificial Life.Paris,France.Elsevier Publish2ing,1991,134-142.
[32]Colorni A,Dorigo M,Maniezzo V.An Investigation of Some Properties of an Ant Algorithm.Proc PPSN'92:509-520.
[33]Colorni A,Dorigo M,Maniezzo V,Trubian M.Belgian[J].Oper.REs.Statist.Comp.Sci.,1994,34(1):39-53.
[34]L.M.Gambardella and M.Dorigo.Ant - Q:A reinforce2ment learning approach to the traveling salesman problem[J].In Proceedings of the Twelfth International Conference on Machine Learning,ML - 95.Palo Alto,CA:Morgan Kaufmann,1995:252-260.
[35]M.Dorigo,L.M.Gambardella.Ant colony system:a co2operative learning approach to the traveling salesman prob21em,IEEE Trans.Evolution Compute.1997,1(1):53-66.
[36]马军建,董增川,王春霞,陈康宁.蚁群算法研究进展.河海大学学报(自然科学版).2005,33(2):139-143.
[37]Eberhart R C,Kennedy J.A new optimizer using part i2cles swarm theory [A].Proc Sixth Int Symposium on Micro Machine and Human Science[C].Nagoya,1995.39243.
[38]高 尚,韩 斌,吴小俊,杨静宇.求解旅行商问题的混合粒子群优化算法.控制与决策.2004,19(11):1286-1289.
[39]Marco Dorigo,Luca Maria Gambardella.Ant Colony System:A Cooperative Learning Approach to the Traveling Salesman Problem.the IEEE Transactionson Evolutionary Computation,Vol.1,No.1,1997.In press.1996.
[40]I.Kassabalidis,M.A.El-Sharkawi.Swarm Intelligence for Routing in Communication Networks.IEEE 2001.
[41]Eric Bonabeaul,Florian Henaux.Routing in telecommunications networks with "smart" ant-like agents.Proc.Intelligent Agents for Telecommunications Applications '98.
[42]Robinson,G.E.Regulation of Vision of Labor in Insect Societies.Annu.Rev.Entomol.37 pp.637-665,1992.
[43]Eric Bonabeau and Christopher Meyer:Swarm intelligence;a whole new way to think about business. Harvard Business Review,May 2001.
[44] William Agassounon, Alcherio Martinoi, Rodney Goodman . A Scalable, Distributed Algorithm for Allocating Workers in Embedded System. Proceedings of the 2001 IEEE Systems, Man and Cybernetics Conference 2001.
[45] Vitorino Ramos and Juan J. Merelo. Self-Organized Stigmergic Document Maps:Environment as a Mechanism for Context Learning. AEB02 MERIDA, 2002.
[46] J.-L. Denebourg, S. Goss, N. Franks, A. Sendova- Franks, C. Detrain, L. Chretien (1991). The Dynamic of Collective Sorting Robot-like Ants and Ant-like Robots. In J.A. Meyer, S.W. Wilson (Eds.), Procs. of SAB'90 - 1st Conf. on Simulation of Adaptive Behavior: From Animal to Animats, Cambridge, MA: MIT Press, pp. 356-365.
[47] R. Schoonderwoerd, O.E. Holland, J.L. Bruten. Ant-like agents for load balancing in telecommunications networks. Proc. 1st ACM International Conference on Autonomous Agents, February 5-8, 1997, Marina del Rey, CA, USA, pp. 209-216.
[48] P.P. Grasse, La reconstruction dunid etles.coordinations interindividuelles chez bellicositermes natalensis et cubitermes sp. La theorie de la stigmergie: essaid'interpretation du comportement des termites constructeurs, Insectes Sociaux 6(1959) 41-81.
[49] Beckers R. Holland O.E. and Deneubourg J.L. From local actions to global tasks: Stigmergy and collective robotics. Brooks R. and Maes P. Artificial Life IV, (pp. 181-189) MIT Press 1994.
[50] E. Bonabeau, M. Dorigo, and G. Theraulaz, Swarm Intelligence: From Natural to Artificial Systems. Oxford, U.K.: Oxford Univ. Press, 1999.
[51] K. Passino. Biomimicry of bacterial foraging for distributed optimization and control. IEEE Control Syst. Mag., vol. 22, pp. 52-67, June 2002.
[52] R. Arkin. Behavior-Based Robotics. Cambridge, MA: MIT Press, 1998.
[53] G. Beni and J.Wang. Swarm intelligence in cellular robotics systems. Proc. NATO Advanced Workshop Robots Biological System, 1, pp. 703-712.
[54] Vincent A. Cicirello and Stephen F. Smith. Ant Colony Control for Autonomous Decentralized Shop Floor Routing.Fifth International Symposium on Autonomous Decentralized Systems,IEEE Computer Society,March 2001.
[55]Marco Dorigo,Eric Bonabeau,Guy Theraulaz.Ant algorithms and Stigmergy.Future Generation Computer Systems 16(2000)851-871,2000.
[56]Owen Holland and Chris Melhuish.Stigmergy,self-organisation,and sorting in collective robotics.Artificial Life 5,173-202(1999)1999.
[57]Vitorino Ramos and Juan J.Merelo.Self-Organized Stigmergic Document Maps:Environment as a Mechanism for Context Learning.AEB'2002-1st Spanish Conference on Evolutionary and Bio-Inspired Algorithms,2002.
[58]CARL ANDERSON.Self-Organization in Relation to Several Similar Concepts:Are the Boundaries to Self-Organization Indistinct? Biol Bull.2Jun;202(3):247-55 2002.
[59]Istv'an Karsai.Decentralized Control of Construction Behavior in Paper Wasps:An Overview of the Stigmergy Approach.Artificial Life 5:117-136 1999.
[60]G.Di Caro and M.Dorigo.Ant colony routing.PECTEL 2 Workshop on Parallel Evolutionary Computation in Telecommunications,Reading,England,April 6-7,1998.
[61]G.Beni and J.Wang.Swarm intelligence in cellular robotics systems.Proc.NATO Advanced Workshop Robots Biological System,1,pp.703-712.
[62]G.Dudek and et al..A taxonomy for swarm robots.IEEE/RSJ Int.Conf.on Intelligent Robots and Systems,(Yokohama,Japan),July 1993.
[63]韩春松.具有双链形通信拓扑结构的群集稳定性分析.鞍山科技大学硕士论文.2006.3.