蚁群算法及其应用研究 ——基于旅行商问题和图像分类

论文摘要

蚁群算法是Marco Dorigo等学者在真实蚂蚁觅食行为的启发下提出的一种具有高度创新性的元启发式搜索算法。它是继模拟退火算法、遗传算法、禁忌搜索算法、人工神经网络算法等之后提出的又一种应用于解决组合优化问题的启发式搜索算法。试验表明,蚁群算法具有较好的求解能力,但是蚁群算法存在收敛速度慢,容易陷入局部最优解等不足。本文主要研究如何改进算法模型并应用于相关领域,主要工作包括以下两部分。首先,对蚁群算法进行基础理论研究,改进并提出分类蚁群算法(CBACO),将其应用于TSP问题。旨在对蚁群算法近年来的研究进展进行总结,归纳算法的成功和存在的不足,对不足之处进行理论分析并改进,目的在于提高蚁群算法的总体性能。改进后的模型在智能蚁群的基础上引入随机蚁群以便扩大搜索空间,不同蚁群实行各自不同的搜索前进策略和信息更新机制,从而避免算法陷入早熟,以获取更大的解空间。并可通过调节随机蚁群与智能蚁群的比例来控制收敛速度,从而提高算法的运行效率。试验表明,将其应用于TSP问题可以获取更好的求解性能。其次,针对基本蚁群算法分类图像速度慢的缺点,根据蚁群算法的聚类和离散性特点,改进蚁群算法并应用于图像分类。随机蚂蚁在图像中识别类、构建类别表,并确定聚类中心、生成相应类的智能蚂蚁,指导智能蚂蚁分类的过程;智能蚂蚁按相应的搜索前进策略向聚类中心聚集,识别目标。同时所有的蚂蚁在搜索前进过程中对图像进行边缘提取,以便提高算法对图像边缘分类的准确度。试验表明,相比基本蚁群算法求解图像分类问题,由于该改进引入初始聚类中心和识别边缘,算法的分类效率和对边缘信息点分类的准确度得到提高,并实现了图像的自动分类。

论文目录

• 摘要
• Abstract
• 第一章 概述
• 1.1 蚁群算法
• 1.1.1 蚁群算法的历史及学科意义
• 1.1.2 蚁群算法的国内外研究概况
• 1.1.3 蚁群算法的特点
• 1.2 旅行商问题
• 1.3 图像分类
• 1.3.1 图像分类的意义及原理
• 1.3.2 图像分类的研究现状
• 1.4 本文的研究内容
• 1.4.1 CBACO 及其在旅行商问题中应用
• 1.4.2 SACBACO 及其在图像自动分类中应用
• 第二章 蚁群算法理论
• 2.1 蚂蚁算法概述
• 2.1.1 蚁群算法起源
• 2.1.2 双桥试验及其模型
• 2.1.3 人工蚁群系统研究
• 2.2 蚁群算法模型及实现
• 2.2.1 基本蚁群算法原理
• 2.2.2 基本蚁群算法模型
• 2.2.3 基本蚁群算法过程
• 2.3 蚁群算法的改进
• 2.3.1 蚁群系统
• 2.3.2 最大最小蚂蚁系统
• 2.3.3 蚁群算法的改进思路
• 第三章 CBACO 在旅行商问题中的应用
• 3.1 CBACO 算法框架
• 3.2 算法模型
• 3.2.1 初始化
• 3.2.2 搜索前进策略
• 3.2.3 信息更新策略
• 3.3 算法过程及流程图
• 3.3.1 算法过程
• 3.3.2 算法流程图
• 3.4 仿真研究
• 3.4.1 试验及结论
• 3.4.2 算法的收敛性分析
• 3.4.3 参数设置分析
• 3.5 本章小结
• 第四章 应用于图像自动分类的改进模型――SACBACO
• 4.1 蚁群算法在图像分类中的应用
• 4.1.1 图像分类的蚁群算法原理
• 4.1.2 图像分类的蚁群算法模型
• 4.1.3 蚁群算法的图像分类
• 4.1.4 本节小结
• 4.2 SACBACO 在图像自动分类中应用
• 4.2.1 问题的提出
• 4.2.2 用于图像自动分类的蚁群算法模型--SACBACO
• 4.2.3 SACBACO 的图像自动分类
• 4.2.4 实验及结论
• 4.3 本章小结
• 第五章 总结与展望
• 5.1 总结
• 5.2 展望
• 致谢
• 参考文献
• 附录：作者在攻读硕士学位期间发表的论文