基于蚁群算法的点覆盖问题研究

论文摘要

点覆盖问题是指在无向图G=(V,E)中顶点集V中存在一个子集K,在G中任给一条边都至少有一个端点存在K中。最小点覆盖问题是在图中用尽可能少的点覆盖所有边,该问题是一个经典的组合优化领域中的NP完全问题。对最小点覆盖问题的求解可以应用到生活中许多方面,例如:网络节点选择问题、垃圾场和停车场的选址问题、共享单车投放问题等。因其应用广泛所以备受关注。关于该问题求解方法的主要研究方向为直接算法、参数化算法以及智能化算法等三方面。最早使用蚁群算法进行求解的就是组合优化类问题,并且在组合优化领域中关于该算法的研究最多、应用最广。论文从蚁群算法出发研究点覆盖问题,主要工作如下:(1)将TSP问题与最小点覆盖问题进行对比发现两个不同之处:TSP问题中顶点的选择与其排列顺序有关,而最小点覆盖问题中排列顺序不影响最后结果;TSP问题中的启发式函数为静态的而最小点覆盖问题中是动态更新的。根据这两个不同点将蚁群算法解决TSP问题进行改进从而得到蚁群算法解决最小点覆盖问题。(2)虽然蚁群算法具有系统性、分布式计算、鲁棒性强、正反馈性等优势,但是当处理数据量巨大时会出现求解时间长或者得不到最优解的情况,而且蚂蚁在循环中可能会因早期停滞问题的出现从而导致算法陷入局部最优。为了防止这种情况的出现使用最大最小蚁群算法进行求解。该算法通过对信息素浓度进行限定使其不会在好的顶点上变得更强,也不会使过弱的点被忽略,避免了算法出现局部最优的现象。通过计算表明该算法的精确度较高。(3)为了避免算法中存在的局部最优解停滞问题提出一种杂交蚁群算法来解决该问题。该算法的主要目的是对最优解进行校正。这种杂交概念是直接怀疑最优解中的某些元素不好,在搜索过程中直接指向可疑的搜索区域,通过减少可疑点的信息素更新值来指导搜索。设置怀疑准则对点进行筛选,然后使用校正规则对顶点进行校正。通过算例表明引入怀疑准则对最优解进行了优化。

论文目录

• 摘要
• Abstract
• 1 绪论
•   1.1 选题背景
•   1.2 国内外研究现状
•     1.2.1 最小点覆盖问题研究现状
•     1.2.2 蚁群算法的研究
•   1.3 本文研究内容
• 2 蚁群算法及其优化算法
•   2.1 蚁群算法的简介
•     2.1.1 蚁群系统
•     2.1.2 蚁群算法基本原理
•   2.2 蚁群算法的优化
•     2.2.1 精英蚁群系统
•     2.2.2 最大最小蚁群算法
•   2.3 小结
• 3 基于蚁群算法的最小点覆盖问题
•   3.1 蚁群算法解决最小点覆盖问题的基本原理
•   3.2 算法设计
•   3.3 算法实例
•   3.4 本章小结
• 4 基于最大最小蚁群算法的最小点覆盖问题
•   4.1 最大最小蚁群算法基本原理
•   4.2 最大最小蚁群算法解决最小点覆盖的基本原理
•   4.3 算法实例
•   4.4 本章小结
• 5 基于杂交蚁群算法求解点覆盖问题
•   5.1 杂交蚁群算法解决最小点覆盖问题基本原理
•     5.1.1 可疑点的信息素怀疑规则
•     5.1.2 可疑点的选择概率
•     5.1.3 怀疑校正规则
•   5.2 算法设计
•   5.3 算法实例
•   5.4 本章小结
• 6 总结与展望
•   6.1 研究结论
•   6.2 研究展望
• 致谢
• 参考文献
• 附录A 主要符号说明
• 附录B 部分程序代码位置
• 读学位期间的研究成果

文章来源

类型: 硕士论文

作者: 吴佩雯

导师: 陈京荣

关键词: 最小点覆盖,蚁群算法,最大最小蚁群算法,信息素更新

来源: 兰州交通大学

年度: 2019

分类: 基础科学,信息科技

专业: 数学,自动化技术

单位: 兰州交通大学

分类号: TP18;O157.5

DOI: 10.27205/d.cnki.gltec.2019.001145

总页数: 43

文件大小: 1829K

下载量: 116