Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

Evolutionary divide and conquer (I): A novel genetic approach to the TSP

Mumford, Christine Lesley ORCID: https://orcid.org/0000-0002-4514-0272 and Jones, Antonia J. 1993. Evolutionary divide and conquer (I): A novel genetic approach to the TSP. Evolutionary Computation 1 (4) , pp. 313-333.

[thumbnail of evco.1993.1.4.313.pdf]
Preview
Text - Published Version
Download (1MB) | Preview

Abstract

Experiments with genetic algorithms using permutation operators applied to the traveling salesman problem (TSP) tend to suggest that these algorithms fail in two respects when applied to very large problems: they scale rather poorly as the number of cities n increases, and the solution quality degrades rapidly. We propose an alternative approach for genetic algorithms applied to hard combinatoric search which we call Evolutionary Divide and Conquer (EDAC). This method has potential for any search problem in which knowledge of good solutions for subproblems can be exploited to improve the solution of the problem itself. The idea is to use the genetic algorithm to explore the space ofproblem subdivisions rather than the space of solutions themselves. We give some preliminary results of this method applied to the geometric TSP.

Item Type: Article
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
Additional Information: This article first published in Evolutionary Computation, Vol 1 no 4 (1993) pp. 313-333.
Publisher: Massachusetts Institute of Technology Press
ISSN: 1063-6560
Related URLs:
Date of First Compliant Deposit: 30 March 2016
Last Modified: 06 May 2023 15:14
URI: https://orca.cardiff.ac.uk/id/eprint/31861

Actions (repository staff only)

Edit Item Edit Item

Downloads

Downloads per month over past year

View more statistics