{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,12,23]],"date-time":"2024-12-23T10:40:22Z","timestamp":1734950422006,"version":"3.32.0"},"reference-count":0,"publisher":"IOS Press","isbn-type":[{"value":"9781643685694","type":"electronic"}],"license":[{"start":{"date-parts":[[2024,12,20]],"date-time":"2024-12-20T00:00:00Z","timestamp":1734652800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024,12,20]]},"abstract":"<jats:p>The Travelling Salesman Problem (TSP) is a well-established NP-hard problem, often tackled using heuristic algorithms. While state-of-the-art learning-driven approaches for TSP perform comparably to classical solvers when trained on trivially small instances, they struggle to generalize the learned policy to larger, practical-scale instances. Consequently, as the number of cities increases, the efficiency of these algorithms diminishes significantly. This paper focuses on the early elimination of non-advantageous edges while retaining advantageous ones, thereby accelerating the TSP solution. Our approach involves capturing the differential frequencies of various edges during the early stages of an intelligent evolutionary algorithm, which we term as \u201cknowledge\u201d derived from the evolutionary process. We then design effective features to characterize the similarities and differences between edges. Leveraging this \u201cknowledge\u201d, we label edges as either advantageous or non-advantageous. By integrating the guidance of a predictor, we intervene in the intelligent evolutionary algorithm to sparsify the TSP graph, ultimately enhancing the TSP solution. Our method effectively prunes edges in TSP instances, preserving the optimal path while minimizing redundant edges. Experimental results demonstrate that our approach significantly improves both computational efficiency and solution quality on the TSP50 and TSP100 test sets compared to other models. This methodology offers a novel perspective by extracting and utilizing latent knowledge among edges, thereby enhancing the performance of intelligent evolutionary algorithms in solving the TSP. Our findings not only improve current methodologies but also encourage further exploration and development in related fields and practical applications.<\/jats:p>","DOI":"10.3233\/faia241426","type":"book-chapter","created":{"date-parts":[[2024,12,23]],"date-time":"2024-12-23T09:48:40Z","timestamp":1734947320000},"source":"Crossref","is-referenced-by-count":0,"title":["Efficient Early Sparsification for Accelerating Solutions to the Traveling Salesman Problem"],"prefix":"10.3233","author":[{"given":"Yonglu","family":"Jiang","sequence":"first","affiliation":[{"name":"School of Information Science and Technology, North China University of Technology, Beijing, China"}]},{"given":"Hongyu","family":"Xing","sequence":"additional","affiliation":[{"name":"School of London Brunel, North China University of Technology, Beijing, China"},{"name":"Department of Mathematics, Brunel University London, London, UK"}]},{"given":"Hanchen","family":"Shi","sequence":"additional","affiliation":[{"name":"School of London Brunel, North China University of Technology, Beijing, China"},{"name":"Department of Mathematics, Brunel University London, London, UK"}]},{"given":"Zijing","family":"Wei","sequence":"additional","affiliation":[{"name":"School of London Brunel, North China University of Technology, Beijing, China"},{"name":"Department of Mathematics, Brunel University London, London, UK"}]},{"given":"Zhongguo","family":"Yang","sequence":"additional","affiliation":[{"name":"School of Information Science and Technology, North China University of Technology, Beijing, China"},{"name":"Beijing Key Laboratory on Integration and Analysis of Large-Scale Stream Data, North China University of Technology, Beijing, China"}]}],"member":"7437","container-title":["Frontiers in Artificial Intelligence and Applications","Fuzzy Systems and Data Mining X"],"original-title":[],"link":[{"URL":"https:\/\/ebooks.iospress.nl\/pdf\/doi\/10.3233\/FAIA241426","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,23]],"date-time":"2024-12-23T09:48:40Z","timestamp":1734947320000},"score":1,"resource":{"primary":{"URL":"https:\/\/ebooks.iospress.nl\/doi\/10.3233\/FAIA241426"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,20]]},"ISBN":["9781643685694"],"references-count":0,"URL":"https:\/\/doi.org\/10.3233\/faia241426","relation":{},"ISSN":["0922-6389","1879-8314"],"issn-type":[{"value":"0922-6389","type":"print"},{"value":"1879-8314","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,12,20]]}}}