大学排课问题中的遗传算法设计

大学排课问题中的遗传算法设计

第32卷　第1期　　　　　延边大学学报(自然科学版)　　　　　Vol.32No.1()2006年3月　JournalofYanbianUniversityNaturalScience　Mar.2006

文章编号:100424353(2006)0120064205

大学排课问题中的遗传算法设计

赵光哲

(延边大学工学院计算机科学与技术专业智能信息处理研究室,吉林延吉133002)

摘要:排课问题实际上是时间表优化的问题,,是运筹学领域和计算机领域一直致力寻求解决但没有得到解决的NP.题,.

关键词:排课;编码;遗传算法

中图分类号:TP301.6,原因在于排课需要考虑教师、教室、课程分布、时间分配、,传统的人工排课相当麻烦而且容易出错,费时费力,其科学性、方便性更难保证.所以利用计算机进行自动排课的想法自然而生.自动排课系统实际上是时间表的优化问题(TimetableProblems,简记TTPs),属NP难解问题[1],即如何根据班级的课程设置、课程的周内次数以及利用现有的教室资源进行科学的合理安排.

遗传算法[2](GeneticAlgorithm,简记GA)是1975年美国Michigan大学J.Holland教授首次提出的,并逐渐发展成为一种迭代自适应启发式概率性搜索算法.近年来,遗传算法在求解优化问题中得到了成功的运用.GA是一种抽象于生物进化过程的、基于自然选择和生物遗传机制的优化技术,它是一种全局优化策略,能避免陷入局部最优.按照“优胜劣汰、适者生存”的原则,通过快速随机搜索力求找到最优解或次优解.遗传算法因在解决各类非线性问题时表现出的鲁棒性、全局最优性、可并行处理性及高效率而深受实际工作者的喜爱.本文针对大学排课问题,讨论了遗传算法设计中的编码方案以及遗传算子的实现方法.1　排课问题的基本问题

排课问题中,主要任务是将班级、教师、课程、教室安排在一周内某一不发生冲突的时间,保证课表在时间的分配上符合一切共性和个性的要求,在此基础上,使其安排在各个目标上并尽量达到全局最优.假设排课问题中有n个决策变量参数,k个目标函数和m个约束条件,目标函数约束条件和决策变量之间是函数关系,则排课最优化目标为

(1)　　maxmize　y=f(x)=(f1(x),f2(x)

,…,fk(x)),

(2)　　subjecttoe(x)=(e1(x),e2(x),…,em(x))≤0,

其中x=(x1,x2,…,xn)∈X,y=(y1,y2,…,yn)∈Y.这里的x表示决策向量,y表示目标向量,X表示决策向量x形成的决策空间,Y表示目标向量y形成的目标空间,约束条件e(x)确定决策向量的可行的取值范围.

收稿日期:2005-11-02

),男(朝鲜族),吉林延吉人,延边大学计算机应用技术专业硕士研究生.作者简介:赵光哲(1979—

大学排课问题中的遗传算法设计

　第1期赵光哲:大学排课问题中的遗传算法设计65

1.1　排课的硬约束条件

排课是将教师与学生在时间和空间上根据不同的约束条件进行排列组合,以使教学正常进行.这里的约束条件主要是为了避免冲突,避免冲突是排课问题中需要解决的核心问题.只有在满足约束条件和避免冲突的基础上,才能保证整个教学计划合理正常进行[3].对教师、教室、班级、时间、课程等几个因素进行最优化组合配置,才能保证充分发挥各资源优势和提高教学质量.如果说一张课表是有效的,则它至少应该满足以下硬约束条件:1)教师不能冲突,同一教师在同一时间不能教授两门课程;2)教室不能冲突,同一教室在同一时间不能安排两门课程;3)班级不能冲突,同一班级在同一时间不能安排两门课程.

1.2　排课的软约束条件

一张高质量的课表,除了应该满足上述硬约束条件外,.硬约束条件是衡量排课方案是否可行的标准,.可以根据学校的实际情况定义软约束条件,)均匀;2)教师对上课时间存在一定的喜好班级相邻的上课地点距离尽可能近;5);6)充分利用教室资源,上.

2　算法描述

遗传算法是基于生物进化理论的原理发展起来的一种广为应用的、高效的随机搜索与优化的方法.其具备以下特点:1)处理对象不是参数本身,而是对参数集进行编码的个体;2)同时处理群体中的多个个体,即对搜索空间的多个解进行评估,减少了陷入局部最优解的风险,同时实现了并行化;3)不需要搜索空间的知识和其他辅助信息,而且仅用适应度函数值来评价个体,在此基础上进行遗传操作,适应度函数不仅不受连续可微的约束,而且其定义域可以任意设定,这一特点使得遗传算法的应用范围大大扩展;4)采用概率变迁规则来指导搜索方向;5)具有自组织、自适应和自学习性.利用进化过程获取的信息自行组织搜索,适应度大的个体具有较高的生存概率,并获得更适应环境的基因结构.

遗传算法演算步骤包括初始化产生初始种群(InitializePopulation)、适应度评估(FitnessEvaluation)、遗传操作(GAoperation),遗传算法的伪码如下:

BEGIN:

　　I=0;

　　InitializeP(I);

　　FitnessP(I);

　　While(notTerminate2Condition)

　　{

I++;

　　GA2OperationP(I);

　　FitnessP(I);

　　}

END.

大学排课问题中的遗传算法设计

66延边大学学报(自然科学版)第32卷

2.1　基因编码

遗传算法中首要考虑的是如何表现其问题,即如何对染色体编码,使之适用于GA操作.在经典的遗传算法中,常采用整数编码、浮点编码、DNA编码、二进制编码等方法,编码方式的优劣关系到信息的完备表达、遗传操作算子的设计和执 …… 此处隐藏：3763字，全部文档内容请下载后查看。喜欢就下载吧 ……