  A variety of strategies have been proposed for overcoming local optimality in
metaheuristic search. This paper examines characteristics of moves that can be
exploited to make good decisions about steps that lead away from a local
optimum and then lead toward a new local optimum. We introduce strategies to
identify and take advantage of useful features of solution history with an
adaptive memory metaheuristic, to provide rules for selecting moves that offer
promise for discovering improved local optima.
  Our approach uses a new type of adaptive memory based on a construction
called exponential extrapolation. The memory operates by means of threshold
inequalities that ensure selected moves will not lead to a specified number of
most recently encountered local optima. Associated thresholds are embodied in
choice rule strategies that further exploit the exponential extrapolation
concept. Together these produce a threshold based Alternating Ascent (AA)
algorithm that opens a variety of research possibilities for exploration.
