Abstract
Evolutionary algorithms (EAs) are stochastic heuristic algorithms which are often successfully used for solving many optimization problems. However, the rigorous theoretical analysis results on the behavior of EAs on combinatorial optimizations are comparatively scarce, especially for NP-hard optimization problems. In this paper, we theoretically investigate the approximation performance of the (1+1) EA, a simple version of EAs on the minimum degree spanning tree (MDST) problem which is a classical NP-hard optimization problem. We show that the (1+1) EA can obtain an approximate solution for the MDST problem with maximum degree at most \(O(\varDelta _{opt}+\log n)\) in expected polynomial runtime \(O(m^2n^3+m\log n)\), where \(\varDelta _{opt}\) is the maximal degree of the optimal spanning tree. It implies that EAs can obtain solutions with guaranteed performance on the MDST problem.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)
Fürer, M., Raghavachari, B.: An NC approximation algorithm for the minimum degree spanning tree problem. In: Proceedings of the 28th Annual Allerton Conference on Communication, Control and Computing, pp. 274–281 (1990)
Fürer, M., Raghavachari, B.: Approximating the minimum degree spanning tree to within one from the optimal degree. In: Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 317–324. ACM, USA (1992)
Ravi, R., Raghavachari, B., Klein, P.: Approximation through local optimality: designing networks with small degree. In: Shyamasundar, R.K. (ed.) FSTTCS 1992. LNCS, vol. 652, pp. 279–290. Springer, Heidelberg (1992)
Fürer, M., Raghavachari, B.: Approximating the minimum-degree steiner tree to within one of optimal. J. Algorithms 17, 409–423 (1994)
Gallagher, K., Sambridge, M.: Genetic algorithms: a powerful tool for large-scale non-linear optimization problems. Comput. Geosci. 20(7–8), 1229–1236 (1994)
Droste, S., Jansen, T., Wegener, I.: On the analysis of the (1+1) evolutionary algorithm. Theor. Comput. Sci. 276, 51–81 (2002)
Jansen, T.: Analyzing Evolutionary Algorithms - The Computer Science Perspective. Natural Computing Series. Springer, Heidelberg (2013)
Neumann, F., Wegener, I.: Randomized local search, evolutionary algorithms, and the minimum spanning tree problem. Theor. Comput. Sci. 378(1), 32–40 (2007)
Witt, C.: Worst-case and average-case approximations by simple randomized search heuristics. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol. 3404, pp. 44–56. Springer, Heidelberg (2005)
Yu, Y., Yao, X., Zhou, Z.: On the approximation ability of evolutionary optimization with application to minimum set cover. Artif. Intell. 180–181, 20–33 (2012)
Xia, X., Zhou, Y., Lai, X.: On the analysis of the (1+1) evolutionary algorithm for the maximum leaf spanning tree problem. Int. J. Comput. Math. 92(10), 2023–2035 (2015)
Raidl, G.R., Julstrom, B.A.: Edge sets: an effective evolutionary coding of spanning tree. IEEE Trans. Evol. Comput. 7(3), 225–239 (2003)
Zhang, X., Tian, Y., Jin, Y.: A knee point driven evolutionary algorithm for many-objective optimization. IEEE Trans. Evol. Comput. PP(99), 1 (2014). doi:10.1109/TEVC.2014.2378512
Zhang, X., Tian, Y., Cheng, R., Jin, Y.: An efficient approach to non-dominated sorting for evolutionary multi-objective optimization. IEEE Trans. Evol. Comput. 19(2), 201–213 (2015)
Chen, T., Tang, K., Chen, G., Yao, X.: A large population size can be unhelpful in evolutionary algorithms. Theor. Comput. Sci. 436, 54–70 (2012)
Doerr, B., Johannsen, D., Winzen, C.: Multiplicative drift analysis. Algorithmica 64, 673–697 (2012)
Acknowledgments
This work was supported by National Natural Science Foundation of China (61170081, 61472143), and Natural Science Foundation of Jiangxi Province of China (20151BAB217008).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Xia, X., Zhou, Y. (2015). Approximation Performance of the (1+1) Evolutionary Algorithm for the Minimum Degree Spanning Tree Problem. In: Gong, M., Linqiang, P., Tao, S., Tang, K., Zhang, X. (eds) Bio-Inspired Computing -- Theories and Applications. BIC-TA 2015. Communications in Computer and Information Science, vol 562. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-49014-3_45
Download citation
DOI: https://doi.org/10.1007/978-3-662-49014-3_45
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-49013-6
Online ISBN: 978-3-662-49014-3
eBook Packages: Computer ScienceComputer Science (R0)