学分制下研究生课程排课算法的设计与实现

发布时间：2020-06-02 17:18

【摘要】：进入21世纪以来,对于研究生的培养,我国提出新的要求,“改革研究生培养方式”,“实行弹性学制”,实行弹性学制建立在学分制的基础上。学分制改革背景下的研究生排课问题,相比于中小学以及职校,其课程的数据规模更大,加上近年来研究生招生范围的扩大,使得学分制下研究生课程排课问题的复杂度更高,已被证明是一种NP完全问题,传统的搜索算法很难求得该问题的最优解。遗传算法凭借其自身的特点,已经被广泛应用于解决该类问题。本论文首先分析了学分制下研究生排课问题的特点及需要满足的约束条件,并对这些条件进行量化,提出适应于解决该问题的适应度函数,然后借鉴遗传的思想展开算法的设计,在对学分制下研究生课程排列问题的特点的分析的基础上,对传统的遗传算法进行了多方面的改进,第一,根据待排课程的难排度对课程进行排序,有利于初始化种群的产生;第二,文中通过对问题的需求进行分析得出算法所依赖的数据库,以数据库数据结构为基础,提出了基于待排课程的染色体编码方式,使得涉及到的数据量更少,编码方式也更加简短,从而方便了问题的求解。第三,在交叉操作上,我们提出了均匀交叉和单点交叉相结合的交叉方式,先进行全局搜索使得遗传算法的收敛速度不会过于缓慢,再进行局部搜索这样就能够保证个体的形状不发生变化。最后实验表明,算法运行呈进化状态,其排课的结果也证明该算法也是合理有效的。
【图文】：

在选择操作之后，将选出的两个个体的结构进行部分替的操作。在遗传算法中标准的交叉方法是单点交叉，单择一个位置作为交叉点，然后两个个体都从该点切断，，。这种交叉方法可以使距离较近的等位基因仍保持在基因则会因此被分开，其优点是单点交叉不会破坏个体体仍保持原来的形状不变，缺点就是产生新个体的可能是所谓的多点交叉，对于多点交叉，可以随机的选择ｍ间间续地相互交换，产生新的后代，但在第一位变量与不做交换，其破坏性比单点交叉大，可以促进解空间的收敛，搜索更加健壮。除了单点交叉和多点交叉，第三点交叉和多点交叉将个体分成片段进行交叉的想法，均个点都作为潜在的交叉点，其中的信息交换和重组最为ｎｄ和Ｇｏｌｄｂｅｒｇ的积木块假设，单点交叉应比均匀交叉好，

１．某学生课程时间表。如表４．４所示，为学生的基本信息，包括学院、专业、逡逑班级等等。这里选择该学生是因为其背景相对比较复杂，不仅需要修班级课程和逡逑自选课程，还含有一门补修课程，如表４．５所示。逡逑表４．４学生基本信息逡逑ｓｔｕｄｅｎｔｌｄ邋（学生编号）Ａｃａｄｅｍｙ邋（学院）Ｍａｊｏｒ邋（专业）Ｃｌａｓｓ邋（班级）逡逑２２２０４逦学院１逦专业１逦１年级１班逡逑表４．邋５学生选课信息逡逑类别逦课程ＩＤ逡逑１２６０、邋１２６１、逡逑学生逡逑逦１２８２、１２７５逦逡逑１０２２、邋１０３８、逡逑
【学位授予单位】：南京师范大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：G643

【参考文献】

相关期刊论文 前10条

1 谢宗霖;刘亚君;霍伟敬;王金环;;基于整数规划的排课优化问题[J];计算机与现代化;2015年07期

2 吴红艳;;浅谈遗传退火算法在高校排课问题中的应用[J];科技展望;2015年02期

3 管妙娴;;如何提高院系两级教学管理模式下排课的科学性[J];湖北函授大学学报;2014年15期

4 马永杰;云文霞;;遗传算法研究进展[J];计算机应用研究;2012年04期

5 苏方方;张金玲;;贪心算法解决活动安排问题研究[J];软件导刊;2011年12期

6 耿幼平;方明;陈光;;模拟退火算法在排课问题中的应用[J];中山大学学报(自然科学版);2009年S1期

7 王帮海;李振坤;;基于贪婪算法的自动排课表系统的研究与实现[J];计算机工程与设计;2008年18期

8 王伟;余利华;;基于贪心法和禁忌搜索的实用高校排课系统[J];计算机应用;2007年11期

9 唐洪英;周敏;;基于分层分次、贪心算法的排课系统的设计与实现[J];微计算机信息;2006年03期

10 朱冠宇,王乘,席大春;利用遗传算法求解中学课表安排问题[J];计算机工程与应用;2004年27期

相关硕士学位论文 前2条

1 丁旭光;排课系统设计与排课算法研究[D];南昌大学;2009年

2 董启明;专家系统在自动排课中的应用与研究[D];长春理工大学;2006年

本文编号：2693507