【作者】 陈誉东；

【导师】 江贺；

【作者基本信息】 大连理工大学 ， 计算机应用技术， 2010， 硕士

【摘要】 在最近一段时间,推广最小生成树(GMST)问题得到了广泛的关注,它定义为在多个簇集合中,在每个簇内仅挑选一个顶点,它的目标是由这些顶点构成的最小生成树的代价值最小。它在通信,大型通信网络设计,能源分配以及农业灌溉中都有广泛的应用。由于它被证明是NP难问题,目前的近似算法尚不能在较短的时间内给出高质量的解,因此有许多启发式算法被提出以求解GMST问题。受到求解NP难问题的"muscle"(最优解的并集)的有效性的启示,本文研究了如何利用muscle来设计求解GMST问题的算法。在定义GMST问题的muscle之前,本文首次定义了GMST问题的启发集(包括主启发集和从属启发集),这些启发集可以通过将GMST问题进行归约,在归约后的实例上计算对应的最小生成树而获得。GMST问题的muscle可以利用这些归约的最小生成树上的主启发集和从属启发集来近似模拟。在分析muscle的基础上,本文提出了求解GMST的启发式方法—基于动态启发集的搜索算法(Dynamic cAndidate set based Search Algorithm,简称为DASA)。和现有的启发式算法相比,DASA算法使用了启发集对解进行初始化和优化；并且在优化的过程中,这些启发集被动态地调整来指导搜索的方向。由于这些启发集能够覆盖大部分的最优解,DASA算法的搜索空间能被有效地归约到一个较小的搜索空间,因此能在较短的时间内发现较优解。在DASA的基础上,本文还提出了基于DASA的局部搜索的快速蚂蚁算法(FANT)该算法也使用了启发集来进行解的初始化,并使用DASA的局部搜索来作为FANT的局部搜索算子。实验结果表明,DASA算法和FANT算法都要优于现有的求解GMST的算法。在现有GMST实例的基础上,本文又生成了一些新的大规模的实例,从这些实例的结果上可以发现,FANT算法要优于DASA算法。更多还原

【Abstract】 The Generalized Minimum Spanning Tree (GMST) problem has attracted much attention during the last few years. Its definition is that select one and only one node from each cluster to construct the minimum spanning tree (MST), the aim of it is that make the cost of this MST minimum. It is widely used in telecommunication, design of backbones in large communication networks, energy distribution, and agricultural irrigation. Since GMST was shown to be a NP-hard problem, there is no algorithm to get highquality solutions in polynomial time. Therefore many heuristic algorithms have been proposed to solve the GMST instances. Motivated by the effectiveness and efficiency of the muscle (the union of all optimal solutions) for solving other NP-hard problems, we investigate how to incorporate the muscle into heuristics design for GMST. Firstly, before define the muscle of the GMST, we show that the muscle can be well approximated by the principle and subordinate candidate sets, which can be calculated on a reduced version of GMST. Therefore, a Dynamic cAndidate set based Search Algorithm (DASA) is presented in this paper for GMST based on the analysis for the muscle to GMST. In contrast to existing heuristics, DASA employs those candidate sets to initialize and optimize solutions. During the search process, those candidate sets are dynamically adjusted to include in new features provided by good solutions. Since those candidate sets cover almost all optimal solutions, the search space of DASA can be dramatically reduced so that elite solutions can be easily found in a short time. Furthermore, a FANT algorithm based on the local search of the DASA, is presented to solve the GMST problem. It also uses the candidate sets to initialize and optimize the solutions of the GMST, and employs the local search of DASA as its local search operator. Extensive experiments demonstrate that the new algorithms including the DASA and FANT for GMST outperforms existing heuristic algorithms in terms of solution quality. And the results on the extension instances which are newly larger created, FANT algorithm outperforms the DASA.更多还原