基于遗传算法和禁忌搜索算法的排课系统研究

1/7基于遗传算法和禁忌搜索算法的排课系统研究基于遗传算法和禁忌搜索算法的排课系统研究引言排课是高校教学管理中十分重要而又复杂的管理工作之一，由于排课问题涉及的因素有时间、教师、教室、课程、班级等，因此排课问题是一个有约束条件、多目标、模糊性极强的组合优化问题1。由于各学校资源差异较大，约束条件复杂，排课系统难以具有普遍适用性。一般教务排课仍以手工为主，计算机为辅，效率低下。研究灵活、高效、自动化程度高的排课系统需求迫切，具有现实意义。国外很早就有人本文由论文联盟HTTP/收集整理研究课表的编排问题，一般利用启发式函数，并且大多数启发式方法都是模拟手工排课的过程实现的。国内对排课问题的研究较晚，并且大部分学者研究的排课系统都依赖于各个学校的教学体制，不具有普遍适用性2。从实际使用情况看，国内研究的排课系统软件在性能上也达不到使用要求。遗传算法是一种借鉴生物界自然选择和进化机制发展起来的高度并行、自适应的随机搜索算法；而禁忌搜索2/7算法是对局部领域的一种扩展，是一种全局逐步寻优的搜索算法。通过对比分析，遗传算法和禁忌搜索算法在解决复杂优化问题中有明显的优势，因而本文采用遗传算法和禁忌搜索算法来实现排课系统。1排课系统分析排课问题的主要任务是将班级、教师、课程安排在一周内某一不发生冲突的时间和教室中，保证课表在时间分配上符合一切共性和个性要求，使安排在各个目标上尽量达到最优。根据是否必须满足，可以将约束条件分为硬约束和软约束。硬约束是指教师、班级、教室在时空概念上发生了冲突，它是在排课过程中必须满足的约束条件，否则将会使排课结果毫无意义。软约束是指排课过程中需尽量满足的约束条件，它能够使课表更加合理。排课的目标是要满足所有的硬约束条件，同时尽可能多地满足软约束条件，实现一个使用方便、效率高的排课系统。基于遗传算法与禁忌搜索算法的排课系统在整个排课过程中，首先需要确定教学计划，然后根据教学计划生成教学任务，教学任务确定了课程、教师、班级3者之间的关系。在排课问题中，由于涉及到教师、教室、课程、班级、时间这5个因素，可以将课程、教师、3/7班级这3个因素绑定为一个整体，作为一个元组，并对这个元组随机分配时间与教室，生成一个可行的课表。本文应用遗传算法对排课问题进行编码，然后再进行选择、交叉、变异等操作，计算适应度函数。在遗传算法的运算过程中使用禁忌搜索算法来代替变异算子，从而得到更优的个体解，最终生成有效的课表。遗传算法编码遗传算法的编码方法有很多种，针对排课系统，本文采用混合式编码方式，将混合式编码作为排课系统遗传算法的基因。该基因由教师编号、课程编号、班级编号组成，每个教师都有一个唯一的教师编号，用八位数字表示。课程编号用一位数字表示，表示该教师教的第几门课程。班级编号也用一位数字表示，表示该教师教的第几个班级。这种编码方式解决了特定时段教师课程的安排问题和普通时段课程的分配问题。系统只要按照算法流程对编码进行处理，对结果进行不断的筛选，就可以得到完善的课程表，通过混合式编码将教师、课程、班级这3个因素的关系表示出来。混合式编码在时间上主要采用时间片划分，上课时间分为周一到周五，一天有10节课，上课方式为一个课次两个相邻小节。所以以一个课次为一个时间片，一天可划分为5个时间片。这样一周就可划分为25个时间片。可以4/7构造一个三维矩阵来表示排课系统，其中X坐标表示时间片，Y坐标表示教师、班级和课程，Z坐标表示教室，通过三维矩阵将影响排课系统的5个因素联系起来。2遗传算法适应度函数适应度函数用于评价某个染色体的适应度，随着排课的进行，课表空间在不断变化，个体的适应度也随着课表空间的改变而改变，本文采用的方法是调整随机生成的初始群体，但是在遗传算法运行过程中，交叉和变异都可能产生冲突，为了减少冲突，可以引入负适应度值来降低冲突个体被选入的概率，同时记录冲突未消除的个体，并在下次迭代中继续消除。对有时间段冲突的两个个体，可以用个体的冲突时间段与该个体的空闲时间段互换来消除冲突，这样就消除了遗传算法运行过程中存在的冲突，增加了个体的适应度。2遗传算法运行选择操作首先采用计算机模拟方法计算个体的选择概率，这种方法的基本思想就是用事件发生的频率来决定事件的概率。接着采用轮盘选择法进行下一代个体的选择。其基本思想就是将整个群体根据个体的适应度不同分布在轮盘上，适应度大的个体占的比例多。在选择算法过程中随机转动轮盘，指针所指区域的个体被选中并生存。这种选择方法5/7对适应度大的个体选中的机会较大，实现了个体的优胜劣汰。传统遗传算法的缺陷是初始种群分布不均匀，为了改进这个缺陷，本文采用分区域的初始种群选择，将整个解空间分成M个区域，初始化种群时，分别在每个1/M小区域中随机选择1/M个体，最后将M个小种群合并为初始种群，这样产生的种群就覆盖了整个解空间，保证了初始种群的均匀分布。交叉操作本文采用的是两点交叉，其基本思想是在两个相互配对的编码串中随机选择两个交叉点，将这两个交叉点之间的基因相互交换得到两个子个体，两个11位的父个体，交叉点的位置为2、6，通过两点交叉运算得到两个子个体。两点交叉运算如下所示父个体111110011010子个体111101011010父个体10101000101子个体10110000101通过这种方式解决了选课学生人数和教室座位人数之间的冲突，交叉操作产生的新个体遗传到下一代。改进的遗传算法传统的遗传算法收敛速度慢、局部寻优能力差、产生的最优解精度不高，同时由于交叉算子使种群染色体之间存在局部相似性，这样就很可能导致搜索停止。如果变6/7异率降低，还会导致“早熟”现象发生。遗传算法在进化过程中，每代总要维持一个较大的群体规模，从而容易使个体后代过多，造成算法“局部收敛”而不能得到全局最优解。因此，必须对个体以变异概率进行局部搜素，跳出局部收敛，获得全局最优解。禁忌搜索算法在搜索过程中可以接受劣解，具有较强的“爬山“能力，新解不是在当前解领域中随机产生的，而是从中选择的最好解，即最好解产生的概率大于其它解。该算法通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，并通过藐视准则赦免一些被禁忌的优良状态，增加获得全局最优解的概率，因此禁忌搜索算法适合作局部搜索3。由于传统的遗传算法存在许多缺点，因此本文在变异阶段用到了禁忌搜索算法，用TS代替变异算子，防止“早熟”现象发生，使个体呈现多样性。改进后的遗传禁忌搜索算法为了使原算法优点保留，弱点被克服或被削弱，提高算法的力度，本文先用GA进行全局搜索，搜索出所有可能的排课情况，并将其分布在解空间的大部分区域，然后在每个个体课表中用TS进行局部变异搜索，得到最优排课情况4。下面给出遗传禁忌搜索算法的算法流程，见图1。7/7改进后的遗传禁忌搜索算法遗传禁忌搜索算法终止条件为在种群中找到了能够接受的最优排课单元；最适应种群的个体占群体比例达到了预定的比例；达到了预定进化代数；达到了指定的最大时间。在遗传算法的迭代中，只要满足上述4个条件之一，算法就终止。TS运用于GA的局部搜索中，避免了GA过度早熟的现象，但是如果一直调用TS会浪费时间5，因此调用TS要根据GA的收敛情况来定，开始时调用TS的次数很少，随着迭代的进行，调用TS的次数也越来越多6，因为各个排课单元越接近最优排课单元，局部搜索的作用也越大，因此在GA中要合理地使用TS。结语本文介绍了国内外排课系统问题