学分制模式下基于遗传算法的排课系统的设计.doc
约34页DOC格式手机打开展开
学分制模式下基于遗传算法的排课系统的设计,33页共计20913字摘 要排课问题是一个多约束、多目标的优化问题，其实质是时间表问题，已经被确认为np完全问题。遗传算法作为一种随机搜索算法，利用群体搜索技术，对解决np问题非常有效。本文将遗传算法应用于学分制模式下的排课系统中，通过对排课因素和约束条件的深入分析，制定了排课问...
内容介绍
此文档由会员 bfxqt 发布
学分制模式下基于遗传算法的排课系统的设计
33页共计20913字
摘 要
排课问题是一个多约束、多目标的优化问题，其实质是时间表问题，已经被确认为NP完全问题。遗传算法作为一种随机搜索算法，利用群体搜索技术，对解决NP问题非常有效。
本文将遗传算法应用于学分制模式下的排课系统中，通过对排课因素和约束条件的深入分析，制定了排课问题的优化目标，设计出了适合于遗传操作的编码模型，给出了合理的适应度值的计算方法。通过对初始种群进行选择、交叉、变异等过程不断进化，取得了优化的课表。
在排课系统设计中，本文采用了面向对象的方法，设计了课表安排中的教室调度算法、基因填充算法、冲突检测算法，使得排课得以实现。利用真实的数据进行系统测试，并分析了各参数对遗传操作及结果的影响。
目 录
1 引言 1
2 遗传算法 2
2.1 遗传算法研究的内容 3
2.2 遗传算法的基本术语 4
2.3 遗传算法的基本思想 5
2.4 遗传算法的基本操作 6
3 排课系统的需求分析 8
3.1 排课系统的业务流程分析 8
3.2 排课因素分析 10
3.3 排课的约束条件 11
4 基于遗传算法的排课算法的描述 12
4.1 排课问题的目标分析 12
4.2 排课系统中的基本算法 15
4.2.1 排课算法的面向对象的应用 15
4.2.2 教室调度算法 17
4.2.3 基因初始化算法 18
4.2.4 冲突检测算法 19
4.3 排课问题中遗传算法的设计 19
4.3.1 遗传算法的编码 19
4.3.2 初始种群的产生 20
4.3.3 遗传操作的设计 20
4.3.4 适应度函数的设计 22
5 实验及结果分析 22
5.1 排课系统开发环境 22
5.2 参数设置对排课效率的影响 23
5.3 结果分析 26
6 总结与展望 27
参考文献 29
关键字：学分制模式；排课系统；遗传算法；多目标优化
参考文献
[1] 薛冬梅. 充分利用资源科学合理排课. 中原工学院学报, 2002, 13(7): 78-80
[2] Gotlieb. The Construction of Class-Teacher Time Tables. Proceeding IFIP Congress, 1963: 73-74
[3] 周明, 孙树栋. 遗传算法原理及其应用. 长沙: 国防工业出版社, 2002
[4] 吴金荣. 求解课表问题的分支定界法. 运筹与管理, 2002, 11(1): 17-22
[5] 何永太. 二部图再排课系统设计中的应用. 安徽水利水电职业技术学院学报, 2003, 9(3): 45-77
[6] 胡顺仁, 邓毅, 王铮. 基于高校排课系统中的图论问题研究. 计算机工程与应用, 2002, 10(4): 221-223
[7] 胡小兵, 鲁宏伟. 基于模糊专家系统的排课关键技术研究. 长沙电力学院学报(自然科学版), 2001, 16(4): 40-42
[8] 黄干平, 姚自珍, 张轶静. 使用模拟退火算法求解排课问题. 武汉大学学报(自然科学版), 2000, 46(5): 55-59
[9] 彭超. 禁忌搜索求解排课问题的研究.
[10] 张林. 基于蚁群算法的排课系统研究与设计. [硕士论文]. 合肥: 安徽大学, 2005
[11] 郑立平, 郝忠孝. 遗传算法理论综述. 计算机工程与应用, 2003, 21: 50-54
[12] 王志美, 陈传仁. 遗传算法理论及其应用发展. 内蒙古石油化工, 2006, 9: 44-45
[13] 王小平, 曹立明. 遗传算法：理论、应用及软件实现. 西安: 西安交通大学出版社, 2002
[14] 薛华成. 管理信息系统. 北京: 清华大学出版社, 2003
[15] 蔡淑琴. 管理信息系统. 北京: 科学出版社, 2004
[16] 邹跃. 人性化排课算法的构造与设计. 重庆科技学院学报, 2006, 8(4): 90-93
[17] 林志雄. 排课数学模型及其算法. 龙岩学院学报, 2006, 24(6): 9-12
[18] 王昊亮, 李刚. Visual C#程序设计教程. 北京: 清华大学出版社, 2003
[19] (美) Jason Price, Mike Gunderloy. Visual C#从入门到精通. 北京: 电子工业出版社, 2003
[20] 萨师煊, 王珊. 数据库系统概论. 北京: 高等教育出版社, 2002
[21] 李律松, 陈少刚, 沈刚. Visual C# 数据库高级教程. 北京: 清华大学出版社, 2005
[22] 王晟. Visual C#.NET 数据库开发经典案例解析. 北京: 清华大学出版社, 2005
[23] Chris Ullman, John Kauffman and etc. Beginning ASP.NET 1.1 with Visual C# .NET 2003. Wrox Press Ltd, 2004
[24] 何鹏飞, 王政. C#实用编程百例. 北京: 清华大学出版社, 2004
33页共计20913字
摘 要
排课问题是一个多约束、多目标的优化问题，其实质是时间表问题，已经被确认为NP完全问题。遗传算法作为一种随机搜索算法，利用群体搜索技术，对解决NP问题非常有效。
本文将遗传算法应用于学分制模式下的排课系统中，通过对排课因素和约束条件的深入分析，制定了排课问题的优化目标，设计出了适合于遗传操作的编码模型，给出了合理的适应度值的计算方法。通过对初始种群进行选择、交叉、变异等过程不断进化，取得了优化的课表。
在排课系统设计中，本文采用了面向对象的方法，设计了课表安排中的教室调度算法、基因填充算法、冲突检测算法，使得排课得以实现。利用真实的数据进行系统测试，并分析了各参数对遗传操作及结果的影响。
目 录
1 引言 1
2 遗传算法 2
2.1 遗传算法研究的内容 3
2.2 遗传算法的基本术语 4
2.3 遗传算法的基本思想 5
2.4 遗传算法的基本操作 6
3 排课系统的需求分析 8
3.1 排课系统的业务流程分析 8
3.2 排课因素分析 10
3.3 排课的约束条件 11
4 基于遗传算法的排课算法的描述 12
4.1 排课问题的目标分析 12
4.2 排课系统中的基本算法 15
4.2.1 排课算法的面向对象的应用 15
4.2.2 教室调度算法 17
4.2.3 基因初始化算法 18
4.2.4 冲突检测算法 19
4.3 排课问题中遗传算法的设计 19
4.3.1 遗传算法的编码 19
4.3.2 初始种群的产生 20
4.3.3 遗传操作的设计 20
4.3.4 适应度函数的设计 22
5 实验及结果分析 22
5.1 排课系统开发环境 22
5.2 参数设置对排课效率的影响 23
5.3 结果分析 26
6 总结与展望 27
参考文献 29
关键字：学分制模式；排课系统；遗传算法；多目标优化
参考文献
[1] 薛冬梅. 充分利用资源科学合理排课. 中原工学院学报, 2002, 13(7): 78-80
[2] Gotlieb. The Construction of Class-Teacher Time Tables. Proceeding IFIP Congress, 1963: 73-74
[3] 周明, 孙树栋. 遗传算法原理及其应用. 长沙: 国防工业出版社, 2002
[4] 吴金荣. 求解课表问题的分支定界法. 运筹与管理, 2002, 11(1): 17-22
[5] 何永太. 二部图再排课系统设计中的应用. 安徽水利水电职业技术学院学报, 2003, 9(3): 45-77
[6] 胡顺仁, 邓毅, 王铮. 基于高校排课系统中的图论问题研究. 计算机工程与应用, 2002, 10(4): 221-223
[7] 胡小兵, 鲁宏伟. 基于模糊专家系统的排课关键技术研究. 长沙电力学院学报(自然科学版), 2001, 16(4): 40-42
[8] 黄干平, 姚自珍, 张轶静. 使用模拟退火算法求解排课问题. 武汉大学学报(自然科学版), 2000, 46(5): 55-59
[9] 彭超. 禁忌搜索求解排课问题的研究.
[10] 张林. 基于蚁群算法的排课系统研究与设计. [硕士论文]. 合肥: 安徽大学, 2005
[11] 郑立平, 郝忠孝. 遗传算法理论综述. 计算机工程与应用, 2003, 21: 50-54
[12] 王志美, 陈传仁. 遗传算法理论及其应用发展. 内蒙古石油化工, 2006, 9: 44-45
[13] 王小平, 曹立明. 遗传算法：理论、应用及软件实现. 西安: 西安交通大学出版社, 2002
[14] 薛华成. 管理信息系统. 北京: 清华大学出版社, 2003
[15] 蔡淑琴. 管理信息系统. 北京: 科学出版社, 2004
[16] 邹跃. 人性化排课算法的构造与设计. 重庆科技学院学报, 2006, 8(4): 90-93
[17] 林志雄. 排课数学模型及其算法. 龙岩学院学报, 2006, 24(6): 9-12
[18] 王昊亮, 李刚. Visual C#程序设计教程. 北京: 清华大学出版社, 2003
[19] (美) Jason Price, Mike Gunderloy. Visual C#从入门到精通. 北京: 电子工业出版社, 2003
[20] 萨师煊, 王珊. 数据库系统概论. 北京: 高等教育出版社, 2002
[21] 李律松, 陈少刚, 沈刚. Visual C# 数据库高级教程. 北京: 清华大学出版社, 2005
[22] 王晟. Visual C#.NET 数据库开发经典案例解析. 北京: 清华大学出版社, 2005
[23] Chris Ullman, John Kauffman and etc. Beginning ASP.NET 1.1 with Visual C# .NET 2003. Wrox Press Ltd, 2004
[24] 何鹏飞, 王政. C#实用编程百例. 北京: 清华大学出版社, 2004
