Show simple item record

dc.contributor.advisorTamir, Dan E.
dc.contributor.authorKing, Charles Ricken_US
dc.date.accessioned2012-02-24T10:19:07Z
dc.date.available2012-02-24T10:19:07Z
dc.date.issued2010-05-01en_US
dc.date.submittedMay 2010
dc.identifier.urihttps://digital.library.txstate.edu/handle/10877/3905
dc.description.abstractConstructive multi-start search algorithms are commonly used to address combinatorial optimization problems such as the traveling salesman problem (TSP). Multi-start algorithms recover from local optima by restarting, which can lead to redundant configurations when search paths converge. Record keeping mechanisms can be used to minimize this redundancy, enabling a time/space tradeoff. This thesis investigates the utility of several restart algorithms and record keeping mechanisms in the context of iterative hill climbing (IHC) in the TSP domain. Restart algorithms including GRASP, greedy enumeration, random restart, Clarke-Wright, and nearest neighbor as well as record keeping mechanisms including unbounded memory, dedicated memory, cache memory, and Bloom filters are investigated. Experiments performed using TSPLIB benchmarks and near-optimal solutions to random TSP instances show that under the above-mentioned mechanisms, IHC produces competitive results, in most cases within 1.5 percent of optimal. The study concludes that GRASP and greedy enumeration significantly outperform other restart mechanisms. Furthermore, the research shows that record keeping can considerably improve both the time performance of IHC and the quality of solutions produced. The cache and Bloom filter record keeping mechanisms reduced the total running time by 90.8 percent when fixing the total number of climbs, resulting in a speed-up factor or 10.9. Unbounded memory experiments confirmed this figure as the upper bound. Additionally, both mechanisms achieved a solution quality improvement of 0.518 percent when fixing the total number of steps, which was again confirmed as the upper bound.en_US
dc.formatText
dc.format.extent106 pages
dc.format.medium1 file (.pdf)
dc.language.isoen_US
dc.subjectTraveling salesmanen_US
dc.subjectSearchen_US
dc.subjectRecorden_US
dc.subjectKeepingen_US
dc.subjectCacheen_US
dc.subjectBloomen_US
dc.subjectFilteren_US
dc.subject.classificationComputer Sciencesen_US
dc.titleImproving the Performance of Constructive Multi-Start Search Using Record Keepingen_US
txstate.documenttypeThesis
dc.contributor.committeeMemberGuirguis, Mina S.
dc.contributor.committeeMemberMcKenney, Mark A.
dc.contributor.committeeMemberMcClellan, Stanley A.
thesis.degree.departmentComputer Scienceen_US
thesis.degree.disciplineComputer Scienceen_US
thesis.degree.grantorTexas State Universityen_US
thesis.degree.levelMastersen_US
thesis.degree.nameMaster of Scienceen_US
txstate.departmentComputer Science


Download

Thumbnail

This item appears in the following Collection(s)

Show simple item record