Importance of Lateral Moves on a Mesa

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.

Table 4.6: Lateral Test Statistics (in millions)

	%	Fall 2000		Fall 1999		Fall 1998
Scheme	Ties	Avg Score	Std Dev	Avg Score	Std Dev	Avg Score	Std Dev
rdhc	0	50.077	0.297	89.100	1.863	71.707	0.687
rldhc	50	49.121	0.244	88.750	0.221	70.992	0.544
rldhc2	100	49.076	0.394	88.730	0.229	71.061	0.540
mr	0	667.506	10.266	867.751	8.214	836.634	5.462
m	0	671.013	7.197	863.249	7.405	838.684	5.431
sigmet4	50	49.051	0.235	88.570	0.214	71.077	0.740
met4	100	49.272	0.426	88.726	0.378	71.057	0.525
sigmet1	50	52.022	0.857	92.998	1.015	74.810	1.209
met1	100	52.006	1.121	92.626	0.926	74.619	0.900

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.