基于LAMP的学分制选排课缴费系统的研究

李 硕，张新明

（1.南通大学 财务处，江苏南通226019；2.南通大学 人事处，江苏 南通226019）

一、前言

近年来随着教育部对于学分制改革推进的要求和高校规模继续不断扩大的现状，我国高校的教育教学管理体制正缓慢地由学年制向学分制的转变。因此，对能够适应学分制教学管理、学生按照各自经济情况和学习目标自主选择学习方向和进度，支付多样化，选排课算法优异的，符合财务管理规定的高效安全的学分制选排课缴费系统进行设计和研究是十分必要的。

在平台选择方面，系统的安全性和健壮性的要求极为重要，LAMP（Linux＋Apache＋MyS QL＋PHP）架构的数据吞吐性能，稳定性安全性较W indows系统更高，对高校这种规模的应用来讲，系统投入的成本也在承受范围之内，所以系统选择采用基于PHP的LAMP体系来研究和构建。

在排课方面，排课问题属于运筹学中的时间表（TTP）问题,高校排课问题很早就成为了众多软件开发者做关注的问题之一，研究人员对排课算法进行了大量的研究和改进，国内的研究主要选用了目前性能公认较为优良的遗传算法，所以本系统选用遗传算法来解决排课的课题。

在网络自主缴费方面，系统主要根据合作银行网银系统的数据接口定义，编制了和银行直接通信的前置系统，能够达到即时结算，准实时数据更新的水平。

二、系统主要问题的实施策略和设计

1.竞争性选课

目前高校在少量的选修课上试点应用了网络选课的方式，但即使在这种极少选课量的情况下，学生争夺教学资源却变成了拼抢硬件资源，为了保证公平性，本系统采用在学生选课初始化时，赋予每个学生同样的分值或者称为“虚拟货币”，出价可以反映学生选择此课程的意愿程度，竞价过程不公开，相当于投标书，然后根据课程开设的规模进行排名，同时可以开放进行多轮选课，解决竞价失败的问题。

2.排课算法

排课问题其实是一种调度问题（Scheduling Problem），是一个非线性的，需要满足各种软硬约束条件的，模糊多目标优化的，N-P完全的时空组合问题。其复杂性来源于要达到排课的目标其需要满足的软硬约束条件非常之多，为了编排出合理人性化的课程表，还必须考虑到课程重要程度、课程优先级、教师时间安排等，多校区教学还要避免出现密集跨校区问题。所以自动排课方案已经成为当今诸多研究者感兴趣的课题。主要排课算法包括遗传算法,禁忌搜索,蚁群算法，进化算法或者上述几种的混合。其中遗传算法正在越来越广泛地得到应用。这是由于这种方法是能够在元素级条件下找到最优解决方案的强大算法，所以以这种算法为基础的改进能够在可控的时间范围完成目标工作。

遗传算法的基本步骤：（1）对问题的可行进行编码，使之形成一条染色体；（2）对最大代数、种群规模、选择概率、交叉概率、变异概率等参数进行初始化；（3）根据设定的参数和编码方案生成初始种群P；（4）使用交差概率对种群进行交叉操作，产生新的染色体并构成子种群P；（5）使用变异概率对子种群进行变异操作，形成P；（6）使用选择概率对种群集合P∪P进行选择操作，生成P；（7）使用适应度函数对P进行评价，若种群P是最优解，则算法结束，若不是则选择适应度较强的染色体形成种群P转第4步。遗传算法流程如图1所示。

图1 遗传算法流程

在学分制管理体系下，公共必修课的教学安排仍然按照学年制的方式有计划地进行，方式仍然为按照行政班级，年级等进行排课，学生不选课。在其他课程包括专业必修课，专业选修课，公共选修课方面，将“班级”和“年级”在学分制体系下合并体现为“所学专业”，则算法的约束条件主要有：

（1）遗传算法在公共必修课的排课业务中的约束条件。本文采用的是对公共必修课按照班级和周课表的形式进行预排课。公共必修课排课的具体约束条件包括硬性条件和软性条件，其中：

1）硬性条件

a.同一个现实世界中的实体对象（学生，老师，教室）不能同时处于两件以上的事务中；

b.一个教室安排的人数不能超过教室能容纳的最大人数；

c.教师半天内不能跨校区授课；

d.教室（场地）设备配备。

2）软性条件

a.课程类型对时间的要求，繁重的课程应放在精神状态比较好的上午；

b.体育课、实习课应安排在下午；

c.课程在时间片上应合理均匀地分布；

d.为了避免教学资源浪费，尽量避免教室内空出大片座位；

e.教师在一天内最好不要跨校区教学；

f.个别教师具体要求。

这些条件也就是适应性函数构成的要素。

（2）遗传算法在公共必修课的排课业务中的算法设计

1）编码

遗传算法中第一个要考虑的问题是如何对染色体进行编码，一条染色体中应包含课程、教师、教室、班级、时间片、校区等相关的信息，采用二维表的形式，以时间片作为基准资源使用，假设每周可供开课的时间片数5×5=25，为每两小节为一个时间片，设时间片集合为：T= {11,12,13,14….53,54,55},11表示周一的第一二节课，以此类推，教室集合为：R={R1,R2,R3……Rn},时间片和教室的笛卡尔积，也就是可供使用的时空资源为 G=T×R= {(11,R1),(12,R1),….(55,Rn)},那么资源一共55×n个，排课所求解的目标就是为每一个教学任务找到合适的资源。

2）生成初始种群

首先要在初始种群生成前进行一些设置操作，比如体育课等要安排在下午等，之后可以开始进行初始种群，首先确定公共必修课教学任务的条数M,并将教学任务进行编号，然后用$L=ran d（0,M－1,1）；shuffle（$L）生成一个随机的0～M-1的不重复的随机数字序列F1，依次将数组F的元素代表的教学任务的信息提取出来生成初始种群。

因为教学任务序列F1经由系统随机产生，仅仅循环M次，导致教学任务所使用的时空资源差异不够，对于后面的再生、交叉、编译操作不利，所以再取随机数列F2,F3,可产生足够数量染色体的初始种群。

3）适应度函数设计

系统重点考虑课程类型对时间片的合理安排和避免教师跨校区教学，则单个基因适应度设计见公式（1）

变量a代表困难课程安排的优劣度评价，权重为0.3，变量b代表体育、实习类课程安排的优劣度评价，权重为0.1变量c代表教学任务在一周内分布的优劣度评价，权重为0.3，同样的一个教学任务，如果相隔太近甚至在同一天安排，则容量太大，如果相隔太长，则容易遗忘。变量d代表教室座位的利用率优劣度评价，权重为0.1，变量e代表教师在同一天内在/不在一个校区内教学，权重为0.3。这样，每条染色体的适应度的值为每个基因的适应度值之和。每个染色体有M个基因，设每个基因的适应度为f（k）（0≤k≤M－1）,则每条染色体的适应度见公式（2）

4）选择操作

选择操作的主要方法有:轮盘赌，局部选择等。轮盘赌选择操作完全依赖于系统生成的随机数，容易丢失极为优良的染色体，系统采用直接对每个染色体的适应度值进行排名，选择最大的20%直接复制到下一代，则可得到全局最优解。

5）交叉操作

交叉操作的主要方法有：单点交叉、均匀交叉等，但由于多校区的因素存在，使得产生硬性冲突的几率极高，所以系统将每对染色体中的部分进行交叉，这样产生冲突的几率大为降低。具体的方法是，设教学任务为TM,TM有三个维度，分别为（Teacher x,Class y,Course z）,而时空资源表有两个维度，分别为教室和时间。根据生成的初始种群，采取二维资源片编码十进制方式混合编码，假设一个基因是TM01000111，表示TM教学任务在01校区0001教室周一上午一二节课上课，依次生成开课的数据，形成一个染色体，交叉操作如图2所示。

图2 排课交叉操作示意

选取一对染色体，随机选择交叉点，将其中的教学任务相同的基因中时空资源部分进行交换。在交叉的过程中既交叉点作为参考点，既可以选择交叉点的前后的基因都进行交叉，也可以单独对交叉点前或者后的基因进行交叉，在对交叉点前后的基因进行交叉时，交叉分步进行，交叉时进行判断，如果有冲突，交叉取消，另随机取交叉点。

6）变异操作

变异操作采用相应的时空资源变异操作，根据变异概率选出一个染色体，随机选择变异点，在变异点前方或者后方选择基因中的时空资源片，变换资源，并检测变异冲突，发现有冲突变异取消，基本过程如图3所示

图3 排课交叉操作示意

7）冲突处理的步骤

在交叉变异的过程中，采用教学任务的时空资源进行交叉，大大减少了冲突发生的情况，但是毕竟冲突是无法避免的，所以应该在进行各种遗传操作之前进行冲突检测，检测到冲突则取消操作，基本方法是：

a.教师冲突的处理：假设总共有T位教师，对教师进行编码，编码范围是0～T-1，并依次读出每个教师可以执教的教学任务，再检测时间片表，如果存在重复的行，则表明冲突，取消遗传操作，没有则表明正常，可以遗传。

b.教室冲突的处理：假设某校区共有R个教室，编码范围是0～R-1,遗传检测同教师冲突

c.班级冲突的处理：假设共有C个班级，编码范围是0～C-1,遗传检测同教师冲突

d.校区冲突的处理：这里系统的交叉操作不会产生学生跨校区上课的情况，因为在生成初始种群时就已经排除了学生跨校区上课的情况，所以同班级要完成的教学任务都在同一个校区内进行，对班级来说，只有时空资源片可能会发生改变，所以系统只需要对教师遍历，如果搜索出多个校区编号的情况，则说明有冲突，则需要恢复到交叉前的状态，进行下一对染色体的交叉操作。

系统采用这样的遗传算法，能够保留遗传的每一代最好的个体，随着遗传代数的增高，不断丢弃最差的个体，在初始进化的数百代中，适应度呈波动变化，随着遗传代数的增大，适应度值平稳增高，逐渐趋近最优解。

（3）遗传算法在其他课程排课业务中的算法设计

其他课程系统采用先选课，后排课的模式进行，同公共必修课排课算法不同的是班级的概念消失了，取而代之的是选课结束以后产生临时的修习同一门课程的学生集，在数据库中必须建立临时教学集合表，代替班级表行使职责。在初始化种群的时候，读取待排课专业的“专业课程树”，一个专业一个专业的按照硬约束初始化种群，当然，占用的时空资源，包括教室占用表，时间片占用表是在专业之间来说公用的。初始化种群时选择专业的先后次序也采用随机抽取的方式，以求专业之间的公平性。

3.网银支付

学生在本系统选课完毕，确认缴费后，使用URL参数传递的方式将信息传至合作行网银系统：缴费成功后，网银系统向本系统发送的信息，本系统接受URL,并通过读取URL参数的方式获取参数信息，并进行相应的数据库操作。

4.安全

Linux为增加系统安全性提供了防火墙保护。系统使用系统内置的软件iptables定制适合自己的“数据包处理策略”。iptables的防火墙策略主要有三种，包过滤（Packet Filter），代理（Proxy），状态分析（Stateful Inspection）。本系统将这三种技术混合使用建立了较为稳固的L inux防火墙系统。

对于恶意攻击，系统选用了Linux平台下广泛使用的PSAD程序，可以和系统防火墙合作，可根据行为判断并防范几乎所有的针对Linux网络的恶意企图，能够深入到应用层对内容进行分析，并对用户进行警告。本系统采用此方法检测入侵和滥用效果良好。

三、系统测试

1.竞价方式选课测试

在现有的选课系统中，采用竞价选课方式的极少，系统对竞价方式选课进行了长时间大量数据的测试，发现还有如下问题需要改善。

（1）需要事先对教学安排有一定的规划和估算，在进行一定的选课导向教育的同时要科学设定授课规模，否则极容易导致选课失败，在邀请学生进行测试的过程中，选课链断裂出现的几率有时候高达13%。

（2）虚拟货币的设定一定要科学，数额最好要大一点，否则容易导致排名的末尾出现多个相同出价的学生，系统无法决策哪个竞价有效，需要人工干预。

2.排课测试

公共必修课排课适应度代数二维图如图4所示。

图4 公共必修课排课适应度示意

非公共必修课排课适应度代数二维图如图5所示。

可见公共必修课排课为了应对多校区的因素对传统遗传算法排课进行了改良，性能良好，非公共必修课因为采用先选课后排课的方式，按照数据初始化时设定的课程优先级，预先抢占一些时空资源片，再进行排课操作，性能较公共必修课排课略差。

图5 非公共必修课排课适应度示意

四、总结

系统将选课、排课、自助缴费这三个学生在校期间的主要活动结合起来协同运作系统，对排课、选课、自助缴费这三大系统进行了较为深入地整合，采用的对公共必修课预排课，其余课程开放学生选课的方式，应用改进遗传算法，较好地解决了完全学分制教学管理体制下的选排课问题，最后的排课结果也比较符合系统设计的目标。

但是，由于完全学分制管理体系下的选排课工作极其复杂，系统在先排后选算法方面仍然有很大的改进余地，应该在提高算法效率，稳定排课结果适应度值方面进一步开展研究。

[1]黄干平,刘娟.解“时间表问题”的启发式算法[J].武汉大学学报（自然科学版）,1996,42(1):71-74.

[2]Nakayama.M,Hoshito.J.Development of A Support System for University Course Selection Using Semantic Web Technology[R].5th InternationalConference on W eb Information Systemsand Technologies,2009:389-392.

[3]Chinnasri.W,Sureerattanan.N.Comparison of performance between different selection strategies on genetic algorithm w ith course timetabling problem[R].Advanced M anagement Science(ICAMS),2010 IEEE International Conference on.2010(2):105.

[4]李敏强,寇纪淞,林丹等.遗传算法的基本理论与应用[M].北京：科学出版社,2002:316-317.

[5]M en-Shen.Tsai,Fu-Yuan.Hsu.Comparison of genetic algorithm reproduction methods for distribution system loss m inim ization [R].International Conference on Machine Learning and Cybernetics.2004(1-7):4113-4118.

[6]李建喜,舒仲远,陈文生.多校区排课遗传算法设计[J].南昌航空工业学院学报,2006,20(2):61-64.