Abstract
Motivated by the telecommunication network design, we study the problem of finding diverse set of minimum spanning trees of a certain complete graph based on the two features which are maximum degree and diameter. In this study, we examine a simple multi-objective EA, GSEMO, in solving the two problems where we maximise or minimise the two features at the same time. With a rigorous runtime analysis, we provide understanding of how GSEMO optimize the set of minimum spanning trees in these two different feature spaces.
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
Abuali, F.N., Schoenefeld, D.A., Wainwright, R.L.: Designing telecommunications networks using genetic algorithms and probabilistic minimum spanning trees. In: Proceedings of the 1994 ACM Symposium on Applied Computing, SAC 1994, pp. 242–246. ACM, New York (1994). https://doi.org/10.1145/326619.326733
Bui, T.N., Zrncic, C.M.: An ant-based algorithm for finding degree-constrained minimum spanning tree. In: Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation, GECCO 2006, pp. 11–18. ACM, New York (2006). https://doi.org/10.1145/1143997.1144000
Chaiyaratana, N., Piroonratana, T., Sangkawelert, N.: Effects of diversity control in single-objective and multi-objective genetic algorithms. J. Heuristics 13(1), 1–34 (2007)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. The MIT Press, Cambridge (2009)
Deb, K., Jain, H.: An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part i: solving problems with box constraints. IEEE Trans. Evol. Comput. 18(4), 577–601 (2014). https://doi.org/10.1109/TEVC.2013.2281535
Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput. 6(2), 182–197 (2002). https://doi.org/10.1109/4235.996017
Dekker, A., Pérez-Rosés, H., Pineda-Villavicencio, G., Watters, P.: The maximum degree & diameter-bounded subgraph and its applications. J. Math. Model. Algorithms 11(3), 249–268 (2012). https://doi.org/10.1007/s10852-012-9182-8
Gao, W., Nallaperuma, S., Neumann, F.: Feature-based diversity optimization for problem instance classification. In: Handl, J., Hart, E., Lewis, P.R., López-Ibáñez, M., Ochoa, G., Paechter, B. (eds.) PPSN 2016. LNCS, vol. 9921, pp. 869–879. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-45823-6_81
Gao, W., Neumann, F.: Runtime analysis for maximizing population diversity in single-objective optimization. In: Genetic and Evolutionary Computation Conference, GECCO 2014, Vancouver, BC, Canada, 12–16 July 2014, pp. 777–784 (2014). https://doi.org/10.1145/2576768.2598251
Giel, O.: Expected runtimes of a simple multi-objective evolutionary algorithm. In: The 2003 Congress on Evolutionary Computation 2003, CEC 2003, vol. 3, pp. 1918–1925, December 2003. https://doi.org/10.1109/CEC.2003.1299908
Gouveia, L., Magnanti, T.L.: Network flow models for designing diameter-constrained minimum-spanning and steiner trees. Networks 41(3), 159–173. https://doi.org/10.1002/net.10069
Khan, M., Pandurangan, G., Kumar, V.S.A.: Distributed algorithms for constructing approximate minimum spanning trees in wireless sensor networks. IEEE Trans. Parallel Distrib. Syst. 20(1), 124–139 (2009). https://doi.org/10.1109/TPDS.2008.57
Könemann, J., Levin, A., Sinha, A.: Approximating the degree-bounded minimum diameter spanning tree problem. Algorithmica 41(2), 117–129 (2005). https://doi.org/10.1007/s00453-004-1121-2
Neumann, A., Gao, W., Doerr, C., Neumann, F., Wagner, M.: Discrepancy-based evolutionary diversity optimization. In: Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2018, Kyoto, Japan, 15–19 July 2018, pp. 991–998 (2018). https://doi.org/10.1145/3205455.3205532
Robins, G., Salowe, J.S.: Low-degree minimum spanning trees. Discrete Comput. Geom. 14, 151–165 (1999)
Ursem, R.K.: Diversity-guided evolutionary algorithms. In: Guervós, J.J.M., Adamidis, P., Beyer, H.-G., Schwefel, H.-P., Fernández-Villacañas, J.-L. (eds.) PPSN 2002. LNCS, vol. 2439, pp. 462–471. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45712-7_45
Zhang, Q., Li, H.: MOEA/D: a multiobjective evolutionary algorithm based on decomposition. IEEE Trans. Evol. Comput. 11(6), 712–731 (2007). https://doi.org/10.1109/TEVC.2007.892759
Zitzler, E., Laumanns, M., Bleuler, S.: A tutorial on evolutionary multiobjective optimization. In: Gandibleux, X., Sevaux, M., Sörensen, K., T’kindt, V. (eds.) Metaheuristics for Multiobjective Optimisation, vol. 535, pp. 3–37. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-642-17144-4_1
Acknowledgements
This work has been supported by Australian Research Council (ARC) grants DP160102401.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Gao, W., Pourhassan, M., Roostapour, V., Neumann, F. (2019). Runtime Analysis of Evolutionary Multi-objective Algorithms Optimising the Degree and Diameter of Spanning Trees. In: Deb, K., et al. Evolutionary Multi-Criterion Optimization. EMO 2019. Lecture Notes in Computer Science(), vol 11411. Springer, Cham. https://doi.org/10.1007/978-3-030-12598-1_40
Download citation
DOI: https://doi.org/10.1007/978-3-030-12598-1_40
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-12597-4
Online ISBN: 978-3-030-12598-1
eBook Packages: Computer ScienceComputer Science (R0)