Genetic Algorithms for Balanced Spanning Tree Problem
Given an undirected weighted connected graph G = (V, E) with vertex set V and edge set E and a designated vertex r ∈ V , we consider the problem of constructing a spanning tree in G that balances both the minimum spanning tree and the shortest paths tree rooted at r. Formally, for any two constants α, β ≥ 1, we consider the problem of computing an (α, β)-balanced spanning tree T in G, in the sense that, (i) for every vertex v ∈ V , the distance between r and v in T is at most α times the shortest distance between the two vertices in G, and (ii) the total weight of T is at most β times that of the minimum tree weight in G. It is well known that, for any α, β ≥ 1, the problem of deciding whether G contains an (α, β)- balanced spanning tree is NP-complete . Consequently, given any α ≥ 1 (resp., β ≥ 1), the problem of finding an (α, β)-balanced spanning tree that minimizes β (resp., α) is NP-complete. In this paper, we present efficient genetic algorithms for these problems. Our experimental results show that the proposed algorithm returns high quality balanced spanning trees. (original abstract)
- ] O. Abdoun, J. Abouchabaka, and C. Tajani, Analyzing the Performance of Mutation Operators to Solve the Travelling Salesman Problem, CoRR abs/1203.3099, 2012.
- Andris P. Engelbrecht, Computational Intelligence: an introduction, John Wiley & Sons, 2007.
- B. Awerbuch, A. Baratz, and D. Peleg, Cost-sensetive analysis of communication protocols, Proc. on Principles of Distributed Computing, pp. 177-187, 1990.
- B. Awerbuch, A. Baratz, and D. Peleg, Efficient broadcast and light-weight spanners, Manuscript, 1991.
- K. Bharath-Kumar and J. M. Jaffe, Routing to multiple destinations in computer networks, IEEE Transactions on Communications 31 (3), pp. 343-351, 1983.
- T. Blickle and L. Thiele, A comparison of Selection Schemes Used in Genetic Algorithms (Technical Report No. 11), Swiss Federal Institute of Technology (ETH) Zurich, Computer Engineering and Communications Networks Lab (TIK), 1995.
- R. Campos and M. Ricardo, A fast algorithm for computing minimum routing cost spanning trees, Computer Networks 52 (17), pp. 3229-3247, 2008.
- A. Chipperfield, P. Fleming, H. Pohlheim, and C. Fonseca, The Matlab Genetic Algorithm User's Guide, UK SERC, 1994.
- J. Cong, A. Kahng, G. Robins, M.Sarrafzadeh, and C. K. Wong, Performance-driven global routing for cell based IC's, Proc. IEEE Intl. Conference on Computer Design, pp. 170-173, 1991.
- J. Cong, A. Kahng, G. Robins, M.Sarrafzadeh, and C. K. Wong, Provably good performance-driven global routing, IEEE Transaction on CAD, pp. 739-752, 1992.
- P. Erdos and A. Renyi, On Random Graphs, Publ. Math, 290, 1959.
- H. N. Gabow and E. W. Myers, Finding all spanning trees of directed and undirected graphs, SIAM Journal on Computing, 7, pp. 280-287, 1978.
- J. Hesser and R. Männer, Towards an Optimal Mutation Probability for Genetic Algorithms, Proceedings of 1st workshop in Parallel problem solving from nature, pp. 23-32, 1991.
- G. Huang, X. Li, and J. He, Dynamic Minimal Spanning Tree Routing Protocol for Large Wireless Sensor Networks. In Proceedings of the 1st IEEE Conference on Industrial Electronics and Applications, Singapore, pp. 1-5, 2006.
- S. Khullar, B. Raghavachari, and N. Young, Balancing minimum spanning trees and shortest-path trees, Algorithmica 14, pp. 305- 322, 1995.
- E. Kreyszig, Advanced Engineering Mathematics, John Wiley & Sons, 2011.
- C. Li, H. Zhang, B. Hao, and J. Li, A Survey on Routing Protocols for Large-Scale Wireless Sensor Networks. Sensors 11, pp. 3498-3526, 2011.
- W-Y. LIN, W-Y. LEE, and T-P. Hong, Adapting Crossover and Mutation Rates in Genetic Algorithms, the Sixth Conference on Artificial Intelligence and Applications, Kaohsiung, Taiwan, 2001.
- O. Roeva, S. Fidanova, and M. Paprzycki, Influence of the Population Size on the Genetic Algorithm Performance in Case of Cultivation Process Modelling. In the Proceedings of the Federated Conference on Computer Science and Information Systems pp. 371-376, 2013.
- K. Vekaria and C. Clack, Selective Crossover in Genetic Algorithms: An Empirical Study, volume 1498 of Lecture Notes in Computer Science, pp. 438-447, 1998.
- B. Xiao, Q. ZhuGe, and E. H.-M. Sha, Minimum Dynamic Update for Shortest Path Tree Construction, Global Telecommunications Conference, San Antonio, TX, pp. 126-130, 2001.
- B. Ye We and K. Chao, Spanning Trees and Optimization Problems, Chapman & Hall, 2004.
- M. Sigurd and M. Zachariasen, Construction of Minimum-Weight Spanners, Springer, Verlag Berlin Heidelberg, pp. 797-808, 2004.
- A. M. Farley, D. Zappala A. Proskurowski and K. Windisch, Spanners and Message Distribution in Networks, Dicrete Applied Mathematics, pp. 159-171, 2004.
- J. Gudmundsson, C. Levcopoulos and G. Narasimhan, Fast Greedy Algorithms for Constructing Sparse Geometric Spanners, SIAM Journal on Computing, pp. 1479-1500, 2002.
- G. Navarro, R. Paredes, and E. Chavez, t-Spanners as a Data Structure for Metric Space Searching, International Symposium on String Processing and Information Retrieval, SPIRE, LNCS 2476, pp. 298-309, 2002.