Estimation of distribution algorithm based on archimedean copulas

ABSTRACT

Both Estimation of Distribution Algorithms (EDAs) and Copula Theory are hot topics in different research domains. The key of EDAs is modeling and sampling the probability distribution function which need much time in the available algorithms. Moreover, the modeled probability distribution function can not reflect the correct relationship between variables of the optimization target. Copula Theory provides a correlation between univariable marginal distribution functions and the joint probability distribution function. Therefore, Copula Theory could be used in EDAs. Because Archimedean copulas possess many nice properties, an EDA based on Archimedean copulas is presented in this paper. The experimental results show the effectiveness of the proposed algorithm.

REFERENCES

• 1: Pedro Larraanaga , Jose A. Lozano, Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation, Kluwer Academic Publishers, Norwell, MA, 2001
• 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: Michèle Sebag , Antoine Ducoulombier, Extending Population-Based Incremental Learning to Continuous Search Spaces, Proceedings of the 5th International Conference on Parallel Problem Solving from Nature, p.418-427, September 27-30, 1998
• 4: 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
• 5: Larranaga, P., Etxeberria, R., Lozano, J. A., and Pena, J. M. 2000. Optimization in continuous domains by learning and simulation of Gaussian networks. In Proceedings of the Genetic and Evolutionary Computation Conference (Las Vegas, Nevada, USA, July 8--12, 2000). GECCO '00 .Morgan Kaufmann, San Francisco, 201--204.
• 6: De Bonet, J. S., Isbell, C. L. , and Viola, P. 1996. MIMIC: Finding optima by estimation probability densities. Advances in Neural Information Processing Systems , Cambridge: MIT Press, 9:424--430. URL= http://books.nips.cc/papers/files/nips09/0424.pdf
• 7: Zhong, W., Liu, J., Liu, F., and Jiao, L. 2004. Second order estimation of distribution algorithms based on kalman filter, Chinese J. Comput., September 2004, 27(9):1272--1277 (in Chinese)
• 8: Pelikan, M., Goldberg, D. E., and Cantu--Paz, E. 1999. BOA: the Bayesian optimization algorithm. In Proceedings of the Genetic and Evolutionary Computation Conference (Orlando, Florida, USA, July 13--17, 1999,). GECCO 1999, .Morgan Kaufmann, San Francisco, 525--532. URL= http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.52.2148&rep=rep1&type=pdf
• 9: Larranga, P., Etxeberria, R., Lozano, J. A., and Pena, J. M. 1999. Optimization by Learning and Simulation of Bayesian and Gaussian Networks. Technical Report EHU-KZAA-IK-4/99, University of the Basque Country, Spain. URL= http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.1895
• 10: Bosman P.A.N. and Thierens D. 2006. Multi-objective optimization with the naive MIDEA. In Towards a New Evolutionary Computation. Advances in Estimation of Distribution Algorithms, J.A. Lozano, P. Larrañaga, I. Inza and E. Bengoetxea, Ed. Springer-Verlag, Berlin, 123--157.URL= http://www.springerlink.com/content/j9n0ul146357r552/
• 11: Nazan, K., Goldberg, D. E., and Pelikan, M. 2002. Multi-objective Bayesian optimization algorithm. IlliGAL Report No.2002009, University of Illinois at Urbana-Champaign, Urbana, Illinois,
• 12: Martin Pelikan , Kumara Sastry , David E. Goldberg, Multiobjective hBOA, clustering, and scalability, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068122]
• 13: Abdellah Salhi , José Antonio Vázquez Rodríguez , Qingfu Zhang, An estimation of distribution algorithm with guided mutation for a complex flow shop scheduling problem, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277076]
• 14: Simionescu, P. A., Beale, D. G., and Dozier, G. V. 2006. Teeth-number synthesis of a multispeed planetary transmission using an estimation of distribution algorithm. J. Mech. Design., January 2006, 128(1):108--115.
• 15: Santarelli, S., Yu, T., Goldberg, D. E., Altshuler, E., O'Donnell, T., and Southall H. 2006. Military antenna design using simple and competent genetic algorithms. Math. Comput. Model., 43(9--10):990--1022
• 16: Roger B. Nelsen, An Introduction to Copulas (Springer Series in Statistics), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 17: Demarta, S., and McNeil, A. J. 2007. The t Copula and Related Copulas, Int. Stat. Rev.,73(1):111--129.
• 18: Maria Elena Giuli , Dean Fantazzini , Mario Alessandro Maggi, A New Approach for Firm Value and Default Probability Estimation beyond Merton Models, Computational Economics, v.31 n.2, p.161-180, March 2008 [doi>10.1007/s10614-007-9112-4]
• 19: Cherubini, U., Luciano, E., and Vecchiato, W. 2004. Copula methods in finance. John Wiley.
• 20: Wang, L. F., Zeng, J. C., and Hong, Y. Estimation of Distribution Based on Copula Theory. In the 2009 IEEE Congress on Evolutionary Computation (Trondheim, Norway, May 18--21, 2009). Paper 622. In press.

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

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

General Terms:
Algorithms, Theory

Keywords:
Sklar's theorem, archimedean copulas, copula theory, estimation of distribution algorithms (EDAS)