Name
Abstract | ||
|---|---|---|
State-space search redundancy, that is, multiple explorations of the same state, is an inherent problem in many heuristic search algorithms. It is prevalent in constructive multi-start algorithms. Record-keeping mechanisms, however, can minimize redundancy and enable exploiting time/space tradeoffs. This paper investigates the utility of record-keeping procedures in the context of Iterative Hill Climbing applied to the Traveling Salesperson Problem using several restart mechanisms including Greedy Randomized Adaptive Search, and Greedy Enumeration. Record-keeping methods such as unbounded memory, dedicated memory, and cache memory, as well as a novel \"book-keeping\" method utilizing a Bloom filter are investigated. Experiments performed using TSPLIB benchmarks and random TSP instances with 100 cities show that under the above mentioned restart and record-keeping mechanisms the IHC produces competitive results. In addition, the research shows that record-keeping, in specific Bloom filters, can considerably improve both the time performance of IHC and the quality of solutions produced. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/978-3-642-31087-4_19 | IEA/AIE |
Keywords | Field | DocType |
unbounded memory,state-space search redundancy,greedy randomized adaptive search,greedy enumeration,dedicated memory,record-keeping method,record-keeping procedure,constructive multi-start search,bloom filter,cache memory,record-keeping mechanism,filter,cache,bloom,record,traveling salesman | Bloom filter,Hill climbing,Mathematical optimization,Heuristic,CPU cache,Constructive,Cache,Computer science,Combinatorial optimization,Theoretical computer science,Redundancy (engineering) | Conference |
Citations | PageRank | References |
0 | 0.34 | 8 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dan E. Tamir | 1 | 79 | 13.26 |
| Charles R. King | 2 | 0 | 0.68 |
| Mark Mckenney | 3 | 4 | 1.43 |