遗传算法在高职院校排课问题中的研究与应用

来源:用户上传      作者:

　　[摘要]随着我国教育改革的不断推进，高职教育的教学形式变得越来越丰富，在这样的情况下，传统的排课方式已经无法适应现阶段规模不断扩大的教学活动。为了适应这种现状，必须研究出一款符合高职院校教学活动要求的排课系统。本文将就基于遗传算法的高职院校排课系统进行研究，用于解决现阶段高职院校遇到的排课问题，为高职教育发展提供助力。
　　[关键词]遗传算法;高职院校;排课
　　[中图分类号]G640 [文献标识码]A [文章编号]1671-5918（2019）01-0076-03
　　doi：10.3969/j.issn.1671-5918.2019.01.034 [本刊网址]http：//www.hbxb.net
　　前言
　　随着我国教育体制的不断完善，我国高职教育获得了迅猛的发展，为我国社会各行业输出了许多技术型人才。随着招生规模的持续扩大，广大高职院校的专业体系也变得越来越丰富完善，这就为排课工作带来了巨大的压力。面对越来越复杂的排课问题，很多高职院校往往需要花费大量的时间。为了解决这一问题，必须采取先进技术措施予以解决。
　　一、遗传算法概述
　　（一）遗传算法的概念。遗传算法是从生物进化理论中衍生出的一种全局搜索优化的概率性算法。根据生物进化理论，在一个种群中，单个生物个体是无法实现遗传进化的，因此种群中的个体所表现出的特征往往存在一定的差异性，这是因为每个生物都具有独一无二的染色体，染色体中则包含了遗传因子。不同个体之间随机交配产生下一代种群，通过基因交叉、突变和自然选择使种群更好地适应外部自然环境。遗传算法正是脱胎于上述过程，通过遗传迭代一定代数后，获得适应度最高的种群，深刻体现了适者生存的自然规则。
　　遗传算法的共同流程如下：首先，构建一个候选解组集。其次，基于一定的适应性条件对这些候选解的适应度进行计算。在此，通过适应度的对比分析淘汰一定的候选解。最后，对保留下来的候选解进行一定的操作，生成新的候选解。将上述内容综合起来，即可对遗传算法进行定义：基于染色体群的并行搜索，带有猜测性质的选择操作、交换操作和突变操作。
　　（二）遗传算法的特点分析。目前，遗传算法已经成为解决搜索问题的一种通用算法，在各类通用问题中都能够发挥着有效的作用。其特点主要包括以下几个方面：
　　1.遗传算法是从问题解的串集开始搜索，这是其于传统优化算法最大的区别。因此它避免了传统算法从单个解人手可能误入局部最优解的问题，覆盖范围更加寬广，实现了全局择优。
　　2.遗传算法可以对群体中的多个个体进行同步处理，更加有利于实现并行化。
　　3.遗传算法不需要使用到搜索空间的知识和其他辅助信息，而是利用适应度函数值对个体进行评估，这时的遗传算法的应用范围更加宽广。
　　4.遗传算法具有自组织、自适应以及自学习性。通过遗传算法对进化过程中获得的信息进行自行组织搜索时，个体的适应度越大，其生存概率也就越高，并获得更适应环境的基因结构。
　　5.遗传算法采用的并不是不确定性规则，而是通过概率的变迁规则对搜索方向进行引导。
　　6.遗传算法本身采用了动态自适应技术，因此可以通过自动调整算法对进化过程中的参数以及编码精度进行控制。
　　目前，遗传算法广泛应用许多学科，函数优化和组合优化是其应用的两个主要领域。现如今，人们构造除了许多形式复杂的测试函数，这类函数具有非线性、多模型以及多目标的特征，在对其优化问题进行研究时需要应用遗传算法。同时，随着问题规模的增大，组合优化问题的搜索空间也随之扩张，面对复杂问题的求解，遗传算法也是最优化的工具。
　　二、高职院校教学活动的特点以及排课的约束条件
　　（一）高职院校教学活动的特点分析
　　高职院校属于专科，其学制为3年，由于高职院校专业课程往往实践性和理论性并重，因此在毕业之前，学生往往需要进行半年左右的顶岗实习，因此告知学生在学校的学习时间最多为两年半。在这段时间内，学生需要完成包括公开课、专业基础课以及专业实践实训课在内的所有课程，时间十分紧张。与此同时，一些发展时间较短的高职院校各方面力量都存在一定的不足，教师的工作量相对较高，为了缓解压力，高职院校通常会从校外聘请一部分兼职教师。
　　在课程安排上，高职院校的教育教学目标是培养具有综合职业能力的高素质人才，因此除了理论教学外，同时也更加注重学生动手实践能力的培养。因此在专业课程体系中，实验实训课程所占的比例很高，基本上可以达到一半。在实验实训课程开展时对教学条件的要求较高，需要高职院校建设专门的实验实训场地。还有部分实验实训活动需要深入到社会企业中开展，这就要求高职院校排课活动必须考虑到场地资源的调配以及学生外出的时间安排。
　　此外，高职院校专业课程中还包括了一些教学实践项目，一般需要占用学生连续几周的实践，在这段时间内，学生很难有多余的精力对完成其他课程，这一点在排课中也需要考虑到。
　　（二）高职院校排课的约束条件分析
　　高职院校排课活动实际上是一个带有约束的多目标组合优化问题，在排课的过程中会受到一些约束条件的限制，同时排课方案并非是固定的。在具体工作中，不同约束条件之间会产生一定的冲突，排课活动的目标就是消除这些冲突，如此才能保障教学计划的顺利实施。通常情况下，高职院校排课的约束条件主要包括以下几个方面：
　　首先，两门不同的课程无法在同一教室的同一时间开展。其次，一个教师无法同时在两个教室开展教学活动。其三，一个学生不能同时上两门不同的课程。其四，教师的座位数必须超过上课班级的总人数。其五，一个班级的同一门课程之间必须设置一定的间隔。其六，体育、实践类课程最好安排在下午。其七，排课必须考虑到外聘教师的实际情况。其八，公共选修或是公共类课程最好优先排课。其九，要对一些制定了教学区且周次不规则的特殊课程进行科学的安排。 　　在利用遗传算法进行排课时，需要根据具体规则和约束条件设置适应度函数，根据计算出的适应度值判断是否存在违反约束条件的情况，以此判断排课方案的合理性。
　　三、基于遗传算法的高职院校排课活动研究
　　遗传算法是模仿达尔文的生物进化理论对复杂的优化问题进行求解。
　　（一）基因编码
　　在遗传算法中，编码即是指将一个问题的可行解从其求解空间转换到能处理的搜索空间。编码的方法决定了生物种群中个体的染色体排列形式，同时也体现了群体遗传进化运算的方式。
　　在高职院校排课过程中，根据基因编码方法，需要将班级、课程、教师、上课时间以及教室等元素进行科学的组合，在此基础上形成课表。通常情况下，高职院校一周的上课时间的五天，每天课程为八节，采用两节连排的方式。因此可以将两节课视作一个时间段，基于此，每周的时间段的数量为20。在具体编码的过程中，可以利用数字对上述五个元素进行编码，即可获得相应的班级号、教师号、课程号、上课时间以及教室号。
　　（二）种群初始化
　　在完成基因编码之后，就需要进行种群初始话，在此基础上一代代进化下去，直到根据进化停止准则终止进化。根据这一流程，高职院校排课过程中，需要利用计算机生成一定数量的排课方案，这样一来，不同的班级就可以获得多个随机的班级一教师—课程一上课时间一教师编码，之后筛选出其中不重复的个体填充到数组中，获得不同班级的初始课程表。最后对所有班级的初始课程表进行综合，形成初时种群。
　　（三）构建适应函数
　　在遗传算法中，适应度值决定了不同个体在种群中的好坏程度，适应度值是下一代种群选取的重要依据。因此在高职院校排课过程中，为了保障适应度值计算的合理性和可靠性，必须构建科学的适应度函数，这样才有利于找到最优解。在设置适应函数的过程中，需要参考各项约束条件。对于一个排课方案而言，若是其中存在冲突，表明其不可行，则其适应度为0，从而被淘汰。对于一个班级而言，同一课程的间隔越长，则适应度值越高。同时，专业类课程设置在上午、实践课程设置在下午的适应度值相对更高。
　　综上所述，可以构建以下适应度函数：
　　Fn=Y*（x1*K+x2*S+x3*J）
　　在该适应函数中，Y为冲突检查结果，K为课表优化中课程时间间隔、s为课程理想時段、J为教师上课要求，x1、x2、x3则分别代表着各期望值在总期望值中所占的比重。
　　以上述函数对不用排课方案的适应度值进行计算，适应度值越高，则表明该排课方案的合理性越高。
　　（四）遗传算子的设计
　　首先，选择。通过适应函数计算获得适应度值，通过适应度值的比对可以从中选择出适应度较高的个体。具体可以采用轮盘赌的方法，将适应度值按照一定的比例转化为概率，通过模拟轮盘赌的方式堆积获得多个随机数，将其与计算获得的不同个体的概率进行对比，以此判断该个体是被遗传还是被淘汰。
　　其次，交叉。在进行交叉操作之前，需要将所有的排课方案按照一定的顺利进行排列，根据选择操作的结果选择两条染色体作为父个体，具体是通过将对应班级的上课时间和上课教室进行交叉即可获得新的染色体。
　　最后，变异。变异运算是使用其他等位基因对个体染色体编码串中的某些基因进行替换，获得新的个体。延伸到排课过程中，是将种群中随即选取个体的时间或是教室进行改变，之后检查是否存在冲突，若是则继续进行变异。
　　（五）遗传进化终止规则
　　随着遗传运算的不断深入，各代种群的优良基因将不断累积，在此过程中，种群平均适应度和个体适应度也将呈现出不断上升的趋势，同时，求解结果也逐渐向目标值靠近。当这一过程达到一定程度，必须通过一定的终止规则对其进行收敛。在高职院校排课过程中，可以适当地参考遗传算法中常用的终止规则设计与之相适应的终止规则，具体内容如下：
　　首先，当种群中个体最大适应度超出预先设定值时，停止排课。其次，当种群的平均的适应度值超出预先设定值时，停止排课。最后，当遗传世代数超过预先设定值时，停止排课。
　　综上所述，遗传算法具有自适应、随机搜索、高度并行等特殊优势，能够有效地适应多约束条件的排课问题优化。
　　（六）遗传算法性能分析
　　为了验证上述遗传算法的应用效果，将其应用到了某高职院校信息工程系2016～2017学年第一学期的排课活动中。
　　通过对迭代次数的比较，当交叉概率为0.6时，变异概率为0.02条件下种群的个体适应度趋于稳定。同时，当交叉概率为0.5时，变异概率0.01条件下种群个体适应趋于稳定。通过数据比对发现，不同种群规模下，通过遗传算法获得的适应度迭代次数都低于普通算法，说明遗传算法的搜索性能更加强大。
　　从运算消耗的时间来看，遗传算法在种群规模明确的情况下，迭代次数越多，所要消耗的时间也会随之增长，与此同时产生的高适应度个体数量也越来越多。在迭代次数相同的情况下，遗传算法所消耗的时间更少，且产生的高适应度个体数量则更多。此外，高适应度个体的数量在迭代次数超过200之后开始趋于稳定。
　　结语
　　综上所述，随着高职院校规模的不断扩大以及专业课程的增加，其排课活动涉及的问题也逐渐增加。为了提升教学活动安排的合理性，本文充分考虑到了现阶段高职院校教学活动特点、教学模式以及人才培养目标，基于遗传算法构建了高职院校排课系统，有效提升了排课工作的效率和质量，促进了我国高职院校教学计划合理性的提升。
转载注明来源:https://www.xzbu.com/1/view-14783692.htm