蚁群算法求解最小点覆盖问题

发布时间：2022-10-19 13:36

　　最小点覆盖问题（Minimum Vertex Cover problem,MVCP）是给定一个无向图G=（V,E）,求顶点集V的最小子集S,使G中每条边在S中至少有一个端点。该问题是经典的NP完全问题,目前没有多项式时间算法,因此研究的重点是在合理计算时间内找到一个接近最优解的可行解。本文利用蚁群算法对最小点覆盖问题进行研究,主要工作如下:（1）将最小点覆盖问题与TSP问题进行比较,通过对状态转移规则和信息素更新规则的修改,得到蚁群算法求解该问题的基本原理。利用改进的蚁群算法,分别研究了无权图和赋权图的最小点覆盖问题,且设计了算法。最后给出实例分析了该算法的合理性和有效性。（2）蚁群算法的正反馈机制易使搜索陷入局部收敛,出现局部最优解。将基本的蚁群算法与最大最小蚁群算法进行比较,得到最大最小蚁群算法求解该问题的基本原理。通过对状态转移规则和信息素更新规则增加限定条件,有效的避免了局部最优现象。利用改进的最大最小蚁群算法,研究了无权图的最小点覆盖问题。最后给出实例验证了该算法的可行性。（3）考虑共享单车对城市交通的影响和企业的运营成本,将共享单车投放点的选择看作是有条件的最小点覆盖问题,... 

【文章页数】：42 页

【学位级别】：硕士

【文章目录】：
摘要
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.3 本章小结
3 基于蚁群算法的最小点覆盖问题
    3.1 蚁群算法求解最小点覆盖问题基本原理
    3.2 算法设计
        3.2.2 点赋权图的最小点覆盖问题
        3.2.3 边赋权图的最小点覆盖问题
        3.2.4 点、边赋权图的最小点覆盖问题
    3.3 算法实例
        3.3.1 无权图算法实例
        3.3.2 点赋权图算法实例
        3.3.3 边赋权图算法实例
        3.3.4 点、边赋权图算法实例
    3.4 本章小结
4 基于最大最小蚁群算法的最小点覆盖问题
    4.1 最大最小蚁群算法解决最小点覆盖的基本原理
    4.2 算法设计
    4.3 算法实例
    4.4 本章小结
5 最小点覆盖问题在共享单车投放点选取的应用
    5.1 引言
    5.2 模型建立
    5.3 算法设计
    5.4 算例求解及结果分析
    5.5 本章小结
结论
致谢
参考文献
攻读学位期间的研究成果


【参考文献】：
期刊论文
[1]最小权点覆盖的扫描测试向量生成算法[J]. 王力,穆东旭.  计算机仿真. 2019(07)
[2]服务半径约束下城市快递双层配送网络节点选址优化[J]. 杜刚诚,冉林娜.  上海海事大学学报. 2019(02)
[3]基于蚁群算法的动态共享单车调度优化[J]. 汪慎文,徐亮,杨锋,李美羽.  南昌工程学院学报. 2019(03)
[4]基于改进势场蚁群算法的移动机器人最优路径规划[J]. 张强,陈兵奎,刘小雍,刘晓宇,杨航.  农业机械学报. 2019(05)
[5]基于蚁群算法的无人机任务规划优化模型研究[J]. 蒋莎,刘学文,叶家君.  重庆师范大学学报(自然科学版). 2019(01)
[6]基于最小点覆盖的共享单车投放点选取方法[J]. 郝斌斌,吕斌,陈京荣.  交通信息与安全. 2018(05)
[7]基于子群划分的共享单车调度优化[J]. 叶锦程,胡骥.  综合运输. 2018(08)
[8]基于核心化技术的点覆盖改进算法[J]. 骆伟忠,蔡昭权.  计算机工程与科学. 2018(08)
[9]一种增量式约简方法求解最小顶点覆盖问题[J]. 占善华,谢小军.  计算机应用研究. 2018(12)
[10]混合算法求解多目标平衡旅行商问题[J]. 董学士,董文永,王豫峰.  计算机研究与发展. 2017(08)

硕士论文
[1]基于合作竞争理论的设施选址问题研究[D]. 郭倩.北京交通大学 2014



本文编号：3693460