（计算机应用技术专业论文）基于遗传算法的计算机排课系统研究与设计.pdf

摘要 摘要 排课是学校教学管理中十分重要、又相当复杂的工作之一。如何更好的解决教学工 作中的排课问题对整个教学计划的进行，起着十分重要的作用。随着高校教育事业的不 断发展，学生人数不断增加，课程开设也不断增加，使得原有的教务管理方法远远不能适 应形势的需要，而课程表编排则是解决这一问题的较好手段。因此，课程编排逐渐成为教 务管理的重要内容。 排课是一个多因素的优化决策问题，也是组合规划中的典型问题，同时又是一个很 有研究价值的实际问题。使用手工或传统的方法来排课，不仅工作量巨大、耗时、耗资， 且准确率低。使用常规方法解决这些问题，除了一些简单的情况之外，人们对于大型复 杂系统的优化和自适应问题显得无能为力。 经过对高校教务工作全面的调查和研究，结合高校教务管理中的实际要求，设计出 一种高效的教务管理系统。具体来说，教务排课管理系统的设计，必须考虑到各高校自 身的教学管理特点和特殊性。本系统采用自动排课和手工排课相结合，整个系统根据需 求划分为初始化管理功能、数据管理功能、排课管理功能、课表管理功能、系统管理功 能等五大功能模块。主要研究方法及成果如下：系统讨论了排课问题的影响因素、主要 约束条件、求解目标和难点，给出了排课问题的数学模型。分析了排课流程，给出了排 课系统的流程图。并充分利用计算机的优势，在国内外研究基础上从遗传算法的基本理 论入手，使用遗传算法设计了一个基于组件结构的排课系统。系统设计成组件结构，每 个组件完成一个较独立的逻辑功能，增加了系统的灵活性和可维护性。 关键词：排课；教务；遗传算法 人连交通人学i ：学硕十学何论文 a b s t r a c t c u r r i c u l u ma r r a n g e m e n ti sa ni m p o r t a n ta n dc o m p l i c a t e dw o r ki ns c h o o l ，s os o l v i n gt h e p r o b l e mi sv e r yi m p o r t a n c ef o rt e a c h i n gp r o g r a m m i n g a l o n gw i t hu n i v e r s i t ye d u c a t i o n u n c e a s i n gd e v e l o p m e n t ，t h es t u d e n tp o p u l a t i o ni n c r e a s e s ，t h ec u r r i c u l u ma l s ou n c e a s i n g l y i n c r e a s e s ，e n a b l e st h eo r i g i n a le d u c a t i o n a la d m i n i s t r a t i o nm a n a g e m e n tb yf 打t om e e tt h e s i t u a t i o nn e e d ，b u tt h ec l a s ss c h e d u l ea r r a n g e m e n ti sg o o dm e t h o dt os o l v e st h i sq u e s t i o n t h e r e f o r e ，t h ec u r r i c u l u ma r r a n g e sb e c o m e st h ei m p o r t a n tc o n t e n tg r a d u a l l yt ot h e e d u c a t i o n a la d m i n i s t r a t i o nm a n a g e m e n t c u r r i c u l u ma r r a n g e m e n ti sa no p t i m i z e dd e c i d i n gp r o b l e mo fm a n yf a c t o r s ，i ti sa l s ot h e t y p i c a lp r o b l e mi nc o m b i n a t i o np r o g r a m ，w h i l ei t i sap r a c t i c a lp r o b l e mt h a th a sm u c h r e s e a r c hv a l u e a r r a n g i n gt h ec o u r s e sb yh a n da n dt r a d i t i o n a lw a y s ，w eh a v eg r e a tw o r k l o a d ， c o s tm u c ht i m e ，u s eu pm a n yr e s o u r c e s ，b u tt h ea c c u r a c yo fc u r d c u l u ms c h e d u l ei sl o w r o u t i n em e t h o d sa r eq u i t eh e l p f u lr e s o l v i n gs i m p l eo p t i m i z a t i o na n ds e l f - a d a p t a t i o np r o b l e m s b u th e l p l e s sf o rc o m p l i c a t e dl a r g e s c a l es y s t e m s t h r o u g h w o r k st h e c o m p r e h e n s i v ei n v e s t i g a t i o n t ot h e u n i v e r s i t y e d u c a t i o n a l a d m i n i s t r a t i o na n dt h er e s e a r c h ，i nu n i o nu n i v e r s i t ye d u c a t i o n a la d m i n i s t r a t i o nm a n a g e m e n t a c t u a lr e q u e s t ，d e s i g n so n ek i n do fh i g h l ye f f e c t i v ee d u c a t i o n a la d m i n i s t r a t i o nm a n a g e m e n t s y s t e m c o n c r e t e ，e d u c a t i o n a la d m i n i s t r a t i o nc u r r i c u l u ma r r a n g e m e n ts y s t e md e s i g n ，m u s t c o n s i d e rv a r i o u su n i v e r s i t i e so w nt e a c h i n gm a n a g e m e n tc h a r a c t e r i s t i ca n dt h ep a r t i c u l a r i t v t h i ss y s t e mu s e st h ea u t o m a t i cc u r d c u l u m a r r a n g e m e n ta n dt h em a n u a lc u r d c u l u m a r r a n g e m e n tu n i f i e s t h eo v e r a l ls y s t e md i v i d e si n t ot h ei n i t i a l i z a t i o nm a n a g e m e n tf u n c t i o n ， c u r r i c u l u ma r r a n g e m e n tm a n a g e m e n tf u n c t i o n ，c l a s ss c h e d u l em a n a g e m e n tf u n c t i o n ，s y s t e m a d m i n i s t r a t i o nf u n c t i o na n ds oo nf i v ef u n c t i o n sa c c o r d i n gt ot h ed e m a n d t h em a i nr e s e a r c h m e t h o d sa sf o l l o w s ：t h es y s t e md i s c u s s e dt h eq u e s t i o nt h a ti n f l u e n c ef a c t o ro fc u r f i c u l u m a r r a n g e m e n t ，t h em a i nc o n s t r a i n tc o n d i t i o n ，s o l u t i o ng o a la n dd i f f i c u l t y ，a n dg i v e nt h e m a t h e m a t i c a lm o d e lo fc u r r i c u l u ma r r a n g e m e n t i th a sa n a l y z e dt h ec u r r i c u l u ma r r a n g e m e n t f l o w ，a n dg i v e nt h ec u r r i c u l u ma r r a n g e m e n tf l o wc h a r t t h i ss y s t e mm a k ef u l lu s e so ft h e s u p e r i o r i t yo ft h ec o m p u t e r ，h a sb a s e do nt h ed o m e s t i ca n df o r e i g nr e s e a r c hf o u n d a t i o n ，s t a r t s w i t ht h eb a s i ct h e o r yo fg e n e t i ca l g o r i t h m s d e s i g nac u r r i c u l u ma r r a n g e m e n ts y s t e mb a s e d o nc o m p o n e n tw i t hg a t h es y s t e ms t r u c t u r ei sb a s e do nc o m p o n e n t a n de a c hc o m p o n e n t a c h i e v e saf u n c t i o ni s o l a t e d t h i si sv e r yh e l p f u lt ot h ef l e x i b i l i t ya n dm a i n t e n a n c eo ft h e s y s t e m k e yw o r d s ：c u r r i c u l u ma r r a n g e m e n t ；e d u c a t i o n a la d m i n i s t r a t i o n ；g e n e t i ca l g o r i t h m s 第一章绪论 第一章绪论 1 1 引言 随着计算机技术的迅速发展，计算机在各项管理中的应用已经非常普及，利用计算 机进行教育教学管理势在必行。特别是对于规模较大的学校来说，排课问题在各高等院 校中越来越受到老师和同学的关注。能否排出质量好、效率高的课表，直接影响着学校 的教学质量以及教学资源的合理利用率。然而排课是教务管理工作中的一个难点，原因 在于排课需要考虑教师、教室、课程分布、时间分配、单双周要求等多方面约束，随着 大学规模的不断扩大，学生人数的不断增加，以及越来越多新专业的开设，使得高校排课 越来越困难。 课程表是学校开展教学活动的指令性文件。在传统方式下，课表编排主要是靠手工 完成的，排课人员需要花费大量的时间和精力，并且容易出错，同时手工操作也不能满 足资源需求的经常变化。利用计算机进行自动排课，可以提高教务管理工作的效率，改 善教学管理质量，合理、高效地利用有限的教学资源。由此出现了众多的计算机排课软 件。但综合分析当前的排课系统软件，大多采用传统方法进行程序设计，把程序作为系 统核心。系统中所使用的排课数据主要考虑了一般性排课原则，对于不同学校的特点考 虑不足，并且数据与程序结合过于紧密，程序的修改维护有很大难度，不便于系统扩充 和升级，因此限制了系统的通用性。对特殊情形只能依赖于人工调整，有很多学校先后 购买过多个排课软件，但都不能圆满地解决课表编排的问题，至今仍是手工排课，造成 了大量的浪费。课表编排问题涉及教师、教室、学生、课程及教学时间等多种因素的组 合规划，具有规模大、约束条件复杂以及不断变化等特点，是当今计算机科学研究的热 点问题之一。所以解决排课问题对于解决其他多约束、大规模的时间表问题也具有重要 的指导意义。 1 2 背景和意义 排课问题很早以前就成为众多科研人员和软件公司的研究课题，但是真正投入使用 的排课软件却很少。原因是多方面的，其中算法的选择是最关键的一个问题。s e v e n 等 人在1 9 7 5 年的研究中证明了排课问题是一个n p c o m p l e t e 问题1 2j ，即算法的计算时间 是呈指数增长的，这一论断确立了排课问题的理论深度。对于n p 完全问题目前在数学 上是没有一个通用的算法能够很好地解决。然而很多n p 完全问题却具有很重要的实际 意义，例如。大家熟悉的路由算法就是很典型的一个n p 完全问题，路由要从多个节点 人连交通人学+ i i 学硕f ：学侮论文 中找出最短路径完成信息的传递。既然都是n p 完全问题，那么很多路由算法就可以运 用到解决排课问题上，如d i j k s t r a 算法、节点子树剪枝构造网络最短路径法等等。 目前大家对n p 完全问题研究的主要思想是如何降低其计算复杂度。即利用一个近 似算法来代替，力争使得解决问题的时间从指数增长化简到多项式增长。结合到课表问 题就是建立一个合适的现实简约模型，利用该简约模型能够大大降低算法的复杂度，便 于程序实现，这是解决排课问题一个很重要的思路。 在高等院校中，培养学生的主要途径是教学。在教学活动中，有一系列管理工作， 其中，教学计划的实施是一个重要的教学环节。每学期管理人员都要整理教学计划，根 据教学计划下达教学任务书，然后根据教学任务书编排课程表。在这些教学调度工作中， 既有大量繁琐的数据整理工作，更有严谨思维的脑力劳动，还要填写大量的表格。因此 工作非常繁重。手工排课时，信息的上通下达是极其麻烦的，而采用计算机排课，教学 中的信息可以一目了然，对于优化学生的学习进程，评估每位教师对教学的贡献，领导 合理决策等都具有重要的意义，必将会大大推进教学的良性循环。 1 3 排课问题的现状1 1 , 2 】 几十年前国外就有人开始研究课表编排j u j 题。1 9 6 2 年，g o t l i e b 曾提出了一个课表 问题的数学模型，并利用匈牙利算法解决了三维线性运输问题1 3 1 。此后，人们对课表问 题的算法、存在性等问题做了很多深入探讨。但是大多数文献所用的数学模型都是 g o t li e b 的数学模型的简化或补充，而至今还没有一个可行的算法来解决课表问题。 近4 0 年来，人们对课表问题的计算机解法做了许多尝试。其中，课表编排的整数 规划模型将问题归结为求一组0 - 1 变量的解，但是其计算量非常大。解决0 - 1 线性优化 问题的分支技术却只适用于规模较小的课表编排，m i h o c 和b a l a s 将课表公式化为一个 优化问题，k r a w c z k 则提出一种线性编程的方法。j u n g i n g e r 将课表问题简化为三维运 输问题，而t r i p a t h y 则把课表问题视作整数线性编程问题并提出了大学课表的数学模 型。 在国内，对课表问题的研究开始于8 0 年代初期。具有代表性的有：南京工学院的 u t s s ( au n i v e r s it yt i m e t a b l es c h e d u li n gs y s t e m ) 系统，清华大学的t i s e r ( t i m e t a b l e s c h e d u l e r ) 系统，大连理工大学的智能教学组织管理与课程调度等，这些系统大多数 都是模拟手工排课过程，以“班”为单位，运用启发式函数来进行编排的。但是这些编 排系统往往比较依赖于各个学校的教学体制，不宜进行大量推广。 从实际使用的情况来看，国内外研制开发的这些软件系统在实用性上仍不尽如人 意。一方面原因是作为一个很复杂的系统，排课要想面面俱到足一件很困难的事；另一 2 第一章绪论 方面每个学校由于其各自的特殊性，自动排课软件很难普遍实用，特别是在调度的过程 中一个很小的变动，要引起全部课程的大调整，这意味着全校课程大变动，在实际的应 用中这是很难实现的事。 1 4 排课问题的发展趋势 计算机软件技术应用于学校的课程安排是发展的必然。充分发挥计算机的优势，将 大量复杂的判断与运算交给计算机来做，是真正意义上的人脑的“减负”。教师设置好 学校基本情况及排课要求，让计算机排出课程表，适度调课后的课表就能满意地应用于 新的学期。随着计算机软件技术的不断发展，排课效率高、出错概率低的排课算法也必 将会逐渐趋向成熟，功能更加完善的排课系统也将应运而生。 1 5 本文研究内容 本系统主要以大连交通大学软件学院教务管理系统为背景，并且融合了多所大学教 务管理及教务改革的经验，数据统一管理，改变了以往教务模块分散，不全面的弊端。 教务数据集中管理，最大程度地实现了数据的共享，从而避免管理漏洞的产生，同时为 学校管理层的决策支持提供详尽的数据。 本章小结 介绍了国内外有关排课的背景、现状、意义和发展趋势，简要说明了本排课系统研 究的内容。 人连交通人学l ：学硕十学何论文 第二章开发环境与理论基础 2 1 系统开发环境介绍 结合所要开发系统的特点，本系统将使用v i s u a lb a s i c6 0 中文版作为开发工具， 后台数据库则采用a c c e s s2 0 0 0 。根据“排课管理系统”的需求说明和模块设计，本系 统将会着意于如何实现各个模块的基本功能，在具体应用中，还需要针对各个学校的具 体情况对系统进行进一步修正。采用a d o 和d a t ac o n t r o l 控件作为排课系统与后台数据 库的接口。排课系统开发平台是w i n d o w sx p 。 2 2 开发语言v is u aib a sic6 0 基本概述和特点 v is u a lb a s i c6 0 是m i c r o s o f t 公司推出的基于w in d o w s 环境的计算机程序设计语 言，它继承了b a s i c 语言简单易学的优点，同时增加了许多新的功能。目前v i s u a lb a s i c 发展至今已至6 0 版，并在全球使用中文的地区推出v i s u a lb a s i c6 o 中文版。v i s u a l 的中文意思足可视的，它是指开发图形用户界血的方法，其方法就是在建立输入输出界 面时，不必撰写程序来描述界面控件的外观和配置，只要使用工具箱的工具，在程序设 计阶段便可达成。v i s u a lb a s i c 就是以b a s i c 语言为基础，再加入许多和w i n d o w sg u i 有关的功能。v i s u a lb a s i c 除了具有传统的b a s i c 的优点外，还具有下列功能【4 l ： ( 1 ) 基于控件的程序设计 v i s u a b a s i c 执行的过程是以控件为主，当使用鼠标或键盘触动那个控件就执行该 控件所设定的动作。 ( 2 ) 输出输入界面设计简单 应用v i s u a lb a s i c 所提供的工具，只要设定该工具的属性，不用写程序便能做到实 用的输出输入界面。 ( 3 ) 用来制作多媒体软件 由于v i s u a lb a s i c 是在w i n d o w s 环境下执行，多媒体界面要求统一，因此编写程序 时不必考虑兼容性问题。 ( 4 ) 多任务处理 在w i n d o w s 环境，v i s u a b a s i c 拥有多任务处理的功能，因此v i s u a lb a s i c 能同时 打开多个窗口执行不同的工作。 ( 5 ) 数据可以互通 v i s u a b a s i c , - i 以直接调用w i n d o w sa p i 函数和应用“动态数据交换”可与w i n d o w s 其他应用程序交换数据。 4 第二章开发环境与理论荩础 ( 6 ) 提供友好的人机界面 v is u a lb a s i c 提供鼠标操作及键盘处理环境。 ( 7 ) 与数据库连结 v i s u a lb a s i c 支持各类数据库，包含a c c e s s ，d b a s e ，s q l 等等，并提供方便的数 据库与控件的数据栏位连结功能，用户只要简单的设定控件与数据库的数据连结，就可 以做出功能强大的数据库管理系统。 由于v i s u a lb a s i c 具有上述的功能和特点，采用面向对象的程序设计技术，摆脱了 面向过程语言的许多细节而将主要精力集中在解决实际问题和设计友好界面上，使开发 w i n d o w s 应用程序更迅速、更简捷。因此，本系统采用v b 作为开发工具，以期有效地提 高应用程序开发与运行效率和可靠性。 2 3 数据库 2 3 1 数据库概念 数据库是依照某种数据模型组织起来并存放二级存储器中的数据集合。这种数据集 合具有如下特点：尽可能不重复，以最优方式为某个特定组织的多种应用服务，其数据 结构独立于使用它的应用程序，对数据的增、删、改和检索由统一软件进行管理和控制。 从发展的历史看，数据库是数据管理的高级阶段，它是由文件管理系统发展起来的。 2 3 2 数据库主要特点1 5 j ( 1 ) 实现数据共享 数据共享包含所有用户可同时存取数据库中的数据，也包括用户可以用各种方式通 过接口使用数据库，并提供数据共享。 ( 2 ) 减少数据的冗余度 同文件系统相比，由于数据库实现了数据共享，从而避免了用户各自建立应用文件。 减少了大鼍重复数据，减少了数据冗余，维护了数据的一致性。 ( 3 ) 数据的独+ 覆性 数据的独立性包括数据库中数据的逻辑结构和应用程序相互独立，也包括数据物理 结构的变化，不影响数据的逻辑结构。 ( 4 ) 数据实现集中控制 文件管理方式中，数据处于一种分散的状态，不同的用户或同一用户在不同处理中 其文件之问毫无关系。利用数据库可对数据进行集中控制和管理，并通过数据模型表示 各种数据的组织以及数据问的联系。 人连交通人学l ：学硕 j 学位论文 ( 5 ) 数据一致性和可维护性，以确保数据的安全性和可靠性 主要包括： 安全性控制：以防止数据丢失、错误更新和越权使用。 完整性控制：保证数据的正确性、有效性和相容性。 并发控制：使在同一时间周期内，允许对数据实现多路存取，又能防止用户之 间的不正常交互作用。 故障的发现和恢复：由数据库管理系统提供一套方法，可及时发现故障和修复 故障，从而防止数据被破坏。 2 3 3a c c e s s 数据库介绍i 6 】 常见的数据库有s y b a s e 数据库、o r a c l e 数据库、d b 2 数据库、s q l 数据库、m y s q l 数 据库及a c c e s s 数据库。a c c e s s 是发开单机小型数据库应用系统的理想工具，可以独立开 发数据库应用系统，也可以作为后台数据库与v i s u a b a s i c 的结合，因此本系统采用了 a c c e s s 数据库。 a c c e s s 是美国m i c r o s o f t 公司推出的关系型数据库管理系统，它作为o f f i c e 的一部 分，具有简洁的操作界面和使用环境，深受广大用户的喜爱。a c c e s s 是一个基于关系型 数据模型的数据库管理系统，它提供了强大的数据处理能力，可以帮助用户组织和共享 数据库信息，以便根据数据库信息做出有效的决策。a c c e s s 的优点在于它比较适合建 立较小型应用软件系统的后台数据库。简单地说它就是一些关于某个特定主题或目的的 信息集合。使用m i c r o s o f ta c c e s s ，可以在单一的数据库文件中管理所有的信息。 a c c e s s 所提供的各类对象都存放在同一个数据库文件( 扩展名为m d b ) 中，而不 是像其他数据库系统那样，分别存放在不同的文件中。这样就方便了数据库对象的管理。 数据库对象是a c c e s s 最基本的容器对象，它是一些关于某个特定主题或目的的信息集 合，具有管理本数据库中所有信息的功能。在数据库对象中，用户可以将自己的数据分 别保存在各自独立的存储窄问中，这些空问称为数据表；可以使用联机窗体来查看、添 加、和更新数据表中的数据；使用查看来查找并检索所需的数据；也可以使用报表以特 定的版面布局来分析及打印数据。归纳起来，a c c e s s 数据库对象中有7 种不同类别的子 对象，即表、查询、窗体、报表、数据访问页、宏和模块。不同的对象在数据库中有着 不同的作用：表是数据库的核心与基础，存放着数据库中的全部数据；报表、查询和窗 体都是从数据库中获得数据信息，以实现用户的某一个特定需求。 2 3 4 数据表 6 筇二章开发环境与理论基础 表表示数据库中最常用的数据存储单元，它包括所有用户可以访问的数据。a c c e s s 的表是二维结构的，由行和列两部分组成。 列也叫字段，它可以定义表的结构。行也叫做记录，保存表中的一条数据。在设计 表结构时，需要定义表中的字段名和数据类型，表生成后可以添加、修改、删除数据。 2 3 5 数据库接口的实现 在v i s u a lb a s i c 中，提供了多种数据库访问技术d a t ac o n t r o l 、o d b c 、d a o 、 o l ed b 、a d o 等，这些技术各有自己的特剧6 。 d a t ac o n t r o l ：d a t a 控件提供了一种方便地访问数据库中数据的方法，使用数据控 件不需要编写代码就可以对v i s u a lb a s i c 所支持的各种类型的数据库执行大部分数据访 问操作。d a t a 控件本身不能显示和直接修改记录，只能与数据控件相关联的数据约束控 件中显示各个记录。d a t a 控件只相当于一个记录指针，可以通过单击其左右两边的箭头 按钮移动这个指针来选择当前记录。如果修改了被绑定的控件中的数据，只要移动记录 指针，就会将修改后的数据自动写入数据库。 o d b c ( o p e nd a t a b a s ec o n n e c t i v i t y ) ：开放式的数据库连接技术。为异种数据库 的访问提供了统一的接口。o d b c 基于s o l ( s t r u c t u r e do u e r yl a n g u a g e ) ，并把它作为访 问数据库的标准。这个接口提供了最大限度的相互可操作性：一个应用程序可以通过一 组通用的代码访问不同的数据库管理系统。一个软件开发者开发的客户服务器应用程 序不会被束定于某个特定的数据库之上。o d b c 可以为不同的数据库提供相应的驱动程 序，是一种公认的关系数据源的接口界面。它快而轻并且提供统一接口的界面，o d b c 对 任何数据源都未作优化。 d a o ( d a t aa c c e s so b j e c t s ) ：数据访问对象。是一种面向对象的界面接口。通过 d a o j e t 功能呵以访问i s a m 数据库，使用d a o o d b cd i r e c t 功能可以实现远程r d 0 功能。 使用d a o 的程序编码非常简单，d a o 提供丰富的游标( c u r s o r ) 类型的结果集和非游标 ( c u r s o r l e s s ) 类型的结果集，同d d i ( 数据描述语言) 的功能很类似。d a o 町通过o d b c 像直接连接到其它数据库一样，直接连接到a c c e s s 数据库。d a o 最适用于单系统应用程 序或小范围本地分布使用。d a o 模型是设计关系数据库系统结构的对象类的集合。它们 提供了完成管理这样一个系统所需的全部操作的属性和方法，包括创建数据库，定义表、 字段和索引，建立表间的关系，定位和查询数据库等工具。 o l ed b ：是一组“组件对象模型”( c o m ) 接口，是新的数据库低层接口，它封装了 o d b c 的功能，并以统一的方式访问存储在不同信息源中的数据。o l ed b 足m i c r o s o f t u d a ( u n i v e r s a ld a t aa c c e s s ) 策略的技术基础。o l ed b 为任何数据源提供了高性能的 7 人连交通人学i ：学硕十学位论文 访问，这些数据源包括关系和非关系数据库、电子邮件和文件系统、文本和图形、自定 义业务对象等等。也就是说，o l ed b 并不局限于i s a m 、j e t 甚至关系数据源，它能够 处理任何类型的数据，而不考虑它们的格式和存储方法。在实际应用中，这种多样性意 味着可以访问驻留在e x c e l 电子数据表、文本文件、电子邮件目录服务甚至邮件服务 器，诸如m i c r o s o f te x c h a n g e 中的数据。但是，o l ed b 应用程序编程接口的目的是 为各种应用程序提供最佳的功能，它并不符合简单化的要求。需要的接口对象法( a p i ) 应该是一座连接应用程序和o l ed b 的桥梁，这就是a c tiv e xd a t ao b j e c t s ( a d o ) 。 a d o ：a d o 即a c t i v e x 数据对象( a c t i v ed a t ao b j e c t s ) ，实际是一种提供访问各种 数据类型的连接机制。是m i c r o s o f t 最新和最强大的数据访问范例o l ed b 而设计的， 是一个便于使用的应用程序层接口。a d o 控件和d a t a 控件的用法相似，同样需要经过 连接数据库和“绑定”两步操作。a d o n 。v 够编写应用程序以通过o l ed b 提供者访问和 操作数据库服务器中的数据。a d o 最主要的优点是易于使用、速度快、内存支出少和磁 盘遗迹小。a d o 在关键的应用方案中使用最少的网络流量，并且在前端和数据源之间使 用最少的层数，所有这些都是为了提供轻量、高性能的接口。之所以称为a d o ，是用了 一个比较熟悉的暗喻，o l e 自动化接口。a d o 设计为一种及简单的格式，通过o d b c 的方 法和数据库接口，可以使用任何一种o d b c 数据源，即不止适合于s q ls e v e r 、o r a c l e 、 a c c e s s 等数据库应用程序，也适合于e x c e l 表格、文本文件、图形文件和无格式的数据 文件。 本章小结 本章主要介绍了系统的丌发工具为v i s u a lb a s i c6 0 中文版，后台数据库为a c c e s s 2 0 0 0 ，系统开发平台是w i n d o w sx p 。并介绍了数据库的相关知识。 8 第章排课 d 题分析及算法 第三章排课问题分析及算法 3 1 排课问题概述 排课是一个多因素的优化决策问题，是组合规划中的典型的n p 完全类问题，由于 涉及信息较多且求解复杂性大使课表规模成指数级增长。考虑排课的复杂性，本系统研 究了一种自动排课和手工排课相结合的算法。 课表是课号、课名、教室、学时、教师以及上课学生等信息的集合。课表的编排就 是为课程分配时间和教室。在排课过程中必须严格遵守以下基本原则【7 j ： ( 1 ) 每位教师在同一时间段内只能安排一门课程。 ( 2 ) 每个学生在一个时间段内只能安排一门课程。 ( 3 ) 分配的教室可容纳人数应该大于学生数。 ( 4 ) 每个学生的每门课程只能安排一次，不能被重复安排。 ( 5 ) 尽量在早上安排必修课，而下午安排选修课，晚上尽量不排课。 ( 6 ) 尽可能满足个别教师的特殊上课时间要求。 ( 7 ) 尽可能满足每个课程教学的客观要求( 比如多媒体教学) 。 ( 8 ) 一门课尽量分散在一个星期中，即某天上完某一门课后，要隔一天以上再上这 门课，以使教师有充足的时间备课和批改作业，而学生也有足够的时间复习消化。 ( 9 ) 一个教师的课不能排满一整天。 ( 1 0 ) 学生课表中的上课时间不能过分集中，应避免一天课程很满而另一天却一整天 没课的情况。 - - f 。j 课程的一次教学工作称为一项教学任务。所有教学任务得以顺利进行所必需的 教窀、学生、教师以及教学时间等称为教学资源。任何违反以上几条基本原则的排课都 会导致两项( 或以上) 教学任务争夺某一教学资源，使教学工作不能正常进行，这一现 象称为冲突。两门( 或以上) 课程若关联着相同的教师或上课学生，称为冲突课程瞵i 。 3 2 排课问题的数学描述 从手工排课的过程可以看出，排课问题需要考虑的因素，几乎是全校性的。像能够 单独完成某种任务的机器一样，学校是一个有机组合而成的整体，其内在各组成部分既 各司其职，又密切协调合作，以保证日常正常教务工作的运转和教学任务的完成。在排 课问题中，我们的主要任务是将班级、教室、课程、教师安排在一周内且不发生时间冲 突。掘此，可以将排课问题涉及因素逐项考虑如下1 9 j ： 学校有r 间教室，c 个班，s 门课程，t 位教师，p 个时间段。 9 人连交通人学t 学硕f ：学化论文 ( 1 ) 教室集合r ( r l ，r 2 ，r n ) ，每间教室分别可容纳( x l ，x 2 x r ) 人； ( 2 ) 班级集合c ( c 1 ，c 2 ，c n ) ，每个班级分别有( k 1 ，k 2 ，k c ) 人，其中有x 个 班级上合班课； ( 3 ) 课程集合s ( s l ，s 2 ，s n ) ，每门课对应c i 个班，1 位教师，( 1 c i c n ) ； ( 4 ) 教师集合t ( t 1 ，t 2 ，t n ) ，每位教师对应s i 门课，c i 个班，( 1 s i s n ，1 c i c n ) ，在初始设置时设定教师的排课要求； ( 5 ) 时问集合p ( p 1 ，p 2 ，p n ) ，假设一周上五天课，每天分为五个教学单元， 每个单元为2 个课时，即上午2 个，下午2 个，晚上1 个，则时问集合包含2 5 个 时间段。如1 1 代表周一第一个教学单元，即周一l 、2 节，1 2 代表周一第二个教学 单元，即周一3 、4 节，以此类推，这些时间段构成一个时问集合p ( 1 1 ，1 2 ，1 3 ，5 5 ) 。 3 3 排课的约束条件 排课是将教师与学生在时间和空间上根据不同的约束条件进行排列组合，以使教学 正常。约束条件主要为避免冲突，避免冲突是排课问题中要解决的核心问题。只有在满 足全部约束条件和避免所有冲突的基础上，才能保证整个教学计划合理正常进行。而对 教师、教室、学生及时问等几部分资源进行最优化组合配置，才能保证充分发挥各资源 的优势和提高教学质量。把排课过程中的约束条件【lo 】分为两类：硬约束条件和软约束条 件。 3 3 1 硬约束条件 如果说一张课表是有效的，则它至少应该满足以下硬约束条件： ( 1 ) 教师不能冲突，同一教师在同一时间不能教授两门课程。 ( 2 ) 教室不能冲突，同一教室存同一时间不能安排两门课程。 ( 3 ) 班级不能冲突，同一班级在同一时问不能安排两门课程。 3 3 2 软约束条件 高质量的课表，除了应该满足上述硬约束条件外，还应该考虑一些软约束条件。硬约 束条件是衡量排课方案是否可行的标准，软约束条件则足衡量排课方案优劣的标准。可 以根据学校的实际情况定义软约束条件，一般的软约束条件为： ( 1 ) 班级课表在星期上分布尽量均匀。 ( 2 ) 教师对上课时问存在一定的喜好。 ( 3 ) 不推荐教师连续上课。 ( 4 ) 班级课程相邻的上课地点距离尽可能近。 l o 菊章排课问题分析及算法 ( 5 ) 同一课程的多个课时段要保持一定的时间间隔。 ( 6 ) 充分利用教室资源，上课学生数和教室容量相匹配。 3 4 排课的求解目标 我们已经知道，排课问题实质上是一个多目标的组合规划问题，对组合规划问题如 果想找到最优解，必须有足够的约束条件来实现。可是，对于部分属于人文范畴的排课 问题，不可能找到充足的约束条件。而且按照多目标优化理论的近似最优概念，能够在 可行解域中找到的解不可避免地是一个解集合。 课表能够满足人工排课中的“合理、实用、有特色 的要求。就认为被安排的课表 是可行的并且相对最优的。在问题求解空间中，求解一套完整的包含所有教室、教师、 课程、学生的信息组合、无任何硬性冲突的课表，是我们进行排课的基本要求，也是课 表满意度衡量的最低限度。而一套可行课表在整体上表现出的某些指标，是我们衡量课 表优劣判断的依据，尽管这些指标在现实中给人总以一种模糊的概念。 根据以上的分析，我们可以确定用计算机排课的二个目标如下j ： ( 1 ) 课表中没有任何硬性冲突。它表示课表必须符合基本硬约束条件，没有无法执 行的冲突，例如，一个教室不能在同一个时间安排两门不同的课程，或者同一名教师在 同一时间不能上两门不同的课程等。它也表示课表还遵守硬约束条件，这些约束条件的 违反会导致冲突，也是现实中衡量课表是否切实可行的标准之一。 ( 2 ) 课表具有较高的质量。一套高质量的课表，在时间、教室资源、课程安排等很 多方面都应该做到安排合理，并且具有人性化考虑。课表随机安排过程中不应该出现太 多未被安排的课程。虽然末被安排课程的出现，可能是与之相关要素的课时分布状况， 或者安排中没有充分考虑后续课程的要求而导致发生的。但是因为在一套完整的课表 中，调整某门课程的安排，往往会牵扯到更多的课程安排，甚至改变了大部分己排好的 课程。因此，如何在局部范 目内对已经安排课程做出相应调整，将未被安排课程减少到 最低限度，成为在随机方案生成过程中考虑的一个重点。通过以上排课目标的分析，可 知课表问题的难点在于：保证课表在时间的分配上符合一切共性和个性要求，质量过关， 没有违反规则之处；在此基础上，对所有的课程都能安排合适的时间和教室；使安排方 案在各个目标上尽量达到全局最优。 3 5 解决n p 问题的几种算法及其比较 排课问题是一个n p - c o m p l e t e 问题，即算法的计算时间是呈指数增长的，这一论 断确立了排课问题的理论深度。对于n p 完全问题目前在数学上是没有一个通用的算法能 火连交通人学i ：学硕1 ：学位沦文 够很好地解决。解决n p 完全问题只能依靠近似算法，所以下面介绍几种常用算法的设计 思想，包括模拟退火算法、贪婪算法、回溯法、遗传算法等。 3 5 1 模拟退火算法 模拟退火算法是一种能应用到求最小值问题或基本先前的更新的学习过程( 随机或 决定性的) 。在此过程中，每一步更新过程的长度都与相应的参数成正比，这些参数扮 演着温度的角色。然后，与金属退火原理相类似，在开始阶段为了更快地最小化或学习， 温度被升得很高，然后才( 慢慢) 降温以求稳定。 模拟退火算法是一种用于求解大规模优化问题的随机搜索算法，它以优化问题求解 过程与物理系统退火过程之间的相似性为基础；优化的目标函数相当于金属的内能；优 化问题的自变量组合状态空间相当于金属的内能状态空间；问题的求解过程就是找一个 组合状态，使目标函数值最小。利用m e t r o p o l i s 准则并适当地控制温度的下降过程实现 模拟退火，从而达到在多项式时间内求解全局优化问题的目标。用模拟退火算法困难之 处在于控制参数的选择，选择不恰当的参数可能使迭代不收敛或运行时间很长。事实证 明，速度和效果很难两全。 3 5 2 贪婪算法 顾名思义，贪婪算法总是做出在当前看来最好的选择。也就是说贪婪算法并不是整 体最优上加以考虑，它所作出的选择只是在某种意义上的局部最优的选择。虽然贪婪算 法不是对所有问题都能得到整体最优解，但对范闱相当广的许多问题它能产生整体最优 解。 在贪婪算法r f l 采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的 决策。决策一旦作出，就不可再更改。作出贪婪决策的依据称为贪婪准则。在有些应用 中，贪婪算法所产生的结果总足最优的解决方案。但对其他一些应用，生成的算法只是 一种启发式方法，可能是也可能不是近似算法。 3 5 3 回溯算法 回溯是一种优先搜索法。它按优先条件向前搜索，以达到目标，但当搜索到某一步 时，发现原先的选择并不优或达不到目标，就退【四一步重新选择。这种走不通就退 u l 的 技术为回溯法，而满足回溯条件的某个状态点称之为i u l 溯点。具体剑计算机智能排谋系 统中，选优条件即为排课数学模型中的约束条件群( 需求集中的元素特征与资源集中的 元素特征相互作用形成的数学关系) 。换言之，若不满足约束条件群，该选择即为不优 1 2 第章排课问题分析及算法 或达不到目标。当遍历该步骤的所有可能仍未满足约束条件群，则该状态满足了回溯条 件，该状态点即为回溯点。 3 5 4 遗传算法 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 是近几年发展起来的一种崭新的全局优化算法， 它借用了生物遗传学的观点，通过自然选择、遗传、变异等作用机制，实现各个个体的 适应性的提高。这一点体现了自然界中”物竞天择、适者生存”进化过程。1 9 6 2 年h o l