{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,2]],"date-time":"2025-10-02T16:18:44Z","timestamp":1759421924338,"version":"3.37.3"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,8,8]],"date-time":"2022-08-08T00:00:00Z","timestamp":1659916800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,8,8]],"date-time":"2022-08-08T00:00:00Z","timestamp":1659916800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61562071","61773410"],"award-info":[{"award-number":["61562071","61773410"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Int J Comput Intell Syst"],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The constrained optimization problems can be transformed into multi-objective optimization problems, and thus can be optimized by multi-objective evolutionary algorithms. This method has been successfully used to solve the constrained optimization problems. However, little theoretical work has been done on the performance of multi-objective evolutionary algorithms for the constrained optimization problems. In this paper, we theoretically analyze the performance of a multi-objective evolutionary algorithms on the constrained minimum spanning tree problem. First, we theoretically prove that the multi-objective evolutionary algorithm is capable of finding a (2,1)-approximation solution for the constrained minimum spanning tree problem in a pseudopolynomial runtime. Then, this simple multi-objective evolutionary algorithm is shown to be efficient on a constructed instance of the problem.<\/jats:p>","DOI":"10.1007\/s44196-022-00111-7","type":"journal-article","created":{"date-parts":[[2022,8,8]],"date-time":"2022-08-08T03:11:38Z","timestamp":1659928298000},"update-policy":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On Performance of a Simple Multi-objective Evolutionary Algorithm on the Constrained Minimum Spanning Tree Problem"],"prefix":"10.1007","volume":"15","author":[{"ORCID":"https:\/\/2.zoppoz.workers.dev:443\/https\/orcid.org\/0000-0002-2849-4298","authenticated-orcid":false,"given":"Xinsheng","family":"Lai","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,8,8]]},"reference":[{"issue":"4","key":"111_CR1","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0305-0548(82)90026-0","volume":"9","author":"V Aggarwal","year":"1982","unstructured":"Aggarwal, V., Aneja, Y.P., Nair, K.P.K.: Minimal spanning tree subject to a side constraint. Comput. Oper. Res. 9(4), 287\u2013296 (1982)","journal-title":"Comput. Oper. Res."},{"key":"111_CR2","unstructured":"Ravi, R., Goemans, M.X.: The constrained minimum spanning tree problem. Paper presented at the 5th Scandinavian workshop on algorithm theory, Reykjav\u00edk, Iceland, 3\u20135 July 1996 (1996)"},{"issue":"3","key":"111_CR3","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/j.orl.2003.06.003","volume":"32","author":"SP Hong","year":"2004","unstructured":"Hong, S.P., Chung, S.J., Park, B.H.: A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem. Oper. Res. Lett. 32(3), 233\u2013239 (2004)","journal-title":"Oper. Res. Lett."},{"issue":"2","key":"111_CR4","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1137\/S0097539703426775","volume":"33","author":"R Hassin","year":"2004","unstructured":"Hassin, R., Levin, A.: An efficient polynomial time approximation scheme for the constrained minimum spanning tree problem using matroid intersection. SIAM J. Comput. 33(2), 261\u2013268 (2004)","journal-title":"SIAM J. Comput."},{"key":"111_CR5","doi-asserted-by":"publisher","unstructured":"Chen, Y.H.: Polynomial time approximation schemes for the constrained minimum spanning tree problem. J. Appl. Math. 2012(Article ID 394721) (2012). https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1155\/2012\/394721","DOI":"10.1155\/2012\/394721"},{"key":"111_CR6","doi-asserted-by":"crossref","unstructured":"Zou, N., Guo, L.: Improved approximating algorithms for computing energy constrained minimum cost steiner trees. Paper presented at the 15th International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP 2015), 567\u2013577 (2015)","DOI":"10.1007\/978-3-319-27119-4_39"},{"issue":"1","key":"111_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1162\/evco.1996.4.1.1","volume":"4","author":"Z Michalewicz","year":"1996","unstructured":"Michalewicz, Z., Schoenauer, M.: Evolutionary algorithm for constrained parameter optimization problems. Evol. Comput. 4(1), 1\u201332 (1996)","journal-title":"Evol. Comput."},{"issue":"3","key":"111_CR8","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1109\/4235.873232","volume":"4","author":"Z Michalewicz","year":"2000","unstructured":"Michalewicz, Z., Deb, K., Schmidt, M., Stidsen, T.: Test-case generator for nonlinear continuous parameter optimization techniques. IEEE Trans. Evol. Comput. 4(3), 197\u2013215 (2000)","journal-title":"IEEE Trans. Evol. Comput."},{"issue":"11\u201312","key":"111_CR9","doi-asserted-by":"publisher","first-page":"1245","DOI":"10.1016\/S0045-7825(01)00323-1","volume":"191","author":"CAC Coello","year":"2002","unstructured":"Coello, C.A.C.: Theoretical and numerical constraint-handling techniques used with evolutionary algorithms: a survey of the state of the art. Comput. Methods Appl. Mech. Eng. 191(11\u201312), 1245\u20131287 (2002)","journal-title":"Comput. Methods Appl. Mech. Eng."},{"issue":"1","key":"111_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TEVC.2004.836819","volume":"9","author":"E Mezura-Montes","year":"2005","unstructured":"Mezura-Montes, E., Coello, C.A.C.: A simple multimembered evolution strategy to solve constrained optimization problems. IEEE Trans. Evol. Comput. 9(1), 1\u201317 (2005)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"111_CR11","doi-asserted-by":"crossref","unstructured":"Runarsson, T.P., X., Y.: Search biases in constrained evolutionary optimization. IEEE Trans. Syst. Man Cybern. Part C (Appl. Rev.) 35(2), 233\u2013243 (2005)","DOI":"10.1109\/TSMCC.2004.841906"},{"issue":"1","key":"111_CR12","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1109\/TSMCB.2011.2161467","volume":"42","author":"Y Wang","year":"2012","unstructured":"Wang, Y., Cai, Z.: A dynamic hybrid framework for constrained evolutionary optimization. IEEE Trans. Syst. Man Cybern. Part B: Cybern. 42(1), 203\u2013217 (2012)","journal-title":"IEEE Trans. Syst. Man Cybern. Part B: Cybern."},{"issue":"16","key":"111_CR13","doi-asserted-by":"publisher","first-page":"7077","DOI":"10.1016\/j.eswa.2014.06.032","volume":"41","author":"VVD Melo","year":"2014","unstructured":"Melo, V.V.D., Iacca, G.: A modified covariance matrix adaptation evolution strategy with adaptive penalty function and restart for constrained optimization. Expert Syst. Appl. 41(16), 7077\u20137094 (2014)","journal-title":"Expert Syst. Appl."},{"issue":"3","key":"111_CR14","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1109\/TEVC.2018.2871944","volume":"23","author":"P Spettel","year":"2019","unstructured":"Spettel, P., Beyer, H.G., Hellwig, M.: A covariance matrix self-adaptation evolution strategy for optimization under linear constraints. IEEE Trans. Evol. Comput. 23(3), 514\u2013524 (2019)","journal-title":"IEEE Trans. Evol. Comput."},{"issue":"3","key":"111_CR15","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1080\/03052150008941301","volume":"32","author":"CAC Coello","year":"2000","unstructured":"Coello, C.A.C.: Treating constraints as objectives for single-objective evolutionary optimization. Eng. Optim. 32(3), 275\u2013308 (2000)","journal-title":"Eng. Optim."},{"issue":"6","key":"111_CR16","doi-asserted-by":"publisher","first-page":"658","DOI":"10.1109\/TEVC.2006.872344","volume":"10","author":"Z Cai","year":"2006","unstructured":"Cai, Z., Wang, Y.: A multiobjective optimization-based evolutionary algorithm for constrained optimization. IEEE Trans. Evol. Comput. 10(6), 658\u2013675 (2006)","journal-title":"IEEE Trans. Evol. Comput."},{"issue":"3","key":"111_CR17","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1109\/TEVC.2008.2009032","volume":"13","author":"YG Woldesenbet","year":"2009","unstructured":"Woldesenbet, Y.G., Yen, G.G., Tessema, B.G.: Constraint handling in multi-objective evolutionary optimization. IEEE Trans. Evol. Comput. 13(3), 514\u2013525 (2009)","journal-title":"IEEE Trans. Evol. Comput."},{"issue":"1","key":"111_CR18","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1109\/TEVC.2010.2093582","volume":"16","author":"Y Wang","year":"2012","unstructured":"Wang, Y., Cai, Z.: Combining multiobjective optimization with differential evolution to solve constrained optimization problems. IEEE Trans. Evol. Comput. 16(1), 117\u2013134 (2012)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"111_CR19","doi-asserted-by":"crossref","unstructured":"Witt, C.: Worst-case and average-case approximations by simple randomized search heuristics. Paper presented at the 22nd Annual Symposium on Theoretical Aspects of Computer Science, Stuttgart, Germany, 24-26 February 2005 (2005)","DOI":"10.1007\/978-3-540-31856-9_4"},{"issue":"5","key":"111_CR20","doi-asserted-by":"publisher","first-page":"1006","DOI":"10.1109\/TEVC.2009.2014362","volume":"13","author":"PS Oliveto","year":"2009","unstructured":"Oliveto, P.S., He, J., Yao, X.: Analysis of the (1+1)-EA for finding approximate solutions to vertex cover problems. IEEE Trans. Evol. Comput. 13(5), 1006\u20131029 (2009)","journal-title":"IEEE Trans. Evol. Comput."},{"issue":"4","key":"111_CR21","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1162\/EVCO_a_00003","volume":"18","author":"T Friedrich","year":"2010","unstructured":"Friedrich, T., He, J., Hebbinghaus, N., Neumann, F., Witt, C.: Approximating covering problems by randomized search heuristics using multiobjective models. Evol. Comput. 18(4), 617\u2013633 (2010)","journal-title":"Evol. Comput."},{"key":"111_CR22","doi-asserted-by":"crossref","unstructured":"Neumann, F., Reichel, J.: Approximating minimum multicuts by evolutionary multiobjective algorithms. Paper presented at the 10th International Conference on Parallel Problem Solving from Nature, Dortmund, Germany, 13-17 September 2008, 72\u201381 (2008)","DOI":"10.1007\/978-3-540-87700-4_8"},{"key":"111_CR23","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/j.artint.2012.01.001","volume":"180\u2013181","author":"Y Yu","year":"2012","unstructured":"Yu, Y., Yao, X., Zhou, Z.H.: On the approximation ability of evolutionary optimization with application to minimum set cover. Artif. Intell. 180\u2013181, 20\u201333 (2012)","journal-title":"Artif. Intell."},{"issue":"3","key":"111_CR24","doi-asserted-by":"publisher","first-page":"1620","DOI":"10.1016\/j.ejor.2006.08.005","volume":"181","author":"F Neumann","year":"2007","unstructured":"Neumann, F.: Expected runtimes of a simple evolutionary algorithm for the multi-objective minimum spanning tree problem. Eur. J. Oper. Res. 181(3), 1620\u20131629 (2007)","journal-title":"Eur. J. Oper. Res."},{"issue":"3","key":"111_CR25","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1162\/EVCO_a_00014","volume":"18","author":"C Horoba","year":"2010","unstructured":"Horoba, C.: Exploring the runtime of an evolutionary algorithm for the multi-objective shortest path problem. Evol. Comput. 18(3), 357\u2013381 (2010)","journal-title":"Evol. Comput."},{"issue":"5","key":"111_CR26","doi-asserted-by":"publisher","first-page":"608","DOI":"10.1109\/TEVC.2006.888929","volume":"11","author":"Y Zhou","year":"2007","unstructured":"Zhou, Y., He, J.: A runtime analysis of evolutionary algorithms for constrained optimization problems. IEEE Trans. Evol. Comput. 11(5), 608\u2013619 (2007)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"111_CR27","unstructured":"Qian, C., Yu, Y., Zhou, Z.H.: On constrained boolean pareto optimization. Paper presented at the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2015), Buenos Aires, Argentina, 25-31 July 2015, 389\u2013395 (2015)"},{"issue":"5","key":"111_CR28","doi-asserted-by":"publisher","first-page":"870","DOI":"10.1109\/TEVC.2019.2894743","volume":"23","author":"Z-Z Liu","year":"2019","unstructured":"Liu, Z.-Z., Wang, Y.: Handling constrained multiobjective optimization problems with constraints in both the decision and objective spaces. IEEE Trans. Evol. Comput. 23(5), 870\u2013884 (2019)","journal-title":"IEEE Trans. Evol. Comput."},{"issue":"1","key":"111_CR29","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1109\/TEVC.2020.3004012","volume":"25","author":"Y Tian","year":"2021","unstructured":"Tian, Y., Zhang, T., Xiao, J., Zhang, X., Jin, Y.: A coevolutionary framework for constrained multiobjective optimization problems. IEEE Trans. Evol. Comput. 25(1), 102\u2013116 (2021)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"111_CR30","doi-asserted-by":"publisher","DOI":"10.1109\/TFUZZ.2021.3113571","author":"QB Zha","year":"2021","unstructured":"Zha, Q.B., Dong, Y.C., Chiclana, F., Herrera-Viedma, E.: Consensus reaching in multiple attribute group decision making: a multi-stage optimization feedback mechanism with individual bounded confidences. IEEE Trans. Fuzzy Syst. (2021). https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1109\/TFUZZ.2021.3113571","journal-title":"IEEE Trans. Fuzzy Syst."},{"key":"111_CR31","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/j.artint.2013.09.002","volume":"204","author":"C Qian","year":"2013","unstructured":"Qian, C., Yu, Y., Zhou, Z.H.: An analysis on recombination in multi-objective evolutionary optimization. Artif. Intell. 204, 99\u2013119 (2013)","journal-title":"Artif. Intell."},{"issue":"1","key":"111_CR32","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/s10107-005-0691-3","volume":"108","author":"A Levin","year":"2006","unstructured":"Levin, A., Woeginger, G.J.: The constrained minimum weighted sum of job completion times problem. Math. Program. 108(1), 115\u2013126 (2006)","journal-title":"Math. Program."},{"issue":"4","key":"111_CR33","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1002\/net.3230100403","volume":"10","author":"GY Handler","year":"1980","unstructured":"Handler, G.Y., Zang, I.: A dual algorithm for the constrained shortest path problem. Networks 10(4), 293\u2013309 (1980)","journal-title":"Networks"},{"issue":"1\u20132","key":"111_CR34","first-page":"39","volume":"2","author":"S Gass","year":"2010","unstructured":"Gass, S., Saaty, T.: The computational algorithm for the parametric objective function. Nav. Res. Logist. 2(1\u20132), 39\u201345 (2010)","journal-title":"Nav. Res. Logist."},{"key":"111_CR35","unstructured":"Knowles, J.D., Corne, D.W.: A comparison of encodings and algorithms for multiobjective minimum spanning tree problems. Paper presented at the IEEE Congress on Evolutionary Computation (CEC 2001), Seoul, South Korea, 27\u201330 May 2001 (2001)"},{"key":"111_CR36","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex Optimization","author":"S Boyd","year":"2004","unstructured":"Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004)"},{"issue":"3","key":"111_CR37","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/s10898-006-9052-x","volume":"37","author":"K Klamroth","year":"2007","unstructured":"Klamroth, K., Tind, J.: Constrained optimization using multiple objective programming. J. Global Optim. 37(3), 325\u2013355 (2007)","journal-title":"J. Global Optim."},{"key":"111_CR38","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/BF02579450","volume":"7","author":"M Kano","year":"1987","unstructured":"Kano, M.: Maximum and kth maximal spanning trees of a weighted graph. Combinatorica 7, 205\u2013214 (1987)","journal-title":"Combinatorica"},{"key":"111_CR39","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/BF01305236","volume":"12","author":"EW Mayr","year":"1992","unstructured":"Mayr, E.W., Plaxton, C.G.: On the spanning trees of weighted graphs. Combinatorica 12, 433\u2013447 (1992)","journal-title":"Combinatorica"},{"key":"111_CR40","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/j.tcs.2006.11.002","volume":"378","author":"F Neumann","year":"2007","unstructured":"Neumann, F., Wegener, I.: Randomized local search, evolutionary algorithms, and the minimum spanning tree problem. Theor. Comput. Sci. 378, 32\u201340 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"111_CR41","doi-asserted-by":"publisher","first-page":"673","DOI":"10.1007\/s00453-012-9622-x","volume":"64","author":"B Doerr","year":"2012","unstructured":"Doerr, B., Johannsen, D., Winzen, C.: Multiplicative drift analysis. Algorithmica 64(4), 673\u2013697 (2012)","journal-title":"Algorithmica"}],"container-title":["International Journal of Computational Intelligence Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/link.springer.com\/content\/pdf\/10.1007\/s44196-022-00111-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/link.springer.com\/article\/10.1007\/s44196-022-00111-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/link.springer.com\/content\/pdf\/10.1007\/s44196-022-00111-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,8]],"date-time":"2022-08-08T03:28:55Z","timestamp":1659929335000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/link.springer.com\/10.1007\/s44196-022-00111-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,8]]},"references-count":41,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2022,12]]}},"alternative-id":["111"],"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1007\/s44196-022-00111-7","relation":{},"ISSN":["1875-6883"],"issn-type":[{"type":"electronic","value":"1875-6883"}],"subject":[],"published":{"date-parts":[[2022,8,8]]},"assertion":[{"value":"18 December 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 July 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 August 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of Interest"}},{"value":"No applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics Approval and Consent to Participate"}},{"value":"No applicable.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for Publication"}}],"article-number":"57"}}