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

目录

第一个书签之前

摘要

ABSTRACT

插图索引

表格索引

符号对照表

缩略语对照表

第一章 绪 论

1.2复杂网络研究现状

1.3复杂网络研究意义

1.4复杂网络的集合优化问题

1.5本文结构安排

第二章 问题描述及相关算法简介

2.2最小顶点覆盖问题

2.3.1基于 2-improvement 的迭代局部搜索算法

2.3.2基于交换的禁忌局部搜索算法

2.3.3求解最大团的局部搜索算法

2.4.1求解最小顶点覆盖的遗传算法

2.4.2混合遗传算法

2.4.3基于粗糙集理论的算法

2.4.4基于边权值的局部搜索算法

2.5算法综合对比分析

2.6本章小结

第三章 复杂网络上的演化博弈

3.1.1囚徒困境博弈

3.1.2雪堆博弈

3.1.4博弈策略更新方法

3.2复杂网络的同步演化博弈

3.2.2基于同步演化博弈求解最小顶点覆盖问题

3.3复杂网络的异步演化博弈

3.3.2异步囚徒困境博弈与最大独立集

3.3.3异步雪堆博弈与最小顶点覆盖

3.4实验结果与分析

第四章 基于 PDG 求解最大独立集的迭代局部搜索算法

4.1.2基于囚徒困境博弈的局部搜索

4.1.3GLS 的博弈顺序

4.1.4基于博弈的扰动方法

4.2基于囚徒困境博弈的迭代局部搜索算法 IGLS

4.2.3算法整体思路

4.2.4时间复杂度分析

4.2.5算法可行性分析

4.3实验结果与分析

4.3.2不同算法搜索合法解的性能对比

4.3.3局部搜索性能对比

4.3.5实验结果分析与统计检验

4.4本章小结

第五章 基于雪堆博弈求解最小顶点覆盖的自然进化算法

5.1.2基于雪堆博弈的局部搜索

5.1.3个体进化总体步骤

5.2.2GMA-MVC 算法元素

5.2.3GMA-MVC 算法总体步骤

5.2.5算法可行性分析

5.3.1实验网络简介

5.3.2初始化性能分析

5.3.3个体进化性能分析

5.3.4基于演化博弈的不同算法对比

5.3.5综合对比实验

5.3.6实验结果分析与统计检验

5.3.7算法参数分析

5.4本章小结

第六章 总结与展望

6.2展望

参考文献

致谢

作者简介