ABSTRACT

Multi-objective optimization problems exist widely in real world applications. Traditional evolutionary algorithms usually employ individual-based evolution strategies to solve these optimization 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.

Keywords:Multi-Objective Optimization, Estimation of Distribution Algorithm, Trend Prediction Model

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

黄忠强，江敏

厦门大学福建省仿脑智能系统重点实验室，福建 厦门

收稿日期：2016年3月11日；录用日期：2016年3月26日；发布日期：2016年3月30日

摘 要

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

关键词 :多目标优化，分布估计算法，趋势预测模型

1. 引言

现实世界中的很多应用都与多目标优化问题存在着紧密的联系，例如购车时希望能买到性能好、价格低廉同时又省油的车。这种紧密的联系也意味着高效的多目标问题的求解方法，能够带来重要的经济利益。因此，对多目标优化问题的研究，尤其是设计通用而且高效的算法受到了相关领域的广泛关注 [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不仅捕获了变量间的依赖关系，同时也刻画了目标与目标以及目标与变量间的相关关系。然而训练一个贝叶斯网络是复杂而耗时的，会造成巨大开销。除了基于贝叶斯网络的EDA方法，还有基于规则化模型的RM-MEDA [11] 、基于GNG网络的MB-GNG [12] 、基于Parzen窗口的MOPEDA [13] 、基于方向模型的IM-MOEA [14] 等。

然而，在相当多的情况下，尤其是对于多目标优化问题而言，传统EDA算法所用来建模的概率模型很难描述真实前沿面的概率分布。当模型偏差较大时，将直接导致EDA算法的失效。一种有效的解决方式是直接从某个带启发式信息的分布上进行采样然后过滤个体，来替代传统EDA的建模和采样过程。如Luhan Zhou等人在 [15] 中所使用的策略，它强调了生成个体和滤除个体之间的配合，展现出某些传统EDA 算法所不具备的优势。我们的方法正是基于这种策略来不断地产生粒子然后过滤粒子，来实现种群的进化。

在这篇论文中，我们提出了一种称为TPM-EDA的算法用于解决多目标优化问题，我们工作的主要贡献在如下两点：

· 利用稀疏度来控制个体的采样频率，使得种群能均匀地分布在Pareto前沿面上，实现了种群的多样性；

· TPM-EDA提出了一种不同的采样方法来生成下一代种群。其在已经选择的个体的基础上，构造一个基于历史信息的趋势预测模型，并在采样过程中使用该模型预测下一代粒子的位置，从而加速寻找前沿面的速度。

本文的文章结构如下。在第二节，介绍了多目标优化问题的相关概念以及分布估计算法。第三节先介绍了TPM-EDA的算法框架，而后详细描述了我们所提出的趋势预测模型以及TPM-EDA算法。第四节是实验部分，包括测试样例、参数设置以及实验结果。最后是总结和展望。

2. 多目标优化方法与进化计算

2.1. 多目标优化问题定义

在这篇论文中，我们考虑无约束的多目标优化问题。一个无约束的多目标问题定义为：

其中，是n维决策变量，是第i个目标函数。

定义1. (Pareto支配)我们称一个解支配另一个解，记作，如果

定义2. (Pareto最优解集，POS)我们将一个多目标问题的解集记为POS，

定义3. (Pareto前沿面，POF)我们将一个多目标问题的前沿面记为POF，

与单目标优化问题寻找一个最优解不同的是，多目标优化问题需要寻找一个最优的解集，即上述定义的POS，使得最优解集中的解不会被其他解支配。多目标优化算法的目的便是寻找到一个最接近理论前沿面的Pareto前沿面及其对应的解集。

2.2. 分布估计算法EDA

EDA算法(Estimation of Distribution Algorithms) [6] [16] - [18] 将统计机器学习与进化计算相结合，通过将概率模型引入进化框架中来对问题进行优化。与基于个体的进化策略不同的是，EDA是基于种群优化的，它通过反复地对候选解所处的空间进行建模和采样来搜索空间。由于EDA的优化过程是概率分布的反复更新，使得它相比较传统进化算法有如下优势：1) 自适应算子，它们可以根据要解决的问题来调整算子；2) 清晰的问题结构，它们提供了问题解的具体概率模型，使得模型的分析和信息挖掘变得容易；3) 先验概率的存在，EDA可以加入先验概率到模型中；4) 降低了内存需要，EDA只需记录概率模型参数而无需直接保存种群，降低了对内存的需求。EDAs已经成功应用在多目标背包问题 [19] ，经济调度 [20] ，蛋白质结构预测 [21] 等上。

近些年来，分布估计算法发展了很多不同的具体实现方法，其差别往往在于采用了不同的概率模型生成方法和不同的采样方法。尽管不同方法的设计思想有很大的不同，但是这些方法都可以归纳为下面两个主要步骤：

· 首先通过某种方法来构建用于描述解空间的概率模型。EDA算法往往会通过对种群的评估，选择优秀的个体集合，然后采用统计学习等手段构造一个描述当前解集的概率模型。我们这这位概率模型的生成。

· 在概率模型的基础上，利用不同的采样方式来产生新的种群。我们称此步骤为采样方法。

EDA算法的大体流程如图1所示。

大多数的EDA算法都是通过显式地构建一个概率模型，并在这个模型上进行采样来得到新的种群。然而要准确地构建概率模型是一件很困难的事情，错误的概率模型将直接导致新得到的种群质量不高，因此很难找到问题的解。一种替代的方法是隐式的建立概率模型，通过不断地产生和过滤个体达到。我们的思路是首先根据稀疏度选择待扩展的个体，然后进行采样，并通过筛选非支配解集来得到优势种群。另外一方面，我们认同Claudio Rossi等人的观点 [22] ，即充分利用某些信息，将能够使得算法提高对变化的前沿面的追踪能力。作者使用了卡尔曼滤波来预测变化的最优点，而我们则认为不仅简单的预测机制对于多目标优化问题而言至关重要，于此同时概率知识，而不是精确值，能够给我们更多的帮助。因此，我们提出了利用基于运动趋势预测的机制来对前沿面进行预测。

3. TPM-EDA方法

在这一节的开始部分，我们首先定义相关的术语，然后给出TPM-EDA方法的算法框架。接下来我们将更加详细地介绍TPM-EDA的两个组成部分：待扩展个体的选择过程和趋势预测模型。前者用于选取待扩展的个体，而后者则是利用历史信息来预测下一代种群。在介绍完这两者之后，我们将给出TPM-EDA具体的算法描述。

图1. 分布估计算法流程图

3.1. TPM-EDA算法框架

定义4. (粒子)粒子是一个二元组，其中表示的是多目标优化问题的解，也叫做个体；而是n维空间中的单位向量，表示粒子的方向。

在TPM-EDA算法中，每次采样时都挑选一个待扩展的粒子，然后在这个粒子所代表的一个特定分布上进行采样。下面，我们结合图2(a)~(e)来简要介绍一下TPM-EDA的算法框架。在某一个时刻，TPM- EDA首先产生若干个粒子(图2(a))，并计算对应的POS (图2(b))。随后计算每个粒子的稀疏度，并根据稀疏度来选择粒子，其原则是稀疏度较高的粒子将会有更高的概率被选中(图2(c))。将趋势预测模型作用到所选择的粒子上，得到一系列新的解(图2(d))，并由此得到新的POS和POF (图2(e))。以此不断循环，直到停止条件满足。

3.2. 选择过程

TPM-EDA的做法是在采样阶段挑选那些更“重要”的粒子，从而保持粒子的多样性和前沿面的分布性。我们的做法是在那些稀疏的个体附近产生更多的子代，而密集的区域只产生少量的个体，即以稀疏度为权重来选择个体。假设当前群体为，每个个体的拥挤度为其他粒子对其的相互作用之和。距离更近的个体相互作用应该更高，因此我们定义粒子的拥挤度为：

其中，参数h表示带宽。个体p_k的稀疏度则定义为拥挤度的倒数：

每次采样时我们依据粒子的Sparseness值进行轮盘赌法。可以看出当粒子处在较稀疏的位置时，被采样的概率较高，能在其领域内产生更多的子代；而较密集的地方产生子代的概率小。这样，我们调节了所获得前沿面的稀疏程度，从而能够保持粒子的多样性，使前沿面更具有分布性。

3.3. 趋势预测模型

在上述选择过程挑选完待扩展的粒子后，我们需要在这粒子所代表的某个特定分布上进行采样。在物理上，如果知道了一个物体的运动方向，那么下一时刻的位移方向便等于。可以写成：

与这种简单的线性预测不同的是，我们希望给物体的运动添加一些概率性，使得速度只是提供给物体一个可能的运动趋势而非直接确定下一时刻运动方向。这样的运动趋势可以很好地引导粒子进行更新，从而更快、更精确地逼近前沿面。

定义5. (趋势预测模型，TPM)

任意给定向量和距离度量函数。我们把上的一个概率分布叫做趋势预测模型，如果其满足：

这样的一个分布刻画了粒子的运动趋势：将以较大的概率沿着原速度方向，而又允许粒子以较小的概率违背这个方向。

图2. TPM-EDA算法框架

图3展示了这样一个TPM实例。其中黑点是依据稀疏度被选择后的粒子，是其运动方向。如果所代表的TPM模型以cos距离为距离度量方式，定义域为单位球面，则因为相比较更靠近(反应在cos距离上是二者夹角更小)，所以被选择到的概率更高。类似的，的概率比这概率更低，而最不可能被采样到。

在我们的算法当中，每个粒子运动的启发式信息，产生它的父节点指向该节点的方向向量，被作为运动方向记录下来。我们希望设计一个趋势预测模型使得采样出的向量离这个运动方向越近则概率越高。为此，我们设计了一个特定的TPM模型。设定该模型距离度量方式为cos距离，定义域 为单位球面，位移方向与原速度的夹角从均值为0，方差为带宽的高斯分布上进行采样，而粒子的步长则由均值为0，方差为的高斯分布上产生。由于是单位球面，所以其实是关于方向向量的分布，cos距离则刻画了采样出来的位移方向与原速度之间的夹角大小。算法sample描述了这个采样过程的具体实现。

因为每个粒子都带有能够刻画运动趋势的方向向量，因此能够准确预测前沿面的推进方向。为了实现时间维度上的开发与扩展平衡，更具体地，要实现在算法前期具有较高的搜索速度，在后期具有较细致的搜索能力，我们引入趋势度的概念。通过控制算法不同阶段趋势度来调节这个平衡。注意到，当趋于0时，趋于均匀分布。均匀分布可以看作没有任何趋势的分布，因此，我们定义的趋势度为其与均匀分布的距离。

定义6. (趋势度，TD)定义趋势预测模型的趋势度为：

其中dis为分布间距离的度量方式，Uniform表示均匀分布。令算法中的参数带宽h随着迭代不断降低。基于上述定义，模型的趋势度将随着时间递减。算法运行阶段前期趋势度大，粒子会最大可能沿着速度方向前进，从而较快逼近前沿面；后期趋势度不断降低，来达到局部的、更细致地搜索。

我们需要设定个停止条件来让算法终止。定义如下指标来衡量两个前沿面、之间的差距：

该条件描述了离前沿面的临近程度，若、一致，则。因为参数带宽h随着迭代不断降低，粒子运动的步长将不断趋于0，因此以该条件作为TPM-EDA算法的停止条件时，算法是可以停止的。

3.4. TPM-EDA算法

综合上述的选择过程以及趋势预测模型，我们给出TPM-EDA算法的具体实现。

4. 实验

我们将GM-EDA和其他的EDA方法进行了对比性实验，画出了它们解出的前沿面，并利用IGD指标来对各种算法的求得的解的收敛性和多样性进行比较。The inverted generational distance (IGD) [25] 被用来衡量多目标算法的性能。令为均匀分布在最优前沿面上的点集，而是算法求得的前沿面点集。定

图3. 一个TPM实例

义IGD指标为：

要使得IGD值尽量小，需要尽量逼近。因此，该定义刻画了算法求得的POF与最优POF之间的相近程度。

4.1. 测试样例和参数设置

在这篇文章中，我们将所提出的方法与其他四种EDA算法相比较，包括MBN-EDA [10] ，RM-MEDA [11] 和EGNA [23] 。MBN-EDA方法基于联合概率模型，它通过建立多维的贝叶斯网络来捕获决策变量和目标变量间的关系。RM-MEDA是基于规则模型的多目标优化算法。它假定Pareto解集处在分段连续的m-1维流形空间中并使用局部的主成分分析来为候选区域进行建模。EGNA是使用高斯网络来为决策变量建立概率模型的一种简单EDA方法，但它并不考虑目标的信息。

在实验中，我们使用了6个测试样例 [24] ，包括FDA4、FDA5、DIMP2、dMOP2、dMOP3和HE2。这些测试函数具有不同的特性，它们的理论前沿面具有不同的形状，比如连续型的、分离型的等。FDA4和FDA5是3目标函数而其他是两目标函数。

实验中的EDA算法都遵循相同的环境设置：每次迭代至多含有100个个体，最多迭代次数200。各个算法的参数与它们各自的文章中一致：对于MBN-EDA，使用利润增益排序(Profit gain ordering)作为排序方法 [10] ；RM-MEDA中，局部PCA聚类的数目被设置为5 [11] ；EGNA中截断选择被用作选择方法 [23] 。

4.2. 结果

由于篇幅有限，我们只选取部分算法和测试函数来画出他们所获得的前沿面的情况。图4中画出了三个EDA方法求解得到的前沿面情况。红色的点表示算法求得的个体，3D线框展示的是理论的前沿面。从图中可以看出，TPM-EDA方法取得了接近真实前沿面的结果。

图5展示的是DIMP2函数的情况。红色的点是算法求得的解，蓝色实线表示理论的前沿面。所测试的三个方法在这个测试函数上表现都不大理想。但相对而言，TPM-EDA的效果较好，它获得的种群具有更好的分布性。

图6展示的是HE2函数的情况，该函数的前沿面是分离的。从图中可以看出TPM-EDA具有最好的收敛效果，其前沿面最贴近真实的前沿面。然而TPM-EDA算法缺少位于最右侧的前沿面片段中的个体，导致它前沿面的离散程度弱于RM-MEDA。

图4. MBN-EDA, RM-MEDA和TPM-EDA获得的FDA4前沿面

图5. MBN-EDA, RM-MEDA和TPM-EDA获得的DIMP2前沿面

图6. MBN-EDA, RM-MEDA和TPM-EDA获得的HE2前沿面

为了考察算法解的收敛性，对每个标准函数，我们都进行了20次测试。对每次测试得到的IGD值取平均得到算法在这个测试函数上的IGD度量，所获得的结果在表1当中。可以看出TPM-EDA在大部分测试函数上都超过了其他算法。在dMOP2测试函数上，TPM-EDA也处在了第二的位置。因此，算法求得的前沿面具有较好的收敛性，能够很好地逼近理论的最优解。

4.3. 讨论

从静态实验结果以及IGD指标上都可以看出TPM-EDA算法能取得比其他EDA算法更优秀的结果。基于稀疏度的选择过程以及趋势预测模型的使用使得TPM-EDA能够更快、更准确地逼近理论前沿面。趋势预测模型有效地利用了粒子更新过程中的历史信息，以此预测粒子运动的趋势。

我们可以将所提出的TPM-EDA方法应用到很多实际应用中。机器学习中的很多问题都可以转化为

表1. 各个方法的IGD指标

多目标优化问题，如在深度学习中，我们可以利用TPM-EDA同时优化深度神经网络的训练误差和网络结构 [26] ；在迁移学习的领域适应方法中，可以利用多目标优化算法来同时优化映射后领域的相似性以及样本的可分性 [27] ；在云计算的多任务调用中寻找到效率高而又节能的调度方案 [28] 等。

5. 总结和展望

本文提出了一个新的基于趋势预测模型的分布估计算法，TPM-EDA，用来解决多目标优化问题。TPM-EDA通过反复的产生子代个体和筛选优势种群来促进种群的进化，并使用方向向量这个启发式信息来预测子代可能所处的区域，从而提升搜索的准确性。此外，基于稀疏度的选择方法被用来调节个体的稀疏程度、控制种群的多样性，使得获得的前沿面分布性良好。实验结果也充分证明了我们方法的有效性。

一个高效的多目标优化算法是很多问题的基础。我们后期的研究方向包括基于多目标优化的深度学习及迁移学习 [26] [27] ，机器人自主学习 [29] - [31] 以及如何利用多目标优化辅助亚符号模型的知识抽取上 [32] - [36] 。

基金项目

此研究工作受到国家自然科学基金项目(No. 61003014，No. 61105026和No. 61273338)的资助。

文章引用

黄忠强,江 敏. 基于趋势预测模型的多目标分布估计算法
Trend Prediction Model Based Multi-Objective Estimation of Distribution Algorithm[J]. 人工智能与机器人研究, 2016, 05(01): 1-12. http://dx.doi.org/10.12677/AIRR.2016.51001

参考文献 (References)