Dynamic Representations and Escaping Local Optima: Improving Genetic Algorithms and Local Search

Local search algorithms often get trapped in local optima. Algorithms such as tabu search and simulated annealing 'escape' local optima by accepting nonimproving moves. Another possibility is to dynamically change between representations; a local optimum under one representation may not be a local optimum under another. Shifting is a mechanism which dynamically switches between Gray code representations in order to escape local optima. Gray codes are widely used in conjunction with genetic algorithms and bit-climbing algorithms for parameter optimization problems. We present new theoretical results that substantially improve our understanding of the shifting mechanism, on the number of Gray codes accessible via shifting, and on how neighborhood structure changes during shifting. We show that shifting can significantly improve the performance of a simple hill-climber; it can also help to improve one of the best genetic algorithms currently available.