Foundations of Genetic Algorithms 2001 (FOGA 6)

Local Search and High Precision Gray Codes: Convergence Results and Neighborhoods

Darrell Whitley [e-mail]; Laura Barbulescu [e-mail]; Jean-Paul Watson [e-mail]    Department of Computer Science, Colorado State University, Fort Collins, Colorado 80523 USA

Abstract

A proof is presented that shows how the neighborhood structure that is induced under a Gray Code representation repeats under shifting. Convergence proofs are also presented for steepest ascent using a local search bit climber and a Gray code representation: for unimodal 1-D functions and multimodal functions that are separable and unimodal in each dimension, the worst case number of steps needed to reach the global optimum is $\mathcal{O}\left(L\right)$ with a constant ...