（物理电子学专业论文）基于概率动态分布选课算法的研究与应用.pdf

摘要 随着i n t e r n e t 的飞速发展和普及，在我国高校学分制的实行以 来，越来越广泛的要求学生进行自主选课，学生选课系统也从原始的 手工填表过渡到网络选课。本文在综合考虑以往的选课系统中主要应 用的算法的基础上，提出了一种对于选课学生来说相对公开、公平、 公正合理的选课算法基于概率动态分布选课算法。 该算法主要是以学生选课的相对公平性为出发点，所要解决的问 题就是要使得在整个选课过程中，绝大多数学生都能够在选课时间内 尽可能的拥有均等的概率选中某个课堂，同时尽可能的使参加选课的 学生在第一时间( 即实时性) 里得知是否选中。本文首先对已有的选 课算法进行了比较研究，随后对选课人数随时间的分布进行了分析， 并进行相关算法研究，按照选课样本的大小提出了相应的算法；最后 综合上述算法，提出了一种改进的基于概率动态分布的选课算法思 想，使得整个选课过程中，实时性与概率动态分布有了很好的结合与 体现，既实现了实时选课( 即时间效益得到保证) ，又能后使得参选 人尽可能的拥有相等的机会( 即实现选课过程中的相对公平合理性) 选中某个课堂。 关键字：选课算法选课系统概率动态分布 a b s t r a c t w i t ht h ed e v e l o p m e n ta n dg e n e r a l l yu s i n go ft h ei n t e r n e t ，t h e s t u d e n t sa r ed e m a n d e dt os e l e c tt h ec o u r s ei n d e p e n d e n t l ya f t e rt h e c r e d i t s y s t o m i s p u t i n p r a c t i c e i nt h e c o l l e g e s i nc h i n a t h e c o u r s e s e l e c t i o ns y s t e mi st r a n s f e r r e df o r mm a n n e df i l l i n gt a b l et o s e l e c t i n gt h ec o u r s e si nt h ew e b b a s e do nt h em e t h o d su s e di no t h e r c o u r s e s e l e c t i o ns y s t e m s ，o n ek i n do fc o u r s e s e l e c t i o na l g o r i t h mo nt h e b a s eo fd y n a m i cp r o b a b i l i t yd i s t r i b u t i o n ，w h i c hc a nb em o r eo p e n ，m o r e e q u i t a b l e m o r er a t i o n a lf o rm o s to f t h es t u d e n t s ，i sp r o p o s e d t h i sa l g o r i t h ms t a r t sf r o mt h ee q u i t yf o rt h es t u d e n t st os e l e c tt h e c o u r s e s i tc a nm a k em o s to ft h es t u d e n t sc a nc h o o s es o m ec o u r s e sw i t h a l m o s tt h es a m ep r o b a b i l i t y ，a n dc a nm a k ea l lt h es t u d e n t sc a nk n o wi f t h e yp i t c h e do nt h ec o u r s e i nt h et i m ea ss h o r ta s p o s s i b l e t h e a l g o r i t h m sp r o p o s e db y0 t h e r sa r ec o m p a r e da n ds t u d i e d 。t h e l lt h e d i s t r i b u t i o no ft h es t u d e n t sd u r i n gt h ep e r i o di sa n a l y z e da n dt h e a l g o r i t h mi sp r o p o s e da c c o r d i n gt ot h es i z eo ft h et o t a ls t u d e n t ss a m p l e f i n a l l yb a s e do nt h er e s e a r c ha b o v e ，am o d i f i e dd y n a m i cp r o b a b i l i t y d i s t r i b u t i o na l g o r i t h mi sp r o p o s e dt om e e tt h et h er e a l t i m ea n de q u i t y d e m a n do ft h ec o u r s e s e l e c t i o ns y s t e m c o m p a r e dw i t ht h ek n o w n a l g o r i t h m s ，t h i sa l g o r i t h mc a np u ti np r a c t i c er e a l t i m ec o u r s e s e l e c t i o n a tt h es a m et i m et h ea n t i c i p a t o rc a ns e l e c tt h ec o u r s ew i t ht h es a m e p r o b a b i l i t y k e yw o r d s ：c o u r s e - s e l e c t i o na l g o r i t h m c o u r s e - s e l e c t i o ns y s t e m d y n a m i cp r o b a b i l i t yd i s t r i b u t i o n 长春理工大学硕士学位论文原创性声明 本人郑重声明：所呈交的硕士学位论文，基于概率动态分布选课 算法的研究与应用是本人在指导教师的指导下，独立进行研究工作所 取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个 人或集体己经发表或撰写过的作品成果。对本文的研究做出重要贡献的 个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法 律结果由本人承担 作者签名：整l 蓥 年一月一日 长春理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“长春理工大学硕士、博士学 位论文版权使用规定”，同意长春理工大学保留并向国家有关部门或机 构送交学位论文的复印件和电子版，允许论文被查阅和借阅。本人授权 长春理工大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论文。 作者签名：弗，圣 指导导师签名 年月日 年一月一日 第一章绪论 1 1 引言 本课题主要来源于长春理工大学计算机学院开发的高校教务教学 管理平台项目。该项目推出的是一整套能够适应新的教学体制、能够最 大程度满足高校现代管理要求的教务管理系统。在学生选谋模块中需要 一个有效算法，在开发和实际应用中能够实现选课过程中的相对公平合 理，通过该教务管理系统的不断完善，使之能够服务于更多的高校。 选课系统是学分制教学改革的一个重要措施，它允许学生给自己安 排课程、时间以及任课教师，充分发挥学生的主观能动性，调动学生的 学习积极性，拓宽知识面，同时也在教师队伍中引进竞争机制，有利于 促进教学质量的提高。但是，在选课过程中，一方面出于师资、时间、 教室有限，而学生的选课往往又有很大的倾向性；另一方面学生对于选 课结果能否在最短时侧内得到答案，这种需求也是不断在增加。 在以往的选课系统中，主要应用以下几种算法来实现：先来先服务 ( f c f s f i r s tc o m ef i r s ts e r v i c e ) 的算法、抽签算法和分志愿筛选 算法。但是这几种算法都存在很多不足之处：在先来先服务算法中，对 于参选数量较小的选修课来说这种算法的弊端还不是很明显，但随着学 校招生规模的扩大，参加选课人数的增加，使得排在后面的学生几乎没 有机会选到自己满意的课程，经常会给教务管理工作带来许多不必要的 麻烦，相对公平合理的进行选课这一原则得不到体现；而抽签算法的弊 端在于需要对整个学生选课操作结束后才进行后台处理，虽然有一定的 公平性，但是时间效益得不到保证；分志愿筛选算法是采用实时选课处 理和后台批处理相结合的方法来实现的，由于该算法是在所有学生选课 结束后，才进行后台处理的，这样虽然避免了先来先服务的不足，但当 后台处理完之后，仍有可能会有少量的学生3 个志愿都未选中，需要作 一些人工干预等处理，最终产生学生课程表，这种算法虽然一定程度上 达到了公平选课的要求，并且运行处理速度较快，但是，由于该算法仍 需要后台处理才能产生最终的学生课程表，并没有实现学生选课的实时 处理，以人为本的理念也没有得到完全体现。 总的来说，以往采用的选课机制对学生的选课要求不可能全部满 足，以人为本的理念根本得不到体现。鉴于这个原因，对学生选课是否 能够作到进行公开、相对公平、相对公正合理以及是否能够在最短时间 内得到是否选中某门课的问题都己经成为判定选课系统性能是否具有 优越性的个重要指标。 在选课过程中我们采用的是基于概率动态分布的选课算法，可以根 掘概率值和平均分布概率算法产生随机数的方法使在选课时间内所有 想选某个课堂的学生尽可能的拥有均等的概率选中该课堂，从而打破了 以前的那种先来先选中的不公平合理的选课机制。同时，根据随机数来 判断是否选中某个课堂并给出相应信息，可以使参选的学生尽可能早的 在第一时间里知道是否选中，也就是我们所说的算法即时性。当然，在 整个选课结束后仍有可能存在少数学生选不上课的现象，需要做一些人 工干预等处理，产生最终的总课表。 总之，能够作到进行公开、相对公平、公正合理以及能够在最短时 间内得到是否选中某门课这些问题的解决便都能成为优化整个选课系 统的重要因素。 1 2 国内外研究现状 在我国高校学分制的实行以来，越来越广泛的要求学生自主选课， 学生可以根据自己的实际情况，通过选课来自由的安排自己的学习计 划，随着i n t e r n e t 的飞速发展和普及，学生选课系统也从原始的手工 填表过度到网络选课，从最开始的雏形不断的走向成熟。目前各大高校 也普遍开发了适应于自己学校实际情况选课系统。 就目前国内高校的选课系统发展状况来讲，普遍采用以下几种算 法：先来先服务( f c f s ) 的算法、抽签算法和分志愿筛选算法。在先来 先服务算法中，对于参选数量较小的选修课来说这种算法的弊端还不是 很明显，但随着学校招生规模的扩大，参加选课人数的增加，使得排在 后面的学生几乎没有机会选到自己满意的课程，经常会给教务管理工作 带来许多不必要的麻烦。现在，许多高校逐步意识到了这个问题，也采 取了相应的措施抽签算法，即在所有学生选课结束后，对于选课人 数超过限定人数的课堂来说，采用抽签的形式裁决选中与否，虽然某种 程度上具有一定的公平性，但是这种算法的弊端在于需要对整个学生选 课操作结束后才进行后台处理，时间效益得不到保证。目前，又出现一 种采用实时选课处理和后台批处理相结合的分志愿筛选算法，该算法是 在所有学生选课结束后，才进行后台处理的，就避免了先来先服务的不 足，也在一定程度上达到了公平选课的要求，并且运行处理速度较快。 但是，由于该算法仍需要后台处理才能产生最终的学生课程表，并没有 实现学生选课的实时处理，以人为本的理念也没有得到完全体现。 总之，不管哪一种措施都将问题的某一方面作为侧重点来加以考虑 的。从大量的文献中，在不同选课系统中会应用有很多不同的选课算法， 例如：暨南大学，南京河海大学都采用类似填写高考志愿的方法使得选 课系统更加公平合理；桂林电子工业学院则采用马尔可夫过程、烟台师 2 范学院则采用矩阵模型来确定选课人数。但是我们发现不管选课算法的 名称是多么的不同，其主要得选课思想不外乎以下几种算法的体现：先 来先服务( f c f s ) 的算法、抽签算法和分志愿筛选算法。现将其选课思 想分别总结如下： 先来先服务( f c f s ) 的算法：它的实现思想就是“排队买票”的办 法，是最简单的一种调度算法，这个算法也是在选课系统中最早应用得 一个很普遍得算法。现以3 0 0 学生选容纳2 0 0 人的某一课堂为例，在 3 0 0 学生中前2 0 0 人进行选课几乎都可以被选中，而后1 0 0 个想选这个 课堂的学生就不能选中。这个算法虽然在时间上可以有一定的时间效益 保证，但是严重的违背了高校中学生自主选课的原则，并不能够做到公 平合理的安排选课。 抽签算法：它的实现思想就是在整个选课过程中，学生先进行选课， 在整个选课结束后进行后台处理来判断选中是否。当某个课堂的选课的 人数超过容纳人数时，就要对所有参加该课堂选课的学生进行抽签的方 式来决定最终的选课结果。这个算法虽然在原则上具有公平合理性，但 是在时间上却得不到保障，因为最终结果是在对整个学生选课操作结束 后才进行后台处理的。 分志愿筛选算法：在具体实现上，采取类似于高考录取的方法，由 学生在选课时确定3 个志愿，分级处理第1 志愿的优先级最高，最有可 能被选中如果课程第1 志愿已选人数大于限选人数，则不再处理第2 志愿，并将从第1 志愿中按照选课的优先权或通过抽签筛选出多余人员。 对于未选满的课程，进行第2 志愿的处理。处理完毕后，还有课程未满 且有落选人员，再进行第3 志愿处理。这样一来，落选机会少，分布均 匀，基本上做到了公平公正。但是，由于该算法仍需要后台处理才能产 生最终的学生课程表，并没有实现学生选课的实时处理，以人为本的理 念也没有得到完全体现。 总而言之，不管是采用哪种思想的选课算法都不能将问题的全方面 来加以考虑的，对学生的选课要求都不可能全部满足，以人为本的理念 根本得不到体现。我们需要的是一种公开、相对公平、相对公正合理的 选课算法。 1 3 本课题的研究内容 在长春理工大学计算机学院研究开发的高校教务教学管理平台这 个项目中，我们把选课模块里应用到的主要算法作为本论文的主要研究 内容： 1 、理论上，进入选课页面后进行选课操作，系统会及时反映是否 选中并给出提示信息。对于可能存在一个课堂选择的人比较多的情况来 说，并不是每个人都能选中。此时系统会根据选择情况动态的更改当前 课堂的选择概率，用系统( 平均分布概率算法) 来确定随机数的产生； 运用概率动态分布方法与随机数相结合，判定课程选中与否并给予提 示，因此，并不是每次的选课都能选中。最后，系统通过“选修审核” 来判断选课是否通过，最终产生已选课程列表。 2 、实践上，我们主要选用完全面向对象的可视编程语言c # 作为开 发语言，采用的数据库是易于安装、使用和管理的m i c r o s o f ts q l s e v e r 2 0 0 0 数据库，我们同时还运用在断开连接的世界里可以进行操作 的a d o n e t 技术作为数据访问的方法来实现与m i c r o s o f ts q ls e v e r 2 0 0 0 数据库之间的数据访问，使整个选课系统更加利于开发设计与实现。通 过研究和总结，我们将上述的以数学中概率理论为基础的选课算法应用 于实践中，并对这种选课算法与其他的算法进行比较、归纳和总结。 总而言之，在整个选课过程中，我们所要做的就是使得每个学生都 能够在选课时间内尽可能的拥有均等的概率选中该课程，同时能够使参 加选课的学生尽可能的在第一时间里得知是否选中，使整个选课过程， 真正做到以人为本的理念，在时间效益得到保证的同时，相对公平合理 的选课原则得以体现。在以后的研究中我们将搜寻一种数学理论作为奠 基，以此来进一步优化选课算法，使算法更加公平合理。 4 第二章现有选课算法分析 2 1 选课系统分析 2 1 1 选课系统“1 概述 随着计算机技术和网络技术的发展，各高校相继建成了自己的校园 网，并充分利用校园网提供的新环境、新手段为学校的教学、科研和教 务管理服务。近年来，学校的招生规模不断扩大，在校学生人数明显增 多，加之学生分校区管理，给原本繁杂的院级选修课的人工选课工作增 加了不少教务工作量。网上选课系统”3 的推出，使得选修课程的设置维 护、学生选退课及成绩查询、任课教师的学生名单打印及成绩录入 统计等工作均能在互联网上完成。这不仅减轻了教务人员的工作负担， 也大大方便了全校师生对选课信息的维护、查询。 在高校教学管理的规范化、系统化以及计算机网络化的实施过程 中，网上选课系统已成为教学教务管理的关键部分。当前高等学校己从 学年制逐步向学分制”1 过渡。学分制重要的特点是只要学生按照选定专 业的培养计划修完规定的课程并获得相应的学分即可取得相应的学位 或学历，而对学习年限没有规定。实行学分制管理，学生可以在允许的 范围内选择适合自己需要的课程，有利于培养学生的个性化发展。 选课系统是学分制教学改革的一个重要措施，它允许学生给自己安 排课程、时间以及任课教师，充分发挥学生的主观能动性，调动学生的 学习积极性，拓宽知识面，同时也在教师队伍中引进竞争机制，有利于 促进教学质量的提高。但是，在选课过程中，方面由于师资、时间、 教室有限，而学生的选课往往又有很大的倾向性；另一方面学生对于选 课结果能否在最段时间内得到答案，这种需求也是不断在增加。 2 1 2 选课系统中应用的主要技术 选课系统采用的是基于w e b 的三层c s ( 客户机服务器) 结构模型 “( 如图2 1 ) ，这种三层结构是在原二层c s 结构的基础上将服务器端 进一步分解成一个应用服务器( w e b 服务器) 和一个数据库服务器：浏览 器用于接收用户输入并显示从w e b j j i 务器返回的信息；w e b j e 务器用于接 收从浏览器传来的用户信息，向数据库服务器提出操作请求并将操作结 果返回给浏览器；数据库服务器主要完成数据的定义、查询和更新等操 作，并维护数据的安全性和完整性。 客户机 浏览器 i l i基于w e b 应用的服务器 ： l 数据库服务器s q ls e r v e r 图2 1 三层c s 结构模型 选用这样的结构模型主要出于以下几方面的考虑：( 1 ) 选课系统是 面向全校师生的，而三层c s 结构对客户端没有特殊的要求，用户只需 在任何一台能上网的计算机上操作就行。( 2 ) 系统的应用逻辑需要调整 时，只要对w e b 艮务器进行升级，对客户端和数据库服务器几乎没有影 响，这保证了选课系统的可维护性。( 3 ) 数据库服务器可根据具体需要 配置到一台或多台物理服务器上，在数据量不大时，甚至可以与w e b 服 务器合用一台主机( 目前本系统即采用这样的方案) ，这不仅提高了系统 的执行效率，也增加了系统的安全性和灵活性。 在选课过程中，主要选用完全面向对象的可视编程语言c 舯仁为开发 语言”，采用的数据库是易于安装、使用和管理的m i c r o s o f ts q l s e v e r 2 0 0 0 数据库，我们同时还运用在断开连接的世界里可以进行操作 的a d o n e t 技术作为数据访问的方法来实现与m i c r o s o f ts o l s e v e r 2 0 0 0 数据库之间的数据访问，使整个选课系统更加利于开发设计 与实现： 1 c # 程序语言是一种由事件驱动的、完全面向对象的可视编程语言 “”“，程序用一个i d e ( 集成开发环境) 来创建。它汲取了c ，c + + 的很多 优点，通过i d e ，程序员可以方便的创建、运行、测试和调试c # 程序。 有了i d e ，将大大缩短创建一个能实际运行的程序所需的时间。而用j a v a 程序语言编程，虽然代码的运行速度比较快，占有系统资源比较少而且 是可以跨平台进行操作，但是在运行时需要有一个虚拟机j v m ( j a v a v i r t u a lm a c h i n e ) 对其代码进行解释，再加上对j a v a 的学习比较复杂和 开发周期比较长，所以我们选用c # 程序语言作为编程语言。 2 m i c r o s o f ts q ls e v e r 2 0 0 0 是一种典型的具有客户机n 务器体系 6 架构的关系数据库管理系统，它使用t r a n s a c t s q l 语句在服务器和客户 机之间传送请求和回应。m i c r o s o f ts o ls e v e r 具有可靠性、可伸缩性、 可管理性、可用性等特点，为用户提供了完整的数据库解决方案。从工 具软件方面讲，m i c r o s o f ts q ls e v e r 2 0 0 0 数据库较易于安装、使用和 管理，即为“操作简单”，这也是一个减少成本的关键因素。s q ls e r v e r 与w i n d o w s 操作系统无缝集成，m i c r o s o f t 公司总是尽可能将所有的软 件功能捆扎在一起，除非用户还需要其他用处的操作软件包，否则功能 已足够使用了。 3 a d o n e t 是一种全新的数据访问方法“”，是m i c r o s o f t 推出的一种 数据访问技术。a d o n e t 适用于使用连接的以及断开连接的i n t e r n e t 世 界。就a d o n e t 而言，其性能与价格成正比，价格比较合理，它充分利 用了托管数据提供者，从而提高了应用程序的总体速度和性能。此外 a d o n e t 还可同时在使用连接的和断开连接的环境中工作：在连接状态 时，用户可以直接连接到数据库，在读取数据的同时保持与数据库的连 接；在断开连接的世界里，a d o n e t 通过把数据访问这个方面的问题移 到断开连接模型上，把希望编辑或修改的数据从服务器发送到客户，在 客户机上进行本地缓存，然后可以在客户机上进行编辑，在更新数据库 时，可以把数据发回到服务器，从而可为我们解决任何冲突。在a d o n e t 中，读取数据时，使用被称为d a t a r e a d e r 的对象。编辑和更新处理断 开连接的数据时，在d a t a s e t 关系数掘结构中本地缓存数据，d a t a s e t 可以在内存缓存中以表格地形式保存大量数据( d a t a t a b l e 对象) ，它 们地关系( d a t a r e l a t i o n 对象) 和约束条件，接着，可以把它们导出 到外部文件或者另一个d a t a s e t 对象。 2 2 现有选课算法分析 学分制允许学生跨系、跨专业、跨年级选课，学生也可以自由选择 上课时间和自己喜欢的教师。但教学资源有限不能满足所有学生的修读 要求，因此需要有选课条件来限制学生选课，即对部分课程设定一些限 制条件或优先条件。对选课人数超过预定的歼课人数的教学班要进行筛 选，目前培养计划中学生修读的课程大致分为公共基础课、学科基础课、 专业必修课、专业选修课、全院综合选修课等5 大类。对于不同类的课 程应用不同的算法进行筛选，下面分析几种常用的选课系统的公平算 法： 7 2 2 1 先来先服务( f c f s ) 的算法 先来先服务( f c f s ) 的算法“：它的实现思想就是“排队买票”的 办法，是最简单的一种调度算法，这个算法也是在选课系统中最早应用 得一个很普遍得算法。 算法流程如图2 2 所示： 图2 2 先来先服务( f c f s ) 的算法 这种算法虽然实行比较容易，在时间上也有一定的时间效益保证， 但是只要选课的课掌人数已满，对后面任何参加选课的学生来说都没有 机会选择这门课程。例如：有3 0 0 学生参加容纳2 0 0 人的课掌选课，在 3 0 0 学生中前2 0 0 人进行选课几乎都可以被选中，而后i 0 0 个想选这个 课堂的学生就不能选中。这严重的违背了高校中学生自主选课的原则， 并不能够做到公平合理的安排选课。 2 2 2 抽签算法 抽签算法“：它的实现思想就是在整个选课过程中，学生先进行选 课，在整个选课结束后进行后台处理来判断选中是否。当某个课堂的选 课的人数超过容纳人数时，就要对所有参加该课堂选课的学生进行抽签 的方式来决定最终的选课结果。 在抽签算法里，应用抽签的方式“”也很多，主要有随机抽取、按权 重高低抽取和各种优先排列抽取等。 用随机抽取方式的抽签算法，我们仍用3 0 0 学生参加容纳2 0 0 人的 课堂选课为例子作以说明，用抽签算法的思维就是在3 0 0 名学生选课之 后，进行随机抽签的方式来抽出2 0 0 人作为这门课的最终选中名单。 按权重高低抽取方式的抽签算法“”比较简单，就是要求学生在选修 每门课程时投入一定权重分。权重分越高则选中的机率越大，但学生的 每学期权重分总数基本相同。 算法流程图如下所示： 统计某个课堂的选修人数 是否小于该课堂 的容纳人豹n ? 按权重分从高到低选取n 条记录存入结果表 下一个课堂处理 全部记 录存入 结果表 图2 3 按权重高低算法 目前有的高校还应用专业优先算法和成绩优先算法“”等各种优先 排列抽取方式的抽签算法，其中专业优先的算法比较适用专业选修课的 数据处理；成绩优先也就是在前台选课结束后，对选课人数大于预置人 数的课程进行筛选，即将已选某门课程学生的学分积按降序排列，由高 分到低分筛选，从中选出定数量的学生。现以专业优先算法为例，流 9 程如下图所示： 图2 4 专业优先算法 l o 这个算法虽然在原则上具有相对公平合理性，但是在时间上却得不 到保障，因为最终结果是在对整个学生选课操作结束后才进行后台处理 的。 2 2 3 分志愿筛选算法“” 此算法用于同- - 1 3 课程有多个课堂的情况下，学生可有几个优先级 不同的志愿，最多为3 个。计算机按不同的志愿进行处理。首先满足第 一志愿，若第一志愿的人数超过最大上课人数，则采用平均分布概率算 法进一步处理，筛选出多余的人数，不再处理第二志愿。若第一志愿的 人数小于总人数，全部选中。当第一志愿遍历一遍后，再遍历第二志愿； 并将第一志愿该课堂不足的人数作为第二志愿的最大可选人数。处理方 法同第一志愿，以此类推。第一志愿优先级最高、机会最大，最有可能 选中。第二志愿处理对象为：第一志愿处理后该课堂所剩可选人数( m 2 ) 及该课堂的第二志愿所有人数( n 2 ) ，若n 2 m 2 ，则全部选中，否则处理 类似第一志愿，第三志愿处理方法同第二志愿。 处理流程如图： 图2 5 平均分布概率处理流稗 图2 6 第一志愿处理流程 此算法是采用实时选课处理和后台批处理相结合的方法来实现的。 由于该算法是在所有学生选课结束后，才进行后台处理的，这样就避免 了先来先服务的不足。当后台处理完之后，有可能会有少量的学生3 个 志愿都未选中，需要作一些人工干预等处理，最终产生学生课程表。在 经过一段时间的使用后，发现分级筛选算法能够实现相对公平选课的要 求，并且运行处理速度较快，是性能较为优越的选课算法。但是，由于 该算法仍需要后台处理才能产生最终的学生课程表，并没有实现学生选 课的实时处理，以人为本的理念也没有得到完全体现。 2 2 4 一种基于线性不等式组的选课模型。”2 0 选课是大学学习的重要组成部分。如何合理的选课，不但是学生顺 利完成学业的必要条件，而且可避免在学习过程中前序课和后继课之间 的矛盾。一般情况下，可供选择的课程有许多，每门课程都能使学生在 某些方面获得知识，然而，针对某个学生而言，选择适合自己的课程受 到各方面的限制。现在抛开学生本身的素质( 学习能力、学习兴趣) ，也 忽略课程的难易程度，仅仅考虑在现有资源下，组建有限门课程可选性 的数学模型。“，通过求解这个数学模型，现以给出计算机学院某个学期 的计算机类课程可选方案为例，从结果分析该模型的合理性和实际意 义。然而在实际学习过程中，学生则必须结合自身情况，选择最适合自 己的一套方案。 1 2 l 、数学模型的建立 1 ) 决策变量的选取 由于课程之间的不可分性，以某门课程x ，为决策变量，其取舍只存 在两种情况：选修和不选修，数学表达式为 i = l 该课程被选修 i = 0 该课程被拒绝 所以该问题的决策变量只能取0 或l 。 2 ) 指定条件 根据国家的有关规定和学校的培养计划，由于某些课程是学习其他 相关后续课程的基础，如果缺少对它的学习，那么后继课程将无法继续 进行( 比如理工类高等数学) ，因而被直接指定为必修课( 必选) ，用 l 一 1 数学语言描述为工j 2 1 ，o2 i j ，2 ，”j 其中n 为开设课程的总数。 3 ) 相互依存关系 从知识结构来讲，学习是一种系统性的社会活动，课程之间是紧密 联系、环环相扣的，如果前期末学习某门或某些课程，那么后期与之属 于同一个系统的相关课程就不能选修，即后续课的学习是以前期课学习 为基础，两者之间存在依存关系。它们之间应该满足逻辑关系式： 工f = l j 工，= 1 ( f ) 4 ) 学分限制 健全的系统具有条理性和合理性的特点，在学生的实际学习过程 中，必须形成一个完整地封闭系统。无论是从遵循学校的培养计划，还 是从自己将来的发展方向来讲，都有一定的限度，即要形成完整的知识 结构，必须取得一定的学分。在有限的课程中选择一门课，意味着可能 要放弃其他可选课，但同时要能够完成一定的学分。即 9k ，。b其中k ，表示第吖1 课程的规定学分，b 为学校规定该学期 = 内必须完成的最低学分。 5 ) 上界条件 从式手t ，。6 可以看出，学生要达到学分要求，选足够多的课程 乞 就行。然而在实际学习中，它们之问存在一定的上界约束关系，即考虑 到学生的承受能力，学校必须控制学生在本期内选课的上限，即 y x i a其中a 为该学期内最多能选学的课程门数。 智 6 ) 互斥条件 系统各因素之间不是一些零散部件的堆积，而是互相制约的，也就 是说，某些课程之间最多只能选择其一。根据教学计划的安排，这些课 程是同时开课的，由于上课时间发生冲突，势必造成这些课程不能同时 选学，表述为数学中的互斥关系，其表达式为 x + x ，= 1忙，) 7 ) 白有条件 假设只考虑以上主要因素，对选课过程中碰到的其他因素( 客观或 主管原因) 不予以考虑，比如课程是否开设，学生是否有兴趣以及学生 是否愿意选该老师所任的课等等。 定义指标集，= 1 2 ，n ，w2 托，】f ，f ，j ，i o ，。 综合上述讨论，其数学模型为： 工f 口 f e ，o x ，= 1 x 2 x i p i ( f ，) w x + x = 1 取，) w x ：= 0 或1 i ， 2 、模型的求解 1 ) 决策变量约束矩阵 该线性不等式组属于o 一1 线性不等式组，其解法很多，对于规模较 小问题我们采用隐式枚举的方法。由决策变量的系数构成约束矩阵，根 4 据决策变量为o 或1 的情况进行判断。由于计算机不能识别课程之间的约 束，约束的判定必须人工进行。因此，约束条件主要采用人机交互式输 入，一定程度上也增加了操作人员的主动性和灵活性。 2 ) 选课实例模型 现以计算机学院某个学期的计算机类课程可选方案为例，学分要不 低于3 0 学分，最多只能选1 0 门课程，其课程设置和学分如表所示： 表2 一l 课程设置和学分设置 上述条件中，我们设定课程4 、5 、9 、1 0 相互依存，课程1 5 、1 6 、 1 8 相互依存；课程5 、7 、8 、1 l 互斥，1 2 、1 3 、1 4 、1 7 互斥。 用k i 表示第i 门课程的学分，那么数学模型如下： k - 3 0 拒，o ( 总学分控制) 工4 = 1 j x 5 = 1x 5 = 1 j x 9 = 1x 4 = 1 x i o = 1 ( 互存条件) x 1 52 1 = x 1 6 = 1j 1 5 。1 = x 1 82 1 x l2 x 22 x 32 1 b + x 7 + x 8 + 工l l = 12 + x 1 3 + x 1 4 + x 1 7 = 1 工f 1 0 i e | “ x ：= o 或1i i ( 必修条件) ( 互斥条件) ( 课程数目控制) 将上述不等式组进行优化得到的结果如下图表所示： 表2 2 不等式组进行优化结果 ( 选择控制) 选课方案所得学分 1 ，2 ，3 ，4 ，5 ，9 ，1 0 ，1 2 ( 1 3 1 4 1 7 ) ，1 5 1 ，2 ，3 ，4 ，5 ，6 ，9 ，1 0 ，1 5 ，1 6 ( 1 8 ) 1 ，2 ，3 ，4 ，5 ，9 ，1 0 ，1 2 ( 1 3 1 4 1 7 ) ，1 5 ，1 6 ( 培) l ，2 ，3 ，4 ，5 ( 7 例1 1 ) ，9 ，1 2 ( 1 3 1 4 1 7 ) ，1 5 ，1 6 ，1 8 1 ，2 ，3 ，4 ，5 ( 7 8 1 1 ) ，6 ，1 2 ( 1 3 1 4 1 7 ) ，1 5 ，1 6 ，1 8 1 ，2 ，3 ，4 ，9 ，1 2 ( 1 3 1 4 1 7 ) ，1 5 ，1 6 ，1 8 3 1 3 1 3 0 5 3 0 5 3 0 3 0 注：其中5 ( 7 8 1 1 ) 表示在该方案中，即可以选择课程编号为5 的课程，也可选择编号为7 、8 或l l 的课程，其他的依次类推。 3 、结果分析 从上述优化结果可以得到以下结论： ( 1 ) 可供学生选择的方案有5 0 种，并且每一种方案都须选择l o f 或9 门课程，也就是说不会发生某位同学选择很少的几门课就可以取得 规定的学分，这符合均衡的目标： ( 2 ) 所得学分基本相等，差异性不会过大，即从学校的角度来讲， 1 6 规章制度对每个人都是相对公平的： ( 3 ) 结果还反映了数学基础课的培养计划。结果显示选修课程4 占主导地位，表明了学院以算法为主要学科的学科建设计划。 因此选课模型不但给学生提供了选课方案，同时反映学校课程设簧 的一些侧重点，有推广的价值。然而上述模型也存在着不足： ( 1 ) 问题规模小，有待于考虑全校的选课情况； ( 2 ) 只考虑课程的相互依存，而忽略了学生在学习过程中的半途 而废，如数学建模入门和最优化计算方法修完之后而放弃数学建模实践 的学习。 通过上述分析看到，基于线性不等式组的选课模型合理可行，并且 课程门数、学分等具有可调节性，实例有效的解决了学校基础课的选课 问题。 2 3 本章小结 在选课过程中不管是采用哪种思想的选课算法都不能将问题的全方 面来加以考虑的，对学生的选课要求都不可能全部满足，以人为本的理 念根本得不到体现。我们需要的是一种公开、相对公平、相对公正合理 的选课算法。 先来先服务这种算法虽然实行比较容易，在时间上也有一定的时间 效益保证，但是只要选课的课堂人数已满，对后面任何参加选课的学生 来说都没有机会选择这门课程。这严重的违背了高校中学生自主选课的 原则，并不能够做到相对公平合理的安排选课。 就抽签算法而言，这个算法虽然在原则上具有公平合理性，但是在 时间上却得不到保障，因为最终结果是在对整个学生选课操作结束后才 进行后台处理的。 分志愿筛选算法是采用实时选课处理和后台批处理相结合的方法 来实现的。由于该算法是在所有学生选课结束后，才进行后台处理的， 这样就避免了先来先服务的不足。但是，由于该算法是与后台批处理相 结合才能产生最终的学生课程表，并没有实现学生选课的实时处理，以 人为本的理念也没有得到完全体现。 对于基于线性不等式组的选课模型来说，虽然对于问题规模较小的 选课范围来说有着一定意义，但是这种选课模型只是在学生选课时提供 了不同的选课方案，具有一定参考价值，而在实际的选课过程中并没有 解决使得每个学生都能够在选课时间内尽可能的拥有均等的概率选中 某个课堂和使参加选课的学生尽可能早的得知是否选中这一核心问题。 总而言之，我们所需要的选课算法应该是尽可能的使得每个学生都 能够在选课时间内尽可能的拥有均等的概率选中该课程，同时又能够使 参加选课的学生尽可能早的得知是否选中。我们需要在整个选课过程 中，在时间效益得到保证的同时，相对公平合理的选课原则尽可能的得 以体现。 第三章基于概率动态分布选课算法 3 1 基于概率动态分布选课算法的提出 要实现实时选课，使得每个学生都能够在选课时间内尽可能的拥有 均等的概率选中该课程，同时能够使参加选课的学生尽可能的在第一时 间里得知是否选中，真正做到以人为本的理念，我们提出了基于概率动 态分布的选课算法，使得时间效益得到保证的同时，相对公平合理的选 课原则也能够得以体现，真正做到相对公开、公正、公平。而这种算法 中概率选取的是否得当是决定整个算法优越性的关键因素。 为了在选课过程中实现相对公开、公正、公平，并且满足课程安排 的要求，在选课的过程中，需要随时根据实际情况对每个想选该课程的 人选中的概率进行调整。在整个选课过程中，如果参选人数小于或等于 所选课堂容纳的人数，那么全部选中。否则，我们就要采用相应的算法 来对选课过程进行控制。当想选该课程的人数过多时，要降低选中的概 率，以便给后选的人留出适当的机会，当想选该课程的人数过少时，要 提高选中的概率，使选中该课程的人数能够满足开课要求。这样在选课 的过程中就要运用动态概率分布的方法，随时调整选中课程的概率，从 而实现相对公平合理的选课原则。 3 2 基于概率动态分布选课算法的实现 3 2 1 选课人数分布预测 在选课过程中，如果能够对总的选课期间内选课人数随时间的分布 作出准确预测，那么我们就可以对单位时间内选中该课程的人数进行控 制，从而实现不同时刻参选人选中该课程的机会基本一致，保证选课的 相对公平性。从现有资料来看，选课过程开始后单位时间内参加选课的 人数随时间平稳变化，具有明显的规律性，可以利用某些函数来拟合这 种规律性的变化。 1 、参选人数随时间对应分布的曲线拟合 在科学研究与其他许多实际问题中，常常有函数不便于处理或计算 1 9 的情形。有时候函数关系没有明显的解析表达式，需要根据实验观测或 其他方法来确定与自变量的某些值相对应的函数值”；有时函数虽然有 明显的解析表达式，但是使用很不方便。因此，我们希望对这些问题中 的函数建立一个简单的便于计算和处理的近似表达式，即用一个简单的 函数来近似代替复杂的函数。近似代替有叫做逼近。所谓简单函数，一 般指可以用四则运算进行计算的函数，例如多项式、有理分式等。 逼近的方式可以是多种多样的，可以根据问题的性质与要求来选 择。当然，我们所提出的对逼近方式的要求必须合理，这样才能有确定 的解答，不恰当的要求会导致问题无解或解不唯一。在解为唯一的前提 下，还必须考虑求解的方便性。常用的逼近方式有：插值、一致逼近、 均方逼近等。 插值法就是根据函数f ( x ) 已有的数据表格来计算f ( x ) 在一些新的 点x 处的函数值，但是它只能是在给定的函数表中间插入一些所需要的 新的函数值，无法对以后的函数值进行预测；一致逼近与均方逼近解决 问题时，函数f ( x ) 都是在区间 a ，b 上考虑的，如果对于给定函数f ( x ) 在一些离散点xo ，x i ，x 一( 各xr 互不相同) 处考虑其逼近问题，则称 之为曲线拟合。 显然，曲线拟合问题与函数插值问题不同，它不要求曲线通过所有 已知点，只要求得出的近似函数能反映数据的基本关系。因此，曲线拟 合的过程比插值过程得到的结果更能反映客观实际。在对给出的观测数 据( x i ，y 1 ) ( i = 0 ，1 ，2 ，n ) 作拟合曲线时，怎样才算“拟合的最 好”呢? 一般总是希望使观测数据与拟合曲线的偏差的平方和最小，这 样就能使拟合曲线更接近于真实函数。这个原理称之为最小二乘原理。 用最小二乘原理作为衡量“曲线拟合优劣”的准则称之为曲线拟合的最 小二乘法。 我们采用适用于一般函数拟合问题的多项式拟合。考虑一个m 次多 项式 来拟合n 个观测数据点 其中m 远小于n 。 做误差的平方和 d ，7 ( 3 1 ) 2 0 f ，q ，a 。) y ( 以) 再分别对a o ，a - ，a m 求偏导数，并使之为零，得 善= 2 渺小蹦班0 j - 0 l ，”，m 眠 ye a 。+ 口1 工i + + 口。工? 一y k 】工：2 0 k - i 亦即系数ao ，a l ，a 一应满足如下方程组 h 口。工：+ 口。x ；“+ + 口。z x f + ”= z y 。x ! ，j = o ，1 ，m ( 3 2 ) 由于方程组( 2 ) 的系数矩阵是一个对称矩阵，并且是正定的。由 此可以唯一的解出a o ，a - ，a m ，然后带入m 次多项式( 1 ) 便可以得 到由观测点所确定的近似多项式。 由于高次多项式的拟合会引起数值的不稳定，在工程中没有实用价 值。所以在此我们试用三参数二次多项式和四参数三次多项式来拟合选 课过程中的参选人数随时间的对应分布情况。 具体图表如下： 图3 ，l 参选人数随时间的对应分布情况一 图3 2 参选人数随时间的对应分布情况二 从上面的两个图表中，我们可以看出应用多项式来拟合选课过程中 的参选人数分布时，拟合出来的曲线只对观测点后面的很短一段时间有 预测效果，而且拟合曲线与原数据关系极为密切，随着原数据的不同， 拟合出来的曲线也大不相同。 由于在实际的选课过程中，参选的人数是随机的，那么其分布也很 随机，随着时间、环境和设备等外界因素的不同，要作此试验的难度和 随机性都很大，随机因素也很多，例如上课时间、中午休息时间、以及 就餐时间和可以利用的计算机数量等都对选课