Handling Ties

It is easy to overlook the question of what to do about `lateral' ties, moves that leave the score unchanged, yet change the state. The decision can have significant consequences. Unexpectedly, it turns out that simulated annealing, the Metropolis criterion, random lateral descent hillclimbing (rldhc), random descent hillclimbing (rdhc), and iterated next-descent hillclimbing (m) each handles ties differently. The probabilities of accepting differing quality moves by these methods are shown in Table 3.2.

Table 3.2: Probability of Accepting Moves by Methods

Method	Downhill	Uphill	Lateral
sa	sigmoid	sigmoid	sigmoid (= 0.5)
metropolis	1.0	sigmoid	0.5 or 1.0
rldhc	1.0	0.0	0.5 or 1.0
rdhc	1.0	0.0	0.0
m	1.0	0.0	0.0

If the landscape around the current state is a `mesa', it could take many lateral moves before progress can be found. While never taking lateral moves is a feature for iterated next-descent hillclimbing in avoiding possibly never terminating, we may never see the edge of the mesa while searching.

Our simulated annealing approaches symmetrically invoke the sigmoid regardless of the sign and magnitude of the change, yielding a 50-50 chance of accepting lateral moves regardless of temperature.

The Metropolis Algorithm, a well-known simulated annealing algorithm, differs from our uniformly sigmoid-based approach in that it always takes better moves. Its acceptance criterion for lateral moves, however, was left unspecified in the original 1953 journal article [MRR$^+$53]:

We then calculate the change in energy of the system $\Delta E$, which is caused by the move. If $\Delta E < 0$, i.e., if the move would bring the system to a state of lower energy, we allow the move and put the particle in the new position. If $\Delta E > 0$, we allow the move with probability $\exp(-\Delta E/kT)$; i.e., we take a random number $\epsilon_2$ between 0 and 1, and if $\epsilon_2 < \exp(-\Delta E/kT)$, we move the particle to its new position. If $\epsilon_2 > \exp(-\Delta E/kT)$, we return it to its old position.

Subsequent work has differed on their treatment of the $\Delta E = 0$ case, varying from always taking lateral moves (e.g. [vLA87,KGV83,JAM89,AKvL97,EFC98]) to taking them half the time ([vLA87,Ack87a]).

Between DAO versions v1.10 and v1.14, we added the Metropolis criterion, and an adjustable acceptance probability of lateral moves for random descent hillclimbing and Metropolis to test the impact of differing acceptance probabilities on the final outcome, in our problem domain. These results are reported in Sections 4.3.5 and 4.3.6 (starting on page ). For comparisons with our simulated annealing schemes, presented in Section 4.3.7 (page ), we used the sigmoid probability of accepting ties for both random lateral descent hillclimbing and the Metropolis algorithm.

download thesis