基于遗传和禁忌搜索算法排课系统探讨与实现

排课问题是学校教学管理中十分重要而又复杂的管理工作之一,随着课程的增多,学生人数的增加,在教室资源有限的情况下,要在短期内排出一张令所有教师和班级都满足的课表难度相当大,它是一个有约束的、多目标的组合优化问题,并且已被证实是一个NP完全问题。本文分析了大学课表问题的一般性质以及各种求解方案的上风和不足,并针对目前国内高校的教学实际设计了大学课表问题的模型。该模型考虑了教学实际中所涉及的一般因素和约束,由于遗传算法是一种适合求解带有多参数、多变量、多目标和在多区域但连通性较差的NP—HARD优化问题的智能优化算法,所以本文考虑用遗传算法来解决排课问题,但是遗传算法具有早熟的现象,很快收敛到局部最优而非全局最优解,因此结合了局部搜索方法之一的禁忌搜索算法,用遗传算法结合禁忌搜索算法来解决排课问题,对比比较和计算分析,取得了良好的效果。本文主要进行了以下几个方面的研究工作:1、系统讨论了排课问题中的影响因素、主要约束条件、求解目标和难点,用数学模型描述了排课问题。2、设计了排课系统的数据结构,并对一些子算法进行研究。3、研究染色体编码和遗传算子,并在变异阶段用禁忌搜索算法来实现,形成一个多目标的优化排课算法。4、以VS2005为开发工具,SQLSERVER2000为数据库实现了GA(GeneticAlgorithm)结合TS(TabuSearch)的智能排课系统,分析显示该系统能完成预期要求,结果令人满足。【关键词】：排课问题遗传算法禁忌搜索
【论文提纲】：摘要4-5Abstract5-13第一章绪论13-231.1课题背景131.2研究的意义及方法13-141.3排课问题研究综述14-201.3.1基于传统数学和运筹学的方法141.3.2基于人——机交互的方法141.3.3基于人工智能的方法14-151.3.4基于启发式算法的方法15-191.3.5遗传算法与其他搜索技术的比较19-201.4国内外研究现状20-211.5本文主要特色211.6本文的组织结构21-23第二章排课问题分析23-272.1排课问题概述23-242.2排课问题的数学描述24-262.2.1排课问题因素24-252.2.2排课问题中约束的描述252.2.3排课问题的优化求解模型25-262.3排课问题的求解方案262.4本章小结26-27第三章排课问题的算法设计27-363.1排课问题的双目标分析27-283.1.1班级课时日分布优度273.1.2班级日组合优度27-283.2排课问题的GATS算法设计28-343.2.1GA编码283.2.2初始群体的产生及冲突的消除28-293.2.3适应度函数的定义和计算29-303.2.4GA的运行30-343.3与其他排课算法的比较34-353.3.1关联规则FP—growth算法343.3.2基于时间位图迭加匹配算法343.3.3基于分组优化决策算法34-353.3.4分支定界算法353.3.5有限回溯353.4本章小结35-36第四章排课问题的系统分析36-454.1系统开发模式36-384.2排课系统流程图38-394.3数据流程图39-404.4数据表分析404.5系统架构约束与目标40-414.6系统整体框架41-424.7系统安全架构424.8功能模块分析42-434.9系统的非功能性需求43-444.10本章小结44-45第五章系统设计45-645.1选择VS.net作为开发工具优点455.2系统建模45-475.3数据库设计47-495.3.1数据库管理系统特点47-485.3.2数据库管理技术48-495.3.3排课数据库分析495.4概念模型设计49-505.5逻辑模型设计50-515.6数据库具体设计51-555.7算法引入参数的55-565.8功能模块的设计56-585.8.1形成开课任务模块56-575.8.2院系安排任务反馈模块575.8.3自动排课模块575.8.4调整模块575.8.5冲突检查模块57-585.8.6课表输出和打印模块585.9排课系统操纵流程和界面设计58-635.10本章小结63-64第六章总结和展望64-666.1总结64-656.2展望65-66附件66-73参考文献73-76攻读硕士学位期间完成的学术论文76-77致谢77