{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,8]],"date-time":"2025-07-08T16:43:51Z","timestamp":1751993031435,"version":"3.41.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,6,8]],"date-time":"2024-06-08T00:00:00Z","timestamp":1717804800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Brazil by S\u00e3o Paulo Research Foundation - FAPESP","award":["#2021\/09720-2"],"award-info":[{"award-number":["#2021\/09720-2"]}]},{"name":"National Council for Scientific and Technological Development - CNPq","award":["#306689\/2021-9"],"award-info":[{"award-number":["#306689\/2021-9"]}]},{"name":"Center for Artificial Intelligence - C4AI","award":["#2019\/07665-4"],"award-info":[{"award-number":["#2019\/07665-4"]}]},{"name":"Polish National Science Centre - NCN","award":["#2022\/45\/B\/ST6\/04150"],"award-info":[{"award-number":["#2022\/45\/B\/ST6\/04150"]}]},{"name":"PID","award":["2020-116727RB-I00"],"award-info":[{"award-number":["2020-116727RB-I00"]}]},{"name":"EU Horizon 2020 research and innovation programme","award":["MCIN\/AEI\/10.13039\/501100011033 and TAILOR ICT-48 Network (No 952215)"],"award-info":[{"award-number":["MCIN\/AEI\/10.13039\/501100011033 and TAILOR ICT-48 Network (No 952215)"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Evol. Learn. Optim."],"published-print":{"date-parts":[[2024,6,30]]},"abstract":"<jats:p>In pseudo-Boolean optimization, a variable interaction graph represents variables as vertices, and interactions between pairs of variables as edges. In black-box optimization, the variable interaction graph may be at least partially discovered by using empirical linkage learning techniques. These methods never report false variable interactions, but they are computationally expensive. The recently proposed local search with linkage learning discovers the partial variable interaction graph as a side-effect of iterated local search. However, information about the strength of the interactions is not learned by the algorithm. We propose local search with linkage learning 2, which builds a weighted variable interaction graph that stores information about the strength of the interaction between variables. The weighted variable interaction graph can provide new insights about the optimization problem and behavior of optimizers. Experiments with NK landscapes, knapsack problem, and feature selection show that local search with linkage learning 2 is able to efficiently build weighted variable interaction graphs. In particular, experiments with feature selection show that the weighted variable interaction graphs can be used for visualizing the feature interactions in machine learning. Additionally, new transformation operators that exploit the interactions between variables can be designed. We illustrate this ability by proposing a new perturbation operator for iterated local search.<\/jats:p>","DOI":"10.1145\/3651165","type":"journal-article","created":{"date-parts":[[2024,3,2]],"date-time":"2024-03-02T11:21:07Z","timestamp":1709378467000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Iterated Local Search with Linkage Learning"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4027-8851","authenticated-orcid":false,"given":"Renato","family":"Tin\u00f3s","sequence":"first","affiliation":[{"name":"University of S\u00e3o Paulo, Ribeir\u00e3o Preto, Brazil"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2446-6473","authenticated-orcid":false,"given":"Michal W.","family":"Przewozniczek","sequence":"additional","affiliation":[{"name":"Wroclaw University of Science and Technology, Wroclaw, Poland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2752-6534","authenticated-orcid":false,"given":"Darrell","family":"Whitley","sequence":"additional","affiliation":[{"name":"Colorado State University, Fort Collins, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1259-2990","authenticated-orcid":false,"given":"Francisco","family":"Chicano","sequence":"additional","affiliation":[{"name":"University of M\u00e1laga, Malaga, Spain"}]}],"member":"320","published-online":{"date-parts":[[2024,6,8]]},"reference":[{"key":"e_1_3_2_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(99)00265-9"},{"issue":"10","key":"e_1_3_2_3_1","first-page":"264216","article-title":"Reactive search, a history-based heuristic for MAX-SAT","volume":"2","author":"Battiti R.","year":"1997","unstructured":"R. Battiti and M. Protasi. 1997. Reactive search, a history-based heuristic for MAX-SAT. ACM Journal of Experimental Algorithmics 2, 10.1145 (1997), 264216\u2013264220.","journal-title":"ACM Journal of Experimental Algorithmics"},{"key":"e_1_3_2_4_1","first-page":"637","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference","author":"Bosman P. A. N.","year":"2016","unstructured":"P. A. N. Bosman, N. H. Luong, and D. Thierens. 2016. Expanding from discrete cartesian to permutation gene-pool optimal mixing evolutionary algorithms. In Proceedings of the Genetic and Evolutionary Computation Conference. 637\u2013644."},{"issue":"2","key":"e_1_3_2_5_1","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1016\/j.ejor.2020.01.008","article-title":"A memory-based iterated local search algorithm for the multi-depot open vehicle routing problem","volume":"284","author":"Brand\u00e3o J.","year":"2020","unstructured":"J. Brand\u00e3o. 2020. A memory-based iterated local search algorithm for the multi-depot open vehicle routing problem. European Journal of Operational Research 284, 2 (2020), 559\u2013571.","journal-title":"European Journal of Operational Research"},{"key":"e_1_3_2_6_1","doi-asserted-by":"crossref","first-page":"921","DOI":"10.1145\/3205455.3205482","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference","author":"Chen W.","year":"2018","unstructured":"W. Chen, D. Whitley, R. Tin\u00f3s, and F. Chicano. 2018. Tunneling between plateaus: Improving on a state-of-the-art MAXSAT solver using partition crossover. In Proceedings of the Genetic and Evolutionary Computation Conference. 921\u2013928."},{"key":"e_1_3_2_7_1","article-title":"Dynastic potential crossover operator","author":"Chicano F.","year":"2022","unstructured":"F. Chicano, G. Ochoa, D. Whitley, and R. Tin\u00f3s. 2022. Dynastic potential crossover operator. Evolutionary Computation 30, 3 (2022), 409\u2013446.","journal-title":"Evolutionary Computation"},{"key":"e_1_3_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3071178.3071285"},{"key":"e_1_3_2_9_1","first-page":"437","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference","author":"Chicano F.","year":"2014","unstructured":"F. Chicano, D. Whitley, and A. M. Sutton. 2014. Efficient identification of improving moves in a ball for pseudo-boolean problems. In Proceedings of the Genetic and Evolutionary Computation Conference. 437\u2013444."},{"key":"e_1_3_2_10_1","first-page":"1133","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference","author":"Coffin D. J.","year":"2006","unstructured":"D. J. Coffin and C. D. Clack. 2006. gLINC: Identifying composability using group perturbation. In Proceedings of the Genetic and Evolutionary Computation Conference. 1133\u20131140."},{"key":"e_1_3_2_11_1","doi-asserted-by":"crossref","first-page":"1623","DOI":"10.1007\/978-3-540-92910-9_49","volume-title":"Handbook of Natural Computing","author":"Dowsland K. A.","year":"2012","unstructured":"K. A. Dowsland and J. Thompson. 2012. Simulated annealing. In Handbook of Natural Computing, G. Rozenberg, T. B\u00e4ck, and J. Kok (Eds.). Springer-Verlag, 1623\u20131655."},{"key":"e_1_3_2_12_1","unstructured":"D. Dua and C. Graff. 2017. UCI Machine Learning Repository. Retrieved from http:\/\/archive.ics.uci.edu\/ml. Accessed May 25 2022."},{"key":"e_1_3_2_13_1","first-page":"916","article-title":"Predictive learning via rule ensembles","author":"Friedman J. H.","year":"2008","unstructured":"J. H. Friedman and B. E. Popescu. 2008. Predictive learning via rule ensembles. The Annals of Applied Statistics 2, 3 (2008), 916\u2013954.","journal-title":"The Annals of Applied Statistics"},{"key":"e_1_3_2_14_1","first-page":"785","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference","author":"Goldman B. W.","year":"2014","unstructured":"B. W. Goldman and W. F. Punch. 2014. Parameter-less population pyramid. In Proceedings of the Genetic and Evolutionary Computation Conference. 785\u2013792."},{"key":"e_1_3_2_15_1","first-page":"1354","volume-title":"Proceedings of the IEEE Congress on Evolutionary Computation","volume":"2","author":"Han K.-H.","year":"2000","unstructured":"K.-H. Han and J.-H. Kim. 2000. Genetic quantum algorithm and its application to combinatorial optimization problem. In Proceedings of the IEEE Congress on Evolutionary Computation. Vol. 2, 1354\u20131360."},{"key":"e_1_3_2_16_1","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/0-306-48056-5_6","volume-title":"Handbook of Metaheuristics","author":"Hansen P.","year":"2003","unstructured":"P. Hansen and N. Mladenovi\u0107. 2003. Variable neighborhood search. In Handbook of Metaheuristics, F. Glover and G. A. Kochenberger (Eds.). Springer, 145\u2013184."},{"key":"e_1_3_2_17_1","doi-asserted-by":"publisher","DOI":"10.1162\/106365602760972758"},{"key":"e_1_3_2_18_1","doi-asserted-by":"publisher","DOI":"10.1162\/1063656043138914"},{"key":"e_1_3_2_19_1","first-page":"519","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference","author":"Hsu S.-H.","year":"2015","unstructured":"S.-H. Hsu and T.-L. Yu. 2015. Optimization by pairwise linkage detection, incremental linkage set, and restricted \/ back mixing: DSMGA-II. In Proceedings of the Genetic and Evolutionary Computation Conference. 519\u2013526."},{"key":"e_1_3_2_20_1","doi-asserted-by":"crossref","first-page":"766","DOI":"10.1080\/10618600.2021.2007935","article-title":"Visualizing variable importance and variable interaction effects in machine learning models","author":"Inglis A.","year":"2022","unstructured":"A. Inglis, A. Parnell, and C. B. Hurley. 2022. Visualizing variable importance and variable interaction effects in machine learning models. Journal of Computational and Graphical Statistics 31, 3 (2022), 766\u2013778.","journal-title":"Journal of Computational and Graphical Statistics"},{"key":"e_1_3_2_21_1","doi-asserted-by":"crossref","DOI":"10.1016\/j.swevo.2021.100973","article-title":"A prescription of methodological guidelines for comparing bio-inspired optimization algorithms","volume":"67","author":"LaTorre A.","year":"2021","unstructured":"A. LaTorre, D. Molina, E. Osaba, J. Poyatos, J. Del Ser, and F. Herrera. 2021. A prescription of methodological guidelines for comparing bio-inspired optimization algorithms. Swarm and Evolutionary Computation 67, 100973 (2021), 1\u201325.","journal-title":"Swarm and Evolutionary Computation"},{"key":"e_1_3_2_22_1","volume-title":"Benchmark Functions for the CEC 2013 Special Session and Competition on Large-scale Global Optimization","author":"Li X.","year":"2013","unstructured":"X. Li, K. Tang, M. N. Omidvar, Z. Yang, and K. Qin. 2013. Benchmark Functions for the CEC 2013 Special Session and Competition on Large-scale Global Optimization. Technical Report. RMIT University, Australia."},{"key":"e_1_3_2_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-91086-4_5"},{"key":"e_1_3_2_24_1","first-page":"1","volume-title":"Proceedings of the European Conference on Evolutionary Computation in Combinatorial Optimization","author":"L\u00fc Z.","year":"2009","unstructured":"Z. L\u00fc and J.-K. Hao. 2009. A critical element-guided perturbation strategy for iterated local search. In Proceedings of the European Conference on Evolutionary Computation in Combinatorial Optimization. Springer, 1\u201312."},{"key":"e_1_3_2_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.swevo.2012.05.001"},{"key":"e_1_3_2_26_1","first-page":"555","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference","author":"Ochoa G.","year":"2008","unstructured":"G. Ochoa, M. Tomassini, S. V\u00e9rel, and C. Darabos. 2008. A study of NK landscapes\u2019 basins and local optima networks. In Proceedings of the Genetic and Evolutionary Computation Conference. 555\u2013562."},{"key":"e_1_3_2_27_1","volume-title":"Combinatorial Optimization: Algorithms and Complexity","author":"Papadimitriou C. H.","year":"1998","unstructured":"C. H. Papadimitriou and K. Steiglitz. 1998. Combinatorial Optimization: Algorithms and Complexity. Dover Publications."},{"key":"e_1_3_2_28_1","first-page":"742","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference","author":"Przewozniczek M. W.","year":"2020","unstructured":"M. W. Przewozniczek, B. Frej, and M. M. Komarnicki. 2020. On measuring and improving the quality of linkage learning in modern evolutionary algorithms applied to solve partially additively separable problems. In Proceedings of the Genetic and Evolutionary Computation Conference. 742\u2013750."},{"key":"e_1_3_2_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2020.2985497"},{"key":"e_1_3_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3449639.3459333"},{"key":"e_1_3_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3512290.3528734"},{"key":"e_1_3_2_32_1","volume-title":"Characterizing and Benchmarking QUBO Reformulations of the Knapsack Problem","author":"Quintero R. A.","year":"2021","unstructured":"R. A. Quintero and L. F. Zuluaga. 2021. Characterizing and Benchmarking QUBO Reformulations of the Knapsack Problem. Technical Report. Department of Industrial and Systems Engineering, Lehigh."},{"key":"e_1_3_2_33_1","first-page":"289","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference","author":"Thierens D.","year":"2012","unstructured":"D. Thierens and P. A. N. Bosman. 2012. Predetermined versus Learned Linkage Models. In Proceedings of the Genetic and Evolutionary Computation Conference. 289\u2013296."},{"key":"e_1_3_2_34_1","first-page":"877","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference","author":"Thierens D.","year":"2013","unstructured":"D. Thierens and P. A. N. Bosman. 2013. Hierarchical problem solving with the linkage tree genetic algorithm. In Proceedings of the Genetic and Evolutionary Computation Conference. 877\u2013884."},{"key":"e_1_3_2_35_1","doi-asserted-by":"crossref","DOI":"10.1016\/j.asoc.2020.106512","article-title":"Artificial neural network based crossover for evolutionary algorithms","volume":"95","author":"Tin\u00f3s R.","year":"2020","unstructured":"R. Tin\u00f3s. 2020. Artificial neural network based crossover for evolutionary algorithms. Applied Soft Computing 95, 106512 (2020), 1\u201314.","journal-title":"Applied Soft Computing"},{"key":"e_1_3_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3512290.3528716"},{"key":"e_1_3_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2725494.2725497"},{"key":"e_1_3_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3449639.3459296"},{"issue":"21","key":"e_1_3_2_39_1","first-page":"e104\u2013e107","article-title":"Computational radiomics system to decode the radiographic phenotype","volume":"77","author":"Griethuysen J. J. M. Van","year":"2017","unstructured":"J. J. M. Van Griethuysen, A. Fedorov, C. Parmar, A. Hosny, N. Aucoin, V. Narayan, R. G. H. Beets-Tan, J.-C. Fillion-Robin, S. Pieper, and H. J. W. L. Aerts. 2017. Computational radiomics system to decode the radiographic phenotype. Cancer Research 77, 21 (2017), e104\u2013e107.","journal-title":"Cancer Research"},{"issue":"1","key":"e_1_3_2_40_1","first-page":"1","article-title":"COVID-Net: A tailored deep convolutional neural network design for detection of COVID-19 cases from chest x-ray images","volume":"10","author":"Wang L.","year":"2020","unstructured":"L. Wang, Z. Q. Lin, and A. Wong. 2020. COVID-Net: A tailored deep convolutional neural network design for detection of COVID-19 cases from chest x-ray images. Scientific Reports 10, 1 (2020), 1\u201312.","journal-title":"Scientific Reports"},{"key":"e_1_3_2_41_1","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/978-3-319-91086-4_8","volume-title":"Handbook of Metaheuristics","author":"Whitley D.","year":"2019","unstructured":"D. Whitley. 2019. Next generation genetic algorithms: a user\u2019s guide and tutorial. In Handbook of Metaheuristics, M. Gendreau and J. -Y. Potvin (Eds.). Springer, 245\u2013274."},{"key":"e_1_3_2_42_1","doi-asserted-by":"publisher","DOI":"10.1162\/EVCO_a_00184"},{"key":"e_1_3_2_43_1","doi-asserted-by":"publisher","DOI":"10.7326\/0003-4819-110-11-916"},{"key":"e_1_3_2_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/4235.887236"},{"key":"e_1_3_2_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2015.2504420"}],"container-title":["ACM Transactions on Evolutionary Learning and Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651165","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3651165","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:49:53Z","timestamp":1750286993000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651165"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,8]]},"references-count":44,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,6,30]]}},"alternative-id":["10.1145\/3651165"],"URL":"https:\/\/doi.org\/10.1145\/3651165","relation":{},"ISSN":["2688-299X","2688-3007"],"issn-type":[{"type":"print","value":"2688-299X"},{"type":"electronic","value":"2688-3007"}],"subject":[],"published":{"date-parts":[[2024,6,8]]},"assertion":[{"value":"2022-11-28","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-02-27","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-06-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}