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

DOI: 10.12677/AIRR.2016.51001, PP. 1-12

Keywords: 多目标优化，分布估计算法，趋势预测模型
Multi-Objective Optimization, Estimation of Distribution Algorithm, Trend Prediction Model

Full-Text   Cite this paper   Add to My Lib

Abstract:

多目标优化问题广泛存在于现实世界的应用当中。传统的基于个体进化策略的进化算法在处理这些优化问题时往往收敛速度慢、严格依赖于种群大小而且效果不大理想。分布估计算法作为元启发式(meta- heuristics)方法的一种，将统计机器学习同群体进化模式相结合，引起了学者的广泛关注。在这篇文章中，我们提出了一种基于趋势预测模型(TPM)的分布估计算法，TPM-EDA，用于解决多目标优化问题。其特点在于有效地利用了群体进化过程的历史信息来预测粒子运动的趋势，从而加速了查找最优Pareto前沿面的过程，提升了算法的搜索能力。与此同时，通过引入稀疏度来控制个体的采样频率，来实现种群的多样性。我们在6个不同的测试函数上，对TPM-EDA和多种已有的EDA算法进行了对比性试验。实验结果表明了TPM-EDA方法的有效性。
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.

References

[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

Full-Text