蚁群算法及其在Flow Shop问题和聚类问题上的应用

论文摘要

群智能是近年来人工智能研究的一个热点话题,对于没有集中控制并且不提供全局模型的问题,提供了一种复杂的分布式解决方案。本文主要讨论了一种群智能算法——蚁群算法及其发展过程。该算法是Dorigo 等人受到蚁群的社会行为的启发而提出的。本文在分析各种因素对蚁群算法性能的影响的基础之上提出了求解置换Flow Shop问题的改进蚁群算法,在算法过程中加入了参数的自适应变化,引入了问题的信息特征。并且对算法进行了略微调整使之能够解决一般Flow Shop 问题。本文还应用蚁群算法求解了模糊Flow Shop 问题,但是对于模糊Flow Shop 问题的求解还仅仅停留在小规模问题上,对于大规模的模糊Flow Shop 问题还有待于进一步研究。另外,本文中提出了一种依赖信息素解决聚类问题的蚁群聚类算法。应用此蚁群聚类算法对两组人工数据进行分类,分别用穷举法和K-means 方法进行验证;随即利用算法对吉林省部分县市气候、气象数据进行分类,得到的分类结果与实际情况相符。在今后的工作中,还应将不同聚类算法的各自优缺点以及分类性能方面做比较研究,区分不同算法在分析不同数据时的性能差异。

论文目录

• 第一章 引言
• 1.1 群智能
• 1.2 蚁群算法
• 1.3 Flow-Shop 调度问题
• 1.4 聚类问题
• 1.5 本文的研究工作
• 第二章 蚁群算法基本原理
• 2.1 蚁群算法的提出
• 2.2 人工蚂蚁与真实蚂蚁的对比
• 2.3 算法原理
• 2.4 算法基本流程
• 第三章 蚁群算法的研究现状
• 3.1 文献回顾
• 3.2 蚂蚁系统
• 3.2.1 算法
• 3.2.2 蚂蚁系统的优点与不足
• 3.3 典型的改进算法
• 3.3.1 蚁群系统
• 3.3.2 MAX-MIN 蚂蚁系统
• 3.4 蚁群算法的收敛性
• 3.4.1 蚁群算法的马尔可夫链描述
• 3.4.2 蚁群算法的收敛性
• 第四章 蚁群算法在Flow Shop 问题上的应用
• 4.1 Flow Shop 问题描述
• 4.2 启发式方法
• 4.3 应用改进蚁群算法求解置换Flow-Shop 问题
• 4.3.1 一些具体操作对蚁群算法的影响
• 4.3.2 求解置换Flow-Shop 问题的算法流程
• 4.3.3 实验结果与分析
• 4.4 应用改进蚁群算法求解一般Flow-Shop 问题
• 4.5 应用蚁群算法求解模糊Flow-Shop 问题
• 第五章 蚁群算法在求解聚类问题上的应用
• 5.1 聚类问题的数学模型
• 5.2 蚁群聚类算法
• 5.2.1 蚁群聚类算法分析
• 5.2.2 蚁群聚类算法流程
• 5.3 实验结果与分析
• 5.3.1 蚁群聚类算法的人造数据分析验证
• 5.3.2 蚁群聚类算法的应用数据分析验证
• 第六章 结束语
• 参考文献
• 摘要
• Abstract
• 致谢
• 导师及作者简介