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

Trend Prediction Model Based Multi-Objective Estimation of Distribution Algorithm

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

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.