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