求解推广的最小生成树的启发式算法设计
|
摘要
在最近一段时间,推广最小生成树(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算法。
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.
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.
引文
[1]Myung Y S, Lee C H, and Tcha D W.1995. On the generalized minimum spanning tree problem[J]. Networks 26,4 (May 1995),231-241.
[2]Feremans C.2001. Generalized spanning trees and extensions[J]. Doctoral Thesis. Universite Libre de Bruxelles, Belgium.
[3]Feremans C, Labbe M, Laporte G. A comparative analysis of several formulations for the generalized minimum spanning tree problem[J]. Networks 39,1 (January 2002), 29-34.
[4]Feremans C, Labbe M, Laporte G. Generalized network design problems[J]. European Journal of Operational Research 148,1 (July 2003),1-13.
[5]Feremans C, Labbe M, Laporte G. The generalized minimum spanning tree problem: Polyhedral analysis and branch-and-cut algorithm[J]. Networks 43,2 (March 2004), 71-86.
[6]Ghosh D.2003. Solving medium to large sized Euclidean generalized minimum spanning tree problems[M]. Technical report NEP-CMP-2003-09-28. Indian Institute of Management, Research and Publication Department, India.
[7]Hu B, Leitner M, and Raidl G R.2005. Computing generalized minimum spanning trees with variable neighborhood search[C]. In Proceedings of the 18th Mini-Euro Conference on Variable Neighborhood Search (Tenerife, Spain,2005).
[8]Hu B, Leitner M, and Raidl G R.2008. Combining variable neighborhood search with integer linear programming for the generalized minimum spanning tree problem[J]. J. Heuristics 14,5 (Nov.2008),473-499.
[9]Golden B, Raghavan S, and Stanojevic D.2005. Heuristic search for the generalized minimum spanning tree problem[J]. INFORMS J. Comput.17,3 (Summer 2005),290-304.
[10]Wang Z, Che C H, and Lim A.2006. Tabu search for generalized minimum spanning tree problem[C]. In Proceedings of 9th Pacific Rim International Conference on Artificial Intelligence (Guilin, China, Aug.07-11,2006).PRICAI'06. Springer-Verlag, Berlin/Heidelberg,918-922.
[11]Oncan T, Cordeau J F, and Laporte G.2008. A tabu search heuristic for the generalized minimum spanning tree problem[J]. Eur. J. Oper. Res.191,2 (Dec.2008), 306-319.
[12]Dorigo M, Stutzle T著,张军,胡晓敏,罗旭耀等译.蚁群优化[M].北京：清华大学出版社,2007.
[13]李晓晴,张雪萍.基于蚁群优化算法的障碍距离分析[J].计算机工程与设计.2009,30(2)：429-432.
[14]左洪浩.蚁群优化算法及其应用研究[D].合肥：中国科学技术大学,2006.
[15]Dorigo M, Maniezzo V, Colorni A. The Ant System:Optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems, Man, and Cybernetics.1996, 26(1):1-13.
[16]Jiang H, Ren Z L, Hu Y. A Sampling based FANT for the 3-Dimensional Assignment Problem[C]. IEEE Congress on Evolutionary Computation 2008(CEC 2008).2008, 4118-4124.
[17]吴林旭,姚跃华,黄晶.基于蚁群优化在Web数据挖掘分类模型的实现[J].计算机工程与科学,2009,31(3)：89-91.
[18]蔡立军,蒋林波,易叶青.基于蚁群优化算法的基因选择[J].计算机应用研究,2008,25(9)：2754-2757.
[19]赵俊,陈建军.基于混沌蚁群算法的大时滞对象神经网络控制[J].上海交通大学学报,2008,42(7)：1198-1202.
[20]Jiang H, Xuan J F, and Zhang X C.2008. An approximate muscle guided global optimization algorithm for the three-index assignment problem[C]. In Proceedings of the 2008 IEEE Congress on Evolutionary Computation (HongKong, China, Jun.01 06,2008). CEC'08. IEEE Computer Society Press, Piscataway, NJ,2404-2410.
[21]Kruskal J B.1956. On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem [J]. Proc. Am. Math. Soc.7,1 (Feb.1956),48-50.
[22]加理M R,约翰逊D S著.张立昂,沈泓,毕源章译.计算机和难解性-NP完全性理论导引[M].北京：科学出版社,1987.
[23]Michalewicz Z, Fogel D著.曹宏庆,李艳,董红斌等译.如何求解问题[M].北京：中国水利水电出版社,2003.
[2]Feremans C.2001. Generalized spanning trees and extensions[J]. Doctoral Thesis. Universite Libre de Bruxelles, Belgium.
[3]Feremans C, Labbe M, Laporte G. A comparative analysis of several formulations for the generalized minimum spanning tree problem[J]. Networks 39,1 (January 2002), 29-34.
[4]Feremans C, Labbe M, Laporte G. Generalized network design problems[J]. European Journal of Operational Research 148,1 (July 2003),1-13.
[5]Feremans C, Labbe M, Laporte G. The generalized minimum spanning tree problem: Polyhedral analysis and branch-and-cut algorithm[J]. Networks 43,2 (March 2004), 71-86.
[6]Ghosh D.2003. Solving medium to large sized Euclidean generalized minimum spanning tree problems[M]. Technical report NEP-CMP-2003-09-28. Indian Institute of Management, Research and Publication Department, India.
[7]Hu B, Leitner M, and Raidl G R.2005. Computing generalized minimum spanning trees with variable neighborhood search[C]. In Proceedings of the 18th Mini-Euro Conference on Variable Neighborhood Search (Tenerife, Spain,2005).
[8]Hu B, Leitner M, and Raidl G R.2008. Combining variable neighborhood search with integer linear programming for the generalized minimum spanning tree problem[J]. J. Heuristics 14,5 (Nov.2008),473-499.
[9]Golden B, Raghavan S, and Stanojevic D.2005. Heuristic search for the generalized minimum spanning tree problem[J]. INFORMS J. Comput.17,3 (Summer 2005),290-304.
[10]Wang Z, Che C H, and Lim A.2006. Tabu search for generalized minimum spanning tree problem[C]. In Proceedings of 9th Pacific Rim International Conference on Artificial Intelligence (Guilin, China, Aug.07-11,2006).PRICAI'06. Springer-Verlag, Berlin/Heidelberg,918-922.
[11]Oncan T, Cordeau J F, and Laporte G.2008. A tabu search heuristic for the generalized minimum spanning tree problem[J]. Eur. J. Oper. Res.191,2 (Dec.2008), 306-319.
[12]Dorigo M, Stutzle T著,张军,胡晓敏,罗旭耀等译.蚁群优化[M].北京：清华大学出版社,2007.
[13]李晓晴,张雪萍.基于蚁群优化算法的障碍距离分析[J].计算机工程与设计.2009,30(2)：429-432.
[14]左洪浩.蚁群优化算法及其应用研究[D].合肥：中国科学技术大学,2006.
[15]Dorigo M, Maniezzo V, Colorni A. The Ant System:Optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems, Man, and Cybernetics.1996, 26(1):1-13.
[16]Jiang H, Ren Z L, Hu Y. A Sampling based FANT for the 3-Dimensional Assignment Problem[C]. IEEE Congress on Evolutionary Computation 2008(CEC 2008).2008, 4118-4124.
[17]吴林旭,姚跃华,黄晶.基于蚁群优化在Web数据挖掘分类模型的实现[J].计算机工程与科学,2009,31(3)：89-91.
[18]蔡立军,蒋林波,易叶青.基于蚁群优化算法的基因选择[J].计算机应用研究,2008,25(9)：2754-2757.
[19]赵俊,陈建军.基于混沌蚁群算法的大时滞对象神经网络控制[J].上海交通大学学报,2008,42(7)：1198-1202.
[20]Jiang H, Xuan J F, and Zhang X C.2008. An approximate muscle guided global optimization algorithm for the three-index assignment problem[C]. In Proceedings of the 2008 IEEE Congress on Evolutionary Computation (HongKong, China, Jun.01 06,2008). CEC'08. IEEE Computer Society Press, Piscataway, NJ,2404-2410.
[21]Kruskal J B.1956. On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem [J]. Proc. Am. Math. Soc.7,1 (Feb.1956),48-50.
[22]加理M R,约翰逊D S著.张立昂,沈泓,毕源章译.计算机和难解性-NP完全性理论导引[M].北京：科学出版社,1987.
[23]Michalewicz Z, Fogel D著.曹宏庆,李艳,董红斌等译.如何求解问题[M].北京：中国水利水电出版社,2003.