TAM-EDA: Multivariate t Distribution, Archive and Mutation Based Estimation of Distribution Algorithm
Bo Gao, Ian Wood · ANZIAM Journal · 2014
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