《基于离散粒子群算法的机房排课问题研究》由会员分享，可在线阅读，更多相关《基于离散粒子群算法的机房排课问题研究（10页珍藏版）》请在金锄头文库上搜索。
1、基于离散粒子群算法的机房排课问题研究摘要：粒子群优化算法以其实现容易、精度高、收敛快等优点引起了学术界的重视，并且在解决实际问题中展示了其优越性。本文通过改造离散粒子群算法使之适合机房排课问题的求解。从而达到为机房排课问题的解决提供一种新的思路。关键词：粒子群优化算法；离散粒子群算法；机房排课lab course problems study based on discrete particle swarmwang chao(chongqing business vocational college, chongqing 400036,china)abstract: the particle
2、swarm optimization algorithm for its easy implementation, high accuracy, fast convergence advantages attracted the attention of academia, and demonstrated its superiority in solving practical problems. in this paper, the transformation of discrete particle swarm optimization to solving for lab cours
3、e. so as to achieve the solution to the problem for the lab course provides a new way of thinking.keywords: particle swarm optimization algorithm; discrete particle swarm optimization; lab course一、绪论机房排课问题是典型的涉及多种因素的多目标组合优化问题，需要考虑学生学习效果、照顾教师合理的工作安排、充分利用机房资源等因素，传统的人工排课方式在资源紧张、约束条件复杂度增大的情况下，会遇到越来越多的冲突
4、。如果排课的数据规模足够大，则很可能出现冲突难以解决的状况。而用计算机排课代替传统的手工排课将可以最大限度地利用各种排课资源，解决冲突。计算机排课问题是一个多目标组合优化问题。国外从20世纪50年代末开始就对排课问题开展了研究。到目前为止，已知的解决排课问题的方法有：模拟手工排课法，图论方法，拉格朗日松弛法，二次分配法等多种方法。然而，随着排课问题的约束条件越来越复杂，对排课算法的要求也越来越高。粒子群优化算法在函数优化、约束优化、极大极小问题、多目标优化等问题中均得到了成功的应用。在研究粒子群算法原理的基础上，本文通过改造离散粒子群算法1,2用于机房排课问题的求解取得了良好的效果。二、机房排
5、课问题的分析（一）机房排课问题中的要素。机房排课问题涉及的要素主要有任课教师、课程、班级、时间、机房五个要素，其中教师、课程和班级三者之间的关系一般是在排课前就已经确定，机房排课问题的解空间实际上就是这五个要素之间的笛卡尔集。1.任课教师要素。每位任课教师在同一时刻只能上一门课程。每位任课教师每天最多安排4节课。2.课程要素。每门课程会预先确定开课班级、任课教师，在排课算法中会确定机房和时间。3.班级要素。由于上机课不存在合班上大课的情况，因此每个班级的学生人数是固定的。在同一时刻一个班级只能上一门课。4.机房要素。每个机房有固定的容量，机房中计算机的性能的高低及相关设备的配备情况决定机房适合
6、上某种类型的课程。分为1，2，3，4类机房，分别适合上计算机应用基础、多媒体课程、设计类课程、网络课程。5.时间要素。时间要素主要考虑一周中的教学工作日、每天可以安排的教学时间以及课次之间的时间间隔等。（二）机房排课问题的数学描述。机房排课问题实际上就是将任课教师、课程、班级、机房四个要素合理地安排在一周五天工作日的相应时间里，目标是没有冲突。因此，在机房排课问题中共有五个相关要素。下面分别用五个集合来表示如下：任课教师集合：t=t1，t2，tnt；（nt表示任课教师总数）课程集合：c=c1，c2，cnc；（nc表示课程总数）班级集合：l=l1，l2，lnl；（nl表示班级总数）机房集合：ar
7、=ar1，ar2，arna；（na表示机房）上课时间集合：lt=lt1，lt2，ltnl；（nl表示上课时间总数）由任课教师、课程、班级、机房、上课时间五个要素构成的笛卡尔积tclarlt就是机房排课问题的解空间，机房排课问题的求解就是在解空间中找到那些满足约束条件的解。课程的数量越多，教学规模越大，解空间的规模也就越大。在上述五个要素中，课程、班级和任课教师的对应关系是在排课前已经确定好的。而机房和上课时间是arlt完全映射。通过分析机房排课问题的相关约束条件，可建立适应度函数如公式2.1所示：xx（2.1）式（2.1）中x为问题的一个可行解，x为所有可行解组成的集合；1、2、3分别表示适应
8、度函数f1、 f2 、f3的权值（其中1+2+3=1）。f1是所排课程分散度的适应度函数；f2是所排课程时间安排合理性的适应度函数；f3是机房安排合理性的适应度函数。（三）机房排课问题的多目标分析。机房排课的目的是将任课教师、学生、相应的课程在时间和机房选择上根据不同的约束条件进行合理的安排。使所有课程安排都达到比较合理的状态。得到较为合理的课表，即找到排课问题的最优解。1.机房排课问题的约束条件。机房排课问题的约束条件分为必须满足的硬约束条件和应尽量满足的软约束条件。也就是说，满足硬约束条件的就是机房排课问题的可行解，而既满足硬约束条件又满足软约束条件的就是机房排课问题的最优解。硬约束：（1
9、）同一个老师在同一时间只能上一门课；（2）同一个班级在同一时间只能参加一门课的学习；（3）一个机房在同一时间只能安排一门课程的上机教学；（4）机房的容量必须满足上课学生人数；（5）机房数量要大于同一时间安排的上机课程总数；（6）部分课程必须安排在能满足该课程上机用软件所需计算机性能的计算机所在的机房。软约束（1）同一门课程的上机课时间应尽量安排在该课程理论课上课时间之后（本周内）；（2）上机课应尽量安排在下午或上午3，4节；（3）尽可能满足个别教师的特殊上课时间要求；（4）同一个班级的同一门上机课在一周之内应间隔排列；（5）课程尽量安排在与之对应类型的机房上课，如果机房资源不够，在机房能基本满
10、足教学实训的前提下，可退而求其次，选择其它类型的机房。满足上述中的硬约束条件的映射就是机房排课问题的解。而在此基础上尽量满足软约束条件就是获得一个科学、合理的排课结果必须考虑的问题。2.机房排课问题的优化。机房排课问题的优化目标就是怎样在满足基本的硬约束条件，获得可行解的前提下，通过满足尽量多的软约束，以获得较优解。现将机房排课问题涉及到的软约束指标归纳如下：（1）时间安排合理性。课程安排时间为3，4/5，6、7，8、1，2、9，10节的，对应时间安排合理性1取值为6，4，2，1；与理论课时间相隔的天数为1/无理论课时、2、3/0、=4/=-4、-3、-2、-1的，对应时间安排合理性取值2分别
11、为10、8、6、5、3、2、1。其中，1，2分别表示时间安排合理性指标1，2的权值，两者的和应该等于1； 分别表示课表上每门课程的时间安排合理性指标1，2的值；n表示所有的课程数量；kmax表示时间安排合理性指标1，2的最大值。（2.2）（2）机房安排的合理性。机房多余的座位数分别为5座以内、5-10座、10座以上的，对应机房利用率1取值分别为5、3、1；机房使用频率为30节次以上/周、20-30节次/周、20节次以下/周的，对应机房利用率2取值分别为5、3、1；课程所排机房情况为适合、基本适合的，则课程与所安排机房的适合度为5、3。（2.3）在公式（2.3）其中，1，2，3分别表示机房的利用
12、率1，2，课程与所安排机房的适合度的权值，三者的和应该等于1； 分别表示课表上每门课程的机房的利用率1，2，课程与所安排机房的适合度的值；n表示所有的课程数量； 表示时间安排合理性指标1，2的最大值。三、求解机房排课问题的粒子群算法设计（一）粒子群优化算法求解机房排课问题的编码设计根据排课问题的特征，排课算法的调度方案的编码方式有矩阵表示法1、三维编码、布尔矩阵编码三种。求解机房非课问题需要根据所选择的算法及软件开发技术来选择合适的编码方式。由于矩阵表示法的特点适合用数据库来表示，因此，本文在矩阵表示法的基础上根据所研究问题的特点确定了所用的编码方式：设有二维矩阵xk，l，其中k表示在课表编排
13、过程中可以用来作为机房上课的时间的数量，l表示可以用于上机课使用的机房数量。矩阵中的每个元素都由课程、任课教师、上课班级三部分组成。在机房排课问题的实现算法中，这个二维矩阵将与关系数据库中的一张数据表对应（行表示可供排课使用的机房，列表示可以排课的时间）。同时，每一张数据表表示粒子中群中的一个个体。对粒子的初始化就是对数据表的初始化。（二）求解机房排课问题的算法设计1.初始化种群。粒子群作为机房排课问题的解空间，一个可行解就与群中一个粒子相对应，因此种群的初始化就是构造机房排课问题的初始解空间。因为种群初始化在机房排课问题中就是形成一定数量的问题可行解，所以在初始化过程中，应尽量做到在随机排课
14、时，不存在任何冲突的前提下，如果一门课程每周上课次数超过两次，则两次课上课时间的间隔一天是最好选择，其次是两天、三天。同时也应尽量满足多次上同一门课程要安排在同一个机房。从而完成一个粒子的初始化。然后重复以上过程以构造出指定数量的粒子，从而完成种群的初始化过程。2.适应度函数。适应度函数的建立是在充分考虑机房排课问题是多目标组合优化问题的基础上，根据4.2.1中提到的要求确定下来的，如下式：xx（3.1）式（3.1）中x为问题的一个可行解，x为所有可行解组成的集合；1、2、3分别表示适应度函数f1、 f2 、f3的权值（其中1+2+3=1）。f1是所排课程分散度的适应度函数；f2是所排课程时间
15、安排合理性的适应度函数；f3是机房安排合理性的适应度函数。3.粒子位置更新操作。本文对为解决机房排课问题所采用的粒子群算法中粒子位置更新公式进行修改以适应本文所研究的问题。如公式（3.2）、（3.3）所示：（3.2）(3.3）在上述公式中，利用遗传算法的交叉操作改造了粒子位置的更新公式，在满足条件的前提下将待更新粒子的当前位置与该粒子的历史最好位置、粒子群全局最好位置进行交叉操作，再引入遗传算法的变异思想对该粒子按公式（3.3）进行局部交换，从而完成了粒子位置的更新。在更新时，本文选择将待更新粒子与其历史最优位置及全局最优位置的粒子对应的二维表的列进行交叉操作，即在操持机房不变的情况下，改变上课的时间。在上述操作过程中，若遇到的冲突，将按算法的规则进行调整，使之符合可行解的要求。即如果遇到的冲突能通过调整解决，则交换，否则放弃交换操作。4.算法流程。根据上文的分析，总结求解机房排课问题的离散粒子群算法如下所示：对粒子数量m进行初始化，概率c1，和c2，给计数器n赋初值0；采用随机方式产生各初始粒子的位置，并计算各初始粒子的适应度值；令各粒子群中各粒子的当前最好位置 等于各粒子的当前位置 ，令粒子群当前全局最优粒子的位置为gn；判断算法的收敛条件是否满足，如满足，则由gn得到最优解，即最终课表，算法结束；否则跳转到步骤对粒子群中所有粒子进行如下操作：1)按公式（3.2
