基于博弈的独立集和顶点覆盖问题研究

发布时间：2021-10-09 21:26

　　复杂网络可以用于描述同一系统内不同个体之间、个体与整体之间以及不同整体之间的关系。复杂网络的最大独立集问题（MISP）和最小顶点覆盖问题（MVCP）是两个典型的集合优化问题,且都是NP-hard问题。最大独立集问题指的是求解一个（或若干个）网络节点构成的集合,使得所求得的集合规模最大、且集合内的节点相互之间没有连边。该优化问题得到整个网络中个体之间互不影响的最大的个体集合。最小顶点覆盖问题的目的在于找出给定复杂网络的规模最小的节点集合,并保证网络中任意一条边至少有一个顶点在所选的节点集合中。现实生活中的许多问题可以归结为这两种问题,比如高校教师排课系统、监控设备安置问题、线路规划问题、网络优化问题等。本文首先研究复杂网络的演化博弈动力学行为,然后创新性地结合网络的博弈规律,分别对局部搜索和全局搜索方法进行了研究、改进与实验,提出了基于囚徒困境博弈求解最大独立集问题的迭代局部搜索算法（IGLS）和基于雪堆博弈和遗传机制求解最小顶点覆盖问题的进化算法（GMA-MVC）。最后,通过实验,验证了本文所提出的IGLS算法和GMA-MVC算法的优势。本文的主要内容如下:1.研究复杂网络上的节点博弈... 

【文章来源】：西安电子科技大学陕西省 211工程院校 教育部直属院校

【文章页数】：104 页

【学位级别】：硕士

【文章目录】：
摘要
ABSTRACT
符号对照表
缩略语对照表
第一章 绪论
    1.1 复杂网络概述
    1.2 复杂网络研究现状
    1.3 复杂网络研究意义
    1.4 复杂网络的集合优化问题
    1.5 本文结构安排
第二章 问题描述及相关算法简介
    2.1 最大独立集问题
    2.2 最小顶点覆盖问题
    2.3 最大独立集的求解方法
        2.3.1 基于2-improvement的迭代局部搜索算法
        2.3.2 基于交换的禁忌局部搜索算法
        2.3.3 求解最大团的局部搜索算法
    2.4 最小顶点覆盖的求解方法
        2.4.1 求解最小顶点覆盖的遗传算法
        2.4.2 混合遗传算法
        2.4.3 基于粗糙集理论的算法
        2.4.4 基于边权值的局部搜索算法
    2.5 算法综合对比分析
    2.6 本章小结
第三章 复杂网络上的演化博弈
    3.1 演化博弈
        3.1.1 囚徒困境博弈
        3.1.2 雪堆博弈
        3.1.3 纳什均衡
        3.1.4 博弈策略更新方法
    3.2 复杂网络的同步演化博弈
        3.2.1 同步演化博弈
        3.2.2 基于同步演化博弈求解最小顶点覆盖问题
    3.3 复杂网络的异步演化博弈
        3.3.1 异步演化博弈
        3.3.2 异步囚徒困境博弈与最大独立集
        3.3.3 异步雪堆博弈与最小顶点覆盖
    3.4 实验结果与分析
    3.5 本章小结
第四章 基于PDG求解最大独立集的迭代局部搜索算法
    4.1 基于囚徒困境博弈的局部搜索机制GLS
        4.1.1 基于囚徒困境博弈求得极大独立集
        4.1.2 基于囚徒困境博弈的局部搜索
        4.1.3 GLS的博弈顺序
        4.1.4 基于博弈的扰动方法
    4.2 基于囚徒困境博弈的迭代局部搜索算法IGLS
        4.2.1 弱扰动机制
        4.2.2 基于模拟退火思想的解集更新方法
        4.2.3 算法整体思路
        4.2.4 时间复杂度分析
        4.2.5 算法可行性分析
    4.3 实验结果与分析
        4.3.1 实验网络简介
        4.3.2 不同算法搜索合法解的性能对比
        4.3.3 局部搜索性能对比
        4.3.4 综合对比实验
        4.3.5 实验结果分析与统计检验
    4.4 本章小结
第五章 基于雪堆博弈求解最小顶点覆盖的自然进化算法
    5.1 个体进化
        5.1.1 基于雪堆博弈求解合法解
        5.1.2 基于雪堆博弈的局部搜索
        5.1.3 个体进化总体步骤
    5.2 带有个体进化的自然进化算法GMA-MVC
        5.2.1 基于节点度的初始化方法
        5.2.2 GMA-MVC算法元素
        5.2.3 GMA-MVC算法总体步骤
        5.2.4 时间复杂度分析
        5.2.5 算法可行性分析
    5.3 实验结果与分析
        5.3.1 实验网络简介
        5.3.2 初始化性能分析
        5.3.3 个体进化性能分析
        5.3.4 基于演化博弈的不同算法对比
        5.3.5 综合对比实验
        5.3.6 实验结果分析与统计检验
        5.3.7 算法参数分析
    5.4 本章小结
第六章 总结与展望
    6.1 总结
    6.2 展望
参考文献
致谢
作者简介


【参考文献】：
期刊论文
[1]复杂网络:认知世界的科学新方法[J]. 黄欣荣.  江西财经大学学报. 2012(01)
[2]CPU与GPU上几种矩阵乘法的比较与分析[J]. 刘进锋,郭雷.  计算机工程与应用. 2011(19)
[3]复杂网络及其在国内研究进展的综述[J]. 刘建香.  系统科学学报. 2009(04)
[4]复杂网络上的博弈[J]. 吴枝喜,荣智海,王文旭.  力学进展. 2008(06)
[5]小世界网络与无标度网络的社区结构研究[J]. 杜海峰,李树茁,W.F.Marcus,悦中山,杨绪松.  物理学报. 2007(12)
[6]复杂网络上动力系统同步的研究进展[J]. 赵明,汪秉宏,蒋品群,周涛.  物理学进展. 2005(03)
[7]复杂网络理论及其应用研究概述[J]. 刘涛,陈忠,陈晓荣.  系统工程. 2005(06)
[8]BA模型的三种扩展[J]. 陈禹,宗骁,郝杰,许彦.  系统工程学报. 2005(02)
[9]从统计物理学看复杂网络研究[J]. 吴金闪,狄增如.  物理学进展. 2004(01)
[10]网络“建筑学”[J]. 朱涵,王欣然,朱建阳.  物理. 2003(06)

硕士论文
[1]基于雪堆博弈的复杂网络最小节点覆盖[D]. 皎魁.西安电子科技大学 2015



本文编号：3427030