  Many problems in science and technology require finding global minima or
maxima of various objective functions. The functions are typically
high-dimensional; each function evaluation may entail a significant
computational cost. The importance of global optimization has inspired
development of numerous heuristic algorithms based on analogies with physical,
chemical or biological systems. Here we present a novel algorithm, SmartRunner,
which employs a Bayesian probabilistic model informed by the history of
accepted and rejected moves to make a decision about the next random trial.
Thus, SmartRunner intelligently adapts its search strategy to a given objective
function and moveset, with the goal of maximizing fitness gain (or energy loss)
per function evaluation. Our approach can be viewed as adding a simple adaptive
penalty to the original objective function, with SmartRunner performing hill
ascent or descent on the modified landscape. This penalty can be added to many
other global optimization algorithms. We explored SmartRunner's performance on
a standard set of test functions, finding that it compares favorably against
several widely-used alternatives: simulated annealing, stochastic hill
climbing, evolutionary algorithm, and taboo search. Interestingly, adding the
adaptive penalty to the first three of these algorithms considerably enhances
their performance. We have also employed SmartRunner to study the
Sherrington-Kirkpatrick (SK) spin glass model and Kauffman's NK fitness model -
two NP-hard problems characterized by numerous local optima. In systems with
quenched disorder, SmartRunner performs well compared to the other global
optimizers. Moreover, in finite SK systems it finds close-to-optimal
ground-state energies averaged over disorder.
