research-article

Evolutionary algorithms and elliptical copulas applied to continuous optimization problems

Authors:

Harold Dias de Mello Junior,

André V. Abs da Cruz,

Marley M.B. Rebuzzi VellascoAuthors Info & Claims

Information Sciences—Informatics and Computer Science, Intelligent Systems, Applications: An International Journal, Volume 369, Issue C

Pages 419 - 440

https://doi.org/10.1016/j.ins.2016.07.006

Published: 10 November 2016 Publication History

Abstract

Estimation of Distribution Algorithms (EDAs) constitutes a class of evolutionary algorithms that can extract and exploit knowledge acquired throughout the optimization process. The most critical step in the EDAs is the estimation of the joint probability distribution associated to the variables from the most promising solutions determined by the evaluation function. Recently, a new approach to EDAs has been developed, based on copula theory, to improve the estimation of the joint probability distribution function. However, most copula-based EDAs still present two major drawbacks: focus on copulas with constant parameters, and premature convergence. This paper presents a new copula-based estimation of distribution algorithm for numerical optimization problems, named EDA based on Multivariate Elliptical Copulas (EDA-MEC). This model uses multivariate copulas to estimate the probability distribution for generating a population of individuals. The EDA-MEC differs from other copula-based EDAs in several aspects: the copula parameter is dynamically estimated, using dependence measures; it uses a variation of the learned probability distribution to generate individuals that help to avoid premature convergence; and uses a heuristic to reinitialize the population as an additional technique to preserve the diversity of solutions. The paper shows, by means of a set of parametric tests, that this approach improves the overall performance of the optimization process when compared with other copula-based EDAs and with other efficient heuristics such as the Covariance Matrix Adaptation Evolution Strategy (CMA-ES).

References

[1]

K. Aas, C. Czado, A. Frigessi, H. Bakken, Pair-copula constructions of multiple dependence, Insur. Math. Econ., 44 (2009) 182-198.

[2]

A. Auger, N. Hansen, A restart CMA evolution strategy with increasing population size, in: IEEE Congress on Evolutionary Computation, 2005, pp. 1769-1776.

[3]

S. Baluja, Population-based incremental learning: a method for integrating genetic search based function optimization and competitive learning, 1994.

[4]

S. Baluja, S. Davies, Using optimal dependency-trees for combinatorial optimization: learning the structure of the search space, in: Proceedings of the 14th International Conference on Machine Learning, 1997, pp. 30-38.

Digital Library

[5]

E. Bonabeau, M. Dorigo, G. Théraulaz, Swarm Intelligence: from Natural to Artificial Systems, Oxford University Press, New York, 1999.

Digital Library

[6]

J.S. De Bonet, C.L. Isbell, P. Viola, MIMIC: finding optima by estimating probability densities, Adv. Neural Inf. Process. Syst., 4 (1997) 424-430.

Digital Library

[7]

L.B. Booker, D.E. Goldberg, J.H. Holland, Classifier systems and genetic algorithms, Artif. Intell., 40 (1989) 235-282.

Digital Library

[8]

P.A.N. Bosman, D. Thierens, Advancing Continuous IDEAs with Mixture Distributions and Factorization Selection Metrics, in: Proceedings of the Optimization by Building and Using Probabilistic Model. OBUPM Workings in Genetic Evolution of Computational Conference GECCO-2001, 2001, pp. 208-212.

[9]

P.A.N. Bosman, D. Thierens, Numerical optimization with real-valued estimation-of-distribution algorithms, in: Scalable Optimization via Probabilistic Model, Springer Berlin Heidelberg, Berlin, Heidelberg, 2006, pp. 91-120.

[10]

F. Caraffini, F. Neri, L. Picinali, An analysis on separability for Memetic Computing automatic design, Inf. Sci. (Ny)., 265 (2014) 1-22.

Digital Library

[11]

U. Cherubini, E. Luciano, W. Vecchiato, Copula Methods in Finance, John Wiley & Sons Ltd, Chichester, 2004.

[12]

L. delaOssa, J.A. Gamez, J.L. Mateo, J.M. Puerta, Avoiding premature convergence in estimation of distribution algorithms, in: 2009 IEEE Congress on Evolutionary Computing, 2009, pp. 455-462.

Digital Library

[13]

M. Dorigo, G. Di Caro, L.M. Gambardella, Ant algorithms for discrete optimization, Artif. Life., 5 (1999) 137-172.

Digital Library

[14]

P. Embrechts, A. McNeil, D. Straumann, Correlation and dependence in risk management: Properties and pitfalls, in: Risk Management Value Risk and Beyond, Cambridge University Press, 2002, pp. 176-223.

[15]

M.G. Epitropakis, F. Caraffini, F. Neri, E.K. Burke, A separability prototype for automatic memes with adaptive operator selection, in: 2014 IEEE Symposium on Foundations of Computer Intelligence, 2014, pp. 70-77.

[16]

L.J. Fogel, A.J. Owens, M.J. Walsh, Artificial Intelligence Through Simulated Evolution, John Wiley and Sons, New York, 1966.

[17]

Y. Gao, L. Peng, F. Li, M. Liu, X. Hu, Multiobjective Estimation of Distribution Algorithms Using Multivariate Archimedean Copulas and Average Ranking BT - Foundations of Intelligent Systems: Proceedings of the Eighth International Conference on Intelligent Systems and Knowledge Engineering, S, in: Multiobjective Estimation of Distribution Algorithms Using Multivariate Archimedean Copulas and Average Ranking BT - Foundations of Intelligent Systems: Proceedings of the Eighth International Conference on Intelligent Systems and Knowledge Engineering, S, Springer Berlin Heidelberg, Berlin, Heidelberg, 2014, pp. 591-601.

[18]

A.R. Goncalves, F.J. Von Zuben, Online learning in estimation of distribution algorithms for dynamic environments, in: 2011 IEEE Congress on Evolutionary Computation, 2011, pp. 62-69.

[19]

Y. González-Fernandez, M. Soto, copulaedas: An R package for estimation of distribution algorithms based on copulas (version 1), (2012).

[20]

Y. González-Fernandez, M. Soto, Copulaedas: An R package for estimation of distribution algorithms based on copulas, J. Stat. Softw., 1 (2014).

[21]

N. Hansen, A. Ostermeier, Completely derandomized self-adaptation in evolution strategies, Evol. Comput., 9 (2001) 159-195.

Digital Library

[22]

N. Hansen, R. Ros, N. Mauny, M. Schoenauer, A. Auger, Impacts of invariance in search: When CMA-ES and PSO face ill-conditioned and non-separable problems, Appl. Soft Comput., 11 (2011) 5755-5769.

Digital Library

[23]

G. Harik, E. Cantu-Paz, D.E. Goldberg, B.L. Miller, The gambler's ruin problem, genetic algorithms, and the sizing of populations, in: Proceedings of the 1997 IEEE International Conference on Evolutionary Computation (ICEC '97), IEEE, n.d.: pp. 7-12.

[24]

G.R. Harik, F.G. Lobo, K. Sastry, Linkage learning via probabilistic modeling in the extended compact genetic algorithm (ECGA), Stud. Comput. Intell., 33 (2007) 39-61.

[25]

M. Hauschild, M. Pelikan, An introduction and survey of estimation of distribution algorithms, Swarm Evol. Comput., 1 (2011) 111-128.

[26]

M. Hyrs, J. Schwarz, Multivariate gaussian copula in estimation of distribution algorithm with model migration, in: 2014 IEEE Symposium on Foundations of Computation Intelligence, 2014, pp. 114-119.

[27]

Y. Jiao, I. Joe, Energy-efficient resource allocation for heterogeneous cognitive radio network based on two-tier crossover genetic algorithm, J. Commun. Netw., 18 (2016) 112-122.

[28]

H. Joe, Multivariate Models and Dependence Concepts, Chapman and Hall, London, 1997.

[29]

J. Kennedy, R. Eberhart, Particle swarm optimization, in: Proceedings of ICNN'95 - International Conference on Neural Networks, 1995, pp. 1942-1948.

[30]

J.R. Koza, Genetic Programming: On the Programming of Computers by Means of Natural Selection, The MIT Press, Cambridge, 1992.

Digital Library

[31]

P. Larrañaga, A review of estimation of distribution algorithms, in: Estimation of Distribution Algorithms a New Tool Evolutionary Computation, Springer US, New York, 2002, pp. 57-100.

[32]

P. Larrañaga, R. Etxeberria, J.A. Lozano, J.M. Pena, Optimization by learning and simulation of Bayesian and Gaussian networks, Tech. Rep. EHU-KZAAIK-IK-4/99, Intelligent Systems Group, Department of Computer Science and Artificial Intelligence, University of the Basque Country, 1999.

[33]

P. Larrañaga, J.A. Lozano, Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation, Kluwer Academic Publishers, Boston, 2002.

Digital Library

[34]

J.A. Lozano, P. Larrañaga, I. Inza, E. Bengoetxea, Towards a New Evolutionary Computation, Springer Berlin Heidelberg, Berlin, Heidelberg, 2006.

Digital Library

[35]

A. Maesani, G. Iacca, D. Floreano, Memetic viability evolution for constrained optimization, IEEE Trans. Evol. Comput., 20 (2016) 125-144.

[36]

S.W. Mahfoud, Niching methods for genetic algorithms, in: Technical Report on 95001, Illinois Genetic Algorithms Laboratory (IlliGAL), University of Illinois at Urbana-Champaign, 1995.

Digital Library

[37]

J.-F. Mai, M. Scherer, Simulating copulas: Stochastic models, Imperial College Press, London, 2012.

[38]

Z. Michalewicz, Genetic Algorithms+Data Structures=Evolution Programs, Springer, New York, 1994.

Digital Library

[39]

Z. Michalewicz, D.B. Fogel, How to Solve it: Modern Heuristics, Springer, New York, 2000.

Digital Library

[40]

E. Mininno, F. Neri, F. Cupertino, D. Naso, Compact differential evolution, IEEE Trans. Evol. Comput., 15 (2011) 32-54.

Digital Library

[41]

P. Moscato, C. Cotta, A. Mendes, Memetic algorithms, in: New Optimization in Technical Engineering, Springer Berlin Heidelberg, Berlin, Heidelberg, 2004, pp. 53-85.

[42]

H. Mühlenbein, G. Paaß, From recombination of genes to the estimation of distributions I. binary parameters, in: Parallel Problem Solving from Nat. - PPSN IV, Springer-Verlag, 1996, pp. 178-187.

Digital Library

[43]

R.B. Nelsen, An Introduction to Copulas, Springer, New York, 2006.

Digital Library

[44]

F. Neri, E. Mininno, G. Iacca, Compact particle swarm optimization, Inf. Sci. (Ny)., 239 (2013) 96-121.

Digital Library

[45]

M. Pelikan, Hierarchical Bayesian Optimization Algorithm: Toward a New Generation of Evolutionary Algorithms, Springer-Verlag, Berlin Heidelberg, 2005.

[46]

M. Pelikan, D.E. Goldberg, E. Cantú-Paz, BOA: The bayesian optimization algorithm, in: Proceedings of the Genetic Evolutionary Computational Conference GECCO 1999, 1999, pp. 525-532.

Digital Library

[47]

M. Pelikan, H. Mühlenbein, Marginal distributions in evolutionary algorithms, in: Proceedings of the International Conference on Genetic Algorithms Mendel'98, 1999, pp. 90-95.

[48]

J.M. Peña, J.A. Lozano, P. Larrañaga, Benefits of data clustering in multimodal function optimization via EDAs, in: Estimization on Distributed Algorithms a New Tool for Evolutionary Computation, Springer US, 2002, pp. 101-127.

[49]

I. Rechenberg, Evolutions Strategie: Optimierung Technischer Systeme Nach Prinzipien Der Biologischen Evolution, Frommann-Holzboog Verlag, Stuttgart, 1973.

[50]

M.J. Reddy, P. Ganguli, Bivariate flood frequency analysis of upper godavari river flows using archimedean copulas, Water Resour. Manage., 26 (2012) 3995-4018.

[51]

R. Salinas-Gutiérrez, A. Hernández-Aguirre, E.R. Villa-Diharce, Copula selection for graphical models in continuous estimation of distribution algorithms, Comput. Stat., 29 (2013) 685-713.

Digital Library

[52]

R. Santana, Estimation of distribution algorithms with Kikuchi approximations, Evol. Comput., 13 (2005) 67-97.

Digital Library

[53]

A. Sklar, Fonctions de répartition à n dimensions et leurs marges, in: Publications de l'Institut de Statistique de L'Université de Paris, 1959.

[54]

M. Soto, A. Ochoa, J. Arderí, Gaussian copula estimation of distribution algorithm, in: Technical Report ICIMAF 2007-406, Institute of Cybernetics, Mathematics and Physics, 2007.

[55]

R. Storn, K. Price, Differential evolution - A simple and efficient heuristic for global optimization over continuous spaces, J. Glob. Optim., 11 (1997) 341-359.

Digital Library

[56]

P.N. Suganthan, N. Hansen, J.J. Liang, K. Deb, Y.-P. Chen, A. Auger, S. Tiwari, Problem definitions and evaluation criteria for the CEC 2005 special session on real-parameter optimization, in: Technical Report on 2005005, Nanyang Technological University, Singapore, and KanGAL, 2005.

[57]

E.G. Talbi, Metaheuristics: From Design to Implementation, John Wiley and Sons, New Jersey, 2009.

Digital Library

[58]

V. Veloso de Melo, G. Iacca, A CMA-ES-based 2-stage memetic framework for solving constrained optimization problems, in: 2014 IEEE Symposium of Foundations in Computational Intelligence, 2014, pp. 143-150.

[59]

D. Wallin, C. Ryan, On the diversity of diversity, in: 2007 IEEE Congress Evolution Computation, IEEE, 2007, pp. 95-102.

[60]

S. Xiangman, T. Lixin, A novel hybrid differential evolution-estimation of distribution algorithm for dynamic optimization problem, in: 2013 IEEE Congress Evolution Computation, 2013, pp. 1710-1717.

[61]

S. Yin, X. Zhu, Intelligent particle filter and its application on fault detection of nonlinear system, IEEE Trans. Ind. Electron., 62 (2015).

[62]

A. Zhigljavsky, A. Zilinskas, Stochastic Global Optimization, Springer, New York, 2008.

Cited By

de Oliveira Rde Assis TFirmino PFerreira T(2017)Copulas-based time series combined forecastersInformation Sciences: an International Journal10.1016/j.ins.2016.10.022376:C(110-124)Online publication date: 10-Jan-2017
https://dl.acm.org/doi/10.1016/j.ins.2016.10.022
Rodrguez LCastillo OSoria JMelin PValdez FGonzalez CMartinez GSoto J(2017)A fuzzy hierarchical operator in the grey wolf optimizer algorithmApplied Soft Computing10.1016/j.asoc.2017.03.04857:C(315-328)Online publication date: 1-Aug-2017
https://dl.acm.org/doi/10.1016/j.asoc.2017.03.048

Evolutionary algorithms and elliptical copulas applied to continuous optimization problems
1. Information systems
  1. Data management systems
    1. Database administration
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Enhanced opposition-based differential evolution for solving high-dimensional continuous optimization problems
Special Issue on scalability of evolutionary algorithms and other metaheuristics for large-scale continuous optimization problems

This paper presents a novel algorithm based on generalized opposition-based learning (GOBL) to improve the performance of differential evolution (DE) to solve high-dimensional optimization problems efficiently. The proposed approach, namely GODE, ...
Probabilistic model-building genetic algorithms
GECCO '07: Proceedings of the 9th annual conference companion on Genetic and evolutionary computation

Probabilistic model-building algorithms (PMBGAs) replace traditional variation of genetic and evolutionary algorithms by (1) building a probabilistic model of promising solutions and (2) sampling the built model to generate new candidate solutions. ...
Hybrid biogeography-based evolutionary algorithms

Hybrid evolutionary algorithms (EAs) are effective optimization methods that combine multiple EAs. We propose several hybrid EAs by combining some recently-developed EAs with a biogeography-based hybridization strategy. We test our hybrid EAs on the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Information Sciences: an International Journal

Information Sciences: an International Journal Volume 369, Issue C

November 2016

791 pages

ISSN:0020-0255

Issue’s Table of Contents

Copyright © Elsevier Inc.

Publisher

Elsevier Science Inc.

United States

Publication History

Published: 10 November 2016

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

de Oliveira Rde Assis TFirmino PFerreira T(2017)Copulas-based time series combined forecastersInformation Sciences: an International Journal10.1016/j.ins.2016.10.022376:C(110-124)Online publication date: 10-Jan-2017
https://dl.acm.org/doi/10.1016/j.ins.2016.10.022
Rodrguez LCastillo OSoria JMelin PValdez FGonzalez CMartinez GSoto J(2017)A fuzzy hierarchical operator in the grey wolf optimizer algorithmApplied Soft Computing10.1016/j.asoc.2017.03.04857:C(315-328)Online publication date: 1-Aug-2017
https://dl.acm.org/doi/10.1016/j.asoc.2017.03.048

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents