Repository logo
 

Generalized partition crossover for the traveling salesman problem

Simple item page
dc.contributor.authorHains, Douglas R., author
dc.contributor.authorWhitley, L. Darrell, advisor
dc.contributor.authorHowe, Adele E., committee member
dc.contributor.authorMueller, Jennifer L., committee member
dc.date.accessioned2007-01-03T05:15:39Z
dc.date.available2007-01-03T05:15:39Z
dc.date.issued2011
dc.description.abstractThe Traveling Salesman Problem (TSP) is a well-studied combinatorial optimization problem with a wide spectrum of applications and theoretical value. We have designed a new recombination operator known as Generalized Partition Crossover (GPX) for the TSP. GPX is unique among other recombination operators for the TSP in that recombining two local optima produces new local optima with a high probability. Thus the operator can 'tunnel' between local optima without the need for intermediary solutions. The operator is respectful, meaning that any edges common between the two parent solutions are present in the offspring, and transmits alleles, meaning that offspring are comprised only of edges found in the parent solutions. We design a hybrid genetic algorithm, which uses local search in addition to recombination and selection, specifically for GPX. We show that this algorithm outperforms Chained Lin-Kernighan, a state-of-the-art approximation algorithm for the TSP. We next analyze these algorithms to determine why the algorithms are not capable of consistently finding a globally optimal solution. Our results reveal a search space structure which we call 'funnels' because they are analogous to the funnels found in continuous optimization. Funnels are clusters of tours in the search space that are separated from one another by a non-trivial distance. We find that funnels can trap Chained Lin-Kernighan, preventing the search from finding an optimal solution. Our data indicate that, under certain conditions, GPX can tunnel between funnels, explaining the higher frequency of optimal solutions produced by our hybrid genetic algorithm using GPX.
dc.format.mediumborn digital
dc.format.mediummasters theses
dc.identifierHains_colostate_0053N_10245.pdf
dc.identifier.urihttp://hdl.handle.net/10217/47314
dc.languageEnglish
dc.language.isoeng
dc.publisherColorado State University. Libraries
dc.relation.ispartof2000-2019
dc.rightsCopyright and other restrictions may apply. User is responsible for compliance with all applicable laws. For information about copyright law, please see https://libguides.colostate.edu/copyright.
dc.subjectgenetic algorithms
dc.subjectTraveling Salesman Problem
dc.subjectsearch space
dc.subjectlocal search
dc.titleGeneralized partition crossover for the traveling salesman problem
dc.typeText
dcterms.rights.dplaThis Item is protected by copyright and/or related rights (https://rightsstatements.org/vocab/InC/1.0/). You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).
thesis.degree.disciplineComputer Science
thesis.degree.grantorColorado State University
thesis.degree.levelMasters
thesis.degree.nameMaster of Science (M.S.)

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Hains_colostate_0053N_10245.pdf
Size:
498.89 KB
Format:
Adobe Portable Document Format
Description:
Download

Collections

2000-2019
Theses and Dissertations