Exploiting Local Optimality in Metaheuristic Search
This work addresses the challenge of improving search efficiency in optimization for researchers and practitioners, but it appears incremental as it builds on existing adaptive memory metaheuristics.
The paper tackles the problem of overcoming local optimality in metaheuristic search by exploiting characteristics of moves to transition between local optima, resulting in a threshold-based Alternating Ascent algorithm that uses exponential extrapolation and adaptive memory strategies.
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.