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

发布时间：2020-10-14 19:34

　　 支配集是图论中的重要概念,支配集的许多变种问题,如独立支配集、连通支配集、完全支配集等,在科学研究和工程实践的许多领域有着广泛应用,包括编码理论、图像处理、数值分析、密码学、信息检索,以及通信基础设施的布局、城市交通路线规划等。人们在研究过程中发现,支配集的这些变种问题,往往是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问题上明显优于目前的启发式算法。
【学位单位】：东北师范大学
【学位级别】：博士
【学位年份】：2019
【中图分类】：TP18;O157.5
【部分图文】：

图 1. 1 密母算法流程示意图密母（Memes）一词代表信息的传播[23]。密母算法代表了进化计算研究领域的最新发展，一般是在求解过程中，将进化计算或是其他基于种群的方法，与独立个体学习或是局部增强过程相结合，而对算法进行深入研究[24]。密母算法往往也被称之为混合进化算法（Hybrid Evolutionary Algorithms）、Baldwinian 进化算法（BaldwinianEvolutionary Algorithms ） 、 Lamarckia 进 化 算 法 （ Lamarckia EvolutionaryAlgorithms）、文化算法（Cultural Algorithms）或是遗传局部搜索（Genetic LocalSearch）等。对于复杂的优化问题，许多密母算法的不同实例已经应用到广泛领域，通常能够较传统优化算法获得高质量的解。与不同智能优化算法的结合，相应的密母算法也不同，比较常见的密母算法包括：混合遗传算法[25]、混合免疫算法[26]、混合粒子群算法[27]、混合蚁群算法[28]、混合蜂群算法[29]等等。进一步地，将密母应用到计算框架中，称为密母计算（Memetic Computing），对于求解优化问题，特别是在处理与其他确定性优化技术相结合的进化算法领域，密母计算将密母（Memes）的概念扩展到知识增强过程或表示的概念实体。

2.1 图的基本概念1736 年，瑞士数学家欧拉在它的一篇论文中讨论了哥尼斯堡（Konigsberg）七桥问题，由此产生了一个全新的数学分支——图论（graph theory）。在此，我们也引用哥尼斯堡七桥问题的例子中的问题启发而给出图的基本定义。除本文定义的术语外，其他图论相关的术语可以参考《图论及其应用》[43]，Gary Chartrand 和 Ping Zhang 的《Introduction to Graph Theory》[44]和 Douglas B. West 的《Introduction to Graph Theor(Second Edition)》[45]。例哥尼斯堡七桥问题。哥尼斯堡市座落于普鲁士的普莱格尔河畔，在它的一个公园里，有 7 座桥将普莱格尔河中的两个岛以及岛与河的两岸连接起来，在图 2.1 的左图中用 A、B、C、D 分别表示 4 块陆地区域。市民们想知道如果他们从这 4 块陆地区域中任一块出发，经过每座桥恰好一次，能否返回原点。该问题被简化为遍历图 2.1 的右侧的图，图中黑色顶点表示陆地，线表示桥。

定理 2-3 支配集问题是 NP 完全问题[52]。证明：（1）给定图 = ( , )，对于任意顶点集合 和正整数 t，如果满足条件| | ≤ ，则可以在多项式时间内判断集合 S 是否为图 G 的一个支配集的结论，即∈ 。（2）引出 3-SAT（boolean SATisfiability problem）问题。给定一个有穷的布尔变量集合 U 和子句集合 C，是否存在一个真值赋值，使得子句集合 C 为真，即其中的每个子句为真。3-SAT 的实例为 = { , , , }， = { , , , }为每个变量的赋值，只要验证每个子句都为真即可。很明显，可以在多项式时间内完成该验证，即 3SAT 问题为 NP 完全问题。下面，将 3-SAT 变换为支配集问题（ ），如图 2.2[52]所示。
【相似文献】

相关期刊论文 前10条

1 骆伟忠;冯启龙;王建新;陈建二;;完全p-支配集的参数算法[J];计算机学报;2013年09期

2 王康;禹继国;;无线网络中一种简单的弱连通支配集构造策略[J];计算机工程与应用;2011年20期

3 李镇坚;葛启;王海涛;朱洪;;图的支配集若干问题的研究[J];计算机科学;2007年01期

4 黄民肃;向东;;无线自组网络中的基于多个支配集的路由协议[J];计算机应用研究;2007年05期

5 吴迪;梁辉;王光兴;;无线自组网簇间网关支配集优化策略[J];计算机工程;2007年24期

6 孙立山;郝燕玲;;能量限制的连通支配集分布式构造[J];计算机工程与应用;2006年32期

7 苏岐芳;图的支配集的有效算法[J];台州学院学报;2003年06期

8 张光铎，王正志;图论中独立支配集的最佳求解算法研究[J];国防科技大学学报;1995年02期

9 沈湘钟;黄友锐;吴建坤;;基于连通支配集的无线传感器网络拓扑控制算法仿真研究[J];仪表技术与传感器;2016年09期

10 赵学锋;;求解最小连通r-跳k-支配集的启发式算法[J];计算机工程;2012年21期

相关博士学位论文 前10条

1 袁福宇;若干支配集优化问题求解的方法研究[D];东北师范大学;2019年

2 施韦;移动Ad Hoc网络中连通支配集若干关键问题的研究[D];浙江大学;2007年

3 汪文勇;无线传感器网络若干节能关键技术研究[D];电子科技大学;2011年

4 骆伟忠;无线网络中若干NP-难问题的参数算法[D];中南大学;2012年

5 刘卓;无线传感器网络拓扑建立方法与应用技术研究[D];华中科技大学;2011年

6 陶凯;广域定向MANET组网关键技术研究[D];哈尔滨工程大学;2015年

7 郑莹;基于树分解的难解问题的参数算法研究[D];中南大学;2013年

8 于瑞云;无线传感器网络中面向数据采集的支配集算法与策略研究[D];东北大学;2009年

9 张强;基于连通性的无线传感器网络节点定位技术研究[D];天津大学;2011年

10 李睿智;基于局部搜索策略的若干组合优化问题求解算法研究[D];东北师范大学;2017年

相关硕士学位论文 前10条

1 徐彤;WSN中连通支配集构造算法的研究[D];南昌航空大学;2019年

2 齐晓晗;基于多连通支配集调度机制的飞行自组网拓扑控制算法[D];哈尔滨工业大学;2018年

3 荆莹;基于时变连通支配集的多层卫星网络路由算法[D];哈尔滨工业大学;2017年

4 刘华丽;若干图的连通支配问题研究[D];中国计量大学;2017年

5 刘培丽;基于集序的集优化问题的稳定性及鲁棒性分析[D];重庆大学;2018年

6 徐培培;无线传感网络中强连通支配集的构造研究[D];南昌航空大学;2016年

7 任思君;最小连通支配集算法研究[D];上海交通大学;2015年

8 鲁登月;无线传感器网络中连通支配集的构造算法研究[D];苏州大学;2014年

9 林霖;无线传感器网络分布式连通支配集构造方法研究[D];电子科技大学;2012年

10 陈蓓玮;加权边支配集问题的参数算法研究[D];中南大学;2009年

本文编号：2841085