Abstract
Markov Chain Monte Carlo (MCMC) methods may be employed to search for a probability distribution over a bounded space of function arguments to estimate which argument(s) optimize(s) an objective function. This search-based optimization requires sampling the suitability, or fitness, of arguments in the search space. When the objective function or the fitness of arguments vary with time, significant exploration of the search space is required. Search efficiency then becomes a more relevant measure of the usefulness of an MCMC method than traditional measures such as convergence speed to the stationary distribution and asymptotic variance of stationary distribution estimates. Search efficiency refers to how quickly prior information about the search space is traded-off for search effort savings. Optimal search efficiency occurs when the entropy of the probability distribution over the space during search is maximized. Whereas the Metropolis case of the Hastings MCMC algorithm with fixed candidate generation is optimal with respect to asymptotic variance of stationary distribution estimates, this paper proves that Barker’s case is optimal with respect to search efficiency if the fitness of the arguments in the search space is characterized by an exponential function. The latter instance of optimality is beneficial for time-varying optimization that is also model-independent.
Similar content being viewed by others
References
Barker, A.A.: Monte Carlo calculations of the radial distribution functions for a proton-electron plasma. Aust. J. Phys. 18, 119–133 (1965)
Brémaud, P.: Markov Chains: Gibbs Fields, Monte Carlo Simulation and Queues. Springer, New York (1999)
Brooks, S.P.: Markov chain Monte Carlo method and its application. J. R. Stat. Soc. Ser. D (Stat.) 47(1), 69–100 (1998)
Gilks, W.R., Richardson, S.: Spiegelhalter. Markov Chain Monte Carlo in Practice. Chapman & Hall, London (1996)
Hansen, N., Ostermeier, A.: Adapting arbitrary normal mutation distributions in evolution strategies: the covariance matrix adaptation. In: Proceedings of the 1996 IEEE International Conference on Evolutionary Computation (ICEC ’96), Nagoya, pp. 312–317 (1996)
Hastings, W.K.: Monte Carlo sampling methods using Markov chains and their applications. Biometrika 57(1), 97–109 (1970)
Jaynes, E.T.: Information theory and statistical mechanics. Phys. Rev. 106(4), 620–630 (1957)
Jaynes, E.T.: Entropy and search theory. In: Proceedings of the First Maximum Entropy Workshop (1981)
Kerridge, D.F.: Inaccuracy and inference. J. R. Stat. Soc. Ser. B (Methodol.) 23(1), 184–194 (1961)
Kirkpatrick, S., Gelatt Jr, C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220(4598), 671–680 (1983)
Meerkov, S.M.: Mathematical theory of behavior—individual and collective behavior of retardable elements. Math. Biosci. 43(1–2), 41–106 (1979)
Menezes, A.A.: Selective evolutionary generation systems: theory and applications. Ph.D. thesis, University of Michigan, Michigan (2010)
Menezes, A.A., Kabamba, P.T.: Efficient and responsive stochastic optimization. In: Proceedings of the 18th IFAC World Congress, Milano (2011)
Menezes, A.A., Kabamba, P.T.: Selective evolutionary generation: a model for optimally efficient search in biology. In: Proceedings of the 2011 American Control Conference, San Francisco (2011)
Rubinstein, R.Y., Kroese, D.P.: The Cross-Entropy Method: A Unified Approach to Combinatorial Optimization, Monte Carlo Simulation, and Machine Learning. Springer, New York (2004)
Shannon, C.E.: A mathematical theory of communication. Bell Syst. Tech. J. 27, 379–423, 623–656 (1948)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Menezes, A.A., Kabamba, P.T. Optimal search efficiency of Barker’s algorithm with an exponential fitness function. Optim Lett 8, 691–703 (2014). https://doi.org/10.1007/s11590-013-0608-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11590-013-0608-7