几种智能排课算法的对比探讨

来源:用户上传      作者:

　　摘要：该文给出了排课系统避免冲突所需要遵循的条件和因素，对可实现于排课的几种智能算法做了介绍和分析，并对智能算法以后的发展进行了探究，为今后的各种排课需求提供参考。
　　关键词：排课;智能算法;分析对比
　　中图分类号：TP312
　　文献识别码：
　　文章编号：1009-3044（2020）04-0159-02
　　收稿日期：2019-12-05
　　基金项目：江苏省大学生实践创新训练计划项目校级项目“机房排课系统的设计与实现"（项目编号：51800021644）
　　作者简介：黄岭（1979—），男，江苏常州人，讲师，硕士，研究方向为电子及计算机应用;秦春娣，女，工程师，本科;陈伟，男，专科生。
　　Comparison of several intelligent Course Scheduling Algorithms
　　HUANG Ling，QIN Chun-di，CHEN Wei
　　（Changzhou Vocational Institute of Textile and Garment，Changzhou 213164，China）
　　Abstract：This paper gives the conditions and factors that need to be followed to avoid conflict in course scheduling system，analyzes and compares several intelligent algorithms that can be used to solve course scheduling problems，and forecasts the development pros-pect of intelligent algorithm，so as to provide reference for future various courses scheduling needs.
　　Key words：course scheduling;intelligent algorithm;analysis and comparison
　　人類每一次的思考创新都离不开技术革新带来的取代传统手工操作，转向高效人工智能处理的进步。一直困扰着学校教务的排课问题也随着专业、班级、课程等必要条件的不断扩展而显得愈演愈烈。排课问题作为资源分配调度的一种典型问题，已经被证明是非确定性多项式（NP）完全问题。完成排课课程表这个过程的课程调度算法也是NP问题中较难的一类。近些年，许多研究人员将人工智能、神经网络、模糊算法、进化算法等方面的研究成果不断在控制盒优化、复杂线性系统模型.创建方面进行探索，并产生了一系列的智能排课算法，本文就常用的几种算法做一个比较分析。
　　1 排课问题分析
　　排课问题需要解决的是根据具体教学需要满足诸如节次、班级、教学地点、教师这一系列因素的组合，并且能够很好地处理特殊需求，协调各因素之间的矛盾冲突，换言之就是要借助计算机技术权衡各种制约条件，最终达到课程安排合理化的结果[1]。
　　排课系统中的涉及的约束条件归纳起来主要有三种：基础硬约束、硬约束和软约束。
　　1）基础硬约束：是指教师、班级和教学地点在节次上不可发生的冲突，包括“同一节次同一班级不能上两门不同的课程”;“同一节次同一教师不能上两门不同课程”，这类约束条件是所有排课模型都会涉及的，最基础的要求，这个约束若无法
　　满足，排课也就没有意义了。
　　2）硬约束：是指排课时需要遵循的教学计划规定的一些硬性要求或实际教学场地的条件限制的原则。如“课程按照最小两节或六节进行”;“课程的总周数有要求”;“教学地点容纳学生数限制”等。
　　3）软约束：是指在若能够完成基础硬约束和硬约束排课的前提下，可适当考虑教学规律或个性化排课需求。如“每个班级的课程周分布均匀”;“教师特定时间段上课”等。
　　2 几种算法比较
　　当前常用的排课算法，主要包括回溯算法、人工免疫算法、遗传算法、粒子群优化算法、图着色算法、贪婪算法、模拟退火算法、蚁群算法等，下面对这几种常用算法的特点加以描述。
　　2.1 回溯算法
　　回溯算法也称为试探法，它是一种类似枚举 的系统搜索问题解的方法，原理是在搜索探试过程中寻找问题的解，当发现不满足求解条件时，就“回溯"返回，尝试别的路径。
　　回溯算法基本步骤：面向设定问题，定义问题的解空间，它至少包含问题的一个解;设计易于搜索的解空间结构模型，使其能用回溯法搜索整个解空间;以深度优先的方法搜索解空间，并且在搜索过程中用剪枝函数来避免无效的搜索。
　　其优势是整体结构清晰，容易理解;空间占比较小;适合处理组合数较大且有限的问题。其不足体现在算法计算量较大，回溯层次多时过于耗时[1]。
　　2.2 遗传算法
　　遗传算法是在20世纪六七十年代由美国密歇根大学的Holland教授创立的。Holland在设计人工自适应系统时建议参考遗传学基本原理来模拟生物自然进化的方法。遗传算法是一种基于进化论的自然选择、遗传进化并行，且随机自适应的搜索算法[2]，将问题解通过复制、交叉、变异来编码，生成的“染色体”群通过一代代的不断进化、收敛，最终成为最适应的群体。
　　遗传算法的基本步骤：预估期望进化代数，计数器初始设置，随机生成多个初始群体;评估群体中各体适应度;在评估基础上将优化的个体直接或者配对交叉产生新个体遗传到下一代;将交叉算子（在此算法中起核心作用）作用于群体;群体通过选择、交叉、变异运算这一系列手段修改来自个体串的某些基因座上的基因值从而得到下一代群体;若计数达到期望进化代数，则可得到最大适应度个体，即最优解[2]。 　　其优势是便捷易操作;并行计算能力强;容错能力强;良好的可扩展性。其不足是灵活性较差;算法较为烦琐，容易出现收敛过早现象;随着约束条件增多会使得效率下降明显。
　　2.3 贪心算法
　　贪心算法，又称贪婪算法，它的基本思路是每次选择都将所求问题简化，从某个最初解开始一步步地进行，遵循一定的优化测量，保证每一步都是局部最优解。
　　贪心算法的基本步骤：选择建立合适需要解决问题的数学模型;分解问题，生成若干子问题;分别对每一个子问题求解，得到子问题的局部最优解;合成所有子问题的解生成需要解决问题的一个解[3]。
　　其优势是具有不可回溯，之前决策影响之后的决策;能够动态规划降低时间复杂度，从而得到局部最优解。其不足在于算法寻找组合侧重明显，未能考虑全局均衡优化[1]。
　　2.4 模拟退火算法
　　模拟退火算法源于1953年N.Metropolis等人提出。其基本原理是模拟固体退火原理，这是一种使用概率的算法，模拟退火算法从一顶值初始温度出发，在温度不断降低的过程中，应用概率突跳的特点随机地在解空间搜索設定函数的全局最优解[4]。
　　模拟退火算法的基本步骤：在当前解中使用解函数随机产生一个符合目标的新解;计算设定函数与此新解的增量值并判断否能接受此新解;若新解能被接受，则用新解取代当前解。这样当前解也就完成一次迭代，然后开始下一轮测试。若新解不能被接受，则转回原来的当前解，继续下一轮测试[4]。
　　其优势是计算原理简便;少限制条件下可快速产生解;并行计算优势明显。其不足在于权衡选择参数不易，资源消耗相对较大;多限制条件下执行时间长，收敛速度下降明显，得到全局最优解较困难。
　　2.5 蚁群算法
　　蚁群算法是由意大利学者Dorigo、Maniezzo等人于上世纪90年代首先提出。蚁群算法基本思路为：把需要优化解决问题的可行方案解用蚂蚁的行径轨迹来表示，把需要优化解决问题的所有方案解用整个蚁群的所有轨迹来表示。轨迹较短的蚂蚁的信息素量较多，较短轨迹上累积的信息素浓度会随时间不断增加，选择该轨迹的蚂蚁数也会随之增加。最终，整个蚁群会在正反馈的作用下集中到最佳的轨迹上，这时就可得到最优方案解。
　　其优势是健壮性表现良好;全局搜索能力突出;方便实现并行。其不足是代码执行效率偏低，复杂度较高情况下搜索容易发生滞怠，造成搜索时间增加[5]。
　　2.6 人工免疫算法
　　人工免疫算法是一种具有生成结合检测的迭代过程的群智能搜索，高度进化算法。在整个迭代的过程中，在继承前一代最佳个体特征的条件下，遗传算法能够实现全局收敛。
　　人工免疫算法的基本步骤：随机产生初始父代种群X1，根据经验知识抽取疫苗;如若当前群体中包括了最佳个体，则直接输出结果，否则继续;对目前第n代父代种群Xn进行交叉计算，产生种群Yn;对Yn进行变异计算，，产生种群Zn;对Zn进行接种疫苗计算，产生种群An;对An进行免疫选择计算，产生新一代父本Xn+1，转到判断是否包含最佳个体一步。
　　其特点是可与遗传算法相互融合，既可延续遗传算法优化特性，又可通过有针对性地利用待解决问题中的一些显著特征和已知信息来控制其在优化阶段发生的退化迹象[6]。
　　2.7 粒子群优化算法
　　粒子群优化算法首先由kennedy和Eberhart博士于1995年提出，此算法受鸟群觅食活动行为规律的启发，通过建立粒子群模型模拟动物活动群体信息共享的一种随机搜索算法[5]。
　　粒子群优化算法的基本步骤：种群随机初始化;对种群内的每一个个体计算适应值;种群根据适应值进行复制;如果终止条件满足的话，就停止，否则转步骤二。
　　其优势是可以处理一些传统方法不能处理的演化计算，与遗传算法相比大多数情况下，所有粒子收敛更快。其不足是遗传算子的选择有时比较麻烦，在处理某些问题上性能并不是特别好。
　　2.8 图着色算法
　　图着色算法也称为着色问题，是鼎鼎有名的NP完全问题中的一个。图论里最具代表性的猜想就是道路着色问题。
　　图着色算法的基本思路：定义x[n]数组存储n个顶点的可行解着色方案，假设一个图需要的颜色为m种。从t=1开始依次对当前第t个顶点进行着色处理：如果t》n，则表示成功完成一个着色解的输出方案。如果t《n，则依次对第t顶点着色1至m，如果t与其他相邻顶点都未发生着色冲突的话，可接着进行下一轮顶点的着色处理;反之，则需回溯着色处理阶段，测试下一轮颜色方案[7]。
　　由于图论中目前还没有有效地算法来确定一个图的色数，所以还需要结合其他算法和策略共同解决排课问题。
　　3 算法展望
　　以上八种智能算法无不例外都是人类对自然和社会的发展过程进行观察理解之后所做出的仿真模拟。随着智能优化算法的蓬勃发展，其简单的算法结构、强大的并行处理机制以及突出的求解能已被诸多研究者所重视，这些算法被广泛应用于技术经济领域并取得了显著的成果。不过由于这些算法大多是对群落、生物、物种的社会性进行模拟，还缺乏充分的数学理论支撑和系统分析过程。而且这些算法大多都是针对某：个特定具体问题而设计，缺乏通用性，算法中的参数设置大多需要凭借主观经验来确定或调整。因此对智能排课问题是巨大的研究空间和现实意义的。除了继续深入研究改进优化智能算法之外，更可考虑把排课系统模型进行策略化、阶段化分解分析，充分考虑各种算法所长，尽可能地弥补各算法的缺陷，在不同处理阶段采用不同的智能算法和分治策略，进而形成一个能够充分利用领域知识，且计算最小、优化快速，并具有全局收敛性的较优的混合算法。
　　参考文献：
　　[1]黄岭，秦春娣，陈伟.多约束条件下排课系统模型的创建[J].电脑知识与技术，2019，15（17）：64-66.
　　[2]赵伟.基于混合遗传算法的船舶减横摇模糊神经网络控制研究[D].哈尔滨：哈尔滨工程大学，2007.
　　[3]张鹏程，茹江燕.基于贪心策略的单一下料问题求解研究[J].河北水利电力学院学报，2018（4）：44-47.
　　[4]王现磊，郝文宁，陈刚，等.基于模拟退火策略的Sarsa强化学习方法[].计算机仿真，2019，36（4）：219-222，228.
　　[5]陈程.基于混合蚁群算法的车间作业调度问题求解[D].成都：电子科技大学，2008.
　　[6]孔令发，刘云超.基于免疫算法的应用层组播路由算法[J].计算机应用，2006，26（1）：40-42.
　　[7]chenglinhust的专栏-博客频道-CSDN.NET，图着色算法详解[EB/OL].（2013-06-20）.http：//blog.csdn.net/chdhust/article/de-tails/9138333.
　　[通联编辑：谢媛媛]
转载注明来源:https://www.xzbu.com/8/view-15161822.htm