﻿ 基于趋势预测模型的多目标分布估计算法

基于趋势预测模型的多目标分布估计算法Trend Prediction Model Based Multi-Objective Estimation of Distribution Algorithm

Abstract: Multi-objective optimization problems exist widely in real world applications. Traditional evolu-tionary algorithms usually employ individual-based evolution strategies to solve these optimiza-tion problems, leading to low convergence rate, strong dependency on population size and poor results. As a meta-heuristic algorithm, the Estimation of Distribution Algorithm (EDA) combines the statistical machine learning with population evolution model and has attracted a wide spread attention. In this paper, we proposed a trend-prediction-model (TPM) based EDA method, called TPM-EDA, to solve multi-objective problems. The characteristic of TPM is that it effectively utilizes the historic information generated in evolutionary process to predict the trend of particles, so as to promote the search speed for finding Pareto-optimal front and the search ability of algorithm. Meanwhile, the sparseness is applied in our algorithm to control the sampling frequencies of individuals for the purpose of achieving the diversity of population. We compared our method with multiple existing EDA algorithms on 6 different test instances. The experimental results proved the effectiveness of our method.

[1] Ahmadi, M.H., et al. (2013) Thermo-Economic Multi-Objective Optimization of Solar Dish-Stirling Engine by Im-plementing Evolutionary Algorithm. Energy Conversion and Management, 73, 370-380.

[2] Ponsich, A., Jaimes, A.L. and Coello, C.A.C. (2013) A Survey on Multiobjective Evolutionary Algorithms for the Solution of the Portfolio Optimization Problem and Other Finance and Economics Applications. IEEE Transactions on Evolutionary Computation, 17, 321-344. http://dx.doi.org/10.1109/TEVC.2012.2196800

[3] Mukhopadhyay, A., et al. (2014) Survey of Multi-Objective Evolutionary Algorithms for Data Mining: Part II. IEEE Transactions on Evolutionary Computation, 18, 20-35.

[4] Coello, C.A.C., Van Veldhuizen, D.A. and Lamont, G.B. (2002) Evolutionary Algorithms for Solving Multi-Objective Problems. Springer, Vol. 242. http://dx.doi.org/10.1007/978-1-4757-5184-0

[5] Gong, M.-G., Jiao, L.-C., Yang, D.-D. and Ma, W.-P. (2009) Evolutionary Multi-Objective Optimization Algorithms. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.503.5879

[6] Larranaga, P. and Lozano, J.A. (2002) Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation. Springer Science & Business Media, Vol. 2. http://dx.doi.org/10.1007/978-1-4615-1539-5

[7] Khan, N., Goldberg, D.E. and Pelikan, M. (2002) Multi-Objective Bayesian Optimization Algorithm. Urbana, 51, 61801.

[8] Pelikan, M., Sastry, K. and Goldberg, D.E. (2005) Multiobjective hBOA, Clustering, and Scalability. Proceedings of the 7th Annual Conference on Genetic and Evolutionary Computation, ACM, New York, 663-670.

[9] Shah, R. and Reed, P. (2011) Comparative Analysis of Multiobjective Evolutionary Algorithms for Random and Correlated Instances of Multiobjective d-Dimensional Knapsack Problems. European Journal of Operational Research, 211, 466-479. http://dx.doi.org/10.1016/j.ejor.2011.01.030

[10] Karshenas, H., Santana, R., Bielza, C. and Larranaga, P. (2014) Multiobjective Estimation of Distribution Algorithm Based on Joint Modeling of Objectives and Variables. IEEE Transactions on Evolutionary Computation, 18, 519-542.

[11] Zhang, Q.F., Zhou, A.M. and Jin, Y.C. (2008) RM-MEDA: A Regularity Model-Based Multiobjective Estimation of Distribution Algorithm. IEEE Transactions on Evolutionary Computation, 12, 41-63.

[12] Luis Mart´ı, Jesús Garc´ıa, Antonio Berlanga, Carlos A Coello Coello, Jos´ e M Molina. (2011) MB-GNG: Addressing Drawbacks in Multi-Objective Optimization Estimation of Distribution Algorithms. Operations Research Letters, 39, 150-154. http://dx.doi.org/10.1016/j.orl.2011.01.002

[13] Costa, M. and Minisci, E. (2003) MOPED: A Multi-Objective Parzen-Based Estimation of Distribution Algorithm for Continuous Problems. Evolutionary Multi-Criterion Optimization. Springer, 282-294.

[14] Cheng, R., et al. (2015) A Multiobjective Evolutionary Algorithm Using Gaussian Process-Based Inverse Modeling. IEEE Transactions on Evolutionary Computation, 19, 838-856. http://dx.doi.org/10.1109/TEVC.2015.2395073

[15] Zhou, L.H., Zhou, A.M., Zhang, G.X. and Shi, C. (2011) An Estimation of Distribution Algorithm Based on Nonparametric Density Estimation. IEEE Congress on Evolutionary Computation (CEC), 2011. IEEE, , 1597-1604.

[16] Lozano, J.A. (2006) Towards a New Evolutionary Computation: Advances on Estimation of Distribution Algorithms. Springer Science & Business Media, Netherlands, Vol. 192.

[17] Pelikan, M., Sastry, K. and Cantú-Paz, E. (2007) Scalable Optimization via Probabilistic Modeling: From Algorithms to Applications. Springer, Vol. 33.

[18] Larranaga, P., Karshenas, H., Bielza, C. and Santana, R. (2012) A Review on Probabilistic Graphical Models in Evolutionary Computation. Journal of Heuristics, 18, 795-819.

[19] Shah, R. and Reed, P. (2011) Comparative Analysis of Multiobjective Evolutionary Algorithms for Random and Correlated Instances of Multiobjective d-Dimensional Knapsack Problems. European Journal of Operational Research, 211, 466-479. http://dx.doi.org/10.1016/j.ejor.2011.01.030

[20] Chen, C.-H. and Chen, Y.-P. (2007) Real-Coded ECGA for Economic Dispatch. Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation, ACM, New York, 1920-1927. http://dx.doi.org/10.1145/1276958.1277343

[21] Bacardit, J., Stout, M., Hirst, J.D., Sastry, K., Llorà, X. and Krasnogor, N. (2007) Automated Alphabet Reduction Method with Evolutionary Algorithms for Protein Structure Prediction. Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation, ACM, New York, 346-353

[22] Rossi, C., Abderrahim, M. and Díaz, J.C. (2008) Tracking Moving Optimausing Kalman-Based Predictions. Evolutionary Computation, 16, 1-30. http://dx.doi.org/10.1162/evco.2008.16.1.1

[23] Larranaga, P., Etxeberria, R., Lozano, J.A. and Pena, J.M. (2000) Optimization in Continuous Domains by Learning and Simulation of Gaussian Networks. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.3105

[24] Helbig, M. and Engelbrecht, A. (2015) Benchmark Functions for cec 2015 Special Session and Competition on Dynamic Multi-objective Optimization. Tech. rep., Technical Report.

[25] Sierra, M.R. and Coello, C.A.C. (2005) Improving PSO-Based Multi-Objective Optimization Using Crowding, Mutation and I-Dominance. In: Evolutionary Multi-Criterion Optimization, Springer, 505-519.

[26] Jiang, M., Ding, Y., Goertzel, B., Huang, Z., Zhou, C. and Chao, F. (2014) Improving Machine Vision via Incorporating Expectation-Maximization into Deep Spatio-Temporal Learning. International Joint Conference on Neural Networks (IJCNN), Beijing, 6-11 July 2014, 1804-1811.

[27] Jiang, M., Huang, W., Huang, Z. and Yen, G.G. (2015) Integration of Global and Local Metrics for Domain Adaptation Learning Via Dimensionality Reduction. http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=7349204&tag=1

[28] Zhan, Z.H., Liu, X.F., Gong, Y.J., Zhang, J., Chung, H.S.H. and Li, Y. (2015) Cloud Computing Resource Scheduling and a Survey of Its Evolutionary Approaches. ACM Computing Surveys (CSUR), 47, 63. http://dx.doi.org/10.1145/2788397

[29] Jiang, M., Yu, Y., Liu, X., Zhang, F. and Hong, Q. (2012) Fuzzy Neural Network Based Dynamic Path Planning. International Conference on Machine Learning and Cybernetics (ICMLC), Xi’an, 15-17 July 2012, Vol. 1, 326-330.

[30] Chao, F., Chen, F., Shen, Y., He, W., Sun, Y., Wang, Z., Jiang, M., et al. (2014) Robotic Free Writing of Chinese Characters via Human-Robot Interactions. International Journal of Humanoid Robotics, 11, 1450007. http://dx.doi.org/10.1142/S0219843614500078

[31] Chao, F., Lee, M.H., Jiang, M. and Zhou, C. (2014) An Infant Development-Inspired Approach to Robot Hand-Eye Coordination. International Journal of Advanced Robotic Systems, 11, 1-14. http://dx.doi.org/10.5772/57555

[32] Jiang, M., Zhou, C. and Chen, S. (2010) Embodied Concept Formation and Reasoning via Neural-Symbolic Integration. Neurocomputing, 74, 113-120. http://dx.doi.org/10.1016/j.neucom.2009.11.052

[33] Jiang, M., Yu, Y., Chao, F., Shi, M. and Zhou, C. (2013) A Connectionist Model for 2-Dimensional Modal Logic. IEEE Symposium on Computational Intelligence for Hu-man-Like Intelligence (CIHLI), Singapore, 16-19 April 2013, 54-59.

[34] Wu, Y., Jiang, M., Huang, Z., Chao, F. and Zhou, C. (2015) An NP-Complete Fragment of Fibring Logic. Annals of Mathematics and Artificial Intelligence, 75, 391-417. http://dx.doi.org/10.1007/s10472-015-9468-4

[35] Cai, Z., Goertzel, B., Zhou, C., Huang, D., Ke, S., Yu, G. and Jiang, M. (2013) OpenPsi: A Novel Computational Affective Model and Its Application in Video Games. Engineering Applications of Artificial Intelligence, 26, 1-12. http://dx.doi.org/10.1016/j.engappai.2012.07.013

[36] Cai, Z., Goertzel, B., Zhou, C., Zhang, Y., Jiang, M. and Yu, G. (2012) Dynamics of a Computational Affective Model Inspired by Dörner’s Psi Theory. Cognitive Systems Research, 17, 63-80. http://dx.doi.org/10.1016/j.cogsys.2011.11.002

Top