基于改进遗传算法的高中走班制排课算法

王卫红，李文琼

(浙江工业大学 计算机科学与技术学院，浙江 杭州 310023)



基于改进遗传算法的高中走班制排课算法

王卫红，李文琼

(浙江工业大学 计算机科学与技术学院，浙江 杭州 310023)

随着高考制度的深化改革，“走班制”教学模式逐渐替代传统的高中教学方式.这种教学模式的启用，导致影响排课效率的因素和约束条件增多，并且会出现教学资源匮乏的情况.传统的人工编排课表的方式需要花费工作人员大量的时间，且排出的课表不宜调整，已经无法满足“走班制”教学体制的排课需求.根据对现有排课算法存在的问题的分析，结合“走班制”高中教学的特殊性，建立了相应的数学模型、分析了“走班制”教学模式下排课算法需要设计的约束条件.基于“走班制”教学模式下学生分层选课的特性，通过将改进的遗传算法分别运用在学生分组和排课两个阶段对此类排课问题进行求解.实验结果证明：该改进算法可以有效的解决采用“走班制”教学模式的高中学校排课问题.

“走班制”教学；改进遗传算法；排课算法

随着高考制度的深化改革，“走班制”教学模式在各地区逐渐普及.浙江省的部分高中学校采用的“走班制”教学模式，主要指的是分层次教学，即“行政班”学生根据自己的特点和需求选择不同层次的教学班进行学习的模式，在恰当的分层次教学策略和新型的课堂教学结构的双重调控下，实现对教学目标及其过程的优化[1-3].“走班制”不再以行政班为单位，是一种不固定班级、不固定教室的流动性教学模式.在这种教学制度下，排课涉及的信息变得更加繁琐、复杂，导致排课的解集不断被诱发，手动排课需要花费工作人员大量的时间，排出的课表不宜调整，已经无法满足教学要求.在这种新型教育模式下的高中学校迫切的需要一种智能、高效的自动排课方式来快速地得到满足各种排课约束条件的最优可行解.近几年，国内外学者将不同的算法应用在解决排课问题上，如模拟退火算法[4-5]，遗传算法[6-10]，最佳个体置换策略[11-12]，整数规划[13]等，但是这些方法一方面都存在一些缺点，例如：在排课问题的约束条件上考虑的不够充分，并且，针对采用“走班制”教学模式的学校排课问题设计的约束条件还未被考虑；另一方面，这些算法的提出几乎都是用来解决传统教育模式的方案，即同一行政班的课程在该学期固定在同一教室内的非流动性教育模式.因此，传统的排课问题没有考虑流动性的班级的概念.

20世纪70年代，排课问题就一直被当做NP完全问题[14]来解决.NP问题是一个涉及多因素的优化组合问题，任意元素的改变都有可能引起“组合爆炸”，作为一种借鉴了自然选择、变异机制的随机搜索算法，遗传算法利用群体搜索技术，可以高效的解决组合优化问题[15-17].鉴于目前的研究状况及“走班制”教学的特殊性，笔者提出的算法基于对遗传算法的改进，对以“走班制”教学模式为特点的排课算法进行了研究，设计了相应的数学模型，以及符合“走班制”特色要求的选择算子、交叉算子、变异算子和适应度函数等.致力于解决“走班制”教育模式特色下的排课问题，使高校的排课体制趋于智能化，从而有效的提高学生学习效率，降低教务管理工作的复杂度，提高高校教育教学计划完成力度.

1 “走班制”教学模式下的排课问题

1.1 排课问题描述

要解决的难点是在“走班制”的分层教学制度下，对于分层教学的课程，学生根据个人情况对不同层级的课程进行选课.因此，基于“走班制”教学模式下的排课问题无法像传统行政班级一样依据固定的学生成员和教室.笔者提出的解决方案是将学生进行分组，组内的每门课程的学生按层级和相关参数划分多个该课程教学班，在该分组的基础上为每组制定不同的课表.因此，“走班制”教学模式下的排课问题，即如何对时间、教师、教室、课程以及组内和组间的流动教学班等5 个因素进行最优化组合规划的问题，即保证课程安排中尽量少的冲突出现，并解决学校严重的资源冲突问题.

1.2 数学建模

根据上述问题描述，排课问题中涉及到教学班、课程、教师、教室和时间等相互制约的因素，用到的集合：

学生集：S={s1,s2,s3,…，sm}，课程集：C={c1,c2,c3,…，cn}，任课教师集：T={t1,t2,t3,…，tp}，时间段集：P={p1,p2,p3,…，pq}，教室集：R={r1,r2,r3,…，rt}，时间段Pi={(px,py)}，一周可供排课天数daysPerWeek，一天可供排课课时数periodPerDay，x属于daysPerWeek，y属于periodPerDay，i=(x-1)periodPerDay+y.

“走班制”模式的排课过程没有“行政班”的概念，基于学生选课情况对学生按选课情况进行分组形成不同的教学班，其中教学班、教师和课程作为一个授课安排，教室、时间段作为一个教室时间安排，因此排课问题可以演化成为任意授课安排寻找满足约束条件的教室-时间对问题.

排课问题就是在保证合理的分配教学资源的情况下，将教师、学生和课程在不同的时间段下按照特定的约束规则进行优化组合.因此在解决排课问题时，需要为算法设计一些约束规则，确保课表达到有效性的同时具有实用性和合理性.

硬约束条件为在解决排课问题时必须遵守的原则，排课算法只有在符合硬约束条件的要求下得到的解集才能避免课表在时间、空间上发生的冲突.笔者设计的基于“走班制”条件下的排课规则需要考虑到分组和排课两个阶段.具体如下：

1) 由于一个学生对于不同的课程可以选择不同的层级，因此，设计同一个教学时间段，在同一组内的学生不能上一门以上的课程.

2) 同一个时间段的各个课程组安排的课程不能相同.

3) 同一个教学时间段，一个教师不能上一门以上的课程.

4) 同一个教学时间段，一个学生不能上一门以上的课程.

5) 同一个教学时间段，一个学生不能分配在一个以上的组内.

6) 同一个教学时间段，一个教室不能上一门以上的课程.

7) 教室的座位量不能少于被安排的教学班的人数.

软约束条件为在实际的排课过程中，根据不同的排课对象的特殊性制定的优化条件，在解决排课问题时是否遵守了软约束条件将会给排课结果带来很大的影响，排课算法多大程度符合软约束规则，便会得到相应程度优质的解.具体如下：

1) 一门课程的多次上课时间段的分配尽量均匀.

2) 一个学生的所有课程分布不应过度集中，避免某段时间过于空闲.

3) 上课教室的座位数和上课的教学班的人数相差适中，保证教室的利用率.

4) 同一个教师的相近时间段的教学尽量安排在相对固定的教室或相近教室.

5) 艺体课程应避免安排在早上和下午的一、二节次.

6) 逻辑性强的课程尽量安排在教学效果好的上课节次.

7) 公共课及学时多的课应优先安排.

8) 每个教学班的人数不宜过少也不宜过多.

9) 对于上课时间确定的教师，首先确保满足其上课时间.

10) 对学生分组的组数要尽量小于需要进行教学分层的课程数量.

将软、硬约束写入课程的基因中，减少遗传操作中无效课表产生的比例，提高有效课表的合理性.

2 算法设计

2.1 基因编码

自然界里的物种遗传由染色体决定，不同的染色体决定不同物种之间存在的差异，而每种物种特有的遗传信息存放在染色体内，遗传信息按一定的模式排列，即进行了遗传编码.以实施了“走班制”教学模式的某高中学校为例，设计了一组适合该校特定情况的基因编码方式.排课得到的课表作为一条染色体，课表中的信息(排课记录)作为染色体上不同的基因.以总教学时间段数为行数，以已经被分配教师和课程的教学班数(各组教学班总数)为列数，组成二维表，在表内非空单元放入教室编号.涉及的排课信息采用二进制编码方式表示，染色体编码方案如图1所示.

图1 染色体编码方案Fig.1 Chromosome coding scheme

2.2 排课问题约束满足模型

针对这些硬约束条件建立一些数学约束模型，从而保证进行智能课表编排时教学资源、对象不产生冲突.

1) 在排课结果集中排课信息不能重复，由时间段和教室组成的教学单位组成的集合，如果时间和教室都不同，才保证由它们组成的教学单位不同，数学表示如下：

设pi∈P，pj∈P，rλ∈R，rγ∈R，vα∈V，vβ∈V

则vα=〈pi，rλ〉，vβ=〈pj，rγ〉

规定：当pi≠pj，且rλ≠rγ时，必有vα≠vβ.

2) “走班制”模式下教学班的课程和学生固定，因此将教学班gc和教师t的组合作为一个待排课任务集，所以由教学班和教师组成的排课对象列表TT中，排课任务集不能重复.笔者设计的解决方案中，组内各课程保证每个层级教学班有唯一与之对应的教师，因此，组内教学班和教师都不同，组成的排课任务集才不同，数学表示如下：

设gci∈GC，gcj∈GC，gx∈G，gy∈G，ttλ∈TT，ttγ∈TT

则ttλ=〈gci，gx〉，ttγ=〈gcj，gy〉

规定：当gci≠gcj，且gx≠gy时，满足ttλ≠ttγ.

3) 一个教学班在同一时间段不能分配在一个以上的教室，数学表示如下：

设{ri，rj}∈R，{pλ，pβ}∈P且ttο=〈gcК，gx〉，ttυ=〈gcη，gy〉

当rλ≠rγ，gcК≠gcη，pi≠pj时，满足ttο≠ttυ.

4) 层级课程的授课教师是固定的，组内排课是同一时间只针对一门课安排教学单元，要保证一个授课教师在同一教学单元只对一个教学班进行授课.数学表示如下：

设{gx，gy}∈G，{gcК，gcη}∈GC且vα=〈pi，rλ〉，vβ=〈pj，rγ〉，

ttο=〈gcК，gx〉，ttυ=〈gcη，gy〉

当gcК≠gcη，pi=pj，gx≠gy时，ttο≠ttυ.

5) 每门课程在某层级安排的教师是固定的人员，为了避免资源冲突，要求在同一时间段内，教学组间的课程类别各不相同.数学表示如下：

设{gtК，gtρ}∈GT，lυ=〈gtК，cλ，pi〉，lρ=〈gtη，cγ，pj〉

如果lυ=lρ，则要求gtК=gtη，cλ=cγ，pi=pj.

2.3 设计适应度函数

基于上述建立的数学模型，提出了将“走班制”下的排课问题拆分为分组、排课两部分来解决排课问题的算法设计，该算法以基本遗传算法为基础，并将其应用在分组和排课两个阶段，重点描述排课阶段的设计.该排课算法设计的适应度直接影响该算法是否能解决排课问题中的资源冲突和找到组合规划最优解.排课问题作为多组合目标规划问题，受到多个约束条件的影响，如：各个课程在教学时间段分配的均匀度、学生课程安排均匀度、教室资源利用率以及课程时间段安排优度等，将这些约束条件的综合评价作为笔者算法的适应度函数，表示为

(1)

式中：crashg为该种群个体的冲突次数；rewardg为该种群个体的奖励指数；uλi为在第λ教学组中第i个课程的教学时间段分配均匀度；nteam为分组组数；ngcourseλ为第λ教学组内分层后课程总数.统计该课程在其组内的教学时间段分配记录tcourseλi={tcourse1, tcourse2, tcourse3,…, tcoursentime}，ntime表示该课程被分配的教学时间段总数.课程在教学时间段分配的均匀度为

(2)

式中dαβ为课程的第α个教学时间段到第β个教学时间段的距离.具体如下：

1) 用vλj表示在第λ教学组中第j个学生的课程安排均匀度，ngstuλ表示第λ教学组内学生总数.“走班制”教学下采用的是流动式教学班，班级内的学生不固定，因此上课时间段均匀度细化到每个学生，统计学生一周内每天上课的次数，计算方差，其值越小，安排效果越好.学生上课时间段的分配均匀度为

(3)

2) 用wλ表示课程时间段安排优度，不同课程之间或者不同层级的课程之间的逻辑强度、重要程度都不同，不同教学时间段的教学效果不同，课程节次的安排优度为

(4)

式中：courseweightυω为第ν个课程在第ω个教学时间段的教学效果权重；ngcourse为该教学组课程总数；ppd为一天内教学时间段个数.

3) 用rλ表示教室资源利用率，在一次教学安排中，一间教室内分配的教学班学生数过少会浪费教室资源，与该教室容量过度相近则会影响教学质量，将教学班学生个数与教室容量的比值作为资源利用率的衡量标准，并设置当其值为0.8时，资源利用率为最佳[9].组内资源利用率为

(5)

式中：nclass为该教学组内教学班数量；nroom为该教学组内教室数量；nstuclassi为第i个教学班学生个数；nsturoomj为第j个教室容量.

2.4 初始种群的产生

以教学组为单位，首先同时为每个教学组内已分配课程和教师的教学班分配教学时间段，以教学时间段为行，以教学班为列生成一个二维表.采用随机生成的方式，为每个教学班在各个时间段上分配教室，若教室、教师和时间资源不产生冲突，则将教室编号填入二维表非空单元，一个完整的二维表则表示一个排课方案，作为排课算法初始种群中的一条染色体.产生n条染色体则形成一个初始群.

2.5 选择算子

排课算法中，选择操作是基于适应度进行优胜略汰的过程.算法根据种群中每个个体的适应度大小，保留第g代中优越的候选解进入第g+1代，放弃其他一些非优的候选解.其中个体适应度越大，个体基因的优值越高，被遗传到下一代种群的概率就越高.为了避免在此过程中出现的种群早熟早收敛现象，算法在选择操作时引入了竞争机制的同时采用了是轮盘赌算法.具体操作：找到g代种群中最大奖励值和最大适应度值，调用轮盘赌算法方法，首先以轮盘安置方式按种群适应度降序排列，设置随机值r，采用二分查找的方式查找r在轮盘中对应位置设为id，该位置为要选择的染色体位置.

2.6 交叉算子

在交叉操作过程中，通过将第g代种群中所有个体随机的进行两两配对，产生更高效、合理的新个体解.为解决传统遗传算法在交叉操作时用来作为搜索解的空间相对较小的问题，采用计算编码间的海明距离的方式，使得每两对个体都有部分染色体相互交换，产生新个体，保持群体的多样性，从而提高了种群变化的效率，避免早熟现象.具体操作：针对每个个体进行交叉操作预测，产生随机值rd，根据选择操作中计算的种群最大适应度、参数、该染色体的适应度计算交叉概率，若rd小于交叉概率则进行交叉操作，并通过轮盘赌法找到与当前染色体进行交叉操作的位置，实现交叉操作.需要说明的是，这里的交叉操作为两个个体中同一个课程组的课表进行交叉操作，取当前个体课表优先安排，另一个课表先安排无冲突的课程，有冲突的课程随机安排在无课的时间段.

2.7 变异算子

变异操作作为算法产生新个体的辅助方法，将个体染色体的部分基因编码随机交换，达到产生新个体的目的.为了扩大了遗传算法中搜索区域的范围，同时提高了种群变化的效率以及种群最优解搜索能力，变异概率的设置与交叉概率类似，采用自适应方式.种群中染色体的基因编码(课程信息)以自适应的概率变异，若变异则随机一个课程时间段安排与之交换.

3 实例验证

实验数据来自浙江省宁波市鄞州中学实行了“走班制”教学模式的高中学校2015—2016(2)学期高二年级的实际教学活动数据.实验数据包括教师、教室、学生、分层课程、一周时间段(该校每周上课5 天，一天9 节课，即一天9 个时间段，一周为45 个时间段)、班级最大人数、最少人数以及软硬约束条件等信息，其中每组最少100 人，最多120 人，教学班最少20 人，最多40 人.实验环境：Visual Studio 2015，C++，SQLServer.

根据笔者对改进遗传算法设计的描述，排课过程中控制参数的设计切实影响算法的效率.排课算法的控制参数描述如下：

1) 种群规模，符号表示Population，种群规模对算法效率有着一定的影响，规模较小会导致算法求解目标值波动较大，无法反映出对各个目标的优化；规模过大不仅会延长目标收敛时间而且导致内存消耗过盛.设置种群规模为300.

2) 算法遗传代数，n=3 000，N值影响算法求解目标的收敛性和最优解求解范围，N值过大导致各目标不收敛；较小时导致最优解极大可能不是最优解.

3) 选择率，设计个体的选择率是由该个体在当代种群中的适应度值与所有个体适应度总和的比例值，公式为

(6)

式中：fitg[i]为个体i在第g代种群中的适应度大小；fit.back()为存放种群个体的适应度总和.

4) 交叉概率，交叉概率的大小直接影响算法最优解的收敛程度，概率设置过大导致算法求解过程中解的波动范围过大，设置的太小导致算法收敛缓慢，交叉概率pc初始值设置为0.02，执行交叉操作时自适应交叉概率为

(7)

式中：fitmax为最大适应度值；fitg[i]为个体当代种群中的适应度大小.

5) 变异概率，变异概率设置太大导致解的范围波动过大，设置过小引发全局最优解收敛过缓慢，一般其值取0.001～0.2之间，变异概率设置初始值pm为0.01.

实验的分组结果：由于科目繁多，仅以语文、物理、化学、地理和历史等5 门课程作为代表，展示这5门课程的分组结果，如表1所示.

表1 分组结果

Table 1 Grouping result

组号教学班语文物理化学地理历史0语文1物理A1物理A2化学A1化学A2地理A1地理A2历史A1历史A2语文2物理B1化学B1化学B2地理B1历史B1语文3物理C1化学C1地理C1历史C11语文1物理A1物理A2化学A1地理A1地理A2历史A1语文2物理B1化学B1化学B2地理B1历史B1历史B2语文32语文1物理A1化学A1地理A1地理A2历史A1历史A2语文2物理B1物理B2化学B1化学B2地理B1历史B1语文3

向读者展示第一组、第二组的排课结果，分别如表2，3所示.

表2 第一组排课结果

Table 2 The timetable of the first group

组号周一周二周三周四周五1历史A1(教学楼201)历史A2(教学楼210)历史B1(教学楼203)历史C1(教学楼106)数学1(教学楼301)数学2(教学楼302)数学3(教学楼203)数学1(教学楼201)数学2(教学楼301)数学3(教学楼306)信息1(科艺楼203)信息2(科艺楼205)信息3(科艺楼211)化学A1(教学楼403)化学A2(教学楼401)化学B1(教学楼402)化学B2(教学楼405)化学C1(教学楼410)2语文1(教学楼101)语文2(教学楼112)语文3(教学楼201)通技1(科艺楼301)通技2(科艺楼303)通技3(科艺楼306)艺术1(科艺楼401)艺术2(科艺楼410)艺术3(科艺楼403)英语1(教学楼101)英语2(教学楼102)英语3(教学楼110)物理A1(教学楼304)物理A2(教学楼410)物理B1(教学楼405)物理C1(教学楼302)3英语1(教学楼102)英语2(教学楼108)英语3(教学楼203)政治A1(教学楼102)政治A2(教学楼104)政治B1(教学楼305)政治C1(教学楼311)英语1(教学楼103)英语2(教学楼101)英语3(教学楼104)物理A1(实验楼201)物理A2(实验楼203)物理B1(实验楼210)物理C1(实验楼207)生物A1(教学楼307)生物A2(教学楼206)生物B1(教学楼209)4通技1(科艺楼303)通技2(科艺楼307)通技3(科艺楼305)体育1(体育小管)体育2(体操管)体育3(足球场)政治A1(教学楼201)政治A2(教学楼310)政治B1(教学楼207)政治C1(教学楼203)化学A1(教学楼403)化学A2(教学楼401)化学B1(实验楼102)化学B2(实验楼105)化学C1(实验楼110)政治A1(教学楼101)政治A2(教学楼110)政治B1(教学楼301)政治C1(教学楼303)5体育1(体育小馆)体育2(体操管)体育3(足球场)历史A1(教学楼210)历史A2(教学楼201)历史B1(教学楼104)历史C1(教学楼106)地理A1(教学楼106)地理A2(教学楼204)地理B1(教学楼202)地理C1(教学楼311)语文1(教学楼101)语文2(教学楼110)语文3(教学楼103)6生物A1(实验楼301)生物A2(实验楼310)生物B1(实验楼309)语文1(教学楼101)语文2(教学楼110)语文3(教学楼203)化学A1(教学楼402)化学A2(教学楼405)化学B1(教学楼403)化学B2(教学楼401)化学C1(教学楼410)数学1(教学楼201)数学2(教学楼302)数学3(教学楼306)7数学1(教学楼201)数学2(教学楼302)数学3(教学楼203)信息1(科艺楼203)信息2(科艺楼205)信息3(科艺楼210)历史A1(教室楼201)历史A2(教学楼205)历史B1(教学楼105)历史C1(教学楼107)政治A1(教学楼103)政治A2(教学楼111)政治B1(教学楼301)政治C1(教学楼310)数学1(教学楼302)数学2(教学楼310)数学3(教学楼203)8物理A1(教学楼304)物理A2(教学楼410)物理B1(教学楼405)物理C1(教学楼302)地理A1(教学楼303)地理A2(教学楼106)地理B1(教学楼311)地理C1(教学楼202)语文1(教学楼201)语文2(教学楼210)语文3(教学楼303)艺术1(科艺楼401)艺术2(科艺楼405)艺术3(科艺楼410)地理A1(教学楼211)地理A2(教学楼304)地理B1(教学楼308)地理C1(教学楼209)9地理A1(教学楼202)地理A2(教学楼303)地理B1(教学楼106)地理C1(教学楼108)化学A1(实验楼111)化学A2(实验楼102)化学B1(教学楼401)化学B2(教学楼403)化学C1(教学楼407)物理A1(教学楼303)物理A2(教学楼304)物理B1(实验楼203)物理C1(实验楼207)生物A1(教学楼301)生物A2(教学楼310)生物B1(教学楼209)英语1(教学楼102)英语2(教学楼107)英语3(教学楼210)

表3 第二组排课结果

Table 3 The timetable of the second group

组号周一周二周三周四周五1物理A1(教学楼204)物理A2(教学楼202)物理B1(教学楼105)物理A1(教学楼201)物理A2(教学楼210)物理B1(教学楼101)历史A1(教学楼201)历史B1(教学楼203)历史C1(教学楼106)地理A1(教学楼307)地理A2(教学楼301)地理B1(教学楼303)2数学1(教学楼201)数学2(教学楼302)数学3(教学楼306)语文1(教学楼101)语文2(教学楼112)语文3(教学楼201)数学1(教学楼306)数学2(教学楼302)数学3(教学楼210)地理A1(教学楼206)地理A2(教学楼210)地理B1(教学楼302)历史A1(教学楼210)历史B1(教学楼203)历史C1(教学楼106)3生物A1(教学楼205)生物A2(教学楼303)生物B1(教学楼308)体育1(体育小馆)体育2(体操管)体育3(足球场)物理A1(教学楼304)物理A2(教学楼410)物理B1(教学楼303)信息1(科艺楼203)信息2(科艺楼207)信息3(科艺楼211)数学1(教学楼201)数学2(教学楼301)数学3(教学楼306)4地理A1(教学楼202)地理A2(教学楼310)地理B1(教学楼304)政治A1(教学楼101)政治B1(教学楼305)政治B2(教学楼303)化学A1(教学楼403)化学B1(教学楼402)化学B2(教学楼405)政治A1(教学楼103)政治B1(教学楼301)政治B2(教学楼310)体育1(体育小馆)体育2(体操管)体育3(足球场)5语文1(教学楼110)语文2(教学楼208)语文3(教学楼106)化学A1(实验楼110)化学B1(实验楼102)化学B2(实验楼105)英语1(教学楼102)英语2(教学楼110)英语3(教学楼205)艺术1(科艺楼401)艺术2(科艺楼405)艺术3(科艺楼403)6艺术1(科艺楼405)艺术2(科艺楼403)艺术3(科艺楼410)英语1(教学楼102)英语2(教学楼107)英语3(教学楼203)语文1(教学楼106)语文2(教学楼110)语文3(教学楼103)英语1(教学楼203)英语2(教学楼102)英语3(教学楼110)政治A1(教学楼106)政治B1(教学楼311)政治B2(教学楼303)7化学A1(教学楼402)化学B1(实验楼102)化学B2(实验楼110)历史A1(教学楼101)历史B1(教学楼106)历史C1(教学楼207)地理A1(教学楼206)地理A2(教学楼108)地理B1(教学楼202)化学A1(教学楼410)化学B1(教学楼401)化学B2(教学楼402)生物A1(实验楼301)生物A2(实验楼302)生物B1(实验楼310)8英语1(教学楼203)英语2(教学楼110)英语3(教学楼104)通技1(科艺楼301)通技2(科艺楼310)通技3(科艺楼304)通技1(科艺楼305)通技2(科艺楼307)通技3(科艺楼306)数学1(教学楼211)数学2(教学楼310)数学3(教学楼203)物理A1(实验楼201)物理A2(实验楼203)物理B1(实验楼210)9政治A1(教学楼103)政治B1(教学楼301)政治B2(教学楼310)数学1(教学楼301)数学2(教学楼304)数学3(教学楼206)生物A1(教学楼301)生物A2(教学楼310)生物B1(教学楼209)语文1(教学楼201)语文2(教学楼210)语文3(教学楼103)信息1(科艺楼201)信息2(科艺楼207)信息3(科艺楼211)

实验结果证明：通过笔者设计的排课算法，可以为实行“走班制”教学模式下的高中学校制定合理、高效的课表.

4 结 论

目前国内外学者对传统排课设计了很多算法，而针对“走班制”教学模式设计的排课算法却没有，笔者对传统遗传算法进行研究后，采取了一定的改进措施，研究、设计适应以“走班制”教学为特色的排

课算法.虽然笔者设计的算法可以使教学管理者从繁琐、复杂的教务劳动中脱离出来，能够尽可能的提高教学效率，并且将学校教学资源尽可能的不被浪费，但是算法依然存在不足之处，希望在以后的研究中有所改进.

[1] 黄文涛.高中选课走班制教学的实践与思考[J].教育科学论坛,2014(4):22-23.

[2] 王开香.探析分层走班制的应用态、实然态和必然态[J].教育探索,2012(1):72-74.

[3] 邹冬梅,高轩.基于培智学校学生特点的“走班制”教学路径[J].现代特殊教育,2013(11):42-44.

[4] 吴红艳.浅谈遗传退火算法在高校排课问题中的应用[J].科技展望,2015(2):256-258.

[5] LIU Yongkai，ZHANG Defu，LEUNG S C H. A simulated annealing algorithm with a new neighborhood structure for the timetabling problem[C]//Proceedings of the 1st ACM/SIGEVO Summit on Genetic and Evolutionary Compu-tation. London: William Langdon,2009:381-386.

[6] KOHSHORI M S，LIRI M S. Multi population hybrid genetic algorithms for university course timetabling[J]. Interna-tional journal for advances in computer science，2012，3(1)：12-22.

[7] 孙彤,郭倩倩.基于新型免疫遗传算法的高校排课仿真研究[J].计算机仿真,2012,29(2):386-391.

[8] 马玉芳,张海娜,邵杰.遗传算法在高校排课系统中研究与实现[J].计算机系统应用,2014(5):112-115.

[9] 张燕,唐启涛,王聪,等.基于遗传算法的高校排课算法研究[J].科技展望,2015(19):272-273.

[10] PILLAY N, BANZHAF W. An informed genetic algorithm for the examination timetabling problem[J]. Applied soft com-putting,2010,10(2):457-467.

[11] 朱颢东,李红婵.采用十进制最佳个体置换遗传算法求解高校排课问题[J].计算机工程与科学,2013,3(6):186-190.

[12] 李红婵,朱颢东.基于最佳置换策略的高校排课问题求解[J].计算机工程,2011,37(19):186-189.

[13] 谢宗霖,刘亚军,霍伟敬,等.基于整数规划的排课优化问题[J].计算机与现代化,2015(7):15-19.

[14] 杜立智,陈和平,符海东.NP完全问题研究及前景剖析[J].武汉工程大学学报,2015,37(10):73-77.

[15] 胡恒,鲁建夏,李英德.基于多群体并行遗传算法的混流混合车间模糊调度研究[J].浙江工业大学学报,2012,40(5):554-558.

[16] 兰月政,鲁建夏,孔令革.基于遗传算法的混流生产线产品分组指派问题研究[J].浙江工业大学学报,2011,39(3):312-316.

[17] 陈勇,胡婷婷,鲁建夏.基于遗传算法改进的动态车间调度[J].浙江工业大学学报,2012,40(5):537-543.

(责任编辑：陈石平)

Timetabling algorithm of high school optional class system based on improved genetic algorithm

WANG Weihong, LI Wengqiong

(College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310023, China)

With the deepening reform of the college entrance examination system, the "course selection system" education mode gradually replaces the traditional teaching pattern in high schools. This teaching pattern leads to the increased factors and constraints that influence the effectiveness of curriculum arrangement, as well as the shortage of teaching resources. Traditional manual scheduling curriculum will take a lot of staff time and the schedule is hard to be adjusted. It can not meet the demand of the current teaching pattern. According to the analysis about the weakness of existing timetabling problem(TP), combining with the specificity of class-selection-system teaching pattern, we establish the corresponding mathematical model and analyze the constraint condition needed to be designed for TP. Based on the characteristics of course selected hierarchically by students, we solve this type of TP through applying improved genetic algorithm on students grouping and courses arranging. The experiment results show that the improved algorithm can effectively solve the TP of class-selection-system.

class-selection-system; improve genetic algorithm; curriculum arrangement algorithm

2016-02-28

国家自然科学专项基金资助项目(61340058)；浙江省自然科学基金重点资助项目(LZ14F020001)

王卫红(1969—)，男，浙江临海人，教授，研究方向为图像图形处理、遥感与地理信息系统以及信息安全等方面，E-mail：wwh@zjut.edu.cn.

TP311

A

1006-4303(2016)06-0601-07