Given a random algorithm, does varying non-zero probabilities of accepting an uphill move work better than never taking an uphill move?
Here, in some sense, we are comparing hillclimbing and simulated annealing. To answer this question we use the same 50% lateral move probability, and 40 million hillclimbing attempts followed by a minimization step.
Figures 4.2 through 4.4 show us the answer is `not necessarily'. For example, hillclimbing (rldhc) without minimization was significantly different than sa1/m and sigmet1/m in every dataset: Hillclimbing can beat some simulated annealing schedules. Furthermore, we cannot say our best ranked simulated annealing schedule was statistically different than these hillclimbing results. In fact, in the Fall 1998 dataset -- the only dataset where the mean rank order (Figure 4.4) did not match the average score sorted order (Figure 4.7) -- the rldhc average score was the lowest.
Sometimes, with a good annealing schedule, we can escape local minimal traps that catch hillclimbers, and arrive closer to the global optimal solution, though how close we cannot say. As we see in the next section, accepting lateral moves is essential to finding a good solution in our domain. With a sufficient number of attempts, random lateral descent hillclimbing (rldhc) produced results comparable to simulated annealing.