进化算法是求解多目标优化(Multi-objective optimization, MO) 问题的主要方法之一^[1-2].对于昂贵MO问题^[3-4], 目标向量评估所需计算时间或实验成本高昂, 大量昂贵评估必然导致成本灾难.如何有效解决昂贵MO问题, 目前已引起学界的广泛关注.通过深入研究, 国内外学者提出了基于代理模型辅助进化算法^[5-9]和模式分类方法^[10-13]的解决方案.

在解决昂贵MO问题的代理模型辅助进化算法研究方面, Zhang等将昂贵多目标优化问题分解为多个单目标优化子问题, 用高斯过程模型预测各单目标子问题的解, 对减少某些多目标优化问题的目标评估次数取得了较好效果^[5]. Akhtar等使用径向基函数迭代更新响应面模型来近似昂贵目标函数, 通过评估少量的个体获得较好的非支配集^[8]. Montemayor-García等对几种常用代理模型应用于多目标优化问题的准确性、鲁棒性、有效性和可扩展性进行实验研究, 比较各模型的优缺点^[9].由于各种代理模型都有各自的优势和缺点, 因此需要在不同优化问题上选择各自合适的模型.但随着实际问题复杂程度的增强, 建模的难度越来越大, 模型的精度也将难以保证, 导致近似优化往往得不到与真实模型一致的最优解.

在解决昂贵MO问题的模式分类方法研究方面, Guo等首先提出采用模式识别方法进行多目标优化Pareto支配性预测的思路, 通过将2个n维候选解样本决策向量串接成2n维的训练样本, 直接预测Pareto支配性, 从而减少对昂贵目标函数的评价次数^[10-11].随后, 他们在原有工作基础上提出基于等价分量交叉相似性的Pareto支配性预测方法, 通过在决策向量中引入对Pareto支配性贡献度相同的等价维, 进行交叉相似性最近邻搜索, 改善具有线性相关等价维特征的决策空间最近邻个体与目标空间最近邻个体的一致性, 提高Pareto支配性预测最近邻分类方法的准确率^[12].受此启发, 陈志旺等利用最近邻方法实现Pareto支配性预测和可行解预测, 并基于决策空间的流形理论, 利用K-均值聚类和PCA (Principle component analysis) 提出决策空间拥挤距离的计算方法, 改进求解昂贵区间多目标优化问题的NSGA-II (Non-dominated sorting genetic algorithm II) 算法，进一步验证了最近邻方法进行Pareto支配性预测的有效性^[13].然而, 以上研究主要针对原始决策空间^[13]以及具有线性相关等价维特征决策空间^[12]中的Pareto支配性最近邻预测, 对于具有非线性相关特征的昂贵多目标优化问题, 难以真实度量候选解样本间的距离, 极易出现决策空间最近邻个体与目标空间最近邻个体一致性较差的问题.为使决策空间最近邻个体与目标空间最近邻个体尽可能一致, 进一步提高Pareto支配性预测最近邻分类方法的准确性, 本文研究决策空间不同属性变化对目标空间分类正确率的影响, 利用代理模型方法在离散数据上的拟合能力, 提出属性变化趋势模型的构造方法, 建立一种低计算成本的属性趋势模型.通过属性趋势模型, 对多目标问题的决策空间进行变换, 让决策空间数据能承载更多的目标空间信息, 提高决策空间与目标空间邻域关系的一致性.

本文余下内容组织如下:第1节简要介绍文章涉及的基本概念.第2节阐述决策属性趋势模型和决策空间变换方法.第3节针对MO仿真实例问题进行决策空间变换, 分析决策空间变换的可行性.第4节阐述Pareto支配性的预测最近邻算法, 并与现存算法的Pareto支配性预测进行对比实验.最后, 在第5节给出全文结论.

1.   相关概念

1.1   Pareto支配性

一般地, 具有n维决策变量, m个目标函数的最小化无约束多目标优化问题, 可以表述为:

其中, $\boldsymbol{X}$为n维决策空间, $\boldsymbol{Y}$为m维目标空间, $\boldsymbol{F}$为将决策空间映射到目标空间的一组映射关系, 相关定义如下:

定义 1 (Pareto支配性).  对任意向量$\boldsymbol{u}=[u_1, u_2, \cdots, u_m]\in \boldsymbol{Y}$, $\boldsymbol{v}=[v_1, v_2, \cdots, v_m]\in \boldsymbol{Y}$, 当且仅当$\forall i\in\{1, \, 2, \, \cdots, m\}\!\!: u_i\leq v_i\wedge\exists j\in\{1, 2, \cdots, m\}\!\!:u_j < v_j$为真时, 称u支配v, 记作$\boldsymbol{u}\succ \boldsymbol{v}$; 或称v受支配于u, 记作$\boldsymbol{v}\prec \boldsymbol{u}$; 否则, 称u与v不可比, 记作$\boldsymbol{u}\sim \boldsymbol{v}$.

定义 2 (Pareto最优解).  $\boldsymbol{x}\in \boldsymbol{X}$称为Pareto最优解(或Pareto非支配解、非劣解), 当且仅当$\neg\exists~\boldsymbol{x}'\in \boldsymbol{X}$, $\boldsymbol{v}=\boldsymbol{F}(\boldsymbol{x}')\succ \boldsymbol{u}=\boldsymbol{F}(\boldsymbol{x})$.

定义 3 (Pareto最优集).  决策空间中所有最优解的集合称为Pareto最优集, 目标空间中与之对应的目标向量集称为Pareto前沿或Pareto最优面.

1.2   决策属性与目标属性的相关系数

给定MO问题(m个目标函数, n维决策变量) 的N个训练样本$(\boldsymbol{x}^1, \boldsymbol{x}^2, \cdots, \boldsymbol{x}^N)$, 构建样本集的决策矩阵$X\, (\boldsymbol{x}^1, \boldsymbol{x}^2, \cdots, \boldsymbol{x}^N\in \mathrm{\bf{R}}^n)$及目标矩阵$Y\, (\boldsymbol{y}^1, \boldsymbol{y}^2, \cdots, \boldsymbol{y}^N\in \mathrm{\bf{R}}^m)$, 设$M=[X\ Y]$, 则

矩阵M中的前n列中, 每一元素表示决策空间向量的一个决策属性$(x_i)$, 后m列的每一元素表示多目标优化问题中的一个目标属性$(y_j)$.矩阵中决策属性与目标属性的相关性可通过计算相关系数得到^[14], 如式(3).

其中, cov$(x_i, y_j)$为参数${x}_i$与${y}_j$的协方差; $\sigma_{x_i}, \sigma_{y_j}$为属性的标准差; $\overline{x}_i$, $\overline{y}_j$为样本均值; E ($\cdot$) 表示数学期望.计算矩阵M中的前n列与后m列的相关系数, 得到决策属性与目标属性的相关系数矩阵R, 表示为

式中$r_{ij}$表示第i个决策属性与第j个目标属性的相关性. $r_{ij}$的性质如下:

1) $r_{ij}\in [-1, 1]$;

2) $|r_{ij}|=0$, 表示$x_i$属性关于第j个目标函数是非线性相关或者无关;

3) $|r_{ij}|\neq0$, 表示$x_i$属性关于第j个目标函数的线性相关程度.

2.   决策空间变换

最近邻分类方法是按照某种度量准则搜索待分类个体在已知空间的最近邻.在有限样本集的决策空间中, 直接搜索待测样本的最近邻个体, 逼近待测样本的目标函数值, 存在决策空间最近邻与目标空间最近邻不一致的问题(如图 1).因此, 为使待测样本在决策空间与目标空间最近邻个体尽可能一致, 则需要根据这个目标函数的映射特征对决策空间进行空间变换.

图 1  决策空间的线性化过程(圆点表示原样本点的分布, 三角表示经过趋势模型$y=g (x_i)$映射后的样本点

Fig. 1  The linearization process of decision space (Circles are the original sample points and triangles are the mapped sample points by the trend model $y=g (x_i)$.)

下载: 全尺寸图片 幻灯片

2.1   决策属性的趋势模型

在最近邻分类方法中, 待分类个体可以看作是它最近邻个体在系统平衡点的线性增量问题^[15].若建立非线性属性的趋势模型, 则可有效解决在逼近待测样本目标函数值时, 决策空间与目标空间最近邻不一致的问题.本节给出一种非线性相关属性的趋势模型构造方法, 步骤如下:

步骤 1.  计算样本数据决策属性与目标属性的相关系数;

步骤 2.  对目标函数$f (\boldsymbol{x})$, 选择与函数$f (\boldsymbol{x})$非线性相关的属性$x_i$作为可增量的变量, 并把其余属性看成常量;

步骤 3.  改变$x_i$的值(采用样本集中已有的不同$x_i$值, 将相近的$x_i$值看作是彼此的线性增量), 观察$f (\boldsymbol{x})$目标函数值的变化趋势;

步骤 4.  应用最小二乘法进行曲线拟合, 建立$x_i$属性的趋势模型$ { {y}}=g (x_i)$.

显然, 对决策空间与目标函数的非线性相关属性$x_i$, 采用$\boldsymbol{x}=(x_1, \cdots, x_i, \cdots, x_n)\rightarrow \boldsymbol{x}^\prime=(x_1, \cdots, g (x_i), \cdots, x_n)$的方式进行趋势拟合, 将决策空间进行变换, 这相当于对非线性相关属性$x_i$进行了线性化处理(如图 1), 将样本决策空间进行了变换, 使决策空间的最近邻更加真实地反映目标空间的最近邻.

在图 1中, ${\pmb A}$、${\pmb B}$、${\pmb C}$为原决策空间的三个样本, ${\pmb A} '$、${\pmb B}'$、${\pmb C}'$分别为采用趋势模型映射后的样本, ${\pmb Q}$为待查询点, ${\pmb Q}'$为映射后的查询点.若直接在原决策空间中查询${\pmb Q}$的最近邻, 则其最近邻为样本${\pmb B}$或${\pmb C}$.但将${\pmb Q}$映射为${\pmb Q}'$后, 查询到的最近邻为${\pmb A}'$, 即原空间中的${\pmb A}$.

2.2   空间变换

由于决策空间可能是高维的, 考虑建模的复杂性, 不可能对目标函数的每一维属性都建立趋势模型.因此, 根据第1.2节相关系数计算方法, 计算决策空间属性与目标函数$f (\boldsymbol{x})$的相关系数, 得到目标函数$f (\boldsymbol{x})$的决策属性相关系数向量$\boldsymbol{r}=(r (x_1, f (\boldsymbol{x})), r (x_2, f (\boldsymbol{x})), \cdots, r (x_n, f (\boldsymbol{x})))$.然后选择与函数$f (\boldsymbol{x})$的相关系数近似于0~(非线性相关或无关) 以及相等的决策属性进行建模.

因此, 决策空间的变换方法为:

1) 若选择相关系数近似相等的决策属性, 选取任意一个样本$\boldsymbol{x}$, 其中属性$x_i\neq x_j$, 交换$x_i$与$x_j$, 比较目标值, 做可交换验证;

2) 若选择的属性变化趋势是近似线性的, 则不建立模型;

3) 若$x_i$增量变化时, $f (\boldsymbol{x})$不变, 则认为属性$x_i$与$f (\boldsymbol{x})$是无关的, 则去除该属性, 将决策空间进行降维变换;

4) 若存在变化趋势一致的$x_i$和$x_j$属性, 且$x_i$与$x_j$是可交换的, 则建立相同的属性趋势模型$g (\boldsymbol{x})$, 对这些属性应用$g (\boldsymbol{x})$求值并排序, 形成新的样本空间;

5) 若$x_i$是一非线性相关属性, 直接建立属性趋势模型$g (\boldsymbol{x})$并求值, 形成新的样本空间.

3.   多目标决策空间变换的最近邻方法

为验证决策空间变换最近邻方法的有效性, 选取ZDT1、ZDT3、ZDT6、KUR、UF1、DTLZ2和DTLZ4这7个测试函数^[16-19]进行实验.所用实验平台为: Intel (R) i3 CPU 3.3 GHz, RAM 4 GB, 所有程序代码均在Win7系统下的Matlab 2011a上运行.

3.1   决策属性与目标函数的相关系数计算

对每一个测试函数, 在定义范围内产生均匀分布的样本集.设二目标优化问题训练样本集与测试样本集的大小$N=200$, 三目标优化问题训练样本集与测试集样本的大小$N=1\, 000$.分别对每个测试函数进行100次实验, 每次实验都重新生成训练样本集.测试函数的相关系数如表 1所示.

表 1  测试函数的决策属性与目标属性的相关系数

Table 1  Correlation coefficient of decision attribute and objective attribute of test function

测试函数		f1 (x)	f2 (x)	f3 (x)
ZDT1	n=10	(1, 0, 0, 0, …)	(-0.59, 0.27, 0.27, 0.27, …)
	n=30	(1, 0, 0, 0, …)	(-0.79, 0.11, 0.11, 0.11, …)
ZDT3	n=3	(1, 0, 0)	(-0.28, 0.65, 0.65)
	n=10	(1, 0, 0, 0, …)	(-0.49, 0.25, 0.25, …)
ZDT6	n=3	(0.47, 0, 0)	(0.02, 0.69, 0.69)
	n=10	(0.48, 0, 0, 0, …)	(0.02, 0.69, 0.69)
KUR	n=3	(0.02, 0, -0.01)	(0.02, 0.02, 0.02)
UF1	n=15	(0.92, 0, -0.07, 0, -0.07, 0, …)	(-0.51, -0.11, 0, -0.12, …)
DTLZ2	n=10	(-0.64, -0.64, 0.01, -0.01, …)	(-0.64, 0.64, 0.01, 0.01, …)	(0.94, 0, 0, 0.01, 0, …)
DTLZ4	n=10	(-0.64, -0.64, 0.01, -0.01, …)	(-0.64, 0.64, 0.01, 0, -0.01, …)	(0.94, -0.01, 0, 0.01, 0, …)

下载: 导出CSV 

| 显示表格

3.2   基于趋势模型的决策空间变换

由表 1数据可知, 在这些测试函数的决策属性与目标属性相关系数向量中, 存在线性相关、非线性相关和无关等情况, 按照第2.2节方法对这些测试问题的子目标函数进行决策空间变换, 过程如下.

对ZDT1和ZDT3的子目标函数$f_1(\boldsymbol{x})$, 属性$x_1$的相关系数为1, 其余为0且是无关的, 因此可将子目标函数$f_1(\boldsymbol{x})$的原n维决策空间降至1维, 实现子目标函数$f_1(\boldsymbol{x})$的决策空间变化.对ZDT1和ZDT3的子目标函数$f_2\, (\boldsymbol{x})$, 除属性$x_1$外, 其余属性的相关系数相等, 观察$x_i\, (i\neq1)$变化引起的子目标函数$f_2\, (\boldsymbol{x})$值的变化, 发现变化趋势相同且线性, 所以不构造ZDT1和ZDT3的子目标函数$f_2\, (\boldsymbol{x})$关于属性$x_i\, (i\neq1)$的趋势模型, 但属性$x_i\, (i\neq1)$是可交换的, 因此对属性$x_i\, (i=2, 3, \cdots, n)$进行排序, 形成新样本空间, 避免在使用最近邻模型距离计算过程中因相同趋势属性之间数据相差太大产生的计算误差.

对ZDT6的子目标函数$f_1\, (\boldsymbol{x})$, 属性$x_i\, (i=2, 3, \cdots, n)$的相关系数近似0且是无关的, 因此可将子目标函数$f_1\, (\boldsymbol{x})$的原n维决策空间降至1维, 实现子目标函数$f_1\, (\boldsymbol{x})$的决策空间变化.对ZDT6的子目标函数$f_2\, (\boldsymbol{x})$, 除属性$x_1$外, 其余属性的相关系数是相等的, 观察$x_i\, (i=2, 3, \cdots, n)$变化引起的子目标函数$f_2\, (\boldsymbol{x})$值的变化, 发现变化趋势相同且为$g\, (\boldsymbol{x})=\sqrt{24\boldsymbol{x}}$, 且属性$x_i\, (i\neq1)$是可交换的, 因此对属性$x_i\, (i=2, 3, \cdots, n)$进行变换并排序, 形成新的样本空间.

对KUR的子目标函数$f_1\, (\boldsymbol{x})$, 属性$x_i\, (i=1, 3)$的趋势模型相同且为$g\, (\boldsymbol{x})=|\boldsymbol{x}|$, 属性$x_i\, (i=1, 3)$是可交换的, 对属性$x_i\, (i=1, 3)$进行变换并排序, 形成新的样本空间.对KUR的子目标函数$f_2\, (\boldsymbol{x})$, 存在相关系数相同的$x_i\, (i=1, 2, 3)$属性, 发现变化趋势相同且为$g\, (\boldsymbol{x})=5\sin (\boldsymbol{x}^3)$, 属性$x_i\, (i=1, 2, 3)$是可交换的, 同样对$x_i\, (i=1, 2, 3)$属性进行变换并排序, 形成新的样本空间.

对UF1的子目标函数$f_1(\boldsymbol{x})$, 由于偶数维属性的相关系数近似为0, 经过分析是无关的, 因此偶数维属性在最近邻模型中不考虑, 直接去除偶数维; 对于除第1维外的奇数维属性的相关系数相同, 观察其趋势变化也相同, 但建模复杂, 因此不选择构造趋势函数, 仅对除第1维外的奇数维属性进行排序, 形成新的样本空间.对UF1的子目标函数$f_2(\boldsymbol{x})$, 由于除第1维外的奇数维相关系数近似为0, 经过分析是无关的, 因此奇数维属性在最近邻模型中不考虑, 直接去除; 而偶数维属性的相关系数基本相同, 观察其趋势变化也相同, 但建模复杂, 因此不选择构造趋势函数, 仅对偶数维属性进行排序, 形成新的样本空间.

对DTLZ2和DTLZ4的子目标函数$f_1(\boldsymbol{x})$, 分为两部分:属性$x_1$和$x_2$的相关系数相同, 且对子目标函数$f_1\, (\boldsymbol{x})$的影响是线性的, 因此不构造趋势模型; 属性$x_3$到$x_n$的相关系数相同, 且变化趋势是关于0.5对称的, 因此趋势模型选取为$g\, (\boldsymbol{x})=1-\boldsymbol{x}\, \, \, \, (\boldsymbol{x}>0.5)$.对DTLZ2和DTLZ4的子目标函数$f_2\, (\boldsymbol{x})$, 决策空间的处理方法与子目标函数$f_1\, (\boldsymbol{x})$相同.对DTLZ2和DTLZ4的子目标函数$f_3\, (\boldsymbol{x})$, 属性$x_2$相关系数为0, 经过分析是无关的, 则在最近邻模型中不考虑; 属性$x_3$到$x_n$的处理方法与子目标函数$f_1\, (\boldsymbol{x})$相同.

由测试函数决策空间变换可知, 对于MO问题, 原始决策空间将根据不同子目标函数变为对应的新决策空间.

3.3   决策空间变换的最近邻方法分析

在MO问题中, 采用搜索待分类个体在决策空间有限样本集中的最近邻个体, 预测待分类个体的目标函数值, 存在目标空间中子目标函数不能同时最近邻的问题.因此, 对MO问题的各子目标函数, 根据决策属性的趋势模型进行空间变换.对7个存在不同类型相关系数的MO测试问题进行实验, 选择100个待测样本, 比较决策空间变换前后在训练样本集中搜索到待测样本最近邻个体在子目标函数值上的平均误差和最大误差.

由表 2数据可知, 直接去除与子目标函数无关的属性, 相当于对原始决策空间进行降维来实现决策空间的变换, 可减少最近邻方法中的距离计算, 增加最近邻方法预测的准确性.如ZDT1、ZDT3和ZDT6的子目标函数$f_1(\boldsymbol{x})$与UF1的子目标函数$f_1(\boldsymbol{x})$和$f_2(\boldsymbol{x})$.对于与子目标函数非线性相关的属性, 进行趋势拟合, 并对趋势一致的属性进行拟合后排序, 形成新的样本空间, 避免在使用最近邻模型距离计算过程中因相似属性之间数据相差太大产生的计算误差, 增加最近邻方法预测的准确性.如ZDT1、ZDT3和ZDT6的子目标函数$f_2(\boldsymbol{x})$与KUR、DTLZ2和DTLZ4的所有子目标函数.因此, 对不同测试函数, 找到其子目标函数的最近邻个体, 子目标函数值的误差均值明显要优于直接在原始决策空间上找到的最近邻个体时的误差均值, 子目标函数值的最大误差也明显减小, 说明候选解个体与最近邻个体的距离更近了.所以, 该方法能有效改善MO问题决策空间的近邻个体不能代表子函数目标空间近邻个体的问题, 可增加最近邻预测方法的准确性.

表 2  变换前后的最近邻分类误差

Table 2  Nearest neighbor classification error before and after transformation

测试函数		按目标分类的误差均值			按目标分类的最大误差
		f1 (x)	f2 (x)	f3 (x)	f1 (x)	f2 (x)	f3 (x)
ZDT1	原空间	0.1516	0.4302		0.5115	1.3159
	变换后	0.0013	0.1725		0.0074	0.9304
ZDT3	原空间	0.0437	0.446		0.1837	1.7126
	变换后	0.0011	0.3282		0.0042	1.5289
ZDT6	原空间	0.1047	0.1873		0.6864	1.8303
	变换后	0.0031	0.0765		0.0454	0.4374
KUR	原空间	0.6601	5.7885		2.2948	23.423
	变换后	0.2909	1.6843		1.6411	4.6841
UF1	原空间	0.1985	0.1753		0.8847	1.0659
	变换后	0.0753	0.068		0.2736	0.4554
DTLZ2	原空间	0.2314	0.2368	0.2344	1.0053	0.8732	1.0964
	变换后	0.0624	0.0569	0.0471	0.3102	0.1942	0.199
DTLZ4	原空间	0.2072	0.2431	0.2459	0.8283	0.7537	0.895
	变换后	0.0582	0.0724	0.0488	0.2478	0.2178	0.0488

下载: 导出CSV 

| 显示表格

4.   多目标Pareto支配性预测实验

4.1   最近邻模型的Pareto支配性预测算法

本节主要阐述基于决策空间变换最近邻方法的Pareto支配性预测算法, 用两个候选解在决策空间的信息来预测它们在目标空间上的支配关系.首先, 给定昂贵MO问题(m个目标函数, n维决策变量) 的N个训练样本$(\boldsymbol{x}^1, \boldsymbol{x}^2, \cdots, \boldsymbol{x}^N)$, 计算出子目标函数的相关系数向量$\boldsymbol{r}_k$.然后, 对样本决策空间, 根据第3.2节方法, 构造趋势模型进行空间变换.其次, 对候选解样本根据趋势模型进行相应变换, 并在对应的决策空间中采用最近邻方法搜索最近邻个体.这样将会从变换后的m个决策空间中找到m个最近邻个体$(\boldsymbol{x} ^{ik}| k=1, \cdots, m)$.对于候选解样本$\boldsymbol{x}^i$在变换后决策空间中搜索到的每一个最近邻都是对应子目标函数的最近邻$(\min_{f_j}| f_j (\boldsymbol{x}^i)-f_j (\boldsymbol{x})|, ~j=1, \cdots, m)$.最后, 比较两个候选解对应子目标函数最近邻个体的目标值进行Pareto支配性预测.

因此, 对于两个候选解$\boldsymbol{x}^i$与$\boldsymbol{x}^j$, 其Pareto支配性预测算法如算法1.

算法 1. ${\pmb m}$个目标的MO问题

步骤 1.  生成大小为N的训练样本, 计算决策属性与目标属性的相关系数矩阵R;

步骤 2.  对相关系数矩阵R中的0分量和相等分量, 在原始训练样本决策空间采用第3.2节中的空间变换方法, 生成m个子目标函数对应的新决策空间;

步骤 3.  对待测候选解样本$\boldsymbol{x}^i$与$\boldsymbol{x}^j$, 首先按子目标函数进行空间变换, 然后采用最近邻方法, 找到对应训练样本新决策空间中的m个最近邻个体$(\boldsymbol{x} ^{ik}| k=1, \cdots, m)$与$(\boldsymbol{x} ^{jk}| k=1, \cdots, m)$;

步骤 4.  参照训练样本的目标空间, 分别将$\boldsymbol{x}^i$与$\boldsymbol{x}^j$的m个最近邻个体对应的目标值作为它们的子函数目标值;

步骤 5.  比较$\boldsymbol{x}^i$与$\boldsymbol{x}^j$的各子函数目标值, 判别Pareto支配性.

在步骤1中, 在计算决策空间属性(n维) 与目标属性(m维) 的相关系数矩阵时, 计算每一个决策属性与目标属性协方差与标准差的计算复杂度均为O (N), 所以计算相关系数矩阵的时间复杂度为O ($nmN$).步骤2中, 设有k个决策属性($k \leq n$}) 与子目标函数$f_j (\pmb x)$是非线性相关且不等价的, 则需建立k个趋势函数.由于属性趋势函数的建立是采用最小二乘方法, 时间复杂度为O ($N^2$), 所以完成m个分目标函数空间变换的时间复杂度为O ($kmN^2$).步骤3中, 对决策空间运用最近邻分类方法对待测候选解样本进行预测的时间复杂度为O ($mN^2$).步骤4和步骤5的时间复杂度为O (m).因此, 两个候选解${\pmb x}^i$与${\pmb x}^j$的Pareto支配性预测的时间复杂度为max{O ($nmN$), O ($kmN^2$), 这说明最近邻分类Pareto支配性预测方法的时间复杂度是可接受的.

4.2   实验研究

选取与第3节相同的实验环境和测试函数, 将决策空间变换的最近邻方法(Nearest neighbor method based on decision space transformation, DSTNN) 与简单欧氏距离相似性测度的最近邻方法(Nearest neighbor classification based on Euclidian distance measurement, ENNC)^[11]、等价分量最小交叉距离加权和的最近邻方法(Nearest neighbor classification based on equivalent similarity, ESNNC)^[12]和采用高斯过程(Gaussian process, GP) 模型^[5]对每一个目标函数分别建模, 用模型的输出值近似真实目标值的方法进行Pareto支配性预测比较.对二目标优化问题设计训练样本集与测试集样本的大小$N=200$, 三目标优化问题样本集与测试集样本的大小$N=1\, 000$.分别对每个测试问题进行100次实验, 每次实验都重新生成训练样本集, 测试样本集不变, 则100次Pareto支配性预测实验的Pareto支配性的正确性评价如表 3所示.参考数值主要有决策空间维数n和支配性平均预测精度.

表 3  Pareto支配性预测的平均精度

Table 3  Average precision of Pareto dominance prediction

测试函数	方法	n	Pareto支配性(%)
			总体正确	非支配类	支配类	不可比类
ZDT1	DSTNN	10	92.32	81.7	88.61	96.64
	ENNC		64.79	40.58	42.3	74.88
	ESNNC		83.23	70.32	75.24	88.31
	GP		88.76	65.55	65.55	90.21
	DSTNN	30	90.85	71.2	81.51	95.2
	ENNC		54.32	17.36	23.26	63.41
	ESNNC		68.9	37.49	40.28	80.54
	GP		73.41	32.97	32.97	84.49
ZDT3	DSTNN	3	93.13	80.47	93.14	97.19
	ENNC		76.84	75.54	69.03	79.2
	ESNNC		68.82	56.95	68.85	72.26
	GP		57.73	54.6	54.6	59.48
	DSTNN	10	83.29	71.53	77.56	88.69
	ENNC		59.33	34.81	38.61	70.03
	ESNNC		77.86	72.05	66.85	84.12
	GP		71.1	54.2	54.2	78.56
ZDT6	DSTNN	3	95.94	89.83	95.59	99.36
	ENNC		53.68	42.23	48.88	55.9
	ESNNC		49.78	43.06	49.49	52.97
	GP		52.96	36.92	36.92	66.89
	DSTNN	10	91.43	87.77	93.58	92.33
	ENNC		44.3	37.8	47.55	46.1
	ESNNC		64.86	66.12	60.53	66.44
	GP		48.88	47.03	47.03	50.82
DTLZ2	DSTNN	10	86.49	43.89	66.87	89.66
	ENNC		54.89	17.24	17.42	58.87
	ESNNC		90.92	22.68	28.41	95.31
	GP		89.5	12	12	96.75
DTLZ4	DSTNN	10	85.39	50.14	74.64	88.55
	ENNC		53.74	16.93	20.42	57.23
	ESNNC		72.23	48.38	44.56	79.99
	GP		70.87	9.51	9.51	76.65
UF1	DSTNN	10	86.14	71.9	84.17	91.64
	ENNC		60.08	54.86	50.23	65.76
	ESNNC		60.84	65.23	70.69	71.49
	GP		57.7	61.53	61.53	51.61
KUR	DSTNN	3	85.43	79.73	86.79	89.87
	ENNC		46.47	53.95	56.71	34.54
	ESNNC		50.73	52.88	55.39	45.02
	GP		44.19	41.79	41.79	47.76

下载: 导出CSV 

| 显示表格

由表 3可知, 1) DSTNN算法同其他算法相比, 预测的准确性提高幅度较大, 尤其是对于MO优化过程中起重要作用的非支配类, 所以该算法将在MO问题的进化优化中具有较大优势; 2) DSTNN算法在样本空间类别分布不平衡的DTLZ2、DTLZ4和UF1测试函数上都显示出较好的正确性; 3) Pareto支配性预测的正确率跟决策空间的维数是负相关的, 这从ZDT1、ZDT3和ZDT6等函数的维数变化可知, 随着维数的降低, 支、ZDT6和UF1测试问题的实验结果表明降维有利于提高正确性.该方法对于昂贵MO问题, 虽然在构造属性趋势模型时增加了昂贵函数额外的计算成本, 但当计算完成后, 则不再需要对原昂贵函数进行评估, 很大程度上减少了昂贵函数的评价次数.

5.   结论

昂贵MO问题在采用进化算法求解时需要对耗时复杂的目标函数多次评估, 面临适应值评估难的问题, 研究表明采用最近邻分类方法预测候选解间的Pareto支配性, 可有效克服计算成本问题.但现有的最近邻方法在搜索多目标问题的决策空间时, 存在目标空间中子目标函数不能同时最近邻的问题.本文通过对子目标的决策属性进行分析, 提出基于决策属性趋势模型的空间变换方法, 在决策空间搜索候选解样本的最近邻个体, 预测候选解之间的Pareto支配关系.该代理模型并不要求高精度、易于构造, 使得变换后的决策空间承载了更多的目标空间信息.结合趋势模型空间变换的最近邻方法进行昂贵MO问题的Pareto支配性预测, 避免复杂耗时的目标函数评估.实验结果表明, 该方法显著优于现有的最近邻分类算法和典型代理模型的Pareto支配性预测结果.

对于Pareto支配性预测方法与优化算法的交互, 我们已开展了相关应用研究, 并取得初步效果.进一步工作将探索该方法在蛋白质、基因等实际昂贵多目标优化问题中的应用.