基于遗传-蚁群混合算法的排课系统①

2019-04-10胡粔珲

计算机系统应用 2019年2期

孙弋,胡粔珲

(西安科技大学通信与信息工程学院,西安 710054)

引言

教务管理是教育活动的重要支撑,随着高校教育改革的发展,高校人数的增加,但教学资源却相对有限的情况下,排课工作的难度和复杂程度都有所提高.因此,如何设计一个能满足多约束条件并且高效的排课系统成为了目前待解决的问题[1].

排课系统的核心是排课,排课算法一个NP完全问题,即算法的计算时间呈指数增长[2].常用的排课算法有: 蚁群算法、遗传算法、贪心算法、图论算法等.遗传算法模拟生物进化过程,具有自适应全局寻优和智能搜索等优点,但是容易收敛得到局部近似最优解,进行大量的无用迭代,难以收敛于最优解[3,4].蚁群算法启发于蚂蚁寻找最优路径的行为,具有较强的鲁棒性,是一种正反馈算法.但当群体规模较大时,搜索初期信息素匮乏,容易产生停滞现象.单算法在解决问题时都会有局限性,花费的时间成本更多,求解的结果不理想[5,6].

为了提高排课的效率和成功率,本文提出一种将遗传算法与蚁群算法结合使用的方法,首先使用遗传算法对初始种群进行优化选择,生成蚁群算法所需的信息素,再通过蚁群算法求得全局精确解.优劣互补,充分发挥两者的优势[7].

1 排课问题的分析

排课问题主要涉及教师、教室、课程、班级、上课时间等因素,排课的实质就是要求课程表在安排的时候不能在上述五个因素中发生冲突.可使用五个集合来表示这些因素.

班级集合:C={C1,C2,C3,···,Cn}

课程集合:S={S1,S2,S3,···,Sm}

教师集合:T={T1,T2,T3,···,Tx}

教室集合:R={R1,R2,R3,···,Rt},教室有多种类型,例如实验室、多媒体教室、机房等,每个教室容纳的人数也不相同.

时间段集合:P={P1,P2,P3,···,Pi},Pi表示时间段,例如P1为周一的1-2节课,P2为3-4节课.时间和教室的笛卡儿积为:N=R*P={(r1,p1),(r2,p2),…,(rn,pn)},N中的元素是教室-时间对.排课问题由此转化为一门课寻找一个合适的教室时间对.

1.1 硬约束条件

硬约束是在排课过程中必须要遵守的约束条件,如果排课过程中无法遵守硬约束条件,则会导致日常的教学计划无法顺利的进行.例如:

(1)同一个教师在同一时间段内只能够上一门课,并且教室的性质要和课程要求相吻合;

(2)同一个班级在同一时间段内只能够接受一门课;

(3)一门课程安排的教室座位数量要大于或等于本门课程上课的人数.

1.2 软约束条件

软约束条件需要将人体生物规律与排课进行结合.满足软约束条件越多,课表越能让教师与学生满意.例如:

(1)尽量将专业课或者难度较大的课程安排在学生思维活跃的时间段;

(2)体育课应安排在下午或者上午的第二大节,因为体育课后人体疲惫不适宜安排专业性过强的课程.

2 算法概述

2.1 遗传算法

遗传算法是通过模拟生物界遗传选择和自然淘汰的生物进化过程的计算模型,借鉴了生物界适者生存、优胜劣汰的进化规律,从而演化的随机化搜索方法.遗传算法从一个种群开始,在这个种群中可能存在问题的潜在解,每个种群是由经过编码的N个个体组成,每个个体就是带有一定特征的染色体实体.在每一代中,选择适应度较大的个体进行培育,然后借助遗传学中的遗传算子进行多次组合交叉、变异等操作,产生出代表新的解集的种群.这样经过了多次演化之后得到的种群就可以看作问题的近似最优解.

遗传算法的流程如下:

(1)随机产生一定数量的初始种群,数量由业务需求定义.

(2)对全部个体进行适应度的评估,如果某个个体的适应度已经满足最优化的要求,则输出此个体,并结束计算.否则转向第(3)步.

(3)从所有个体中取出适应度较强的个体成为再生个体.

(4)依据交叉概率,变异概率生成新的个体.

(5)由上述两步交叉和变异产生新一代种群,然后返回第(2)步.

2.2 蚁群算法

蚁群算法是一个寻找最优路径的方法.蚂蚁在寻找食物的过程中,通过释放信息素留下信息,后面的蚂蚁就会根据路上的信息素来选择路径,信息素的浓度与行走的路程成反比,走的路途越长,信息素浓度越低,则越不容易找到,路途越短,信息素浓度含量越高.随着时间的推移最优路上的信息素浓度越大,最终蚁群会找到一个最优路径.

2.3 遗传-蚁群混合算法

遗传,蚁群算法是两大仿生算法,都有各自的优势和不足.遗传算法的优势在于在大范围内具有快速全局搜索的能力,但在处理反馈信息时利用率过低,容易过早的收敛,或求解到一定范围时会做大量的无用迭代,从而会降低求解过程中的效率.蚁群算法采用正反馈机制,具有较强的鲁棒性,使搜索过程不断收敛,有更好的全局优化能力.但是在搜索初期信息素分布较少时,求解速率较慢.

而排课问题的实质就是一个NP完全问题,影响排课因素的细微变动,尤其是信息量一点点的增加,都会给排课带来“组合爆炸”灾难,当排课规模较大时,单算法在排课问题中就表现出局限性,会出现排课时间较长、排出的课表无法令教师学生满意等现象.因此,本文将两算法结合应用于排课问题中,首先利用遗传算法在大范围内快速的生成信息素分布,再利用蚁群算法求出全局最优解,优势互补,可以减少求解的时间,提高精确率.

3 遗传-蚁群混合算法解决排课问题

3.1 遗传算法在排课问题中的应用

3.1.1 构造基因编码和染色体

实施遗传算法的第一步就是对需要解决问题的参数进行基因编码,从而进行相关的遗传操作.本文采用二进制对编码数据进行设计.如表1所示.

表1 编码方式

3.1.2 适应度函数

在遗传算法的进化过程中,其根据适应度函数来确定进化方向.适应度是对课表优劣的一种体现.适应度越大则证明课表的效果越优秀.因此适应度函数直接决定着排课方案的寻优速率和能否找到最优解.

所以这就需要制定一个合适的适应度函数(期望).在本文中,课表的期望值可以分为以下三种: 课程离散程度期望,节次优化度期望和特殊课程期望.

(1)课程离散程度期望

同一门课程安排的时间应该分布均匀,每周安排的时间不能分散也不能太集中.本文将每天的教学时间段分为4个,每周一共20个时间段.用编号相同课程的时差来表示离散程度的大小如表2所示.

表2 课程离散程度期望

每一个课程时差对应一个期望,期望函数公式为:

(2)节次优化度期望值

人体生物钟规律应与教学内容相匹配,逻辑思维活跃的时间段一般在早晨,而下午更容易疲倦所以学习效率较低.根据人体生物钟规律节次的不同的课程期望值也不同,如表3所示.

表3 节次优化度期望值

对于难度比较大的课程就可以安排在期望值高的节次上,对于节次期望值函数的公式为:

(3)特殊课程的期望值

特殊课程包含体育课与自习课,此类课程最好安排在下午的第二节.当体育课结束后,人体处于疲倦状态,不适于将专业性过强的课程安排在体育课后.如表4对特殊课程给出了不同的期望.

表4 特殊课程的期望值

对体育课排课就依据上表的期望值为:

应将课表中没有课程的时间段安排给自习课.则计算特殊课程期望值的公式为:

根据以上分析可得出适应度函数F,如下公式为:

式中,K1,K2,K3为调控期望值对总期望影响程度的参数.

3.1.3 种群操作

当形成初始种群,并设计好适应度函数后,下一步就是要进行遗传操作.遗传算法包括三个基本操作: 选择、交叉和变异.

(1)选择操作

选择操作就是依照适应度的值保留优良的个体,适应度越高证明越近似于最优解.本文中保留优良个体的依据是期望值方法,选择期望值高的个体进行交叉变异操作.

(2)交叉操作

交叉操作就是把两个个体的部分结构进行替换重组从而产生新的个体.根据选择操作的结果,选择两条染色体作为父代,进行交叉操作.为了防止染色体的结构发生更改,本文的交叉操作只针对教室和上课时间,这样教师和班级都没有发生改变,维持了染色体原本的结构.同时设定交叉概率为PJ,若PJ大于随机值r(0＜r＜1),就进行交叉操作.

(3)变异操作

变异操作能够随机的对个体的局部进行搜索,提高种群的多样化.本文中的变异操作

就是对染色体编码中教室和时间段的局部编码进行修改,可以提高染色体的适应度.同时设定变异概率为PG,若PG大于随机值r(0＜r＜1),就进行变异操作.

3.2 蚁群算法在排课问题中的应用

蚁群算法最初用于解决TSP(Traveling Salesman Problem),TSP具有广泛的代表意义,许多问题都可类似的抽象为TSP问题的求解.

因此以TSP来描述蚁群算法的模型: 一只蚂蚁要去n个有食物的地区,它先随机选择一个地方作为起点,然后在逐个到达所有地区,留下信息素,最后再返回起点,每个地区只能到达一次,蚂蚁要怎么样选择顺序才能使行程最短.下面建立蚁群算法的数学模型:

m为蚁群中的蚂蚁数量;n为问题的规模大小(有食物地方的个数);bi(t)为t时刻位于i地区的蚂蚁数量,故蚂蚁数量为:

其中,τij(t)为t时刻路径(i,j)上的信息素;µij(t)为蚂蚁从i到j地区的期望程度;pkij(t)为t时刻蚂蚁k从i转移到j的概率.

蚂蚁k是根据τij(t)的结果来决定该往哪个方向前进,一般会选择τij(t)值高的路径,则蚂蚁k在t时刻由i地转移到j的概率为:其中,α为信息启发因子,表示在蚂蚁选择行走路径时信息量的影响;μ为期望启发式因子,表示启发信息对蚂蚁选择路径时产生的影响程度.

在每只蚂蚁访问完所有的地区以后,每条路上的信息素浓度会发生变化,因此需要对信息素进行更新.

其中,ρ是信息素挥发系数(0＜ρ＜1),1-ρ表示路径残留的信息素量;Δ τij(t)为从i到j地区路上增加的信息素量;Δ τkij(t)为蚂蚁k在i到j地区路上留下的信息素量;Q为表示信息素浓度;Lk为蚂蚁k需要行走的路径长度.

3.2.1 蚁群算法的二分图模型

当遇到需要用图结构解决的问题时可以使用蚁群算法.在本文中,用蚁群算法解决排课问题,首先需将排课问题用图结构G来描述:

上式中,N是图的顶点;S是边的集合;C是边集有关的权值集合.

排课问题涉及五个要素,在蚁群算法中这五个要素的关系可转化为“课程,教师,班级”关系与“时间,教师”关系,排课问题就是解决这两个关系所构成的二分图的最大匹配问题.

(1)二分图的顶点集定义

在本文将“课程,教师,班级”的关系定义为RLSC,RLSC=L×S×C,RLSC的元素组成的集合为GLSC,称其为二分图左侧的顶点集.“时间,教室”的的关系为RTR,RTR=T×R,RTR的元素组成的集合为GTR,为二分图右侧的顶点集.

(2)二分图的边集定义

在排课中对教室的安排要满足两个要求: 一是安排人数不能大于教室座位数量,二是教室类型满足课程要求.因此,GLSC与GTR之间只有满足上述两个基本要求的节点才能进行连接.二分图的边集就是GLSC中的节点与GTR中相匹配节点的连线.

(3)二分图中边的权值

每条边上的权值根据具体课程时间的期望度来构造.例如,较难的专业课嵌入式教师对课程的期望度是上午的第二节课,那么GLSC中所有嵌入式课程与GTR中时间段为满足上午第二节的所有节点连接的边权值要尽可能的小.通过设置权值,才能更加合理的排出质量高的课表.

3.2.2 二分图模型

根据上节构造好的二分图模型,蚂蚁都是从左侧GLSC的顶点集出发,根据转移概率的值和边集在右侧GTR寻找匹配的节点.然后再返回至GLSC进行下一次的搜索工作,如此反复直到蚂蚁为GLSC的顶点集全部安排好上课地点和时间后,一次循环结束.

图1 二分图模型

图1展示了蚂蚁一次循环的过程,蚂蚁从A1出发,则蚂蚁此次行走的路径为:

其中,B1是第一次匹配的终点,A2是第二次匹配的起点,B1和A2可以看成是一个逻辑节点.同理,B4和A3在此次周游中也可以看成是相同的逻辑节点.

3.3 遗传-蚁群混合算法在排课问题中的应用

本文将遗传与蚁群算法进行混合,首先利用遗传算法生成信息素分布,在利用蚁群算法求出问题的精确解.在遗传算法生成信息素时,为了防止其在收敛后进行无用的迭代,要设置相应的终止条件.在运算工程中,当连续两次运算结果出现的差值小于0.01,或迭代100次,满足其中一个条件时可停止运算并将取得的最优解作为蚁群算法的初始解.蚁群算法在进行100次迭代之后,选择路径最短的解即可作为最优解.遗传-蚁群混合算法对排课问题解决步骤如图2所示.