Improving the Performance of Constructive Multi-Start Search Using Record Keeping

Simple item page
dc.contributor.advisorTamir, Dan E.
dc.contributor.authorKing, Charles Rick
dc.contributor.committeeMemberGuirguis, Mina S.
dc.contributor.committeeMemberMcKenney, Mark A.
dc.contributor.committeeMemberMcClellan, Stanley A.
dc.date.accessioned2012-02-24T10:19:07Z
dc.date.available2012-02-24T10:19:07Z
dc.date.issued2010-05
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.
dc.description.departmentComputer Science
dc.formatText
dc.format.extent106 pages
dc.format.medium1 file (.pdf)
dc.identifier.citationKing, C. R. (2010). Improving the performance of constructive multi-start search using record keeping (Unpublished thesis). Texas State University-San Marcos, San Marcos, Texas.
dc.identifier.urihttps://hdl.handle.net/10877/3905
dc.language.isoen
dc.subjecttraveling salesman
dc.subjectsearch
dc.subjectrecord
dc.subjectkeeping
dc.subjectcache
dc.subjectbloom
dc.subjectfilter
dc.titleImproving the Performance of Constructive Multi-Start Search Using Record Keeping
dc.typeThesis
thesis.degree.departmentComputer Science
thesis.degree.disciplineComputer Science
thesis.degree.grantorTexas State University-San Marcos
thesis.degree.levelMasters
thesis.degree.nameMaster of Science

Files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
fulltext.pdf
Size:
1.21 MB
Format:
Adobe Portable Document Format
Download

Collections

Graduate Theses and Dissertations