遗传算法的研究及其在TTP问题中的应用

论文摘要

时间表问题TTP(Time Table Problem)是一类特殊的资源调度问题,是一个多因素优化决策问题,也是组合优化中的典型问题。随着计算机的飞跃发展以及各高校教学管理体制的完善,用计算机来辅助排课成为了各大高校急需解决的问题。本文以大连交通大学研究生学院的时间表问题——排课问题为研究对象,分析了其约束条件,建立了数学模型,提出了基于遗传算法的改进算法,并用此算法解决排课问题。遗传算法GA(Genetic Algorithm)作为一门新兴学科,从二十世纪八十年代开始迅速发展。它是一种用于解决优化问题的并行寻优算法,已被广泛用于解决各类NP问题。标准遗传算法仍然存在一些缺陷,为了克服这些缺陷,本文设计了一个全新的改进遗传算法MEGA(Modified and Evolved algorithm based on Genetic Algorithm),这一算法在进化方式上与传统的改进遗传算法明显不同,最后用遗传算法常用的测试函数对MEGA算法进行数学分析,证实了它相对基本的遗传算法有一定的改进。通过设计MEGA算法的选择、交叉、变异算子等,证明了MEGA算法能有效地消除冲突,保证种群多样性,防止局部早熟收敛;通过一些典型函数测试验证了其有效性;处理排课问题时把课程分为两类,简化了问题的求解难度。在变异过程中引入混沌理论,在较优个体的变异操作中引入一个混沌小扰动,并把混沌运动的遍历范围“放大”到优化变量的取值范围,通过一代代地不断进化,收敛到一个最适合环境的个体上,求得问题的最优解。根据大连交通大学研究生课程排课问题的特点,本文对遗传算法进行了多方面的改进,重点分析了遗传算法、TTP问题及其数学模型、面向对象技术,把理论研究和实际应用结合起来设计开发了基于遗传算法的排课系统。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 课题研究背景、目的及意义
• 1.2 国内外研究现状综述
• 1.2.1 遗传算法的国内外现状
• 1.2.2 TTP 问题的国内外现状
• 1.2.3 遗传算法求解TTP 问题的国内外现状
• 1.3 研究目标及主要内容
• 1.4 本文结构
• 第二章 遗传算法和UML 技术
• 2.1 引言
• 2.2 遗传算法
• 2.2.1 遗传算法原理
• 2.2.2 遗传算子
• 2.2.3 遗传算法收敛性分析
• 2.2.4 遗传算法的基本特征
• 2.3 UML 技术
• 2.3.1 UML 的发展和定义
• 2.3.2 UML 的内容体系
• 2.3.3 UML 的建模机制
• 2.3.4 UML 建模的基本特征
• 本章小结
• 第三章 时间表问题
• 3.1 对排课时间表问题的认识
• 3.2 排课时间表问题分析
• 3.2.1 人工排课过程
• 3.2.2 计算机排课的逻辑模型
• 3.2.3 UML 技术分析排课系统
• 3.2.4 排课算法数学模型
• 3.2.5 解决排课问题的基本算法
• 3.3 排课时间表问题研究的目的和意义
• 本章小结
• 第四章 标准遗传算法解决排课问题
• 4.1 引言
• 4.2 编码方法
• 4.3 适应度函数
• 4.4 遗传操作
• 4.4.1 选择操作
• 4.4.2 交叉操作
• 4.4.3 变异操作
• 4.4.4 自适应变异算子
• 4.5 遗传算法的相关参数
• 4.6 标准遗传算法的不足和改进
• 本章小结
• 第五章 一种改进的遗传算法在时间表问题中的应用
• 5.1 引言
• 5.2 MEGA 算法总体思想
• 5.3 问题定义
• 5.4 算法的改进及流程
• 5.4.1 必修类课程
• 5.4.2 选修类课程
• 5.5 原型系统实现
• 5.5.1 约束条件的实现方法
• 5.5.2 采用的数据结构
• 5.5.3 主要程序说明
• 5.6 试验结果比较及分析
• 5.6.1 试验结果及比较
• 5.6.2 运行结果及分析
• 本章小结
• 第六章 应用实例——排课系统实现
• 6.1 引言
• 6.2 数据库设计及其分析
• 6.2.1 数据库连接技术
• 6.2.2 数据库设计
• 6.2.3 表结构
• 6.3 系统总体设计
• 6.3.1 采用的体系结构
• 6.3.2 系统结构图
• 6.3.3 模块功能解析
• 6.4 系统子程序
• 6.5 优点技术及难点解决
• 6.6 软件测试和排课质量分析
• 本章小结
• 结论
• 参考文献
• 攻读硕士学位期间发表的学术论文
• 致谢