2026-09-18T20:07:32Zhttps://api.mountainscholar.org/server/oai/request

oai:mountainscholar.org:10217/473142025-12-30T03:28:08Zcom_10217_100532com_10217_100000com_10217_100388com_10217_100303col_10217_100538col_10217_100389

Hains, Douglas R., author Whitley, L. Darrell, advisor Howe, Adele E., committee member Mueller, Jennifer L., committee member 2007-01-03T05:15:39Z 2007-01-03T05:15:39Z 2011 Hains_colostate_0053N_10245.pdf http://hdl.handle.net/10217/47314 https://doi.org/10.25675/3.018670 The 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. born digital masters theses English eng Colorado State University. Libraries 2000-2019 Copyright 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. genetic algorithms Traveling Salesman Problem search space local search Generalized partition crossover for the traveling salesman problem Text Master of Science (M.S.) Masters Computer Science Colorado State University This 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). open.access