SGMIT: using selfish gene theory to construct mutualinformation trees for optimization

ABSTRACT

In this paper, a new approach named SGMIT in the field of Estimation of Distribution Algorithm (EDA) is proposed. While the current EDAs require much time in the statistical learning process as the relationships among the variables are too complicated, the Selfish Gene Theory (SG) is deployed in this approach and a Mutual Information Tree (MIT) model with an incremental learning and resample scheme is also set to optimize the probability distribution of the virtual population. Experimental results on several benchmark problems demonstrate that, compared with BMDA, COMIT and MIMIC, SGMIT often performs better in convergent reliability, convergent velocity, and convergent process.

REFERENCES

• 1: C. W. Ahn and . R.S. Ramakrishna. On the scalability of real-coded bayesian optimization algorithm. Evolutionary Computation, IEEE Transactions on, 12(3):307--322, 2008.
• 2: Shummet Baluja, Population-Based Incremental Learning: A Method for Integrating Genetic Search Based Function Optimization and Competitive Learning, Carnegie Mellon University, Pittsburgh, PA, 1994
• 3: 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
• 4: Shumeet Baluja , Scott Davies, Fast probabilistic modeling for combinatorial optimization, Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, p.469-476, July 1998, Madison, Wisconsin, United States
• 5: J. Bonet, C.L.Isbell, and P.Viola. Mimic: Finding optima by estimating probability densities. In Advances in Neural Information Processing Systems, volume 9, pages 424--430. MIT Press, Cambridge, MA, 1997.
• 6: C.Chow and C.Liu. Approximating discrete probability distributions with dependence trees. Information Theory, IEEE Transactions on, 14(3):462--467, 1968.
• 7: F. Corno, M. S. Reorda, and G. Squillero. A new evolutionary algorithm inspired by the selfish gene theory. In ICEC'98: IEEE International Conference on Evolutionary Computation, pages 575--580, 1998.
• 8: Fulvio Corno , Matteo Sonza Reorda , Giovanni Squillero, The selfish gene algorithm: a new evolutionary optimization strategy, Proceedings of the 1998 ACM symposium on Applied Computing, p.349-355, February 27-March 01, 1998, Atlanta, Georgia, United States [doi>10.1145/330560.330838]
• 9: F.Corno, M. Reorda, and G.Squillero. Exploiting the selfish gene algorithm for evolving cellular automata. Neural Networks, 2000. IJCNN 2000, Proceedings of the IEEE-INNS-ENNS International Joint Conference on, 6:577--581, 2000.
• 10: G.R.Harik, F.G.Lobo, and D.E.Goldberg. The compact genetic algorithm. Evolutionary Computation, IEEE Transactions on, 3(4):287--297, 1999.
• 11: 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
• 12: Pedro Larraanaga , Jose A. Lozano, Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation, Kluwer Academic Publishers, Norwell, MA, 2001
• 13: M. Pelikan, D.E.Goldberg, and E. Cantl·s-Paz. Boa: The bayesian optimization algorithm. In Proceedings of the Genetic and Evolutionary Computation Conference(GECCO-99), pages 525--532. Morgan Kaufmann, 1999.
• 14: M. Pelikan and H. Muhlenbein. Marginal distribution in evolutionary algorithms. In In Proceedings of the International Conference on Genetic Algorithms Mendel'98, pages 90--95, 1998.
• 15: M. Pelikan and H. Muhlenbein. The bivariate marginal distribution algorithm. In Advances in Soft Computing:Engineering Design and Manufacturing, pages 521--535. Springer-Verlag, London, 1999.
• 16: R.Dawkins. The Selfish Gene -- new edition. Oxford University Press, 1989.
• 17: G. R.Harik, F. G.Lobo, and K. Sastry. Linkage learning via probabilistic modeling in the extended compact genetic algorithm(ecga). Scalable Optimization via Probabilistic Modeling, pages 39--61, 2006.
• 18: S.D.Zhou and Z.Q.Sun. A survey on estimation of distribution algorithms. ACTA AUTOMATICA SINICA, 33(2):113--124, 2007.
• 19: S.Y.Yang, S.L.Ho, G.Z.Ni, J.M.Machado, and K.F.Wong. A new implementation of population based incremental learning method for optimizations in electromagnetics. Magnetics, IEEE Transactions on, 43(4):1601--1604, 2007.
• 20: S. Yang and X. Yao. Population-based incremental learning with associative memory for dynamic environments. Evolutionary Computation, IEEE Transactions on, 12(5):542--561, 2008.
• 21: Y.Hong, S. Kwong, H. Wang, Z.H.Xie, and Q. Ren. Svpcga: Selection on virtual population based compact genetic algorithm. In IEEE Congress on Evolutionary Computation, pages 265--272, 2008.

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
EDAS, genetic algorithms