Does accepting lateral moves impact the search for a minimal solution?
To investigate the significance of lateral moves, we ran three random descent hillclimbing methods, based on 40 million attempts, and varying the probability of accepting lateral moves from never (rdhc), to half (rldhc), and then to all the time (rldhc2). We also ran the Metropolis algorithm with half and all lateral moves accepted based on the table-driven (sigmet1 & met1) and reheating (sigmet4 & met4) cooling schedules.
Across the Fall 2000 and 1999 datasets (Table 4.6), we found random lateral descent hillclimbing, accepting all or half of the ties, differed significantly from random descent hillclimbing (rdhc) and iterated next-descent hillclimbing (m & mr), both never taking lateral moves and producing less desireable results. This suggests our problem domain has `mesa' characteristics -- large regions of unchanging value.
Varying the probabilities of accepting lateral moves with the Metropolis algorithm showed no significant difference for either cooling schedule when tested on all three datasets (Table 4.6). With a mesa landscape, accepting lateral moves is essential to finding better solutions -- whether the best probability is 100% or 50% depends upon the dataset.