A comparison study between genetic algorithms and bayesian optimize algorithms by novel indices

ABSTRACT

Genetic Algorithms (GAs) are a search and optimization technique based on the mechanism of evolution. Recently, another sort of population-based optimization method called Estimation of Distribution Algorithms (EDAs) have been proposed to solve the GA's defects. Although several comparison studies between GAs and EDAs have been made, little is known about differences of statistical features between them. In this paper, we propose new statistical indices which are based on the concepts of crossover and mutation, used in GAs, to analyze the behavior of the population based optimization techniques. We also show simple results of comparison studies between GAs and the Bayesian Optimization Algorithm (BOA), a well-known Estimation of Distribution Algorithms (EDAs).

REFERENCES

• 1: Shummet Baluja, Population-Based Incremental Learning: A Method for Integrating Genetic Search Based Function Optimization and Competitive Learning, Carnegie Mellon University, Pittsburgh, PA, 1994
• 2: Shumeet Baluja , Scott Davies, Using Optimal Dependency-Trees for Combinational Optimization, Proceedings of the Fourteenth International Conference on Machine Learning, p.30-38, July 08-12, 1997
• 3: T. Fukao. Thermodynamical theory of distributed System. Shyoukoudou, 1987.
• 4: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 5: K. Hamada, N. Mori, and K. Matsumoto. A spin glass based genetic algorithm. In Proceedings of the 45th ISCIE Conference (SCI'01), pages 39--40, 2001.
• 6: K. Hamada, N. Mori, and K. Matsumoto. A spin glass based genetic algorithm-ii. In Proceedings of the 46th ISCIE Conference (SCI'02), pages 593--594, 2002.
• 7: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 8: S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science, 220:671--680, 1983.
• 9: N. Mori, S. Imanishi, H. Kita, and Y. Nishikawa. Adaptation to changing environments by means of the memory based thermodynamical genetic algorithm. In Proceedings of the 7th International Conference on Genetic Algorithms, pages 299--306, 1997.
• 10: N. Mori and H. Kita. The entropy evaluation method for the thermodynamical selection rule. In Proc. of the 5th the Genetic and Evolutionary Computation Conference (GECCO'99), page 799, 1999.
• 11: Naoki Mori , Hajime Kita , Yoshikazu Nishikawa, Adaption to a Changing Environment by Means of the Thermodynamical Genetic Algorithm, Proceedings of the 4th International Conference on Parallel Problem Solving from Nature, p.513-522, September 22-26, 1996
• 12: Naoki Mori , Hajime Kita , Yoshikazu Nishikawa, Adaptation to a Changing Environment by Means of the Feedback Thermodynamical Genetic Algorithm, Proceedings of the 5th International Conference on Parallel Problem Solving from Nature, p.149-158, September 27-30, 1998
• 13: N. Mori, J. Yoshida, H. Tamaki, H. Kita, and Y. Nishikawa. A thermodynamical selection rule for the genetic algorithm. In Proc. of 2nd IEEE Conference on Evolutionary Computation, pages 188--192, 1995.
• 14: Heinz Mühlenbein , Gerhard Paass, From Recombination of Genes to the Estimation of Distributions I. Binary Parameters, Proceedings of the 4th International Conference on Parallel Problem Solving from Nature, p.178-187, September 22-26, 1996
• 15: H. Nishimori. Spin Glass Theory and Statistical Mechanics of Information. Iwanami, 1999.
• 16: M. Pelikan. http://www.cs.umsl.edu/~pelikan/software.html, 2000.
• 17: M. Pelikan, D. E. Goldberg, and E. Cantú-Paz. BOA: The Bayesian optimization algorithm. In Proceedings of the Genetic and Evolutionary Computation Conference GECCO-99, volume I, pages 525--532, 13-17 1999.
• 18: Martin Pelikan , David E. Goldberg , Erick E. Cantú-paz, Linkage Problem, Distribution Estimation, and Bayesian Networks, Evolutionary Computation, v.8 n.3, p.311-340, September 2000 [doi>10.1162/106365600750078808]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.m Miscellaneous

General Terms:
Algorithms

Keywords:
bayesian optimization algorithms, diversity, genetic algorithms, population-based optimization methods