蚁群优化在时间表问题中的研究与应用

论文摘要

时间表问题(Timetabling Problem,TTP)是一类典型的组合优化(Combinatorial Optimization)和不确定性调度问题。随着人工智能等技术的发展,人们对自动化解决时间表问题产生了迫切的需要。蚁群优化(Ant Colony Optimization,ACO)是群智能算法中相当活跃的一种优化算法,具有良好的全局搜索能力,在优化问题中有着广泛的应用。本文首次将蚁群优化推广到解决时间表问题中,以蚁群优化和概率统计理论为基础,提出了基于蚁群优化的时间表算法,并对蚁群优化及算法中所涉及的个体启发信息策略、自适应选择策略、最大最小信息素策略和信息素平滑处理机制等关键问题作了系统、深入和较为全面的研究：首先,从理论上介绍了ACO的生物原理及算法模型,并提出了ACO算法的若干改进策略,如：信息素更新机制,分组策略等；然后,以课程表问题为例,对时间表问题进行数学描述,提出了时间表问题的二分图模型；接着,从理论上论述了如何用ACO算法来解决时间表问题,提出了基于蚁群优化的时间表算法；最后,将基于蚁群优化的时间表算法应用到课程表问题中,并对算法进行了分析,得到了较高质量的课程表。研究与应用结果表明,本文提出的基于蚁群优化的时间表算法是可行的,它拓宽了时间表算法的解决方案；以概率统计理论和蚁群优化理论为基础,对其中所涉及的信息素策略和选择机制等问题的研究也是有效的,推广了ACO的应用。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 引言
• 1.2 时间表问题简述
• 1.3 蚁群优化简述
• 1.4 主要内容及意义
• 第2章 时间表问题
• 2.1 引言
• 2.2 课程表问题
• 2.2.1 问题概述
• 2.2.2 数学描述
• 2.3 求解时间表问题的常用算法
• 2.4 小结
• 第3章 蚁群优化算法
• 3.1 引言
• 3.2 蚁群优化算法原理
• 3.2.1 ACO生物原理
• 3.2.2 ACO算法模型
• 3.2.3 ACO算法系统特征
• 3.3 蚁群优化算法系统模型的实现
• 3.3.1 TSP数学描述
• 3.3.2 ACO算法系统模型的实现
• 3.3.3 算法分析
• 3.4 ACO算法的改进
• 3.5 ACO算法的应用领域
• 3.6 小结
• 第4章 基于蚁群优化的时间表算法
• 4.1 引言
• 4.2 数学模型的建立
• 4.2.1 二分图模型的顶点集
• 4.2.2 二分图模型的边集
• 4.2.3 二分图模型边的权植
• 4.2.4 二分图模型的创建
• 4.3 算法设计
• 4.3.1 蚂蚁个体的构造
• 4.3.2 蚂蚁的一次周游
• 4.3.3 路径构建机制
• 4.3.4 信息素更新机制
• 4.4 约束的检测和处理
• 4.4.1 硬性约束的检测和处理
• 4.4.2 软性约束的检测和处理
• 4.5 算法流程图
• 4.6 小结
• 第5章 应用案例与分析
• 5.1 应用案例
• 5.1.1 数据介绍
• 5.1.2 算法实现
• 5.1.3 结果效果图
• 5.2 案例结果分析
• 5.2.1 参数对算法的影响
• 5.2.2 课程表质量分析
• 5.3 与其他算法的比较
• 5.4 小结
• 第6章 结论
• 6.1 本文的结论
• 6.2 未来的研究方向
• 参考文献
• 致谢