{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,17]],"date-time":"2026-08-17T16:12:50Z","timestamp":1786983170028,"version":"build-2736575974"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,4,29]],"date-time":"2024-04-29T00:00:00Z","timestamp":1714348800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,4,29]],"date-time":"2024-04-29T00:00:00Z","timestamp":1714348800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100011033","name":"Agencia Estatal de Investigaci\u00f3n","doi-asserted-by":"publisher","award":["TED2021-129319B-I00"],"award-info":[{"award-number":["TED2021-129319B-I00"]}],"id":[{"id":"10.13039\/501100011033","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100011033","name":"Agencia Estatal de Investigaci\u00f3n","doi-asserted-by":"publisher","award":["PID2022-136787NB-I00"],"award-info":[{"award-number":["PID2022-136787NB-I00"]}],"id":[{"id":"10.13039\/501100011033","id-type":"DOI","asserted-by":"publisher"}]},{"name":"FONDECYT","award":["11230359"],"award-info":[{"award-number":["11230359"]}]},{"DOI":"10.13039\/501100003339","name":"Consejo Superior de Investigaciones Cientificas","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100003339","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Int J Comput Intell Syst"],"abstract":"Abstract<\/jats:title>\n \n One of the problems with exact techniques for solving combinatorial optimization problems is that they tend to run into problems with growing problem instance size. Nevertheless, they might still be very usefully employed, even in the context of large problem instances, as a sub-ordinate method within so-called hybrid metaheuristics. \u201cConstruct, Merge, Solve and Adapt\u201d (\n Cmsa<\/jats:sc>\n ) is a hybrid metaheuristic technique that allows the application of exact methods to large-scale problem instances through intelligent instance reduction. However,\n Cmsa<\/jats:sc>\n does not make use of an explicit learning mechanism. In this work, an algorithm called\n \n \n $$\\textsc {Learn}\\_\\textsc {Cmsa}$$<\/jats:tex-math>\n \n \n L<\/mml:mi>\n \n E<\/mml:mi>\n A<\/mml:mi>\n R<\/mml:mi>\n N<\/mml:mi>\n <\/mml:mstyle>\n _<\/mml:mi>\n C<\/mml:mi>\n \n M<\/mml:mi>\n S<\/mml:mi>\n A<\/mml:mi>\n <\/mml:mstyle>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n is presented for the application to the far from most string problem (FFMSP), which is an NP-hard combinatorial optimization problem from the field of string consensus problems.\n \n \n $$\\textsc {Learn}\\_\\textsc {Cmsa}$$<\/jats:tex-math>\n \n \n L<\/mml:mi>\n \n E<\/mml:mi>\n A<\/mml:mi>\n R<\/mml:mi>\n N<\/mml:mi>\n <\/mml:mstyle>\n _<\/mml:mi>\n C<\/mml:mi>\n \n M<\/mml:mi>\n S<\/mml:mi>\n A<\/mml:mi>\n <\/mml:mstyle>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n results from hybridization between\n Cmsa<\/jats:sc>\n and a population-based algorithm. By means of this hybridization, explicit learning is introduced to\n Cmsa<\/jats:sc>\n . Even though the FFMSP is a well-studied problem,\n \n \n $$\\textsc {Learn}\\_\\textsc {Cmsa}$$<\/jats:tex-math>\n \n \n L<\/mml:mi>\n \n E<\/mml:mi>\n A<\/mml:mi>\n R<\/mml:mi>\n N<\/mml:mi>\n <\/mml:mstyle>\n _<\/mml:mi>\n C<\/mml:mi>\n \n M<\/mml:mi>\n S<\/mml:mi>\n A<\/mml:mi>\n <\/mml:mstyle>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n achieves superior performance when compared to current state-of-the-art solvers.\n <\/jats:p>","DOI":"10.1007\/s44196-024-00488-7","type":"journal-article","created":{"date-parts":[[2024,4,29]],"date-time":"2024-04-29T06:02:05Z","timestamp":1714370525000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Extension of CMSA with a Learning Mechanism: Application to the Far from Most String Problem"],"prefix":"10.1007","volume":"17","author":[{"given":"Pedro","family":"Pinacho-Davidson","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1736-3559","authenticated-orcid":false,"given":"Christian","family":"Blum","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"M. Ang\u00e9lica","family":"Pinninghoff","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ricardo","family":"Contreras","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2024,4,29]]},"reference":[{"key":"488_CR1","volume-title":"Hybrid Metaheuristics. Powerful Tools for Optimization","author":"C Blum","year":"2016","unstructured":"Blum, C., Raidl, G.R.: Hybrid Metaheuristics. Powerful Tools for Optimization. Springer, Switzerland (2016)"},{"key":"488_CR2","doi-asserted-by":"crossref","unstructured":"Raidl, G.R., Puchinger, J., Blum, C.: In: Gendreau, M., Potvin, J.-Y. (eds.) Metaheuristic Hybrids. Springer, Cham (2019)","DOI":"10.1007\/978-3-319-91086-4_12"},{"key":"488_CR3","doi-asserted-by":"crossref","unstructured":"Boschetti, M.A., Maniezzo, V., Roffilli, M., Boluf\u00e9\u00a0R\u00f6hler, A.: Matheuristics: Optimization, simulation and control. In: Blesa, M.J., Blum, C., Di\u00a0Gaspero, L., Roli, A., Sampels, M., Schaerf, A. (eds.) Proceedings of HM 2009 \u2013 6th International Workshop on Hybrid Metaheuristics. Lecture Notes in Computer Science, vol. 5818, pp. 171\u2013177. Springer, Berlin, Heidelberg (2009)","DOI":"10.1007\/978-3-642-04918-7_13"},{"key":"488_CR4","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.cor.2015.10.014","volume":"68","author":"C Blum","year":"2016","unstructured":"Blum, C., Pinacho, P., L\u00f3pez-Ib\u00e1nez, M., Lozano, J.A.: Construct, merge, solve & adapt: A new general algorithm for combinatorial optimization. Comput. Oper. Res. 68, 75\u201388 (2016)","journal-title":"Comput. Oper. Res."},{"key":"488_CR5","doi-asserted-by":"crossref","unstructured":"Blum, C.: Construct, Merge, Solve and Adapt: Application to unbalanced minimum common string partition. In: Blesa, M.J., Blum, C., Cangelosi, A., Cutello, V., Di\u00a0Nuovo, A., Pavone, M., Talbi, E.-G. (eds.) Proceedings of HM 2016 \u2013 10th International Workshop on Hybrid Metaheuristics. Lecture Notes in Computer Science, vol. 9668, pp. 17\u201331. Springer, Cham (2016)","DOI":"10.1007\/978-3-319-39636-1_2"},{"key":"488_CR6","doi-asserted-by":"crossref","unstructured":"Thiruvady, D., Blum, C., Ernst, A.T.: Maximising the net present value of project schedules using CMSA and parallel ACO. In: Blesa, M.J., Blum, C., Gambini\u00a0Santos, H., Pinacho-Davidson, P., Campo, J. (eds.) Proceedings of HM 2019 \u2013 11th International Workshop on Hybrid Metaheuristics. Lecture Notes in Computer Science, vol. 11299, pp. 16\u201330. Springer, Cham (2019)","DOI":"10.1007\/978-3-030-05983-5_2"},{"key":"488_CR7","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/j.cor.2018.11.015","volume":"103","author":"R Lewis","year":"2019","unstructured":"Lewis, R., Thiruvady, D., Morgan, K.: Finding happiness: An analysis of the maximum happy vertices problem. Comput. Oper. Res. 103, 265\u2013276 (2019)","journal-title":"Comput. Oper. Res."},{"key":"488_CR8","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/s10732-020-09462-w","volume":"27","author":"J Ferrer","year":"2021","unstructured":"Ferrer, J., Chicano, F., Ortega-Toro, J.A.: CMSA algorithm for solving the prioritized pairwise test data generation problem in software product lines. J. Heuristics 27, 229\u2013249 (2021)","journal-title":"J. Heuristics"},{"issue":"8","key":"488_CR9","first-page":"1200","volume":"4","author":"SR Mousavi","year":"2010","unstructured":"Mousavi, S.R.: A hybridization of constructive beam search with local search for far from most strings problem. Int. J. Comput. Inform. Eng. 4(8), 1200\u20131208 (2010)","journal-title":"Int. J. Comput. Inform. Eng."},{"key":"488_CR10","doi-asserted-by":"crossref","unstructured":"Blum, C., Festa, P.: A hybrid ant colony optimization algorithm for the far from most string problem. In: Proceedings of EvoCOP 2014 \u2013 European Conference on Evolutionary Computation in Combinatorial Optimization, pp. 1\u201312. Springer, Berlin, Heidelberg (2014)","DOI":"10.1007\/978-3-662-44320-0_1"},{"issue":"4","key":"488_CR11","first-page":"1204","volume":"2","author":"ST Odonkor","year":"2011","unstructured":"Odonkor, S.T., Addo, K.K.: Bacteria resistance to antibiotics: Recent trends and challenges. Int. J. Biol. Med. Res. 2(4), 1204\u20131210 (2011)","journal-title":"Int. J. Biol. Med. Res."},{"key":"488_CR12","doi-asserted-by":"crossref","unstructured":"Ricardo\u00a0Contreras, A., Valentina\u00a0Hern\u00e1ndez, P., Pinacho-Davidson, P., Ang\u00e9lica Pinninghoff\u00a0J., M.: A bacteria-based metaheuristic as a tool for group formation. In: Proceedings of IWINAC 2022 \u2013 9th International Work-Conference on the Interplay Between Natural and Artificial Computation. Lecture Notes in Computer Science, vol. 13259, pp. 443\u2013451. Springer, Berlin, Heidelberg (2022)","DOI":"10.1007\/978-3-031-06527-9_44"},{"issue":"1","key":"488_CR13","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/S0890-5401(03)00057-9","volume":"185","author":"J Lanctot","year":"2003","unstructured":"Lanctot, J., Li, M., Ma, B., Wang, S., Zhang, L.: Distinguishing string selection problems. Inform. Comput. 185(1), 41\u201355 (2003)","journal-title":"Inform. Comput."},{"issue":"3","key":"488_CR14","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1109\/MEMB.2005.1436464","volume":"24","author":"CN Meneses","year":"2005","unstructured":"Meneses, C.N., Oliveira, C.A., Pardalos, P.M.: Optimization techniques for string selection and comparison problems in genomics. IEEE Eng. Med. Biol. Magaz. 24(3), 81\u201387 (2005)","journal-title":"IEEE Eng. Med. Biol. Magaz."},{"issue":"2","key":"488_CR15","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/j.mbs.2006.11.012","volume":"207","author":"P Festa","year":"2007","unstructured":"Festa, P.: On some optimization problems in mulecolar biology. Math. Biosci. 207(2), 219\u2013234 (2007)","journal-title":"Math. Biosci."},{"issue":"1","key":"488_CR16","doi-asserted-by":"publisher","first-page":"663","DOI":"10.1007\/s10479-011-1028-7","volume":"196","author":"P Festa","year":"2012","unstructured":"Festa, P., Pardalos, P.M.: Efficient solutions for the far from most string problem. Ann. Oper. Res. 196(1), 663\u2013682 (2012)","journal-title":"Ann. Oper. Res."},{"key":"488_CR17","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/s10732-011-9177-z","volume":"18","author":"SR Mousavi","year":"2012","unstructured":"Mousavi, S.R., Babaie, M., Montazerian, M.: An improved heuristic for the far from most strings problem. J. Heuristics 18, 239\u2013262 (2012)","journal-title":"J. Heuristics"},{"key":"488_CR18","doi-asserted-by":"crossref","unstructured":"Ferone, D., Festa, P., Resende, M.G.C.: Hybrid metaheuristics for the far from most string problem. In: Blesa, M.J., Blum, C., Festa, P., Roli, A., Sampels, M. (eds.) 8th International Workshop on Hybrid Metaheuristics. Lecture Notes in Computer Science, vol. 7919, pp. 174\u2013188. Springer, Berlin, Heidelberg (2013)","DOI":"10.1007\/978-3-642-38516-2_14"},{"key":"488_CR19","doi-asserted-by":"crossref","unstructured":"Ferone, D., Festa, P., Resende, M.G.C.: Hybridizations of grasp with path relinking for the far from most string problem. Int. Trans. Oper. Res. 23(3), 481\u2013506 (2016)","DOI":"10.1111\/itor.12167"},{"key":"488_CR20","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/j.engappai.2015.01.020","volume":"41","author":"JE Gallardo","year":"2015","unstructured":"Gallardo, J.E., Cotta, C.: A GRASP-based memetic algorithm with path relinking for the far from most string problem. Eng. Appl. Artif. Intell. 41, 183\u2013194 (2015)","journal-title":"Eng. Appl. Artif. Intell."},{"key":"488_CR21","doi-asserted-by":"crossref","unstructured":"Blum, C., Pinacho-Davidson, P.: Application of negative learning ant colony optimization to the far from most string problem. In: Proceedings of EvoCOP \u2013 European Conference on Evolutionary Computation in Combinatorial Optimization. Lecture Notes in Computer Science, vol. 13987, pp. 82\u201397. Springer, Cham (2023)","DOI":"10.1007\/978-3-031-30035-6_6"},{"key":"488_CR22","doi-asserted-by":"crossref","unstructured":"Pinninghoff\u00a0J, M.A., Orellana\u00a0M, J., Contreras\u00a0A, R.: Bacterial resistance algorithm. an application to CVRP. In: Proceedings of IWINAC 2019 \u2013 8th International Work-Conference on the Interplay Between Natural and Artificial Computation. Lecture Notes in Computer Science, vol. 11487, pp. 204\u2013211. Springer, Cham (2019)","DOI":"10.1007\/978-3-030-19651-6_20"},{"key":"488_CR23","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/j.orp.2016.09.002","volume":"3","author":"M L\u00f3pez-Ib\u00e1\u00f1ez","year":"2016","unstructured":"L\u00f3pez-Ib\u00e1\u00f1ez, M., Dubois-Lacoste, J., C\u00e1ceres, L.P., Birattari, M., St\u00fctzle, T.: The irace package: Iterated racing for automatic algorithm configuration. Oper. Res. Perspectiv. 3, 43\u201358 (2016)","journal-title":"Oper. Res. Perspectiv."},{"key":"488_CR24","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1007\/978-3-031-30035-6_6","volume-title":"Evolutionary Computation in Combinatorial Optimization","author":"C Blum","year":"2023","unstructured":"Blum, C., Pinacho-Davidson, P.: Application of negative learning ant colony optimization to the far from most string problem. In: P\u00e9rez C\u00e1ceres, L., St\u00fctzle, T. (eds.) Evolutionary Computation in Combinatorial Optimization, pp. 82\u201397. Springer, Cham (2023)"},{"key":"488_CR25","first-page":"2677","volume":"9","author":"S Garc\u00eda","year":"2008","unstructured":"Garc\u00eda, S., Herrera, F.: An extension on \u201cstatistical comparisons of classifiers over multiple data sets\u2019\u2019 for all pairwise comparisons. J. Mach. Learn. Res. 9, 2677\u20132694 (2008)","journal-title":"J. Mach. Learn. Res."}],"container-title":["International Journal of Computational Intelligence Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s44196-024-00488-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s44196-024-00488-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s44196-024-00488-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,29]],"date-time":"2024-04-29T06:03:47Z","timestamp":1714370627000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s44196-024-00488-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,29]]},"references-count":25,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2024,12]]}},"alternative-id":["488"],"URL":"https:\/\/doi.org\/10.1007\/s44196-024-00488-7","relation":{},"ISSN":["1875-6883"],"issn-type":[{"value":"1875-6883","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,4,29]]},"assertion":[{"value":"5 December 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 March 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 April 2024","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 no conflicts of interest. The funders played no part in the study\u2019s design, data collection, analysis, interpretation, manuscript writing, or decision to publish the results.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"109"}}