基于离散粒子群算法的排课研究

摘要 排课问题属于背包问题中具有重要实用价值的一类优化组合难题, 描写了如何利用粒子群算法解决排课中的多种冲突。但由于粒子群算法有收敛速度慢且易收敛于局部最优的缺点, 针对排课问题中最优解的分布特点, 对粒子群算法进行了改进。本文提出了一种改进的离散粒子群算法。采用基于矩阵的编码方式,对粒子的位置和速度更新方法进行重新定义。利用C#语言实现了一个基于离散粒子群算法的排课系统。并以不同学院一个学期的课程表为依据对系统进行了评估,结果验证了粒子群算法在排课系统中应用的可行性,在一定程度上解决了高校复杂的排课难题,实现了智能化、人性化的排课过程。

关键词: 排课 粒子群优化 离散粒子群优化

1. 引言

排课问题是一个涉及多种因素的动态组合规划问题,它要保证各种教学资源不产生冲突,并且要满足教学资源各方面的约束条件。教学资源主要包括课程、教师、教室、时间。排课问题的求解过程就是对任何课程、班级、教师、教室安排出一个相同的空闲时间,在安排时排课不能发生冲突,同时遵守一些约束条件。所谓冲突就是将上不同课程的两个或多个班排成了同一时间或同一教室,或在同一时间为一个教师安排了多门课程等等。一般的排课流程是:首先,各院系将各自的新学期课程表、任课教师教师情况、班级课程安排情况的数据录入排课系统,然后,排课系统根据本学校的教室情况以及各种约束条件进行排课。排课问题被证明是NP完全问题[1]。

粒子群优化算法(Particle Swarm Optimization,PSO)作为进化计算的一个分支，是由Eberhart和Kennedy于1995年提出的一种全局搜索算法，同时它也是一种模拟自然界的生物活动以及群体智能的随机搜索算法。因此粒子群算法一方面吸取了人工生命，鸟类觅食，鱼群学习和群理论的思想，另一方面又具有进化算法的特点，和遗传算法，进化策略，进化规划等算法有相似的搜索和优化能力。虽然POS是一个非常适合于连续领域问题优化的算法，并且已经在很多连续空间领域获得了相当的成功的应用，但是很多现实问题都是定义在离散空间中的。为了将POS应用到这些离散组合问题，本文结合排课问题的特点，对传统的PSO算法进行了改进，构造了一种基于矩阵编码的离散粒子群算法，实验表明这种算法能有效解决高校的排课问题。

2.排课问题的描述

排课问题[6]就是将课程、班级、教师安排在一周内相应的时间和教室内且不发生冲突。因此，给出如下描述：学校有R 间教室，C 个班级，L门课程，P 位教师，T 个时间段；教室集合R={Ri，i=1,2,3…Nr}；教室分别可容纳的人数集合X={Xi，i=1,2,3…Xp};班级集合C={Ci，i=1,2,3…Nc}；每个班级学生人数集合K={Ki，i=1,2,3…Nk}；课程集合L={Li，i=1,2,3…Nl}；每门课程上课班级数集合Y={Yi，i=1,2,3…Ny}；教师集合P={Pi,i=1,2,3…Np}；每位教师负责上课门数Z ={Zi，i=1,2,3…Nz}；时间段集合T={Ti，i=1,2,3…Nt}。

结合学校的实际情况，对于一个可行的课程表必须满足以下约束条件：

（1）同一时间段同一个班级只能上一门课程；