遗传算法在大学排课问题中的应用概要.docx
《遗传算法在大学排课问题中的应用概要.docx》由会员分享，可在线阅读，更多相关《遗传算法在大学排课问题中的应用概要.docx（12页珍藏版）》请在冰点文库上搜索。
遗传算法在大学排课问题中的应用概要
遗传算法在大学排课问题中的应用
口王维陈满林胡冠字
（长春工业大学软件职业技术学院吉林・长春130012
摘要:
针对排课问题,基于遗传算法的特点分析了解决排课问题的可能性,介绍了排课原则,以及遗传算法在排课问题上的应用性研究,利用遗传算法进行编码,交叉、变异,以及进行冲突检测,用遗传算法解决这一复杂的NP问题。
关键词:
排课遗传算法最优解冲突检测
中图分类号:
024文献标识码:
A文章编号:
1007-3973（201009—167・02
当今时代,伴随着计算机技术的快速发展,许多繁琐的人工操作已经被计算机系统所取代。
排课系统作为高校教务管理系统中最重要也最复杂的部分之一,已经成为国内外众多高校以及软件公司的研究课题,在这方面也取得了许多的理论成果和实现方法。
因此,研究开发一个实用的排课系统具有十分重要的现实意义。
1研究背景
随着我国教育体制改革的不断深入和发展,高校的办学规模逐年扩大,因此,编排一张适用的、科学的课表已经成为每一所高校在新学期开始之前必须进行的一项极其重要工作。
简而言之,它具体的工作内容就是将课程、教师、教室和学生四者之间进行合理的调度分配,从而达到四者之间的完美结合,从而使整个教学活动能够正常、有序地顺利进行。
大学课表的编排不但数量多、规模大、涉及的因素多、限制条件多,而且结构复杂,要想编排出合理、科学的课表必然要消耗大量的时间与精力,它复杂性的原因在于排课中资源约束条件与特殊要求对有限时空目标的限制。
由于近几年各个高校连年扩招,使得课程安排的工作量逐年增大,学校自身问题的逐步暴露,这也给课程安排增加了许多的难度,这些问题主要包括:
教室资源的不足、师资力量的不足、多媒体教学设备的不足等,这些问题的出现对排课工作提出更高的要求。
伴随着科学技术的不断发展和提高,计算机具有的强大功能已经被人们所深刻地认识,计算机应用技术也已经逐渐进入人类社会的各个领域,同时在各个领域都发挥着非常重要的作用。
作为计算机应用技术的一部分,通过计算机进行排课,具有手工排课无法比拟的优点,包括:
排课速度快、省时省力、
一I・一・.‘・一・一・一・一・一・.‘・.I・.‘・.‘・■・一‘・一‘・一‘・■・.t・.‘・一・■・■・一・一I・一・■・.t・一・.t・■・一‘・一・一・一・一・一・.t・.‘・一・一・.‘・.I・一‘・一・■・40
使学生对所讲授的树种特征产生直观的感受,这样不仅调动了他们的兴趣,同时也大大提高了教学效果;其次,园林树木学教师本身应利用一切机会到各地考察、研究,在专业知识方面进一步完善自己,在课堂讲授中就会做到绘声绘色。
作为学生,则必须对实验和教学实习格外重视。
在教学时数不断缩短的情况下,理论课教学必须是突出重点,不可能面面俱到。
学生只有在实验和实习过程中,依靠自己亲手的观察和解剖,才能对一些结构、概念和术语理解透彻,?
使课内知识进一步深化,做到永生不忘。
园林树木学这门学科实践性很强,必须经过从课本到实际观察,再到课本几个来回的重复,才能够对树种的形态特征了如指掌。
如:
学生到山上实习,让他们投入到大自然的怀抱,在老师对现场树种的讲解下,学生边认树木边采集标本,通过大量的实物,使学生很轻松、自如掌握了知识要点,很顺利的就记住了每种园林树木的特征、特性,同时还培养学生观察、思维、动手、综合解决生产实际问题和创新等能力,与学生呆在枯燥的实验室里,面对变形的干标本相比,学习效果明显要强得多。
寓教于乐,在游玩中认识了不少树种,是最有效的授课方法。
4重视学生学法指导,培养学生自学能力
哈佛大学教学理念:
学习是为了有能力继续学习。
一个优秀的学生不是老师教出来的,而是在老师的指导下学出来的。
方法是运用知识的桥梁。
在教学过程中,教师只有依据学生的特点,结合相应的教学内容,有意识地渗透有科学性、有针对性的学法指导,融教法与学法为一体,才能使学生养成良好的学习习惯,掌握科学的学习方法,最终实现教师“授人以渔”,培养学生终身的学习能力。
例如,我与学生交流时发现,学生普遍感觉记忆园林树木种类特征、科属特征、拉丁文学名是一件很枯燥的事情,有些学生时间花费不少,就是记不住。
我告诉他们理解是记忆的前提,记忆是理解的过程,如果不理解而硬背,只能成为知识的“容器”。
并总结了在理论结合实际的基础上,运用主要树种法、常见法、本地法、要点法、比较归纳法、总论指导法、各论主体法、识别基础法等多种方法,实践效果良好。
如:
园林树木的科、属、种虽然很多,但相似的科与科、属与属、种与种之间的形态特征等却有一定的规律,采用比较法找到这一规律,即找出它们的相同特征和不同特征,记忆将会成为一件比较轻松的事情。
通过比较,不仅掌握的它们的规律所在,强化了记忆效果,更掌握了园林树木学的重要学习方法。
由理解到记忆抓知识的实质:
由分散到集中抓知识的积累;由累加到串联抓知识的结构:
由应试到应用抓知识的运用。
这样,学生在学习中通过主动思考,积极思维,就能实现学习目标。
学会学习是时代发展的需要,更是学生终身学习与发展的需要。
综上所述,教师在教学中要灵活运用各种有效的教学方法,努力探索,从而达到最佳教学效果。
参考文献:
【l】邱国金,孙贤琦,刘国华.高职《园林树木学》课程的教改研究与实践【J】.中国农业教育,2003.02.
【2】沈大刚.《园林树木学》课程的教改研究与实践【J】.安徽农业科学,2009.02.
【3】陈建.《园林树木学》教改初探【J】.安徽农业科学,2007.08.
——斛协论坛・2010年第9期（下——斛鲍
查找方便、检索迅速、可靠性较高、保密性较好、存储量较大、人工成本较低、使用寿命较长等。
这些优点可以极大地提高排课管理工作的效率。
排课系统是对一个教育单位而言是不可缺少的重要组成部分,排课效果的好坏直接影响到教学工作能否有序地、正常地开展,对于学校的领导来说也是一项至关重要的工作,因此排课系统必须为用户提供充足的信息以及快捷的查询手段。
利用计算机进行排课操作,任何具有使用者都能够清晰的看到教学中的各种信息,可以高效、快速的工作,这不但减轻了教务人员手Tf#课的工作,而且极大提高了管理工作的效率,可以合理高效地分配、利用教学资源,间接地提高了教学质量,推进了教学活动的良性循环。
因此,研究并改进一个排课系统具有十分重要的实际意义。
2排课原则
排课问题实质上一种资源竞争问题。
在排课过程中要全面考虑教师、课程、教室、时间、学生人数等多方面因素,做到统筹兼顾,才能排出即符合教学规律,又满足各方面要求的课程表。
一个好的课表应该既能符合学校的管理要求,又能满足所有参与者的基本要求,尽量使绝大多数课程的安排能够令学校师生满意。
为了达到这样的目的,在排课中必须遵守以下六个基本原则:
（1在同一时间段内,一位教师只能安排一门课程。
（2在同一时间段内,一个班级只能安排一门课程。
（3在同一时间段内,一问教室只能安排一门课程。
（4根据能提供的教室总数安排同一时间段内安排的课程总数,二者要相适应。
（5每门课程的学生人数不应大于所安排教室的座位数,二者也要相适应。
（6多媒体教室应合理安排,因为有的科目用多媒体设备教学的效果比较好,但是有的科目并不需要多媒体教室,如果安排了多媒体,就造成了教学资源的浪费。
同时,为了使排出的课表更具人性化、更合理、更科学,排课还需要考虑以下五个因素:
（1尽可能保证同一个班级连续的两门课之间更换教室的机率最小,或就近安排。
（2每门课程在一周内的上课时间尽可能合理分布。
（3同一门课程的不同上课时间应尽可能安排在同一间教室,同时要隔一天以上再安排,以给任课教师留出充足的备课和批改作业的时间,使学生也有足够的时间复习和消化所学的内容,并有时间预习下次课的内容。
（4学生每天必修课的安排尽可能趋于合理、平衡,应尽量避免出现全天有课,而第二天一天没课的情况。
（5满足个别教师（如外聘教师的特殊上课时间要求。
3遗传算法在排课问题中的应用
遗传算法应用类似基因演化的循环过程,它的演算过程如下:
（1根据排课的因素产生相关基因编码和染色体,并随机产生一定数目的初始种群,即一定数目的班级课程表。
（2对个体,即班级课程表适应度进行评估,如果个体的适应度与优化准则相符,则输出最佳个体和它所代表的最优解,并结束计算,否则进入第（3步。
（3依据适应度情况选择再生个体。
（4按照一定的交叉概率及交叉方法生成新个体。
（5按照一定的变异概率及变异方法生成新个体。
（6由交叉和变异产生新一代种群,之后返回第（2步,最后进行冲突检测与消除。
通常可利用编码技术对变量进行编码,将变量转化成适合群体进化的表达形式。
对目标函数进行处理操作,使其能够蕴含遗传算法的适应度函数。
这样,在群体进化的过程之中,适应度就能够反映模型的目标函数。
当群体进化结束的时候,适应度值最大的那个个体对应的目标函数值最小,这个个体即为最优解。
最佳个体的产生过程是这样的:
首先产生一个初始化种群,然后对初始化种群中的每一个个体进行适应度的计算,得出个体对环境的适应程度。
计算后的这个个体能否满足准则判定,如果能够满足,那么算法就找到了这个个体并停止汁算,如果不满足准则判定,那么算法将会对这个种群进行选择、交叉、变异等相关操作。
遗传操作的目的是从初始化种群中筛选出较优的个体,之后进行演变,对演变后的子代群体,再重新进行优化准则的判定,如此循环下去,直到找到一个最优的个体,或者不满足其它循环条件为止。
约束条件和优化的目标有轻重缓急的分别,约束条件必须满足,优先级别必须最高,同时,各种优化目标之间也有优先级的分别,应尽量满足级别较高的优化目标。
将它们都转化成罚值,而其罚值权则是不同的,高一级的罚值权比所有低级的罚值的和值还要大。
由此可以得出,采用静态定标罚值权的方法是不可取的,因此我们采用动态罚值权的定标方法。
遗传进化在进行选择的操作过程中,我们着眼于目标函数或者适应度函数的相对值而并不关心它的绝对值,确定这个个体目标函数的真正目的在于确定该个体在群体中的优劣,因此我们可以根据整个群体情况进行罚值权的统一定标,把各级的罚值用向量进行表示,此时,目标函数就是各级罚值的带权和。
如果想终止可以采用以下方法;
（1给定一个迭代步数;.
（2当设定与估计的最优解的距离小于某个范围时,就终止搜索:
（3当与最优解的距离连续若干步保持不变时,就终止搜索。
排课问题同样是一个N.P问题,无论应用哪种方法冲突问题的出现都不可能避免。
但是,解决冲突问题的方法有很多种,这里采用一种利用二进制0、1矩阵检测冲突的方法。
在冲突检测过程中其基本的约束条件为:
（1任何教师在同一时间最多只能安排一门课。
（2任何班级在同一时问最多只能安排一门课。
（3任何教室在同一时间最多只能有-I"1课程被安排。
为了避免冲突的出现,在本系统的设计、实现过程中引进了冲突检测函数,保证当排完一位教师的所有相关课程后,系统就会通过该冲突检测函数对这位教师课程安排的冲突情况进行检测并做出相应的修正。
参考文献:
【1】毕晓君.信息智能处理技术【M】.北京:
电子工业出版社,2010【2】陈强.通用高校排课算法研究【J】.科技广场,2006年第07期【3】张文修。
梁怡.遗传算法的数学基础（第2版【M1.西安:
西安交通大学出版社,2003.
【4】潘以锋.高校智能排课系统的算法【J】.上海师范大学学报（自然科学版,2006,（10.
——斛协论1ij・2010年第9期（下——
遗传算法在大学排课问题中的应用
作者:
王维,陈满林,胡冠宇
作者单位:
长春工业大学软件职业技术学院,吉林·长春,130012
刊名:
科协论坛（下半月
英文刊名:
SCIENCE&TECHNOLOGYASSOCIATIONFORUM
年,卷（期:
2010,""（9
被引用次数:
0次
参考文献（4条
1.毕晓君.信息智能处理技术[M].北京:
电子工业出版社,2010.
2.陈强.通用高校排课算法研究[J].科技广场,2006年第07期.
3.张文修,梁怡.遗传算法的数学基础（第2版[M].西安:
西安交通大学出版社,2003.
4.潘以锋.高校智能排课系统的算法[J].上海师范大学学报（自然科学版,2006,（10.
相似文献（10条
1.期刊论文张燕.宋锦斌基于遗传算法的排课系统-电脑知识与技术2010,6（11
排课问题是一直是业界NP完全问题,牵涉到多约束,多条件,多目标等问题,遗传算法一直是当今解决排课问题的优先选择算法.把班级,课程,教师,教室等因素进行染色体编码,利用遗传算法的选择、交叉,变异等特性进行对排课因子进行选择筛选,得到的最优解,基本能满足当代大学排课的基本需求,在实际运行中有一定的实用价值.
2.学位论文肖鹏遗传算法在排课系统中的应用研究2008
现代科学理论在研究与实践中存在大量与组合优化、自适应等相关的问题。
使用常规方法解决这类问题,除一些简单情况之外,人们对于大型复杂系统的优化和自适应问题的处理显得无能为力。
排课问题正是一个有约束的、多目标的组合优化时间表问题,并且已经被证明为一个NP完全问题。
遗传算法借鉴生物界自然选择和自然遗传机制,使用群体搜索技术,尤其适用于处理传统搜索方法难以解决的复杂的非线形问题。
经过近50年的发展,遗传算法在理论研究与实际应用中取得了巨大的成功,是一种非常有效的解决NP完全组合问题的方法。
本文结合湖北工业大学工程技术学院教务管理的实际情况,采用遗传算法求解排课问题,并从遗传算法的基本理论入手,首先,分析了遗传算法的特点、数学基础以及遗传操作和算法结构;其次,讨论了排课问题中的排课因素、主要约束条件与求解目标,分析了排课问题的组合爆炸性和不确定性,并用数学模型完整地描述了排课问题。
在实际的排课系统算法设计中采用运筹学中分层规划的思想,对具体问题应用遗传算法进行分步求解,设计了遗传算法的基因、适应度函数及成本函数,改进了单点交叉以及变异操作,确定了种群规模及遗传代数,设计并编程实现了一个基于遗传算法与调整算法相结合的排课系统。
系统经时间性能和排课性能测试,表明降低了排课复杂度,提高了排课效率。
该排课算法的实现很好地满足了工程技术学院复杂的排课管理需求,同时对其他高校排课系统的开发也具有参考价值。
3.期刊论文兰兆青.白艳萍.LanZhaoqing.BaiYanping遗传算法在排课问题中的应用-太原师范学院学报（自然科学版2008,7（1
在分析造成排课困难的各种因素的基础上,将遗传算法运用到解决排课问题中.并给出了该算法的详细设计（文中采用了二进制编码和矩阵编码相结合的编码方法;给出了带有权值的适应度函数;对染色体中的时间码采用映射同/异或交叉;采用两点变异的变异方法和排课模型;很好地解决了多约束条件下的排课问题.
4.学位论文熊婷基于遗传算法的高校排课系统研究2006
排课是学校教学管理中十分重要、又相当复杂的教学管理工作之一,尤其是随着高校扩招带来的在校学生人数剧增与学校教学资源紧缺之间的矛盾已经日趋严重,普通的手工排课已经越来越不能满足需求。
随着计算机技术的日益广泛使用,计算机辅助排课系统（CACSS已经成为高校教学管理中的一个重要的研究领域。
排课问题实际上是时间表优化的问题,由于其超大的求解规模和众多的约束条件,是运筹学领域和计算机领域一直致力寻求解决但没有得到解决的NP难解问题,即如何根据班级的课程设置、课程的周内次数以及利用现有的教室、教师资源进行科学的合理安排。
因此,国内外对排课算法的研究越来越活跃,纷纷走向探求排课算法的各类经验方法的求解道路。
本文首先阐述手工排课系统已远远不能胜任当今高校排课需要,然后具体阐述了自动排课系统在国内外的发展现状与趋势,通过细致分析近年来国内外各种有关排课算法与结合我国高等学校现有状况的基础上,提出了基于遗传算法的高校排课系统,并详细阐述了遗传算法设计中的编码方案以及遗传算子的实现方法。
根据高校排课系统的需求,给出了高校排课系统的设计与实现,从高校排课系统的实施结果看出,本文提出的基于遗传算法的高校排课系统不但能够减少排课人员的工作量,而且能够提高排课的准确性,从而具有良好的市场前景。
在系统实施过程中,成功地将排课系统与高校信息管理系统对接,从而使得排课系统能够更好的为高校管理系统服务。
5.期刊论文方江祎.段富基于遗传算法的排课问题分层研究-电脑开发与应用2010,23（5
分析了目前高校排课存在的问题,研究如何利用遗传算法解决排课问题以及冲突,并设计应该考虑的各种约束条件.把传统的排课问题分为时间排课和教室排课两个方面来研究,在时间排课方面又分为单目标排课和多目标排课两个步骤来考虑.通过计算机化管理的排课问题,能够有效地提高工作效率.6.学位论文李建丽基于遗传算法的排课系统研究2009
排课问题是典型的多重约束和组合优化问题,并且已经被证明是一个NP完全问题。
影响排课问题的因素不仅众多,而且各因素之间相互制约,加上不同的学校因各自情况不一,很难形成一个相对固定的排课模式。
借助计算机软件,实现排课的自动化和人性化,已经成为各高校教学管理人员的一个共识,也是解决排课问题的理想途径。
遗传算法是一种借鉴生物界自然选择和进化机制发展起来的高度并行、自适应的随机搜索算法。
由于其思想简单、易于实现以及表现出来的健壮性,是一种非常有效的解决NP完全问题的方法。
用遗传算法解决排课问题是一种较明智的选择。
本论文将遗传算法应用于排课问题的求解。
首先,分析了遗传算法的特点、数学基础以及遗传操作和算法结构,讨论了排课问题中的排课因素、主要约束条件与求解目标,分析了排课问题的组合爆炸性和不确定性,提出了排课问题求解方法的总体框架和技术路线。
其次,采用鲁棒性较好的遗传算法,针对遗传算法搜索效率较低的问题,深入研究了优化解法,构造了混合式的教师基因编码,较之传统编码方案,该编码方案更简单、更高效、更易于理解,并且极大地降低了排课遗传算法的复杂度。
在算法实现过程中,添加了冲突的检测和消除算子,设计了关键的优化遗传算子,完成了自动课程表编排系统。
7.期刊论文张帅.ZHANGShuai遗传算法在排课系统中的应用-电脑编程技巧与维护2009,""（8
随着高校招生规模的扩大,教务管理系统中的排课方式也显得越来越重要.本文讨论了排课问题中的影响因素、各类约束条件、求解目标以及求解难点,运用遗传算法的基本理论,研究了如何解决高校的排课问题.实践证明,利用遗传算法求解排课问题,其搜索过程带有智能性和并行性,并且操作简单,可以更少地依赖于实际问题的情况,从而能够有效地解决排课问题.
8.学位论文王仲华遗传算法求解排课问题的研究2006
排课问题是一个有约束的、多目标的组合优化问题,并且已经被证明为一个NP完全问题。
运用计算机进行自动排课既是高校教务管理的迫切需要,同时也有重要的理论意义。
但由于排课问题复杂多变,几十年来一直没有很好解决。
本文的目的就是要找到一种解决这种复杂问题的方法。
遗传算法是一种借鉴于生物界自然选择和进化机制发展起来的高度并行、自适应的随机搜索算法,是一种非常有效的解决NP完全的组合问题的方法。
本文将遗传算法应用于排课问题的求解,进行了以下几个方面研究工作:
1.系统完整地讨论了排课问题中的影响因素、主要约束条件、求解目标和难点,用数学模型完整地描述了排课问题,并提出了排课问题求解方法的总体框架和技术路线。
2.给出了排课问题的ERD和类图,设计了排课系统的数据结构,并以此对课表安排过程的各个子算法进行了研究。
3.针对排课问题研究了染色体编码方式以及遗传操作算子的设计,并引入多目标决策协调模型,提出了一种基于多目标决策协调模型的适应度计算方法,并改进了遗传算法一般结构,形成了一套多目标协同优化的排课算法。
4.以VC++为基本开发工具,MSSQLSERVER2000为后台数据库,设计和实现基于GA算法的排课测试系统。
通过一个实例分析了遗传算法的各个参数的设置对排课效率以及排课质量的影响,分析显示遗传算法的应用使所得结果令人满意,大大提高了工作人员的排课效率。
9.期刊论文谭保华.彭伟.TANBao-hua.PENGWei基于蚁群遗传算法的高校排课系统-计算机仿真2008,25（12传统的手工排课的方法在效率和合理度上存在较大的缺陷.而利用单纯的遗传算法和蚁群算法则存在着计算时间过长和易导致早熟收敛等缺点.为了解决问题,将蚁群算法与遗传算法相结合,结果发现使用蚁群遗传算法,可以有效地减少搜索空间,使种群在遗传过程按规则分区,在区间中喷洒信息素,染色适应度与种群区间交互,形成正反馈系统,驱动整个算法得到排课较优解.测试结果表明.蚁群遗传算法较大提高了高校排课系统中的效率和合理度.
10.学位论文梁健超基于遗传算法的排课系统设计与实现2006
排课工作不仅是各类型学校教学活动正常进行的前提条件,也是教学管理工作中的一个重要环节。
当前,如何编排出适应高校教学模式并最大程度满足师生教学习惯与喜好的课表,已经成为学校教学管理中较为复杂、最为棘手的难题之一。
排课问题的不仅影响因素众多,而且各因素间相互制约、排课实施的时间跨度长、环节复杂,加上不同的学校因各自情况不一,很难形成一个相对固定的排课模式。
借助计算机软件,实现排课的自动化和人性化,已经成为各高校中教学管理人员的一个共识,也是解决排课问题的理想途径。
广播电视大学是全国性的成人教育高等学校,自实施开放教育试点工作以来,教学模式不断创新,学生人数不断攀升,同时大多数学校都面临教学资源匮乏没有得到有效补充的问题,如何有效合理地利用教学资源也是该类学校同样需要面临的问题。
其中排课问题就是其中一个相当重要的问题。
排课问题是一个有约束、多目标的组合优化问题,在计算机应用范畴已经被证明是一个NP完全问题。
而遗传算法是一种借鉴于生物界自然选择和进化机制发展起来的高度并行、自适应的随机搜索算法,能非常有效地解决NP完全的组合问题。
本论文将遗传算法应用于排课问题的求解。
首先,系统完整地讨论了排课问题的影响要素、主要约束条件、求解目标和难点,提出了排课问题求解方法的总体框架和技术路线。
然后,根据电视大学的实际情况,从排课系统的需求分析出发,建立排课系统的数据模型以及体系结构。
接着,给出排课系统中遗传算法的设计及核心算法实现方法和步骤。
最后,说明了排课系统的总体设计方案、各模块功能结构及相应的实现方法。
该系统是在windowsXPProfessional操作平台上实现的,采用了Delphi作为开发工具,以Access2003作为后台数据库管理系统,设计并成功构建了基于遗传算法的自动排课系统。
本文链接:
授权使用:
华中师范大学（hzsfdx,授权号:
3b49a8af-4500-402a-a186-9e3a0129c26e
下载时间:
2010年11月26日
升级会员 