TAM-EDA: Multivariate t Distribution, Archive and Mutation Based Estimation of Distribution Algorithm

Abstract

We present a novel estimation of a distribution algorithm (eda), tam-eda, which uses a multivariate t distribution model, an archive population and a mutation operation to escape local minima, avoid premature convergence and utilize a record of the best solutions. Earlier edas used multivariate normal distributions to model low-cost regions of the search space. The multivariate t distribution has heavier tails and so is more likely to maintain diversity, while still allowing convergence to occur. The current population of potential solutions has limited ability to represent all the best regions of the search space explored so far. The archive allows storage of a larger population of promising solutions, which are then used in model building. However, the eda model and archive may still become stuck at suboptimal solutions, so to combat this we introduce a decomposition mutation operation which retains most of the attributes of a current solution but attempts large changes in others. A comparison with generic eda, genetic algorithms and the Nelder–Mead method shows that tam-eda is an effective optimization algorithm for a range of test problems. References

• Alfi, A. Particle Swarm Optimization Algorithm with Dynamic Inertia Weight for Online Parameter Identification Applied to Lorenz Chaotic System, International Journal of Innovative Computing, Information and Control 8:1191–1203, 2012. http://www.ijicic.org/ijicic-10-04102.pdf
• Baluja, S. Population-Based Incremental Learning: A Method for Integrating Genetic Search Based Function Optimization and Competitive Learning, Technical Report CMU-CS-94-163, Carnegie Mellon University, 1994. http://www.ri.cmu.edu/pub_files/pub1/baluja_shumeet_1994_2/baluja_shumeet_1994_2.pdf
• Costa, A., Jones, O. D. and Kroese, D. Convergence properties of the cross-entropy method for discrete optimization. Operations Research Letters 35.5: 573-580, 2007. doi:10.1016/j.orl.2006.11.005
• Dimmer, P. R. and Cutteridge, O. P. D. Second derivative Gauss-Newton-based methods for solving nonlinear simultaneous equations. Electronics Letters 10:182–184, 1980. doi:10.1049/ip-g-1.1980.0047
• Kirkpatrick, S., Gelatt, C. D. and Vecchi, M. P. Optimization by Simulated Annealing. Science 220:671–680, 1983. doi:10.1126/science.220.4598.671
• Lagarias, J. C., Reeds, J. A., Wright, M. H., and Wright, P. E. Convergence Properties of the Nelder–Mead Simplex Method in Low Dimensions. SIAM Journal of Optimization 9(1):112–147, 1998. doi:10.1137/S1052623496303470
• Lange, K. L., Little, R. J. A. and Taylor, J. M. G. Robust statistical modeling using the t distribution. Journal of the American Statistical Association, 84(408):881–896, 1989. http://www.jstor.org/stable/2290063
• Larranaga, P., Lozano, J. A. and Bengoetxea, E. Estimation of Distribution Algorithms Based on Multivariate Normal and Gaussian Networks. Techincal Report KZZA-IK-1-01, Department of Computer Science and Artificial Intelligence, University of the Basque Country, Spain, 2001. http://www.sc.ehu.es/acwbecae/ikerkuntza/these/Ch4.pdf
• Lee, S. and Wright, S. J. Decomposition algorithm for training large-scale semiparametric support vector machines. In European Conference on Machine Learning Proceedings Part II, Lecture Notes in Computer Science 5782 pp. 1–14, Springer, Berlin, 2009. doi:10.1007/978-3-642-04174-7_1
• Liu, C. and Rubin, D. B. ML estimation of the t distribution using EM and its extensions, ECM and ECME. Statistica Sinica, 5(1):19–39, 1995. http://www3.stat.sinica.edu.tw/statistica/oldpdf/A5n12.pdf
• Margolin, L. On the convergence of the cross-entropy method. Annals of Operations Research 134(1):201–214, 2005. doi:10.1007/s10479-005-5731-0
• Marti, L., Garcia, J., Berlanga, A., Coello Coello, C. A. and Molina, J. M. On current model-building methods for multi-objective estimation of distribution algorithms: Shortcomings and directions for improvement. Department of Informatics, Universidad Carlos III de Madrid, Madrid, Spain, Tech. Rep. GIAA2010E001,2010. http://www.giaa.inf.uc3m.es/miembros/lmarti/_media/papers%3Bmarti-et-al–2010–model-building-tech-rep.pdf
• Muhlenbein, H. and Paass, G. From recombination of genes to the estimation of distributions I. Binary parameters. Parallel Problem Solving from Nature-PPSN IV, 178–187, Springer-Verlag, 1996. doi:10.1007/3-540-61723-X_982
• Muhlenbein, H. The equation for response to selection and its use for prediction, Evolutionary Computation 5:303–346, 1997. doi:10.1162/evco.1997.5.3.303
• Pant, M., Thangaraj, R. and Abraham, A. Particle Swarm Based Meta-Heuristics for Function Optimization and Engineering Applications. Proceedings of the 7th International Conference on Computer Information Systems and Industrial Management Applications pp. 84–90, IEEE, Piscataway, NJ, 2008. doi:10.1109/CISIM.2008.33
• Posik, P. BBOB-benchmarking a simple estimation of distribution algorithm with Cauchy distribution. In Rothlauf, F. ed., Proceedings of the Genetic and Evolutionary Computation Conference GECCO 2009 pp. 2309–2314, ACM, New York, 2009. doi:10.1145/1570256.1570322
• Price, W. L. A Controlled Random Search Procedure for Global Optimization The Computer Journal 20:367–370, 1977. doi:10.1093/comjnl/20.4.367
• Robert, C. and Casella, G. Monte Carlo Statistical Methods, 2nd ed., Springer, New York, 2005. http://www.springer.com/statistics/statistical+theory+and+methods/book/978-0-387-21239-5
• Rubinstein, R. Y. Optimization of Computer simulation Models with Rare Events, European Journal of Operations Research, 99:89–112, 1997. doi:10.1016/S0377-2217(96)00385-2
• Rubinstein, R. Y. and Kroese, D. P. The cross-entropy method: a unified approach to combinatorial optimization, Monte-Carlo simulation and machine learning. Springer, 2004. http://www.springer.com/computer/theoretical+computer+science/book/978-0-387-21240-1
• Zhang, Q. and Muhlenbein, H. On the convergence of a class of estimation of distribution algorithms. IEEE Transactions on Evolutionary Computation, 8(2):127–136, 2004. doi:10.1109/TEVC.2003.820663