基于遗传与模拟退火算法的排课系统研究.doc

《基于遗传与模拟退火算法的排课系统研究.doc》由会员分享，可在线阅读，更多相关《基于遗传与模拟退火算法的排课系统研究.doc（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、摘 要随着现代社会教育和计算机的不断改革与发展，综合教学网络已经应用到中小学、高中、大学的教学管理领域中，其中，微机排课的系统应用的尤其广泛。排课问题被证明是NP完全类问题之后，人们才注重排课系统算法的研究。排课问题本质上是一个具有多约束限制的多目标组合优化问题，虽然对于排课问题有很多的算法，比如贪婪算法、专家系统算法、整数规划算法、图论算法、遗传算法等等，但是这些算法只是针对一个实际问题，并不具有通用性，目前排课软件不多的原因也在此。为了有效的解决这个问题，本文准备从以下几个步骤着手：我们首先要了解课程表制定的原则，在此基础上进行大量的需求分析,因为我们的排课系统是针对大学里面的学生、老师提

2、出来的，所以从学生、老师、还有一个系统管理员三方面来分析，从而建立系统的总体框架，并给出系统的E-R图，从大量的数据中，对数据库进行分析，并建立系统的数学模型。 然后在得到数学模型后，在遗传算法的基础上进行分析，具体包括然对基因和染色体编码、初始种群大小、适应度函数、遗传算子、控制参数等操作，在此过程中，我们加入模拟退火算法，对遗传算法中的遗传因子加以改进。最后在以上基础上，在VC+平台上，利用SQL数据库，得到实现系统的编程代码，从而实现实现管理员、学生、老师功能模块。为了检验其可行性，进行实例测试。关键词：排课；遗传算法；模拟退火；适应度函数- I -The Format Criterio

3、n of Masters Degree Paper of DUTAbstractContents of the abstract. Times New Roman. Key Words：Write Criterion; Typeset Format; Masters Degree Paper- III -目 录摘 要IAbstractII引 言1第一章 绪论21.1 课题的研究背景及意义21.2 排课问题的研究现状21.2.1 国外现状21.2.2 国内现状21.3 课题研究目标21.4 文章的组织结构3第二章 排课系统简介42.1 排课系统的概述42.1.1 课程表问题42.1.2 排课系统

4、常用的算法42.2 排课系统需求分析52.2.1 管理员模块52.2.2 教师模块52.2.3 学生模块52.3 排课系统数据分析62.4 排课系统约束因素72.4.1 排课系统的硬性因素分析72.4.2 排课系统的软性因素分析7第三章 遗传算法83.1 遗传算法基本简介83.1.1 遗传算法由来及其特点83.1.2 遗传算法的主要思想83.1.3 基本遗传算法的表示83.2 遗传算法的基本操作方法83.3 遗传算法的应用步骤83.4 遗传算法的实现83.5 遗传算法的自我改进8第四章 基于遗传算法的模拟退火算法94.1 模拟退火算法简介94.2 遗传与模拟退火相结合的算法9第五章 排课系统整

5、体设计与实现105.1 排课系统数据库分析105.1.1 排课系统的E-R表示图105.1.2 数据表设计105.2 建立排课问题的数学模型105.2.1 排课因素数学化表示105.2.2 排课约束数学化表示105.2.3 排课系统的目标函数化表示105.3 遗传算子的运用105.3.1 编码105.3.2 种群初始化105.3.3 适应度函数105.3.4 遗传操作105.4 模拟退火过程分析105.5 终止条件10第六章 算例应用11第七章 总结与展望12参 考 文 献13附录A 附录内容名称16攻读硕士学位期间发表学术论文情况17致 谢18大连理工大学学位论文版权使用授权书19引 言从引

6、言开始，是正文的起始页，页码从1开始编排。引言包含的内容：说明论文的主题和选题的范围；对本论文研究主要范围内已有文献的评述；说明本论文所要解决的问题。注意不要与摘要内容雷同。建议与相关历史回顾、前人工作的文献评论、理论分析等相结合，如果引言部分省略，该部分内容在正文中单独成章，标题改为绪论，用足够的文字叙述。注意：是否如实引用前人结果反映的是学术道德问题，应明确写出同行相近的和已取得的成果，避免抄袭之嫌。书写格式说明：标题“引言”选用模板中的样式所定义的“引言”；或者手动设置成字体：黑体，居中，字号：小三，1.5倍行距，段后1行，段前为0行。引言正文选用模板中的样式所定义的“正文”，每段落首行

7、缩进2字；或者手动设置成每段落首行缩进2字，宋体，小四，多倍行距 1.25，段前、段后均为0行，取消网格对齐选项。第一章 绪论 1.1 课题的研究背景及意义1.2 排课问题的研究现状1.2.1 国外现状1.2.2 国内现状1.3 课题研究目标1.4 文章的组织结构第二章 排课系统简介2.1 排课系统的概述2.1.1 课程表问题图在正文中的格式示例如图2.1所示。图2.1 样式Fig. 2.1 Manner表、图序号后面，同样适当留空（汉字状态敲两次空格键）。图2.1显示了论文模板中所定义的样式选择方法。使用鼠标选择相应的样式，对应的文字格式就发生相应改变。2.1.2 排课系统常用的算法（1）

8、图的绘制方法 插图、照片应尽量通过扫描粘贴进本文。 简单文字图可用WORD直接绘制。（2） 图的位置 图居中排列。 图与上文之间应留一空行。 图中若有附注，一律用阿拉伯数字和右半圆括号按顺序编排，如注1），附注写在图的下方。（3） 图的版式 “设置图片格式”的“版式”为“上下型”或“嵌入型”，不得“浮于文字之上”。 图的大小尽量以一页的页面为限，不要超限，一旦超限要加续图。（4） 图名的写法 图名居中并位于图下，编号应分章编号，如图2.1。 图名与下文留一空行。 图及其名称要放在同一页中，不能跨接两页。 图内文字清晰、美观。 中文图名设置为宋体，五号，居中。英文名称设置为Times New R

9、oman，五号，居中。2.2 排课系统需求分析2.2.1 管理员模块2.2.2 教师模块2.2.3 学生模块2.3 排课系统数据分析2.4 排课系统约束因素2.4.1 排课系统的硬性因素分析关于主题法的起源众说不一。国内有人认为“主题法检索体系的形式和发展开始于1856年英国克雷斯塔多罗（Crestadoro）的图书馆编制目录技术一书”，“国外最早采用主题法来组织目录索引的是杜威十进分类法的相关主题索引”1。也有人认出为“美国的贝加逊富兰克林出借图书馆第一个使用了主题法”2-4。2.4.2 排课系统的软性因素分析引用的文献在正文中用方括号和阿拉伯数字按顺序以右上角标形式标注在引用处。第三章 遗

10、传算法3.1 遗传算法基本简介3.1.1 遗传算法由来及其特点大连理工大学印刷厂统一制作。3.1.2 遗传算法的主要思想单面打印。3.1.3 基本遗传算法的表示单面打印。3.2 遗传算法的基本操作方法3.3 遗传算法的应用步骤如果是一页，单面打印；如果两页，双面打印；如果三页，第一、二页双面打印，第三页单面打印。3.4 遗传算法的实现单面打印。3.5 遗传算法的自我改进第四章 基于遗传算法的模拟退火算法4.1 模拟退火算法简介4.2 遗传与模拟退火相结合的算法第五章 排课系统整体设计与实现5.1 排课系统数据库分析5.1.1 排课系统的E-R表示图5.1.2 数据表设计5.2 建立排课问题的数

11、学模型5.2.1 排课因素数学化表示5.2.2 排课约束数学化表示5.2.3 排课系统的目标函数化表示5.3 遗传算子的运用5.3.1 编码5.3.2 种群初始化5.3.3 适应度函数5.3.4 遗传操作5.4 模拟退火过程分析5.5 终止条件第六章 算例应用第七章 总结与展望参 考 文 献标题“参考文献”不可省略，选用模板中的样式所定义的“参考文献”；或者手动设置成字体：黑体，居中，字号：小三，1.5倍行距，段后1行，段前为0行。参考文献内容设置成字体：宋体，居中，字号：五号，多倍行距1.25，段前、段后均为0行，取消网格对齐选项。参考文献的著录，按论文中引用顺序排列。参考文献数量不少于20

12、篇，其中期刊不少于10篇，并且包含一定数量的外文期刊。文献类型标志参考国家标准 GB/T 77142005，如下表：文献类型标志代码普通图书M会议录C汇编G报纸N期刊J学位论文D报告R标准S专利P数据库DB计算机程序CP电子公告EB按照引用的文献类型不同使用不同的方法，示例如下：1 普通图书1 广西壮族自治区林业厅.广西自然保护区M.北京:中国林业出版社,1993. 2 蒋有绪,郭泉水,马娟,等.中国森林群落分类及其群落学特征M.北京:科学出版社,1998.3 International Federation of library Association and Institutions. N

13、ames of persons: national usages for entry in catalogues M.3rd ed. London: IFLA International office for UBC, 1977.2 期刊中析出的文献1 李炳穆.理想的图书馆员和信息专家的素质与形象J.图书情报工作,2000(2):5-8. 2 陶仁骥.密码学与数学J.自然杂志,1984,7(7):527. 3 亚洲地质图编目组. 亚洲地层与地质历史概述J.地质学报,1978,3:104-208. 4 DES MARAIS D J, STRAUSS H , SUMMONS R E, et al.

14、 Carbon isotope evidence for the stepwise oxidation of the Proterozoic environment J.Nature ,1992,359:605-609.3 论文集、会议录1 中国力学学会.第3届全国实验流体力学学术会议论文集C.天津:出版者不祥,1990. 2 ROSENTHALL E M. Proceedings of the Fifth Canadian Mathematical Congress, University of Montreal, 1961C. Toronto: University of Toronto

15、Press,1963.4 专著中析出的文献1 国家标准局信息分类编码研究所.GB/T 2659-1986 世界各国和地区名称代码S/全国文献工作标准化技术委员会.文献工作国家标准汇编:3.北京:中国标准出版社,1988:59-92. 2 韩吉人.论职工教育的特点G/中国职工教育研究会.职工教育研究论文集.北京:人民教育出版社,1985:90-99. 3 FOURNEY M E. Advances in holographic photoelasticity C/American Society of Mechanical EngineersApplied Mechanics DivisionS

16、ymposium on Applications of Holography in Mechanics, August 23-25,1971,University of Southern California, Los Angeles, California. New York：ASME,c1971:17-38. 4 MARTIN G. Control of electronic resources in AustraliaM/PATTLE L W , COX B J. Electronic resources: selection and bibliographic control. New

17、 York : The Haworth Press,1966:85-96. 5 学位论文1 张志祥. 间断动力系统的随机扰动及其在守恒律方程中的应用D.北京:北京大学数学学院,1998. 2 CALMS R B. Infrared spectroscopic studies on solid oxygen D. Berkeley: Univof California ,1965.6 专利文献1 刘加林. 多功能一次性压舌板:中国,92214985.2P.1993,04,14. 2 河北绿洲生态环境科技有限公司.一种荒漠化地区生态植被综合培育种植方法:中国,01129210.5P/OL.2001

18、-10-242002-05-28.http:/211.152.9.47/sipoasp/zlijs/hyjs-yx-new.asp?recid=01129210.5& leixin. 3 KOSEKI A ,MOMOSE H, KAWAHITO M, et al .Compiler :US,828402P/OL. 2002-05-252002-02-28. http:/FF&p1 & u =netahtml/PTO/search-bool.html & r = 5 & f=G& l = 50& col = AND & d =PG01 & sl =IBM .AS. & 0S =AN/IBM &

19、RS =AN/IBM. 7 科技报告1 USDepartment of Transportation Federal Highway Administration. Guidelines for handling excavated acid-producing materials, PB 91-194001R. Springfield: U.S. Department of Commerce National Information Service,1990. 2 World Health Organization. Factors regulating the immune respons

20、e: report of WHO Scientific GroupR. Geneva: WHO, 1970. 8 报纸中析出文献1 丁文祥. 数字革命与竞争国际化N.中国青年报,2000 ,11,20(15). 2 张田勤. 罪犯DNA库与生命伦理学计划N.大众科技报,2000,11,12(7).9 电子文献（包括专著或连续出版物中析出的电子文献） 1 江向东.互联网环境下的信息处理与图书管理系统解决方案J/OL.情报学报, 1999, 18(2):42000-01-18. 2 萧钰.出版业信息化迈入快车道 EB/OL. (2001,12,19)2002,04,15. 3 METCALF S

21、W. The Tort Hall air emission studyC/OL /The International Congress on Hazardous Waste, Atlanta Marriott Marquis Hotel, Atlanta, Georgia, June 5-8, 1995: impact on human and ecological health 1998,09,22. http:/atsdrl.atsdr.cdc.gov:8080/cong95.html. 4 TURCOTTE D L. Fractals and chaos in geology and g

22、eophysicsM/OL. Mew York: Cambridge University Press, 19921998,09,23. http:/www.seg.org/reviews/mccorm30.html. 附录A 附录内容名称以下内容可放在附录之内：（1） 正文内过于冗长的公式推导；（2） 方便他人阅读所需的辅助性数学工具或表格；（3） 重复性数据和图表；（4） 论文使用的主要符号的意义和单位；（5） 程序说明和程序全文。这部分内容可省略。如果省略，删掉此页。书写格式说明：标题“附录A 附录内容名称”选用模板中的样式所定义的“附录”；或者手动设置成字体：黑体，居中，字号：小三，1

23、.5倍行距，段后1行，段前为0行。附录正文选用模板中的样式所定义的“正文”，每段落首行缩进2字；或者手动设置成每段落首行缩进2字，字体：宋体，字号：小四，行距：多倍行距 1.25，间距：前段、后段均为0行。攻读硕士学位期间发表学术论文情况仅列出硕士生攻读硕士学位期间发表与学位论文有关的学术论文，并注明属于学位论文内容的部分（章节），所有作者及其顺序、所发表的刊物名称（包括主办单位、是否被SCI、EI检索期刊）、时间、期号与页码。其他时间或与学位论文内容（章节）无关的论文不得列出。书写格式说明：标题“攻读硕士学位期间发表学术论文情况”选用模板中的样式所定义的“发表学术论文情况”；或者手动设置成字

24、体：黑体，居中，字号：小三，1.5倍行距，段后1行，段前为0行。“攻读硕士学位期间发表学术论文情况”正文选用模板中的样式所定义的“正文”，每段落首行缩进2字；或者手动设置成每段落首行缩进2字，字体：宋体，字号：小四，行距：多倍行距 1.25，间距：前段、后段均为0行。例：1作者1，作者2. 中国科学，2004年，卷（期）：起始页码-终止页码. 主办单位：中国科学院。SCI检索期刊，本文SCI检索号：123DX。（本硕士学位论文第一章）注：学位论文作者，加黑。阅后删除此文本框。致 谢 学位论文中不得书写与论文工作无关的人和事，对导师的致谢要实事求是。一同工作的同志对本研究所做的贡献应在论文中做明

25、确的说明并表示谢意。这部分内容不可省略。书写格式说明：标题“致谢”选用模板中的样式所定义的“致谢”；或者手动设置成字体：黑体，居中，字号：小三，1.5倍行距，段后1行，段前为0行。致谢正文选用模板中的样式所定义的“正文”，每段落首行缩进2字；或者手动设置成每段落首行缩进2字，字体：宋体，字号：小四，行距：多倍行距 1.25，间距：前段、后段均为0行。- 17 -大连理工大学硕士学位论文注：页眉，居中，宋体，五号，统招、单考硕士、高校教师在职申请硕士学位、同等学历硕士填写内容为“大连理工大学硕士学位论文”；工程硕士、MBA、EMBA、MPA填写内容为“大连理工大学专业学位硕士学位论文”。阅后删除此文本框。注：此页为封底。阅后删除此文本框。大连理工大学学位论文版权使用授权书本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印、或扫描等复制手段保存和汇编本学位论文。学位论文题目： 作 者 签 名 ： 日期： 年 月 日导 师 签 名 ： 日期： 年 月 日注：此页内容不需要任何改修，手写签名和日期即可。阅后删除此文本框。