基于进化计算的智能排课系统开发
|
摘要
一所学校为了保证其高水平的教学质量，必须制定一套严密、规范的教学计划，并严格执行。而课表管理是其中最为关键的一环。没有一个合理、准确与规范的课程表，整个学校的教学秩序将混乱不堪，这是不难想象的。由此可见课程安排在学校教学计划中的核心地位与重要性。因此，很有必要对排课表问题进行深入研究。但由于各种原因，特别是在大学里，已经普遍实行学分制和选修制，学生上课的教室并不固定，这使排课问题成为一个众所周知的数学难题，吸引了许多人尝试解决它。
使用手工或传统的方法来排课，不仅工作量巨大，耗时、耗资，且准确率低。本文利用软件工程的方法，从排课系统的需求分析，建立系统数据模型，进而对系统进行总体设计，详细设计，最终使系统得以实现并投入使用。作者从人工智能中进化计算的角度，给出一种使用进化模拟退火算法求解课表问题的方案，详细讨论了该方案涉及的各种问题，包括目标函数和初解的确定，临域和新解的产生方法，初始“温度”的确定和“温度”更新的方式，内循环次数及算法终止条件的确定等，对一些具体的技术问题作出相应安排。
该算法已在Windows 2000操作平台上实现，具体使用的开发方法是Delphi可视化程序设计方法，算法的实现充分利用了面向对象的、灵活而又强大的Delphi高级程序设计语言，同时为了进一步满足实用要求，还对算法进行了交互式扩充，使其具有查询、排课、调课、增加、删除等功能，并且全部过程都是通过与用户交互来进行的。实现的系统经应用表明，具有较好的适应性和实用性。
In order to guarantee its advanced teaching and studying quality, a university must draw up a tight and standard teaching and studying plan. The arrangement of curriculum schedule is one of the key questions. Not having a rational, accurate and normal curriculum schedule, the whole university will not has a well teaching and studying order. This shows the courses arranging is the core of teaching and studying plan. Accordingly, deeply studying the question of curriculum schedule is very necessary. As a result of some causes, especially in university, the credit_system and elective_system has universally put into practice, the classrooms of students' classes are not stable, as everyone knows the courses arranging is a mathmatic difficult problem. A lot of people are attracted to study it.
Arranging the courses by hand and traditional ways, we have great work load, cost much time, use up many resources , but the accuracy of curriculum schedule is low. This paper uses the method of software engineering, from requesting analysis of the courses arranging system, sets up data model, designs the structure in the total and in detail. In the last, the system is put into practice. In view of Evolutionary Computation in Artificial Intelligence, the author gives a scheme to solve the course scheduling problem using evolutionary simulated annealing algorithm,and discusses variable problems of the scheme such as target function and initial solution,the method to generate neighboring area and new solution,initial "temperature" selection and the formulation to produce new "temperature", inner cycle number and determinal condition solution, some technical problems in college course arrangement are discussed.
The algorithm has carried on the achievements in Windows 2000 operating system. The actual developing means is one of the visual programming methods-Delphi. The pratice of the algorithm makes full of Delphi programming language. At the same time, in the purpose of further meeting using demands, this paper goes on exchanging augmentation to the algorithm, makes it having many functions on inquiring, arranging, dispatching, increasing, deleting and so on. It is proved that the software developed with the algorithm has good adaptability and availability.
使用手工或传统的方法来排课，不仅工作量巨大，耗时、耗资，且准确率低。本文利用软件工程的方法，从排课系统的需求分析，建立系统数据模型，进而对系统进行总体设计，详细设计，最终使系统得以实现并投入使用。作者从人工智能中进化计算的角度，给出一种使用进化模拟退火算法求解课表问题的方案，详细讨论了该方案涉及的各种问题，包括目标函数和初解的确定，临域和新解的产生方法，初始“温度”的确定和“温度”更新的方式，内循环次数及算法终止条件的确定等，对一些具体的技术问题作出相应安排。
该算法已在Windows 2000操作平台上实现，具体使用的开发方法是Delphi可视化程序设计方法，算法的实现充分利用了面向对象的、灵活而又强大的Delphi高级程序设计语言，同时为了进一步满足实用要求，还对算法进行了交互式扩充，使其具有查询、排课、调课、增加、删除等功能，并且全部过程都是通过与用户交互来进行的。实现的系统经应用表明，具有较好的适应性和实用性。
In order to guarantee its advanced teaching and studying quality, a university must draw up a tight and standard teaching and studying plan. The arrangement of curriculum schedule is one of the key questions. Not having a rational, accurate and normal curriculum schedule, the whole university will not has a well teaching and studying order. This shows the courses arranging is the core of teaching and studying plan. Accordingly, deeply studying the question of curriculum schedule is very necessary. As a result of some causes, especially in university, the credit_system and elective_system has universally put into practice, the classrooms of students' classes are not stable, as everyone knows the courses arranging is a mathmatic difficult problem. A lot of people are attracted to study it.
Arranging the courses by hand and traditional ways, we have great work load, cost much time, use up many resources , but the accuracy of curriculum schedule is low. This paper uses the method of software engineering, from requesting analysis of the courses arranging system, sets up data model, designs the structure in the total and in detail. In the last, the system is put into practice. In view of Evolutionary Computation in Artificial Intelligence, the author gives a scheme to solve the course scheduling problem using evolutionary simulated annealing algorithm,and discusses variable problems of the scheme such as target function and initial solution,the method to generate neighboring area and new solution,initial "temperature" selection and the formulation to produce new "temperature", inner cycle number and determinal condition solution, some technical problems in college course arrangement are discussed.
The algorithm has carried on the achievements in Windows 2000 operating system. The actual developing means is one of the visual programming methods-Delphi. The pratice of the algorithm makes full of Delphi programming language. At the same time, in the purpose of further meeting using demands, this paper goes on exchanging augmentation to the algorithm, makes it having many functions on inquiring, arranging, dispatching, increasing, deleting and so on. It is proved that the software developed with the algorithm has good adaptability and availability.
引文
[1]张海藩．软件工程导论．1999，清华大学出版社
[2]Schmidt G, Strohlein T. Timetable Construction-An Annotated Bibliography. The Computer Journal, 1980, Vol. 23, No. 4, PP. 307-391
[3]Bondy J.A. Graph Theory with Application. 1976, The Macmilan Press Ltd.
[4]周建新．课表编排专家系统．计算机应用，2000，Vol．20，No．5，PP．76-78
[5]董艳云．基于课元相关运算的高校排课算法．西南交通大学学报，1998，Vol．33，No．3，PP．670-673
[6]崔雪梅．自动排课算法设计．延边大学学报，2000，Vol．26，No．3，PP．214-217
[7]费雅洁．基于C／S的开放式智能排课系统的研制．沈阳电力高等专科学校学报，2000，Vol．2，No．3，PP．49-51
[8]龙一飞．基于知识推理的排课系统．电脑开发与应用，2000，Vol．13，No．6，PP．35-37
[9]肖玉巍．排课自动校验系统的研制与开发．山西经济管理干部学院学报，2000，Vol．10，No．2，PP．62-64
[10]王力．高校通用排课管理信息系统的设计与实现．贵州工业大学学报，1999，Vol．28，No．1，PP．87-90
[11]石纯一．人工智能原理．1993，清华大学出版社
[12]陆汝铃．人工智能．1989，科学出版社
[13]Ibrahim H Osman. Heuristics for the Generalised Assignment Problem: Simulated Annealing and Tabu Search Approaches. OR Specktrum, 1999, Vol. 17, No.1, PP.211-255
[14]Kirk Patrick S. Optimization by Simulated Annealing: Ouantitative Studies. J Statis Phy, 1999, Vol. 34, No. 2, PP. 975-986
[15]Fogel L. J. Artificial Intelligence through Simulated Evolution. 1966, John Wiley and Sons Press Ltd.
[16]Yip P.,Yoh-han Pao. Combinatorial Optimization with Use of Guided Evolutionary Simulated Annealing. Neural Networks, 1995, Vol. 6, No. 2, PP. 290-295
[17]刘健勤．人工生命理论及其应用．1997，冶金工业出版社
[18]丁承民，张传生，刘辉．遗传算法纵横谈．信息与控制，1997，Vol．26，No．2，PP．40-47
[19]Alan F. Smeaton. Using Hypertext for computer Based Learning. Computer and Education, 1991, Vol. 17, No. 3, PP. 173-180
[20]M. H. Odocherty etc. Multimedia Information System-The Management and Semantic Retrieval of all Electronic Data Type. The Computer Journal, 1997, Vol. 34, No. 3, PP. 165-172
[21]Xiaofeng Qi, Francesco Palmieri. Theoretical Analysis of Evolutionary Algorithms with an Infinite Population Size in Continuous Space. Part Ⅰ:Basic Properties of Selection and Mutation. Neural Networks, 1994, Vol. 5, No. 1, PP. 102-119
[22]周明, 孙树栋．遗传算法原理与应用．1999，国防工业出版社
[23]Fang L., Li T. Design of Competition Based Neural Networks for Combinatorial Optimization. Int J Neural System, 1990, Vol. 5, No. 3, PP. 221-235
[24]林尧瑞，石纯一．专家系统原理与实践. 1988，清华大学出版社
[25]李明．一个基于智能化搜索的排课表算法及其Client/Server实现．现代计算
机，1997，Vol．35，No．6，PP．21-22
[26]曹娟．计算机辅助排课系统的数学模型的建立．东北电力学院学报，2000，Vol．20，No．1，PP．56-59
[27]俞盘详，沈金发．数据库系统原理．1988，清华大学出版社
[28]赵玉杰．计算机辅助排课系统软件的开发与应用．东北电力学院学报，1997，Vol．17，No．6．PP．52-56
[29]Glover F. Tabu Search part I. ORSAJ Comput, 1989, Vol. 25, No.1, PP. 190-206.
[30]Glover F., Laguna M. Tabu Search partⅡ. ORSAJ Comput, 1990, Vol. 26, No. 2, PP. 4-32
[2]Schmidt G, Strohlein T. Timetable Construction-An Annotated Bibliography. The Computer Journal, 1980, Vol. 23, No. 4, PP. 307-391
[3]Bondy J.A. Graph Theory with Application. 1976, The Macmilan Press Ltd.
[4]周建新．课表编排专家系统．计算机应用，2000，Vol．20，No．5，PP．76-78
[5]董艳云．基于课元相关运算的高校排课算法．西南交通大学学报，1998，Vol．33，No．3，PP．670-673
[6]崔雪梅．自动排课算法设计．延边大学学报，2000，Vol．26，No．3，PP．214-217
[7]费雅洁．基于C／S的开放式智能排课系统的研制．沈阳电力高等专科学校学报，2000，Vol．2，No．3，PP．49-51
[8]龙一飞．基于知识推理的排课系统．电脑开发与应用，2000，Vol．13，No．6，PP．35-37
[9]肖玉巍．排课自动校验系统的研制与开发．山西经济管理干部学院学报，2000，Vol．10，No．2，PP．62-64
[10]王力．高校通用排课管理信息系统的设计与实现．贵州工业大学学报，1999，Vol．28，No．1，PP．87-90
[11]石纯一．人工智能原理．1993，清华大学出版社
[12]陆汝铃．人工智能．1989，科学出版社
[13]Ibrahim H Osman. Heuristics for the Generalised Assignment Problem: Simulated Annealing and Tabu Search Approaches. OR Specktrum, 1999, Vol. 17, No.1, PP.211-255
[14]Kirk Patrick S. Optimization by Simulated Annealing: Ouantitative Studies. J Statis Phy, 1999, Vol. 34, No. 2, PP. 975-986
[15]Fogel L. J. Artificial Intelligence through Simulated Evolution. 1966, John Wiley and Sons Press Ltd.
[16]Yip P.,Yoh-han Pao. Combinatorial Optimization with Use of Guided Evolutionary Simulated Annealing. Neural Networks, 1995, Vol. 6, No. 2, PP. 290-295
[17]刘健勤．人工生命理论及其应用．1997，冶金工业出版社
[18]丁承民，张传生，刘辉．遗传算法纵横谈．信息与控制，1997，Vol．26，No．2，PP．40-47
[19]Alan F. Smeaton. Using Hypertext for computer Based Learning. Computer and Education, 1991, Vol. 17, No. 3, PP. 173-180
[20]M. H. Odocherty etc. Multimedia Information System-The Management and Semantic Retrieval of all Electronic Data Type. The Computer Journal, 1997, Vol. 34, No. 3, PP. 165-172
[21]Xiaofeng Qi, Francesco Palmieri. Theoretical Analysis of Evolutionary Algorithms with an Infinite Population Size in Continuous Space. Part Ⅰ:Basic Properties of Selection and Mutation. Neural Networks, 1994, Vol. 5, No. 1, PP. 102-119
[22]周明, 孙树栋．遗传算法原理与应用．1999，国防工业出版社
[23]Fang L., Li T. Design of Competition Based Neural Networks for Combinatorial Optimization. Int J Neural System, 1990, Vol. 5, No. 3, PP. 221-235
[24]林尧瑞，石纯一．专家系统原理与实践. 1988，清华大学出版社
[25]李明．一个基于智能化搜索的排课表算法及其Client/Server实现．现代计算
机，1997，Vol．35，No．6，PP．21-22
[26]曹娟．计算机辅助排课系统的数学模型的建立．东北电力学院学报，2000，Vol．20，No．1，PP．56-59
[27]俞盘详，沈金发．数据库系统原理．1988，清华大学出版社
[28]赵玉杰．计算机辅助排课系统软件的开发与应用．东北电力学院学报，1997，Vol．17，No．6．PP．52-56
[29]Glover F. Tabu Search part I. ORSAJ Comput, 1989, Vol. 25, No.1, PP. 190-206.
[30]Glover F., Laguna M. Tabu Search partⅡ. ORSAJ Comput, 1990, Vol. 26, No. 2, PP. 4-32
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |