A Stagnation-Aware Genetic Algorithm with Spectral Graph Cuts and Adaptive Neighborhood Search for solving Traveling-Salesman Problem

A Stagnation-Aware Genetic Algorithm with Spectral Graph Cuts and Adaptive Neighborhood Search for solving Traveling-Salesman Problem | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article A Stagnation-Aware Genetic Algorithm with Spectral Graph Cuts and Adaptive Neighborhood Search for solving Traveling-Salesman Problem Arnab Karmakar This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-8604869/v1 This work is licensed under a CC BY 4.0 License Status: Posted Version 1 posted You are reading this latest preprint version Abstract Purpose: The Traveling-Salesman Problem (TSP) is a classical NP-hard combinatorial optimization problem with significant theoretical and practical importance. Although Genetic Algorithms (GAs) are widely used for solving TSP, conventional GA-based approaches often suffer from premature convergence and limited local exploitation, restricting their solution quality. Methods: We propose a Spectral-Adaptive Genetic Algorithm (SAGA) that integrates spectral graph partitioning and adaptive local search into a standard GA framework. Upon detecting population stagnation, the best individual is transformed into a graph representation of the tour, partitioned using the Fiedler vector of the normalized Laplacian, and locally refined within the resulting substructures. The improved solution is then reinjected into the population. Results: The proposed method is evaluated on standard TSPLIB benchmarks, with a detailed experimental study on the berlin52 dataset. Both the baseline GA and SAGA are executed under identical parameter settings using paired random seeds across 200 independent runs. Results demonstrate that SAGA achieves an average improvement of approximately 3.9% in tour length over the baseline GA, with the best solution reaching a tour length of 7744 units compared to the baseline’s best of 8636 units. Conclusion: These findings indicate that incorporating spectral information and adaptive local refinement significantly enhances the effectiveness of Genetic Algorithms for the TSP and provides a promising direction for hybrid metaheuristic design. Combinatorial Optimization Traveling-Salesman Problem Genetic Algorithms Hybrid Metaheuristics Spectral Graph Partitioning Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Posted Version 1 posted You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-8604869","acceptedTermsAndConditions":true,"allowDirectSubmit":true,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":578185770,"identity":"2481ac1f-25ed-488a-aefe-dfc97aa8d366","order_by":0,"name":"Arnab Karmakar","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAABJElEQVRIie2RMUvDQBSAEwrJ8iDrlUj8C08CRTH4WxIK5xK1LiI46GQG0/1K/kT8BVYC7XLRSciRxcW4dCi4FAxiUgeXs8RN5L7hce/d+7h3PE1TKP4gZB2nX0lPOyegR1fNEXe7KtxzenGbIemo6NfUNZn/fSGjH+Uv6YofnFhJfv82MrJgPHl9SlcjolnRjS9TbDgciLgY7rGH46HNIAsmSXgm4mYwwvNUpjgaNQpY9lDjgDaQLLhNQlpAoyA5kitWZYh6eYnbHNx3wCy4E5yKeoNiE2qUUGSIHAY2+NTVmTkrN73SZ5VRbvE57jTKPpt6jh6HTQUJ/PQX8kgNsZhdoNMMVp5+tKucV2JRe44VjaWKDMB17NreYj7/pluhUCj+P5+T2GaKdI1h9wAAAABJRU5ErkJggg==","orcid":"","institution":"Government College of Engineering and Textile Technology, Serampore","correspondingAuthor":true,"prefix":"","firstName":"Arnab","middleName":"","lastName":"Karmakar","suffix":""}],"badges":[],"createdAt":"2026-01-14 20:08:18","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-8604869/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-8604869/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":100867500,"identity":"a1496535-457b-4ea6-8b54-b7a293d4daaa","added_by":"auto","created_at":"2026-01-22 08:41:59","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":1881285,"visible":true,"origin":"","legend":"","description":"","filename":"SAGATSPSource.pdf","url":"https://assets-eu.researchsquare.com/files/rs-8604869/v1_covered_5613530a-f9fe-438e-ad04-e43cd58618df.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"A Stagnation-Aware Genetic Algorithm with Spectral Graph Cuts and Adaptive Neighborhood Search for solving Traveling-Salesman Problem","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":true,"hideJournal":true,"highlight":"","institution":"","isAcceptedByJournal":false,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true},"keywords":"Combinatorial Optimization, Traveling-Salesman Problem, Genetic Algorithms, Hybrid Metaheuristics, Spectral Graph Partitioning","lastPublishedDoi":"10.21203/rs.3.rs-8604869/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-8604869/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"\u003cp\u003e\u003cstrong\u003ePurpose:\u003c/strong\u003e The Traveling-Salesman Problem (TSP) is a classical NP-hard combinatorial optimization problem with significant theoretical and practical importance. Although Genetic Algorithms (GAs) are widely used for solving TSP, conventional GA-based approaches often suffer from premature convergence and limited local exploitation, restricting their solution quality.\u003c/p\u003e\n\u003cp\u003e\u003cstrong\u003eMethods:\u003c/strong\u003e We propose a Spectral-Adaptive Genetic Algorithm (SAGA) that integrates spectral graph partitioning and adaptive local search into a standard GA framework. Upon detecting population stagnation, the best individual is transformed into a graph representation of the tour, partitioned using the Fiedler vector of the normalized Laplacian, and locally refined within the resulting substructures. The improved solution is then reinjected into the population.\u003c/p\u003e\n\u003cp\u003e\u003cstrong\u003eResults:\u003c/strong\u003e The proposed method is evaluated on standard TSPLIB benchmarks, with a detailed experimental study on the berlin52 dataset. Both the baseline GA and SAGA are executed under identical parameter settings using paired random seeds across 200 independent runs. Results demonstrate that SAGA achieves an average improvement of approximately 3.9% in tour length over the baseline GA, with the best solution reaching a tour length of 7744 units compared to the baseline’s best of 8636 units.\u003c/p\u003e\n\u003cp\u003e\u003cstrong\u003eConclusion:\u003c/strong\u003e These findings indicate that incorporating spectral information and adaptive local refinement significantly enhances the effectiveness of Genetic Algorithms for the TSP and provides a promising direction for hybrid metaheuristic design.\u003c/p\u003e","manuscriptTitle":"A Stagnation-Aware Genetic Algorithm with Spectral Graph Cuts and Adaptive Neighborhood Search for solving Traveling-Salesman Problem","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2026-01-22 08:38:56","doi":"10.21203/rs.3.rs-8604869/v1","editorialEvents":[{"type":"communityComments","content":0}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true}}],"origin":"","ownerIdentity":"265c4673-c35d-441a-a364-8e78bff0fd47","owner":[],"postedDate":"January 22nd, 2026","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"posted","subjectAreas":[],"tags":[],"updatedAt":"2026-01-22T08:38:57+00:00","versionOfRecord":[],"versionCreatedAt":"2026-01-22 08:38:56","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-8604869","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-8604869","identity":"rs-8604869","version":["v1"]},"buildId":"XKTyCvWXoU3ODBz1xrDgd","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}