Subthreshold-seeking local search

Algorithms for parameter optimization display subthreshold-seeking behavior when the majority of the points that the algorithm samples have an evaluation less than some target threshold. We first analyze a simple "subthreshold-seeker" algorithm. Further theoretical analysis details conditions that allow subthreshold-seeking behavior for local search algorithms using Binary and Gray code representations. The analysis also shows that subthreshold-seeking behavior can be increased by using higher bit precision. However, higher precision also can reduce exploration. A simple modification to a bit-climber is proposed that improves its subthresholdseeking behavior. Experiments show that this modification results in both improved search efficiency and effectiveness on common benchmark problems. (C) 2006 Elsevier B.V. All rights reserved.