Evolutionary divide and conquer (II) for the TSP

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.

Full text not available from this repository.

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:	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