基于遗传算法的排课系统

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于遗传算法的排课系统范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要:排课问题是一直是业界NP完全问题,牵涉到多约束,多条件,多目标等问题,遗传算法一直是当今解决排课问题的优先选择算法。把班级,课程,教师,教室等因素进行染色体编码,利用遗传算法的选择、交叉,变异等特性进行对排课因子进行选择筛选,得到的最优解,基本能满足当代大学排课的基本需求,在实际运行中有一定的实用价值。

关键词:排课;遗传算法;染色体编码;智能排课

中图分类号:TP311文献标识码:A 文章编号:1009-3044(2010)11-2732-02

近年来随着大学扩招,大学生人数的增加,每学期开学,排课问题一直是教务处一项艰巨的任务,使用人工手动排课对于大学这样一个庞大的课程体系来说是天方夜谭。课程,教师,教室,学生人数等限制问题更是难以解决,使用计算机排课已成为近年来的人们话题。各种排课工具层出不穷,却仍然满足不了实际工作中的需求。总的来说,当今教务排课工作的基本手段是手工排课为主,计算机排课为辅,所以研究一种灵活、高效,自动化的程度高的排课系统不但仍有意义而且迫切需求。

1 遗传算法的描述

遗传算法(Genetic Algorithms,GA)是根据自然界的选择和进化原理发展起来的高度并行、随机、自适应的随机搜索算法。其模拟达尔文的适者生存原理,每个种群所面临的问题是寻找一种对复杂和变化着的环境最有利的适应方式。

遗传算法维持一个潜在的群体(染色体、变量),定义一个函数为:

p(t)={ xt1......,xtn }

染色体通常形成是一串的数组,近年来基于实数编码的遗传算法也得到广泛的应用。每个解用其“适应值”进行评价其优劣程度。然后通过选择更新(t+1次迭代)个新的群体。新群体的成员通过杂交和变异进行变换,以形成新的解。杂交组合了两个亲体染色体的特征,并通过交换父代相应的片断形成了两个相似的后代。例如,如果父代用五维向量来表示,如下:

(a1,b1,c1,d1,e1) ,(a2,b2,c2,d2,e2)

在第二个基因后杂交,染色将产生后代

(a1,b1,c2,d2,e2)

杂交算子的意图是在不同潜在解之间进行信息交换。

变异是通过用一个等于变异率的概率随机地改变染色体上的一个或多个基因。变异算子的意图是向群体加入一些额外的变化性。

我们可以把遗传算法简化以下部骤:

1)产生初始遗传群体的方法。

2)用“适应值”评价解的适应度的评价函数。

3)改变后代组成的遗传算子。

4)遗传算子所使用的各种参数:

流程图如图1。

2 实际排课问题

整个排课流程如下:

1)初始化种群:对教师行编码,即产生染色体,形成一个初始化的二维表,包括对各种数据的初始化。

2)对各种冲突进行检测和消除,如果存在则消除它。

3)计算其适应度。

4)进行选择交叉和变异操作,这是遗传算法的三个基本属性。

5)则可以得出排课结果。

2.1 对排课问题进行染色体编码

排课系统的好坏染色体编码是关键,使用一个数椐表初始种那种群,设置有15个时间段,每天有3个时间段,共5天的课时量,在15个时间子段中填入教师等信息,称之为“基因”,

1个记录代表一个班级的课程表,称之为”染色体“;N个染色体组成“个体”;种群是由N个“个体”组成,在表中,一行代表班级本时间段的课表,一列代表该班级的1-15个时间片。首先把教师编码放入时间字段中。用随机函数产生1-15个数,如有存在相同的数据,则重新产生,直到所有的教师编码无重复的填入数字为止,则这个产生的初始表就构成初始种群。

采取的编码方式是教师号+班级号+课程号,其宽度为:6+1+4共11位。如图2所示。

1)教师号

教师号课标中一个重要的元素,在编码中,每一门课程和授课老师让他共同组合,以便解决一个老师上多个班级的冲突。

2)班级号

在教师号后面添加一个班级号是为了标识一个老师教授多个班级的问题,如用1来表示教师所教授的第一个班级,2表示第二个班级,以此类推, 如222202为教师号,则2222022表示老师教授的第二个班级。以此类推。

3)课程号

课程号是为了 第一个数字是解决一个老师教授多门课程的问题,如用1表示老师教师所教授的第一门课程,2表示第二门课程。以此类推。后面三位是标识课程的输在代码问题

2.2 排课问题的冲突与检测

对于同一时间段,同一个班级同时上一门以上课程的冲突,在编码过程中已经解决,不必考虑,我们需要消除的是同一时间,一个教师同时上一门以上课程的冲突:

1)首先读取二维数组kcb(15)第一行第一列的教师号;

2)然后与二维数组同一下一列的教师号进行比较,如有相同的重新产生随机数J,否则将两个数组元素的值互换。再重新比较。

3)继续读取该行第二列的教师号,重复2的操作,直到所有的元素的教师号不相同;

4)开始读取二维数组kcb(15)第一行第二列的教师号;重复2、3直到所有的元素的教师号不相同,既没有同时间段、一个教师同上一门的课程。

2.3 适应度函数

在实际排课中要排除一个合格、适用的系统,必须要考虑课程的适应度问题,如课程的离散度,具体课程的上课时间段,体育课,计算机课我们可以安排在下午,英语等课我们一般安排在上午。

2.3.1 英语,体育等课程的期望值

定义一个时间点,一周五天的期望值为:

一周上午1时间段的期望值为0;

一周上午2时间段的期望值为5;

一周下午3时间段的期望值为10;

1)查找英语,体育课程的位置,即查找二维数组的课程号编码,如是则读取其时间段,从而找出其相应的期望值Fx(i)(i=1,2,3,4.....15),并对期望求和。

2)检测自习课的期望值,即读取教师编码为空的时间片,对期望求和。Fz(i)(i=1,2,3,4.....15)

对所有的期望值求和,定义函数如下:

Fk=∑(Fx(i)+ Fz(i))

2.3.2课程的离散度的期望值

把一星期课程为不同的时间段。使用编号相同的课程的时间差来描写离散度,

查找每一门课程的位置,计算机出他们的时间差,然后查找出他们对应的离散度,并对其进行求和

Fls=∑(Fls(i))

2.3.3 总期望值

FIT=K1* Fk+K2* Fls

K1,K2为控制总期望值的影响参数(权重)。

2.3.4 设计遗传算子

1)选择操作

从群体中选择一些优质的个体,并复制到下一个群体中,代替原来较差的个体。适应度值是个体被选择的决定性因素。

2)交叉操作

交叉操作就是选择个体中一部分的与另外一个个体积习难改交换操作,如可以把2个父本分为前后2部分,第一部分后部与第2个副本前部相交生成第1个个体,第1个父本的前部与第2个父本的后部组合生成第2个个体。

3)变异算子

对于具有相同特性的染色体的2个基因位(如教师编码)之间,对其教师或者其他编码值进行交换,就成为变异操作,

3 结论

实现自动排课问题是一项艰巨的任务,但其意义非常重大,至今仍没有一套完整,成熟的方案来实现 。本文根据遗传算法的基本原理,并根据实际需求,大胆创新,对排课中的约束性等问题提出了一套适用的方案,基本满足了实际工作中的需求,但对于多项限制条件等排课问题求解,仍没有达到最优解,这对于多说研究人员来说是继续探讨的课题,希望在排课领域的研究有所长者给予指正。

参考文献:

[1] 孙建平,梅晓勇.关联规则在高校智能排课系统中的应用[J].计算机应用,2002(5):37,38,42.

[2] 王力.高校通用排课管理信息系统设计与实现[J].贵州工业大学学报,1999,28(1):87-90.

[3] 谭定英,蔡逸仪,李学征.基于遗传算法的排课系统研究[J].现代计算机:下半月版,2009(9).

[4] 陈江.基于遗传算法的自动排课问题的研究[D].杭州:浙江工业大学,2003.