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

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

现实世界中的很多应用都与多目标优化问题存在着紧密的联系，例如购车时希望能买到性能好、价格低廉同时又省油的车。这种紧密的联系也意味着高效的多目标问题的求解方法，能够带来重要的经济利益。

因此， 对多目标优化问题的研究， 尤其是设计通用而且高效的算法受到了相关领域的广泛关注[1]-[3]。

大量的多目标优化问题难以通过解析方式求得其最优解，这也就使得设计不同的启发式算法成为解决多目标优化问题的主要方法之一[4] [5]。

分布估计算法[6]作为元启发式(meta-heuristics)方法的一种， 其主要特点是将统计机器学习的方法同群体进化模式进行结合。与传统的遗传算法不同，在分布估计算法中，没有交叉、变异等操作，取而代之的是概率模型的学习和采样。EDA 算法往往通过统计学习的手段从宏观的角度为解的分布建立一个概率模型，通过不同的方法在该模型上采样来得到下一代种群，如此反复进行，实现种群的进化。由于在优化的过程中显式的使用概率模型，EDA 算法能够提供其他元启发方法所不能提供的优点。

近些年来，利用EDA 算法来解决多目标优化问题，已经取得了很好的结果。Khan 等[7]提出的多目标贝叶斯优化算法(mBOA)将贝叶斯优化算法同非支配排序算法相结合，利用NSGA-II 中的选择方法来沿着Pareto 前沿面寻找解。这种方法的特点在于通过提供选择压力来确保Exploitation 和Exploration 之间取得某种平衡；Pelikan 等[8]提出的多目标分层BOA (mohBOA)，也借鉴了NSGA-II 和mBOA 中的类似过程来选择可能的候选解，但是不同之处在于在选出了候选解之后，mohBOA 结合了k-means 聚类算法来获得有希望的解的聚类，并使用限制的二进制锦标赛法来将新获得的聚类来与旧的种群集成，来产生下一代种群。实验结果也都证明了这种方法的有效性。Shah 等人证明[9]，ε-hBOA，一种基于ε 占有的分层贝叶斯优化算法，在求解多目标d 维背包问题是较其他两种进化算法有一定优势。Karshenas 等人提出的MBN-EDA [10]建立了关于决策变量和目标变量间关系的多维贝叶斯网络。MBN-EDA 不仅捕获了变量间的依赖关系，同时也刻画了目标与目标以及目标与变量间的相关关系。然而训练一个贝叶斯网络