Effects of a deterministic hill climber on hBOA

ABSTRACT

Hybridization of global and local search algorithms is a well-established technique for enhancing the efficiency of search algorithms. Hybridizing estimation of distribution algorithms (EDAs) has been repeatedly shown to produce better performance than either the global or local search algorithm alone. The hierarchical Bayesian optimization algorithm (hBOA) is an advanced EDA which has previously been shown to benefit from hybridization with a local searcher. This paper examines the effects of combining hBOA with a deterministic hill climber (DHC). Experiments reveal that allowing DHC to find the local optima makes model building and decision making much easier for hBOA. This reduces the minimum population size required to find the global optimum, which substantially improves overall performance.

REFERENCES

• 1: D. H. Ackley. An empirical study of bit vector function optimization. Genetic Algorithms and Simulated Annealing, pages 170--204, 1987.
• 2: U. Aickelin, E. K. Burke, and J. Li. An estimation of distribution algorithm with intelligent local search for rule-based nurse rostering. Journal of the Operational Research Society, 2007.
• 3: K. Binder and A. Young. Spin-glasses: Experimental facts, theoretical concepts and open questions. Rev. Mod. Phys., 58:801, 1986.
• 4: L. Davis, editor. Handbook of Genetic Algorithms. Van Nostrand Reinhold, New York, NY, 1991.
• 5: P. Dayal, S. Trebst, S. Wessel, D. Wurtz, M. Troyer, S. Sabhapandit, and S. Coppersmith. Performance limitations of flat histogram methods and optimality of Wang-Langdau sampling. Physical Review Letters, 92(9):097201, 2004.
• 6: K. Deb and D. E. Goldberg. Sufficient conditions for deceptive and easy binary functions. Annals of Mathematics and Artificial Intelligence, 10:385--408, 1994.
• 7: K. Fischer and J. Hertz. Spin Glasses. Cambridge University Press, Cambridge, 1991.
• 8: David E. Goldberg, The Design of Innovation: Lessons from and for Competent Genetic Algorithms, Kluwer Academic Publishers, Norwell, MA, 2002
• 9: D. E. Goldberg and M. Rudnick. Genetic algorithms and the variance of fitness. Complex Systems, 5(3):265--278, 1991. Also IlliGAL Report No. 91001.
• 10: D. E. Goldberg and S. Voessner. Optimizing global-local search hybrids. IlliGAL Report No. 99001, University of Illinois at Urbana-Champaign, Illinois Genetic Algorithms Laboratory, Urbana, IL, 1999.
• 11: George Harik , Erick Cantú-Paz , David E. Goldberg , Brad L. Miller, The gambler's ruin problem, genetic algorithms, and the sizing of populations, Evolutionary Computation, v.7 n.3, p.231-253, Fall 1999 [doi>10.1162/evco.1999.7.3.231]
• 12: Georges R. Harik, Finding Multimodal Solutions Using Restricted Tournament Selection, Proceedings of the 6th International Conference on Genetic Algorithms, p.24-31, July 15-19, 1995
• 13: William Eugene Hart, Adaptive global optimization with local search, University of California at San Diego, La Jolla, CA, 1994
• 14: M. Hauschild, M. Pelikan, C. Lima, and K. Sastry. Analyzing probabilistic models in hierarchical boa on traps and spin glasses. MEDAL Report No. 2007001, Missouri Estimation of Distribution Algorithms Laboratory, University of Missouri-St. Louis, St. Louis, MO, 2007.
• 15: H. H. Hoos and T. Stutzle. SATLIB: An online resource for research on SAT. pages 283--292. IOS Press, 2000.
• 16: T. Ibaraki. Combinations with Other Optimization Methods, chapter D3. Oxford University Press and Institute of Physics, 1997.
• 17: M. Land. Adaptive global optimization with local search. PhD thesis, University of California, San Diego, San Diego, CA, 1998.
• 18: C. Lima, M. Pelikan, K. Sastry, M. Butz, and D. E. Goldberg. Substructural neighborhoods for local search in the bayesian optimization algorithm. MEDAL Report No. 2006007, Missouri Estimation of Distribution Algorithms Laboratory, University of Missouri-St. Louis, St. Louis, MO, 2006.
• 19: M. Mezard, G. Parisi, and M. Virasoro. Spin glass theory and beyond. World Scientific, Singapore, 1987.
• 20: P. Moscato. On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms. In Caltech Concurrent Computation Program C3P-826, 1989.
• 21: H. Muhlenbein and T. Mahnig. Evolutionary optimization and the estimation of search distributions with applications to graph bipartitioning. Journal of Approximate Reasoning, 31, 2002.
• 22: Heinz Mühlenbein , Thilo Mahnig , Alberto Ochoa Rodriguez, Schemata, Distributions and Graphical Models in Evolutionary Optimization, Journal of Heuristics, v.5 n.2, p.215-247, July 1999 [doi>10.1023/A:1009689913453]
• 23: Martin Pelikan , David E. Goldberg, Bayesian optimization algorithm: from single level to hierarchy, University of Illinois at Urbana-Champaign, Champaign, IL, 2002
• 24: M. Pelikan. Hierarchical Bayesian optimization algorithm: Toward a new generation of evolutionary algorithms. Springer-Verlag, 2005.
• 25: M. Pelikan and D. E. Goldberg. Escaping hierarchical traps with competent genetic algorithms. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001), pages 511--518, 2001. Also IlliGAL Report No. 2000020.
• 26: M. Pelikan and D. E. Goldberg. Hierarchical BOA solves ising spin glasses and MAXSAT. IlliGAL Report No. 2003001, University of Illinois at Urbana-Champaign, Illinois Genetic Algorithms Laboratory, Urbana, IL, 2003.
• 27: M. Pelikan, D. E. Goldberg, and E. Cantu-Paz. Bayesian optimization algorithm, population sizing, and time to convergence. IlliGAL Report No. 2000001, University of Illinois at Urbana-Champaign, Illinois Genetic Algorithms Laboratory, Urbana, IL, 2000.
• 28: M. Pelikan and A. K. Hartmann. Searching for ground states of ising spin glasses with hierarchical BOA and cluster exact approximation. In M. Pelikan, K. Sastry, and E. Cantu-Paz, editors, Scalable Optimization via Probabilistic Modeling: From Algorithms to Applications, pages 333--349. Springer, 2006.
• 29: M. Pelikan, H. G. Katzgraber, and S. Kobe. Finding ground states of sherrington-kirkpatrick spin glasses with hierarchical boa and genetic algorithms. MEDAL Report No. 2008004, Missouri Estimation of Distribution Algorithms Laboratory, University of Missouri-St. Louis, St. Louis, MO, 2008.
• 30: E. Radetic, M. Pelikan, and D. E. Goldberg. Effects of a deterministic hillclimber on hboa. MEDAL Report No. 2009003, Missouri Estimation of Distribution Algorithms Laboratory, University of Missouri-St. Louis, St. Louis, MO, 2009.
• 31: Soraya B. Rana , L. Darrell Whitley, Genetic Algorithm Behavior in the MAXSAT Domain, Proceedings of the 5th International Conference on Parallel Problem Solving from Nature, p.785-794, September 27-30, 1998
• 32: K. Sastry. Efficient atomic cluster optimization using a hybrid extended compact genetic algorithm with seeded population. IlliGAL Report No. 2001018, University of Illinois at Urbana-Champaign, Illinois Genetic Algorithms Laboratory, Urbana, IL, 2001.
• 33: K. Sastry. Evaluation-relaxation schemes for genetic and evolutionary algorithms. Master's thesis, University of Illinois at Urbana-Champaign, 2001.
• 34: A. Sinha and D. E. Goldberg. Verification and extension of the theory of global-local hybrids. IlliGAL Report No. 2001010, University of Illinois at Urbana-Champaign, Illinois Genetic Algorithms Laboratory, Urbana, IL, 2001.
• 35: A. Sinha and D. E. Goldberg. A survey of hybrid genetic and evolutionary algorithms. IlliGAL Report No. 2003004, University of Illinois at Urbana-Champaign, Illinois Genetic Algorithms Laboratory, Urbana, IL, 2003.
• 36: Shigeyoshi Tsutsui , Martin Pelikan , Ashish Ghosh, Edge histogram based sampling with local search for solving permutation problems, International Journal of Hybrid Intelligent Systems, v.3 n.1, p.11-22, January 2006
• 37: A. Young, editor. Spin glasses and random fields. World Scientific, Singapore, 1998.
• 38: T.-L. Yu, K. Sastry, D. E. Goldberg, and M. Pelikan. Population sizing for entropy-based model building in estimation of distribution algorithms. pages 601--608, 2007.
• 39: Q. Zhang, J. Sun, E. Tsang, and J. Ford. Hybrid estimation of distribution algorithm for global optimization. Engineering Computations, 21(1):91--107, 2004.
• 40: Q. Zhang, J. Sun, E. Tsang, and J. Ford. Estimation of distribution algorithm with 2-opt local search for the quadratic assignment problem. In Towards a New Evolutionary Computation, pages 281--292. Springer, 2006.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

General Terms:
Algorithms, Performance

Keywords:
efficiency enhancement, estimation of distribution algorithms, hierarchical boa, hybrid evolutionary algorithms, local search, maxsat, spin glass, trap-5