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 subthreshold-seeking behavior. Experiments show that this modification results in both improved search efficiency and effectiveness on common benchmark problems.