若干支配集优化问题求解的方法研究

论文摘要

支配集是图论中的重要概念,支配集的许多变种问题,如独立支配集、连通支配集、完全支配集等,在科学研究和工程实践的许多领域有着广泛应用,包括编码理论、图像处理、数值分析、密码学、信息检索,以及通信基础设施的布局、城市交通路线规划等。人们在研究过程中发现,支配集的这些变种问题,往往是NP（非确定性多项式,Non-deterministic Polynomial）困难问题,即在多项式时间内难以获得最优解。近年来,启发式算法和进化算法在求解支配集及其变种问题上取得了较好的效果,尽管如此,它们在求解多约束、多变量以及高度非线性等性质的复杂优化问题时,尤其是对大规模图的实例仍有不足。因此,本文针对性地就支配集及其变种问题的求解方面提出有效的优化算法,其中包括:最小支配集问题、最小独立支配集问题,以及最小完全支配集问题的搜索算法求解。在求解的过程中,我们引入了进化算法和局部搜索等策略,针对这些支配集的问题设计高效的求解算法。经过在基准测试数据上进行的一系列实验表明,所提出的算法具有显著效果。本文的主要工作包括以下几个方面:（1）最小支配集（Minimum Dominating Set,简记为MDS）问题是支配集问题的一个重要子问题。对于经典的最小支配集问题,以往的启发式求解方法能够得到可以接受的解,但是现实生活中往往是大规模的组合优化问题,面对这样问题,这些启发式算法的求解表现差强人意。基于上述情况,我们重点关注在大规模实例上求解最小支配集问题的方法研究。通过对大规模实例的分析,结合支配集问题的特点,提出了一个快速高效地求解最小支配集问题的算法FastMDS。在FastMDS算法的求解过程中,首先在预处理过程中对问题进行了有效化简,在初始化过程中采用了低复杂度的策略,在算法迭代过程中引入随机算子对顶点进行选择。通过一系列的实验表明,我们所提出的FastMDS算法,较目前主流的启发式问题求解算法更为高效。（2）最小完全支配集（Minimum Total Dominating Set,简记为MTDS）问题是经典支配集问题的变体。在本文中,我们提出一种结合局部搜索和遗传算法的混合进化算法来求解最小完全支配集问题。在算法中采用一种新颖的评分启发式方法,以提高搜索效率并获得了更好的解决方案。针对MTDS问题求解,在初始化阶段,首先创建一个包括一些初始解的种群,使算法能够搜索更多区域。在局部搜索阶段,通过迭代地交换顶点来优化初始解决方案,并使用基于修复的交叉算子创建新的解来使算法搜索更多可行的区域。为了证明算法的有效性和性能,我们在经典的基准DIMACS上进行了一系列的实验,实验结果表明,我们提出的算法较其他算法具有更好的性能。（3）最小独立支配集（Minimum Independent Dominating Set,简记为MIDS）问题是一个经典的组合优化问题,并在现实生活中得到了广泛的应用。针对MIDS问题求解,设计了一种新的基于禁忌策略的局部搜索算法和两阶段移除策略,包括双检查移除策略和随机多样性移除策略。双检查移除策略对刚刚移除的顶点的第二层邻域进行检查并确认是否对该顶点进行移除,以打破独立性的限制;当候选解的质量经过多次迭代后仍然没有得到改善时,可以采用随机多样性移除策略,该策略动态贪婪地删除大量的顶点,然后将随机游走引入到添加顶点的修复过程中,以逃离次优的搜索空间。我们在DIMACS和BHOSLIB两个经典的基准上进行了一系列的实验,实验结果表明,我们所提出的算法在求解MIDS问题上明显优于目前的启发式算法。

论文目录

• 摘要
• Abstract
• 第一章 绪论
•   1.1 研究背景和意义
•   1.2 国内外研究现状
•   1.3 本文的研究内容和贡献
•   1.4 本文结构
• 第二章 支配集的相关理论
•   2.1 图的基本概念
•   2.2 支配集的定义及性质
•   2.3 局部搜索算法
•   2.4 密母算法
•   2.5 本章小结
• 第三章 在大规模实例上求解最小支配集问题
•   3.1 最小支配集问题
•     3.1.1 基本定义
•     3.1.2 格局检测策略
•     3.1.3 评分策略
•   3.2 CC2-MDS策略
•     3.2.1 CC2策略回顾
•     3.2.2 CC2-MDS的定义及更新规则
•   3.3 预处理策略
•     3.3.1 约简规则
•     3.3.2 构建ConstructRCS
•   3.4 随机选择策略
•   3.5 算法FastMDS框架
•   3.6 实验分析
•     3.6.1 FastMDS算法和RLS0 算法的实验结果对比
•     3.6.2 预处理的实验效果
•     3.6.3 随机删除策略的实验效果
•   3.7 本章小结
• 第四章 求解最小完全支配集问题的混合算法
•   4.1 基本定义
•   4.2 评分启发式方法
•   4.3 用于求解MTDS问题的进化算法HELG
•     4.3.1 种群初始化
•     4.3.2 局部搜索阶段
•     4.3.3 基于修复的交叉操作
•     4.3.4 HELG算法框架
•   4.4 实验分析
•     4.4.1 实验设置
•     4.4.2 实验结果
•   4.5 本章小结
• 第五章 解决最小独立支配集问题的两阶段移除算法
•   5.1 基本定义
•   5.2 MIDS评分策略
•   5.3 局部搜索的基本MIDS框架
•   5.4 针对MIDS的双检查移除策略
•   5.5 针对MIDS的随机多样性移除策略
•   5.6 drMIDS算法
•   5.7 实验分析
•     5.7.1 基准实例
•     5.7.2 实验设置
•     5.7.3 drMIDS算法参数调节
•     5.7.4 DIMACS基准测试的结果
•     5.7.5 BHOSLIB基准测试的结果
•     5.7.6 dcRemoving策略和rdRemoving策略的有效性
•   5.8 本章小结
• 第六章 总结与进一步工作
•   6.1 本文总结
•   6.2 进一步工作
• 参考文献
• 致谢
• 在学期间公开发表论文及著作情况

文章来源

类型: 博士论文

作者: 袁福宇

导师: 殷明浩

关键词: 组合优化问题,最小支配集,最小独立支配集,最小完全支配集,局部搜索,进化算法

来源: 东北师范大学

年度: 2019

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

专业: 数学,自动化技术

单位: 东北师范大学

分类号: TP18;O157.5

总页数: 116

文件大小: 1940K

下载量: 79