Repository logo
 

The anteater analysis: a comparison of traveling salesman tour construction methods and their global frequencies

Simple item page
dc.contributor.authorOurada, Shannon A., author
dc.contributor.authorWhitley, Darrell, advisor
dc.contributor.authorGhosh, Sudipto, committee member
dc.contributor.authorClegg, Benjamin, committee member
dc.date.accessioned2022-08-29T10:15:48Z
dc.date.available2022-08-29T10:15:48Z
dc.date.issued2022
dc.description.abstractFor the Traveling Salesman Problem (TSP), many algorithms have been developed. These include heuristic solvers, such as nearest neighbors and ant colony optimization algorithms. In this work, the ATT48 and EIL101 instances are examined to better understand the difference between biased and unbiased methods of tour construction algorithms when combined with the 2-opt local search operator. First, a sample of tours are constructed. Then, we examine the frequencies of global edges of different sizes using n-grams. Using 2-opt as the tour improvement algorithm, we analyze randomly initialized local optima compared to nearest neighbors local optima as well as ant colony solutions with and without 2-opt. This comparison serves to better understand the nature of these different methods in their relation to the global optimum. We also provide some ways the algorithms may be adapted to take advantage of the global frequencies, particularly the ant colony optimization algorithm.
dc.format.mediumborn digital
dc.format.mediummasters theses
dc.identifierOurada_colostate_0053N_17240.pdf
dc.identifier.urihttps://hdl.handle.net/10217/235565
dc.languageEnglish
dc.language.isoeng
dc.publisherColorado State University. Libraries
dc.relation.ispartof2020-
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.subjectgraph algorithms
dc.subjectant colony optimization (ACO)
dc.subjecttraveling salesman problem (TSP)
dc.titleThe anteater analysis: a comparison of traveling salesman tour construction methods and their global frequencies
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:
Ourada_colostate_0053N_17240.pdf
Size:
2.64 MB
Format:
Adobe Portable Document Format
Download

Collections

2020-
Theses and Dissertations