{"id":{"repo_id":"colostate","oai_identifier":"oai:mountainscholar.org:10217/47314"},"canonical_url":"https://search.dev.ndltd.org/etd/colostate/oai:mountainscholar.org:10217/47314","repository":{"repo_id":"colostate","name":"Colorado State University","base_url":"https://api.mountainscholar.org/server/oai/request"},"display":{"title":"Generalized partition crossover for the traveling salesman problem","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Hains, Douglas R., author","Whitley, L. Darrell, advisor","Howe, Adele E., committee member","Mueller, Jennifer L., committee member"],"institution":"Colorado State University. Libraries","degree_name":"Master of Science (M.S.)","degree_level":"Masters","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011","date_published":"2011","updated_at":"2026-07-27T19:13:11Z","subjects":["genetic algorithms","Traveling Salesman Problem","search space","local search"],"languages":["eng","English"],"rights":["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."],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://doi.org/10.25675/3.018670"],"render_values":[{"text":"https://doi.org/10.25675/3.018670","href":"https://doi.org/10.25675/3.018670","code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/10217/47314","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Hains, Douglas R., author","Whitley, L. Darrell, advisor","Howe, Adele E., committee member","Mueller, Jennifer L., committee member"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2007-01-03T05:15:39Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2007-01-03T05:15:39Z"]},{"key":"dc:date.issued","label":"Date","values":["2011"]},{"key":"dc:publisher","label":"Institution","values":["Colorado State University. Libraries"]},{"key":"dc:type","label":"Dc Type","values":["Text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Masters"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science (M.S.)"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Colorado State University"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["genetic algorithms","Traveling Salesman Problem","search space","local search"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English"]},{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["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."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["Hains_colostate_0053N_10245.pdf"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/10217/47314","https://doi.org/10.25675/3.018670"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:format.medium","label":"Dc Format Medium","values":["born digital","masters theses"]},{"key":"dc:title","label":"Title","values":["Generalized partition crossover for the traveling salesman problem"]}]}],"canonical_facts":{"dc:creator":["Hains, Douglas R., author","Whitley, L. Darrell, advisor","Howe, Adele E., committee member","Mueller, Jennifer L., committee member"],"dc:date.accessioned":["2007-01-03T05:15:39Z"],"dc:date.available":["2007-01-03T05:15:39Z"],"dc:date.issued":["2011"],"dc:description.abstract":["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."],"dc:format.medium":["born digital","masters theses"],"dc:identifier":["Hains_colostate_0053N_10245.pdf"],"dc:identifier.uri":["http://hdl.handle.net/10217/47314","https://doi.org/10.25675/3.018670"],"dc:language":["English"],"dc:language.iso":["eng"],"dc:publisher":["Colorado State University. Libraries"],"dc:rights":["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."],"dc:subject":["genetic algorithms","Traveling Salesman Problem","search space","local search"],"dc:title":["Generalized partition crossover for the traveling salesman problem"],"dc:type":["Text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Masters"],"thesis:degree_name":["Master of Science (M.S.)"],"thesis:institution_name":["Colorado State University"]},"updated_at":"2026-07-27T19:13:11Z"}