Mumford, Christine Lesley ORCID: https://orcid.org/0000-0002-4514-0272 1999. Evolutionary divide and conquer (II) for the TSP. Presented at: GECCO-99, Orlando, FL, USA, 13-17 July 1999. Published in: Banzhaf, Wolfgang, Daida, Jason M., Garzon, Max H., Honavar, Vasant, Jakiela, Mark J. and Smith, Robert E. eds. GECCO-99: Proceedings of the genetic and evolutionary computation conference. GECCO-99: PROCEEDINGS OF THE GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE. Orlando, FL.: Morgan Kauffman, pp. 1744-1749. |
Abstract
Results presented in recent papers demonstrate that it is possible to produce high quality solutions to TSP instances of up to several hundred cities using simple greedy heuristics when a Genetic Algorithm (GA) is used to perturb the city coordinates. The present paper extends the earlier studies to larger problems and a divide and conquer algorithm in the style of Richard Karp. Using a GA to perturb city coordinates in conjunction with a divide and conquer algorithm the feasibility of solving large problems to within a few percent of optimality is demonstrated. The exceptionally rapid execution times of Karp's algorithms together with their almost linear run-time scaling at O(nlogn) set them apart from most other heuristic algorithms.
Item Type: | Conference or Workshop Item (Paper) |
---|---|
Date Type: | Publication |
Status: | Published |
Schools: | Computer Science & Informatics |
Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA75 Electronic computers. Computer science Q Science > QA Mathematics > QA76 Computer software |
Publisher: | Morgan Kauffman |
ISBN: | 1558606114 |
Last Modified: | 20 Oct 2022 09:24 |
URI: | https://orca.cardiff.ac.uk/id/eprint/31847 |
Actions (repository staff only)
Edit Item |