Phased Genetic Programming for Application to the Traveling Salesman Problem
dc.contributor.author | Chitty, D | |
dc.contributor.author | Keedwell, E | |
dc.date.accessioned | 2023-08-09T09:19:06Z | |
dc.date.issued | 2023-07-24 | |
dc.date.updated | 2023-08-08T14:16:43Z | |
dc.description.abstract | The Traveling Salesman Problem (TSP) is a difficult permutation-based optimisation problem typically solved using heuristics or meta-heuristics which search the solution problem space. An alternative is to find sets of manipulations to a solution which lead to optimality. Hyper-heuristics search this space applying heuristics sequentially, similar to a program. Genetic Programming (GP) evolves programs typically for classification or regression problems. This paper hypothesizes that GP can be used to evolve heuristic programs to directly solve the TSP. However, evolving a full program to solve the TSP is likely difficult due to required length and complexity. Consequently, a phased GP method is proposed whereby after a phase of generations the best program is saved and executed. The subsequent generation phase restarts operating on this saved program output. A full program is evolved piecemeal. Experiments demonstrate that whilst pure GP cannot solve TSP instances when using simple operators, Phased-GP can obtain solutions within 4% of optimal for TSPs of several hundred cities. Moreover, Phased-GP operates up to nine times faster than pure GP. | en_GB |
dc.description.sponsorship | Innovate UK | en_GB |
dc.description.sponsorship | City Science | en_GB |
dc.format.extent | 547-550 | |
dc.identifier.citation | GECCO 2023: Genetic and Evolutionary Computation Conference, 15 - 19 July 2023, Lisbon, Portugal, pp. 1712 - 1720, pp. 547-550 | en_GB |
dc.identifier.doi | https://doi.org/10.1145/3583133.3590673 | |
dc.identifier.grantnumber | 10007532 | en_GB |
dc.identifier.uri | http://hdl.handle.net/10871/133741 | |
dc.identifier | ORCID: 0000-0003-3650-6487 (Keedwell, Ed) | |
dc.language.iso | en | en_GB |
dc.publisher | ACM (Association for Computing Machinery) | en_GB |
dc.rights | © 2023 Copyright held by the owner/author(s). Publication rights licensed to ACM. This version is made available under the CC-BY 4.0 license: https://creativecommons.org/licenses/by/4.0 | en_GB |
dc.subject | Genetic Programming | en_GB |
dc.subject | Traveling Salesman Problem | en_GB |
dc.title | Phased Genetic Programming for Application to the Traveling Salesman Problem | en_GB |
dc.type | Conference paper | en_GB |
dc.date.available | 2023-08-09T09:19:06Z | |
dc.identifier.isbn | 9798400701207 | |
dc.description | This is the author accepted manuscript. The final version is available from ACM via the DOI in this record | en_GB |
dc.relation.ispartof | GECCO '23 Companion: Proceedings of the Companion Conference on Genetic and Evolutionary Computation | |
dc.rights.uri | https://creativecommons.org/licenses/by/4.0/ | en_GB |
rioxxterms.version | AM | en_GB |
rioxxterms.licenseref.startdate | 2023-07-24 | |
rioxxterms.type | Conference Paper/Proceeding/Abstract | en_GB |
refterms.dateFCD | 2023-08-09T09:17:38Z | |
refterms.versionFCD | AM | |
refterms.dateFOA | 2023-08-09T09:19:11Z | |
refterms.panel | B | en_GB |
refterms.dateFirstOnline | 2023-07-24 |
Files in this item
This item appears in the following Collection(s)
Except where otherwise noted, this item's licence is described as © 2023 Copyright held by the owner/author(s). Publication rights licensed to ACM. This version is made available under the CC-BY 4.0 license: https://creativecommons.org/licenses/by/4.0