学位论文 > 优秀研究生学位论文题录展示

基于改进型遗传算法的军队院校排课系统研究

作　者: 岳翠翠
导　师: 李其申; 杨彦明
学　校: 南昌航空大学
专　业: 控制工程
关键词: 遗传算法军队院校排课系统三维编码最优保存策略
分类号: TP18
类　型: 硕士论文
年　份: 2013年
下　载: 27次
引　用: 0次
阅　读: 论文下载

内容摘要

课程表编排是一项比较复杂的统筹规划问题，它涉及到多个项目内容、多个制约因素和多个求解目标，并且已被证明是一个NP（Non-deterministic Polynomial）完全问题。排课最终目的是要合理地安排一个关于课程、教员、班次、教室和时间段的可行性组合，既要满足教学资源各方面的要求，又要保证各个资源之间免于发生冲突。为了顺应国家教育体制改革的趋势，各大高校都在不断扩招，专业数和课程数急剧增加，有限教学资源的制约和各种复杂约束条件的限制，都使得传统手工排课不能满足现代教务管理工作的需求。针对传统手工排课重复劳动量巨大、工作效率低下和易发生冲突等弊端，利用计算机设计出一个科学合理、高效实用的排课系统就成为一种势在必行的趋势。遗传算法是一种仿生优化算法，实践证明，它在一定程度上能够很好的解决NP完全问题。因此，本文选择遗传算法解决排课问题，并结合军队院校实际课程表的制定原则及特色，对遗传算法进行了合理改进，设计并实现了适用于军队院校的排课系统。本文主要工作包括：1.针对军队院校排课问题，总结并分析了排课影响因素、主要约束条件，给出了排课问题的复杂度分析和求解目标，建立了相应的数学优化模型，并提出了求解排课问题的总体方案。2.深入研究了遗传算法的基本术语、基本思想、基本流程和基本操作等，在此基础上，对遗传算法进行了合理改进，包括三维编码方案、最优保存策略以及自适应的交叉、变异概率设计方案等。3.以Delphi7.0为前台开发工具，SQL Server2000为后台数据库，设计了系统架构、功能模块、数据库表结构等，开发了基于改进型遗传算法的军队院校排课系统，并详细介绍了利用改进型遗传算法求解排课问题的设计步骤。4.最后，以某军队院校的实际排课数据对本文排课系统进行了测试，并测试了一些控制参数对算法的影响，验证了改进型遗传算法的可行性和有效性。

全文目录

摘要  4-5
ABSTRACT  5-10
第1章绪论  10-18
  1.1 课题研究背景及意义  10-12
    1.1.1 研究背景  10-11
    1.1.2 研究意义  11-12
  1.2 国内外研究现状  12-13
    1.2.1 国外研究现状  12
    1.2.2 国内研究现状  12-13
  1.3 常用排课算法概述  13-16
    1.3.1 模拟退火算法  13-14
    1.3.2 贪心算法  14
    1.3.3 回溯算法  14
    1.3.4 蚁群算法  14-15
    1.3.5 遗传算法  15-16
  1.4 论文研究的主要内容  16-18
第2章遗传算法相关理论  18-24
  2.1 遗传算法概述  18
  2.2 遗传算法的基本术语  18-19
  2.3 基本遗传算法的表示  19-20
  2.4 遗传算法的基本流程  20-21
  2.5 遗传算法的基本算子  21-23
    2.5.1 选择算子  21-22
    2.5.2 交叉算子  22-23
    2.5.3 变异算子  23
  2.6 本章小结  23-24
第3章排课问题分析  24-36
  3.1 排课问题概述  24-25
  3.2 排课问题目标分析  25-30
    3.2.1 排课因素  25-26
    3.2.2 排课约束条件  26-27
    3.2.3 排课问题复杂度分析  27-29
    3.2.4 排课问题求解目标  29-30
  3.3 排课问题数学模型  30-32
    3.3.1 数学描述  30
    3.3.2 硬约束条件描述  30-31
    3.3.3 软约束条件描述  31-32
  3.4 排课问题求解方案  32-35
    3.4.1 求解可行初始排课方案  33-34
    3.4.2 利用遗传算法进行全局优化  34-35
  3.5 本章小结  35-36
第4章排课系统的设计与实现  36-60
  4.1 系统架构设计与系统工作流程  36-38
    4.1.1 系统架构设计  36-37
    4.1.2 教学实施工作流程  37-38
  4.2 系统功能模块的设计  38-39
  4.3 数据库设计  39-45
    4.3.1 数据流程图  39-40
    4.3.2 数据表结构  40-45
    4.3.3 数据表关系  45
  4.4 排课问题中遗传算法的设计  45-52
    4.4.1 构造基因编码和染色体  45-46
    4.4.2 构造可行初始种群  46-47
    4.4.3 冲突检测  47-48
    4.4.4 构造适应度函数  48-49
    4.4.5 自适应的交叉概率和变异概率  49
    4.4.6 遗传操作  49-52
    4.4.7 课程表的产生  52
  4.5 系统功能模块的实现  52-59
    4.5.1 确定教学任务  52-53
    4.5.2 确定教学班次  53-54
    4.5.3 课表编排  54-56
    4.5.4 数据处理与检测  56-57
    4.5.5 课表查询与输出  57-59
  4.6 本章小结  59-60
第5章系统测试与分析  60-64
  5.1 排课系统的测试环境  60
  5.2 排课系统的参数测试  60-62
    5.2.1 种群规模的测试  61
    5.2.2 自适应参数的测试  61-62
    5.2.3 课程数量的测试  62
  5.3 排课系统效率的测试  62-63
  5.4 本章小结  63-64
第6章总结与展望  64-66
  6.1 论文总结  64-65
  6.2 工作展望  65-66
参考文献  66-70
发表论文和参加科研情况说明  70-71
致谢  71-72

基于改进型遗传算法的军队院校排课系统研究

内容摘要

全文目录

相似论文