２０１ ０年第１ ９卷第４期 计算机系统应用 基于变化概率的网络选课系统公平算法① 张 戈（中国青年政治学院计算机教学与应用中心北京１ ０００８９） 摘要： 网络选课系统研发工作的重点和难点就是找到一种算法既能充分体现选课活动的公平性又能很好地解 决大批量并发访问系统带来的网络拥堵问题。对现有选课算法进行了分析和研究，提出并详细阐述用 于实时选课系统的一种新算法——基于变化概率的公平算法。该算法使得每个学生在选课活动当中能 拥有趋于均等的选课概率，从而使选课活动在最大程度上实现了公平性原则并极大的缓解了网络拥堵 问题。 关键词：选课算法；变化概率；公平性；网络拥堵 Ａｌｇｏｒｉｔｈｍｓ ｏｆ Ｗｅｂ Ｃｏｕｒｓｅ Ｓｅｌｅｃｔｉｏｎ－Ａｒｒａｎｇｅｍｅｎｔ Ｓｙｓｔｅｍ Ｂａｓｅｄ ｏｎ Ｖａｄｅｄ Ｐｒｏｂａｂｉｌｉｔｙ ＺＨＡＮＧＧｅ （Ｃｈｉｎａ Ｙｏｕｔｈ Ｕｎｉｖｅｒｓｉｔｙ ｆｏｒ Ｐｏｌｉｔｉｃａｌ Ｓｃｉｅｎｃｅｓ，Ｂｅｉｊｉｎｇ １ ０００８９，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ｍｏｓｔ ｉｍｐｏｒｔａｎｔ ａｎｄ ｄｉｆｆｉｃｕｌｔ ｔｈｉｎｇ ｉｓ ｈｏｗ ｔｏ ｆｉｎｄ ａｎ ａｌｇｏｒｉｔｈｍ ｗｈｉｃｈ ｃａｎ ｒｅｓｏｌｖｅ ｔｈｅ ｅｑｕｉｔｙ ｐｒｏｂｌｅｍ ａｎｄ ｎｅｔｗｏｒｋ ｃｏｎｇｅｓｔｉｏｎ ｐｒｏｂｌｅｍ ｃａｕｓｅｄ ｂｙ ｃｏｎｃｕｒｒｅｎｔ ｖｉｓｉｔ ｔｏ ｓｙｓｔｅｍ ｂｙ ｍｕｌｔｉｔｕｄｉｎｏｕｓ ｓｔｕｄｅｎｔｓ．Ｔｈｉｓ ｐａｐｅｒ ａｎａｌｙｚｅｓ ａｎｄ ｒｅｓｅａｒｃｈｅｓ ｔｈｅｓｅ ｅｘｉｓｔｉｎｇ ａｌｇｏｒｉｔｈｍ，ａｎｄ ｐｒｏｐｏｓｅｓ ｎｅｗ ａｌｇｏｒｉｔｈｍｓ—Ａｌｇｏｒｉｔｈｍｓ ｏｆ Ｗｅｂ Ｃｏｕｒｓｅ Ｓｅｌｅｃｔｉｏｎ－Ａｒｒａｎｇｅｍｅｎｔ Ｓｙｓｔｅｍ ｂａｓｅｄ ｏｎ ｐｒｏｂａｂｉｌｉｔｙ．Ｔｈｅｓｅ ａｌｇｏｒｉｔｈｍｓ ｍａｋｅ ｅｖｅｒｙ ｓｔｕｄｅｎｔ ｈａｖｅ ｅｑｕａｌ ｐｒｏｂａｂｉｌｉｙ ｔｏｎ ｔｈｅ ｍｏｖｅ ｏｆ ｃｏｕｒｓｅ ｓｅｌｅｃｔｉｏｎ．Ｔｈｅｒｅｆｏｒｅ，ｔｈｅ ｅｑｕｉｙ ｔａｎｄ ｎｅｔｗｏｒｋ ｃｏｎｇｅｓｔｉｏｎ ｃａｎ ｂｅ ｒｅｓｏｌｖｅｄ ａｔ ｌａｒｇｅ． Ｋｅｙｗｏｒｄｓ：ａｌｇｏｒｉｔｈｍｓ ｏｆ Ｗｅｂ ｃｏｕｒｓｅ ｓｅｌｅｃｔｉｏｎ—ａｒｒａｎｇｅｍｅｎｔ ｓｙｓｔｅｍ；Ｖａ ｅｄ ｐｒｏｂａｂｉｌｉｙ；ｔｔｈｅ ｅｑｕｉｔｙ ｐｒｏｂｌｅｍ；ｎｅｔｗｏｒｋ ｃｏｎｇｅｓｔｉｏｎ 当前网络选课系统已广泛应用于国内各大专院 会出现系统瘫痪的情况【２】。抽签算法在数学上满足了 公平性原则，但是却忽略了学生专业、学生兴趣等多 方面因素对课程的需求，没有体现真正的公平Ｉ３】。专 业优先筛选算法只适用于专业选修课，适用面狭窄不 能堪当整个选课重任。分志愿筛选算法是一个顾及到 学生意愿的公平算法，但是该算法只适用于同一门课 校，系统研发工作的重点和难点就是找到一种算法既 能充分体现选课活动的公平性又能很好的解决大批量 并发访问系统带来的网络拥堵问题，但遗憾的是目前 还没有一个非常行之有效的算法可以同时解决上面两 个问题。 程开设多个教学班的情况，也具有一定的局限性【４】。 １ 现有选课系统算法分析 目前常见的算法有先到先得筛选算法、抽签筛选 算法、专业优先筛选算法、分志愿筛选算法…等，这 些算法各有利弊。比如先到先得筛选算法，这种算法 由于其简单易实现的特性被不少院校所采用。但是该 算法会造成大量学生在选课的初期时间段内集中访问 对选课算法的现状进行研究和分析之后，发现不 同算法都存在这样或那样的问题，各个院校均采取结 合自己实际情况选择一种或多种选课算法的方式来处 理选课活动【ｓ】。在对一些学校的课程体系分析之后， 发现很多学校的课程设置均存在共性，即选修课分为 公共选修和专业选修两大类。公共选修课的选课活动 系统进行选课，导致网络拥堵，加大系统负担，甚至 占整个选课活动的大部分，选课对象范围最广，参与 ①收稿时间：２００９—０８—０２；收到修改稿时间：２００９—０９—２１ Ｅｘｐｅｒｉｅｎｃｅｓ Ｅｘｃｈａｎｇｅ经验交流１８１ 计算机系统应用 ２０１ ０年第１ ９卷第４期 人数最多，公选课的执行能力直接影响整个选课活动 算如公式（１）。 的效率，因此本文针对公共选修课提出了一种新的选 课筛选算法。 Ａ—Ｚ Ｐ＝．．．—————————————— （Ｂ—ｚ） １１２ 说明：第一，此公式中的符号“Ａ”代表开方； ２公共选修课筛选算法设计 ２．１实时选课方式的采用 由于公共选修课面向学校所有系所有专业学生， 学生的专业差异被弱化，对于这样的课程采用实时选 第二，由于参数Ｂ是选课学生在当前所有选课记录（包 括所有公共选修课的选课记录）中的排序序号，其值总 是大于当前该课程的选中人数Ｚ，所以此公式总有解。 例如，当前已经有３Ｏ人进行了公选课（所有公选课） 课的方式是可行的【６】。实时选课就是实时跟踪学生的 选课情况，实时反映系统总课表的调整情况，以达到 学生选课的准确无误【７】。一般地实时选课系统应具有 如下功能：学生能直观的看到全校每门课程的所有开 课信息，包括真实的上课时间等，而不是时间代码．并 能实时监测每门课程的被选情况；学生可直观地看到自 己随着选课操作而不断变动的个人选课信息；对于每次 选课操作，能实时判断选课时间和选课人数冲突并反馈 选课结果给学生：选课中出现课程调整时，能在选课时 使用的总课表中和选课操作中做出实时反应【８】。实时 选课方式与“前台选课后台筛选”的选课方式的最大 区别在于其选课的实时性。在此方式下，选课系统会 对学生的选课概率做出实时调整，当选课结束或者该 课程达到满员时，选中学生的人数和这些学生的学号 已经基本确定，可直接告知学生这一选课结果，如果 需要，教务工作人员只做部分调整【９】。教务工作人员 不需要在后台对该课程的所有学生做筛选。 ２．２变化概率公平算法设计 针对实时选课，本文提出“变化概率公平筛选算 法”。基于这种算法，学生选课时的选课概率会实时变 化和调整，每个学生具有接近均等的选课概率，从而 使选课活动的公平性达到最大化。该算法描述如下： 步骤１：设置初始值，包括初始选课概率（即第一 个参选该门课程的学生具有的选课概率）和初始随机 数：初始选课概率的设置以以往该课程的选课情况为 参考，具体做法为，取出上次该课程的选课筛选表， 将其初始选课概率（即第一个人的选课概率）设置为１， 然后取所有学生选课概率的平均值；初始随机数＝随 机函数ｘ初始选课概率； 步骤２：在选课过程中，每有一个学生选择该课 程，则随即统计当前选择该课程的参选人数Ａ，该学 生在所有选课记录中的序号Ｂ，当前该课程的选中人 数Ｚ，并计算该学生的选课概率Ｐ，选课概率Ｐ的计 １８２经验交流Ｅｘｐｅｒｉｅｎｃｅｓ Ｅｘｃｈａｎｇｅ 的选课活动，总选课记录为３０，一名学生在选择了＜计 算机网页设计》课程之后，该学生对应的参数Ｂ即为 ３１，而当前《计算机网页设计》课程的选中人数Ｚ总 小于参数Ｂ，则公式总有解。 步骤３：计算随机数Ｒ，Ｒ＝ＲＡＮＤＯＸ系数，系 数为前面所有选课概率中的最大值； 步骤４：对该生的选课概率Ｐ和随机数Ｒ进行比 较，如果Ｐ＞Ｒ，则该生为选中状态，否则该生落选： 步骤５：判断选课时间是否结束或者选中人数是 否达到预置人数上限Ｍ，两个条件有一个满足，则结 束该课程的选课活动： 步骤６：该课程选课活动结束时，统计该课程的 总参选人数Ｓ，总选中人数Ｔ，如果Ｓ＜＝Ｍ，则做出调 整：将所有该课的参选学生设置为选中状态，否则对 Ｔ和Ｍ进行比较，并做出如下处理： 如果Ｔ＝Ｍ，则保留当前筛选结果，该结果为正式 选课结果： 如果Ｔ＞Ｍ，则从选中学生中随机抽取Ｔ＿Ｍ个， 将其选课结果设置为落选； 如果Ｔ＜Ｍ，则从落选学生中随机抽取Ｍ—Ｔ个． 将其选课结果设置为选中。 假设系统当前共有１ ２０人参加所有课程的选课活 动（这里的当前是指同一时间，即同一时刻），有３５人 参加＜计算机网页设计＞课程的选课活动，该课程的 预置上限人数为３０人，其选课筛选表如表１所示。 对上面筛选表做选课概率的折线图，如图１所示。 选课概率折线图 ｌ ０．５ Ｏ ±垄 垩＝垡丝！垄塑 图１ 选课概率折线图 ２０１ ０年第１ ９卷第４期 表１ 选课筛选表 在总选 是 选择该课 课范围 否 选中 程的参选 随机数 选课概率 里的编 选 人数 人数 由 １ ２ Ｏ．４１ ９Ｏ５４ ０．７０７１ ０７ １ １ ２ Ｓ ０．６８３０１ ２ ０．５ ０ １ ３ ８ Ｏ．１ Ｏ５８８３ ０．７５５９２９ １ ２ ４ １２ Ｏ．３Ｏ１ ５９ Ｏ．６３２４５６ １ ３ Ｓ １４ Ｏ．５７６８８７ ０．６０３０２３ １ ４ ６ １８ Ｏ．５５８３５９ ０．５３４５２２ Ｏ ４ ７ ２２ Ｏ．３３Ｏ９１ ９ ０．７０７１ ０７ １ ５ ８ ２５ Ｏ．６１ ７６６３ Ｏ．６７０８２ １ ６ ９ ２６ ０．Ｏ５３６６３ Ｏ．６７Ｏ８２ １ ７ １ ０ ２８ ０．１ ５２５７９ ０．６５４６５４ １ ８ １ １ ３２ ０．Ｏ１ ５３９９ Ｏ．６１ ２３７２ １ ９ １ ２ ３５ ０．４６１ ９８３ Ｏ．５８８３４８ １ １０ １ ３ ３６ ０．２４６０６４ Ｏ．５８８３４８ １ １ １ １４ ３９ ０．５５６６８９ Ｏ．５６６９４７ １ １ ２ １ ５ ４１ Ｏ－３７５９６８ ０．５５７０８６ １ １ ３ １６ ４５ ０．４４２５８ Ｏ．Ｓ３０３３ １ １４ １ ７ ５２ ０．６９８４４３ ０．４８６６６４ ０ １４ １ ８ ５５ Ｏ．５８６９８３ Ｏ．６２４６９５ １ １ ５ １ ９ ５７ ０．１８９１ １６ Ｏ．６１ ７２１ ３ １ １６ ２Ｏ Ｓ９ Ｏ．５９１６２ ０．６Ｏ９９９４ １ １ ７ ２１ ６３ ０．０３０５０３ Ｏ．５８９７６８ １ １ ８ ２２ ６７ ０．２２ ５４８９ ０．Ｓ７１ ４２９ １ １９ ２３ ７３ ０．３０３２３８ ０．５４４３３ １ １ ２Ｏ ２４ ７６ ０．６０６９５ ５ ０．５３４５２２ ０ ２０ ２５ ８Ｏ Ｏ．２２２１９７ ０．６４５４９７ １ ２１ ２６ ８３ ０．２３７８３９ ０．６３５Ｏ０１ １ ２２ ２７ ８８ ０．３３９９１ Ｓ ０．６１ ５４５７ １ ２３ ２８ ９２ ０．５０７００２ Ｏ．６０１ ９２９ １ ２４ ２９ ９４ Ｏ．４１ ４３３７ ０．Ｓ９７６１ ４ １ ２Ｓ ３０ ９Ｓ ０．６３ ７４０３ Ｏ．５９７６１ ４ ０ ２５ ３１ １０２ ０．２ ７７９３８ ０．６８３７６３ １ ２６ ３２ １Ｏ７ ０．４８５ ７７５ ０．６６６６６７ １ ２７ ３３ １ １０ ０．４０８６２９ ０．６Ｓ８５８６ １ ２８ ３４ １ １ １ ０．３８８２０２ ０．６５８５８６ １ ２９ ３Ｓ １ １６ ０．７１２１９９ ０．６４３２６８ ０ ２９ 计算机系统应用 ３公平选课算法的特点及难点分析 从选课筛选表和选课概率折线图可以看出，本文 设计的基于变化概率的公平选课算法具有以下特点。 （１）该算法为每个选课学生计算其对应的选课概 率： （２）该算法对选课概率做出及时合理的调整，具 体表现为每个学生的选课概率受其前面学生选中状 态的影响：当前面学生为选中状态时，则该算法对后 面学生的选课概率进行下调；反之，当前面学生为落 选状态时，则该算法对后面学生的选课概率进行上 调； （３）学生的选课概率在选课概率均值０．６１上下 波动，随着选课人数的增加，选课概率波动幅度越来 越小，最后趋于一个数值。这一现象反映出学生选课 概率的均等性，学生选中与否与其选课先后次序无绝 对关系，从而将选课活动的公平性最大化。 （４）在该算法下，学生选中与否和其选课先后顺 序无关，极大的缓解了选课活动初期阶段大批量学生 并发访问系统带来的网络拥堵问题，优化了选课系 统。 该算法的难点在于初始选课概率的设置，因为该 数值用以往该课程的选课情况作为基准参考，如果上 届该课程的选课情况与本次该课程的选课情况基本吻 合或相近，则初始概率比较准确，如果上届该课程的 选课情况与本次该课程的选课情况相差很远，则初始 概率偏差较大，影响选课结果的准确性。对于这种情 况，建议的解决办法为，在选课的步骤５与步骤６之 间设置一个监视点，由教务工作人员对选课活动刚结 束时的筛选表进行监视，如果发现总选中人数Ｔ与预 置上限人数Ｍ相差较多时，则对初始选课概率做出调 整：Ｔ＞Ｍ，则下调初始概率；Ｔ＜Ｍ，则上调初始概率。 上调和下调的幅度由教务工作人员掌握。 ４应用案例 采用该算法的网络选课系统已经过两次选课过 程，实践证明，该算法的采用使得选课系统性能更加 优化，主要体现在以下几个方面： （１）可承担的并发访问人数增加 图２是使用Ｎａｇｉｏｓ监测系统对选课一周的请求 人数进行监测的结果，可以看出选课系统可同时负担 １ ５００人以上的并发访问，这个数目高于以前未采用 Ｅｘｐｅｒｉｅｎｃｅｓ Ｅｘｃｈａｎｇｅ经验交流１８３ 计算机系统应用 该算法时的选课系统。 图２ 一周请求人数图 （２）体现了选课活动的公平性原则 图３是对选课一周的网络流量进行监测的结果， 结果表明学生不是集中在选课初期，而是均匀的分布 在整个选课时期进行选课活动。由于该算法的采用， 使得每个学生具有几乎均等的选课概率，体现了选课 活动的公平性原则。 图３ 一周网络流量图 （３）极大地缓解系统压力、减轻负载 图４是对选课全过程的负载情况进行的监测结 果，对比未采用该算法时的负载情况（如图５所示）， 可以看出选课初期负载过重的情况已经没有，该算 法的采用极大地缓解了负载过重对系统造成的压 力。 图４采用算法后的负载情况图 １ ８４经验交流Ｅｘｐｅｒｉｅｎｃｅｓ Ｅｘｃｈａｎｇｅ ２０１ ０年第１ ９卷第４期 图５ 未采用算法时的负载情况图 ５结语 选课系统的关键是如何解决选课活动的公平性问 题及大批量学生并发访问系统带来的网络拥堵问题。 本文设计的基于变化概率的公平选课算法，使得每个 学生在选课活动当中拥有趋于均等的选课概率，从而 使学生选中与否和其选课顺序无关，既极大的缓解了 网络拥堵问题，又解决了选课活动的公平性问题。 参考 ＿Ｊ铁 １蔡志文，万力勇，杨俊锋．基于Ｉｎｔｅｍｅｔ的网上选课系统 的设计与实现．成都信息工程学院学报，２００４：２５—３１． ２李冰颖．学分制模式下网上选课系统的算法探析．江 西科学，２００４，２２（５）：３５８—３６０． ３王帮海．基于分散校区网上限时选课系统的研究与 实现．计算机应用研究，２００５：２３２—２３３． ４关慧．网上选课系统的设计与实现．沈阳化工学院学 报，２００４，１８（４）：２９５—２９８． ５唐勇．基于遗传算法的排课系统．计算机应用，２００２， ２２（１０）：９３—９４． ６李振坤，孙延海．基于知识库的学生选课系统的设计 与实践．计算机应用研究，２００５：７２１—７２２． ７车战斌，贾晓辉．学分制网络化选课系统及其应用． 郑州纺织工学院学报，１９９５：２１—２４． ８宣华，郭大勇，顾佩．学分制下学生选课管理的研究与 实践．清华大学教育研究，２００５，（１ １）：５２—５３． ９郭大勇，宣华，邓伟．清华大学实验教学管理模式改革 的新探索一实验课选课系统的设计与实现．高等理 科教育，２００５，（６）：２４—２５．
