1.   引言

自然计算(natural computation)是智能算法中的一个术语，它包含3种方法：(1)从自然种群进化中汲取灵感，从而发现新的问题解决方法；(2)基于利用计算机分析自然现象的方法；(3)利用自然材料(例如分子)进行计算的方法。构成这3个分支的主要研究领域是人工神经网络、进化算法、群体智能、人工免疫系统、分形几何、人造生命、DNA计算和量子计算等^[1]。自然计算方法对实际生产生活具有重要的意义，例如基于遗传算法的相位差异技术图像恢复^[2]，基于蚁群算法的运动时间优化算法研究^[3]，以及基于遗传算法的文本情感分类中的应用^[4]等。

虽然各种自然计算方法模拟的生物机理有所差距，但是它们都是基于种群的优化算法^[5]。在这些方法中，个体维数对算法的全局搜索能力和计算成本有较大的影响^[6]。降维是处理多维数据的重要因素^[7]。较高的维数能够描述个体更多的属性，从而使个体在寻优过程中能够避免陷入局部最优，但是却降低了寻优精度；而个体维数过低又会导致个体属性多样性降低，全局搜索能力不足，易陷入局部最优，但是寻优精度却能提高。因此，如何通过更好的降低维数^[8,9]来平衡算法的全局寻优能力和收敛精度，成为自然计算方法的瓶颈问题。

针对该问题，已经出现了很多有关优化个体维数的方法。Xu等人^[10]提出了维度学习策略，并使用16个经典测试函数，30个CEC2014测试函数和1个实际优化问题来测试所提出的算法的有效性。Wei等人^[11]提出了一种具有维数突变的动态粒子群算法，该算法为了避免陷入局部最优，设计了一下维数变异算子，从突变开始计算各维度的收敛度，最小收敛度的维数根据一定的概率进行变异。纪震等人^[12]在2010年提出了智能单粒子优化算法，即粒子的位置矢量被分成了多个子矢量，从而实现降维。拓守恒等人^[13]提出了一种基于膜计算的优化算法，该算法将高维空间利用数学模型分割成多个子空间，每个子空间作为一个基本膜，基本膜负责搜索局部最优解，表层膜负责搜索全局最优解。文献[14]在分析标准粗糙集理论局限性的基础上，提出了一种基于二进制粒子群优化(Binary Particle Swarm Optimization, BPSO)和概率粗糙集理论的降维方法。2012年拓守恒^[15]针对高维非线性优化存在的收敛速度慢和求解精度低的问题，提出了改进的人工蜂群优化算法，该算法采用了高斯分布和自适应差分算法对高维进行操作，很好地解决了收敛速度和求解精度。一种随机约减粒子群维数的方法由Jin等人^[16]提出，并证明了随机的重要性。梁静等人^[17]提出了协同进化动态粒子群优化算法，该算法可用来求解大规模问题，简单来说就是将高维问题随机重组为低维问题，并对1000维的例子进行测试，实验取得了较好的结果。Yang等人^[18]提出了一种基于粒子群优化算法(Particle Swarm Optimization, PSO)的多因素降维(Multifactor Dimensionality Reduction, MDR)方法，简称PBMDR, PBMDR用于检测多位点之间的相互作用，并在模拟疾病模型中证实了该算法的准确度和高效性。这些方法在一定程度上平衡了算法的收敛精度和全局最优问题，但是，个体的维数都是基于某种自然计算方法而设计的，并且实现过程要依赖该算法具体的操作步骤，不具有普适性。

为了解决这个问题，本文受文献[19,20]的启发，提出一种具有普遍意义的降低个体维数的策略。本策略不依赖算法的具体操作，因而适用于所有基于种群优化的自然计算方法。其创新点有：(1)利用最大线性无关组降低了个体维数；(2)为了更加精准地描述个体特征属性，设计了属性因子。并且，将该策略应用到两种不同的自然计算方法中，采用12个经典的高维测试函数，并与目前主流维数优化算法进行对比，用以验证文中所提基于非线性降维的自然计算方法(natural computing method for Nonlinear Dimension Reduction, NDR)的普适性和有效性。

2.   非线性降维的自然计算方法

大部分随机算法随着维数的增加而使性能变差。因此，找到一种合适的方法将维数降低就显得尤为重要。本文用到的降维方法是利用最大线性无关的思想^[21]。例如，向量a=[2, 3, 5, 6, 1], b=[7, 5, 4, 1, 2], c=[2, 3, 5, 6, 1], e=[2, 1, 5, –2, 6]，若将这4个向量比作4个个体，那么将组成一个规模为4、维数为5的群体，即向量组D，如式(1)所示，那么所求阶梯矩阵$d$如式(2)所示，则列向量的最大线性无关组为每行首个非0元素所在列数，即第1列、第2列和第3列，剩余的列可由最大线性无关组表示，如式(3)所示，这样便减少了信息冗余。

其中，${k_1},\,{k_2},\,{k_3}$代表系数，${{{x}}_i} = \left( {{x_{i,1}},\,{x_{i,2}},\, ··· ,\,{x_{i,j}}} \right)$, ${x_{i,j}}$代表第$i$个个体的第$j$维。因为最大线性无关组可任意表示其他组，所以，所求极小值也一定可以被最大线性无关组式(3)表示。

本文所提NDR就是在高维的情况下，通过计算各维的最大线性无关组从而降低维数。假设有$N$个个体，每个个体有$D$维，则可表示成式(4)所示，通过对式(4)的列向量求最大线性无关组可得式(5)，其中$m \in [1, 2, ···, D]$, $n \in [1, 2, ···, D]$, $q \in$$[1, 2, ···, D]$，且根据最先线性无关组的性质，式(5)的维数最大是$N$，相比式(4)，维数远远降低。

维数的高低决定了个体属性描述的精确程度^[22]。通过本文所提降维操作之后，描述个体的属性参数减少。但是，为了保证个体属性的完整性和多样性，在${A1}$中加入随机系数${r_i}$，如式(6)所示，便可将除最大线性无关组之外的维数表示出来。事实上，高维空间能够尽可能完整地描述个体的特征属性，但是，在有限的空间内永远无法精确地将个体的特征属性表达出来。然而，随机系数却可以解决这一问题，因为，最大线性无关组可以将矩阵中的任何一个向量线性表示，因此，加入随机系数的最大线性无关组能够用形式化语言将个体的特征属性描述。即式(7)所示，其中$j \notin (m,n,h,q)$ 。

从以上叙述可以看出降维的可行性，NDR的伪代码如表1所示($N$为种群规模，$G$为终止进化的代数，$T$为测试的次数)。

表 1  非线性降维的自然计算方法(NDR)

种群规模为N，终止进化代数为G，测试次数为T
(1) 初始化N, G, T 等参数，随机产生第1代种群$\bf{pop}$；
(2) 将生成的种群$\bf{pop}$做线性变换，求得列向量的最大线性无关 　　 组，即为新的种群$\bf{newpop}$；
(3) 对新种群$\bf{newpop}$的各维乘以随机系数${r_i}$，更新$\bf{newpop}$；
(4) 将得到的$\bf{newpop}$使用基于种群的自然计算方法进化；
(5) 结束。

下载: 导出CSV 

| 显示表格

3.   实验结果

实验仿真平台为Window7, Matlab2014b。本实验把NDR策略分别应用到标准遗传算法(Genetic Algorithm, GA)^[23]和标准粒子群算法(Particle Swarm Optimization, PSO)^[24]中，得到NDRGA算法和NDRPSO算法，并与标准遗传算法、标准粒子群算法和4个维数优化算法做对比实验。

近年来，优化高维函数已经成为优化算法领域的研究热点。本实验采用国际通用的12个标准高维测试函数：${F_1}$～${F_{12}}$(如表2所示)。${F_1}$～${F_3}$, ${F_9}$, ${F_{11}}$, ${F_{12}}$是高维单峰函数，仅有一个全局最优点；${F_4}$～${F_8}$是高维多峰函数，这些测试函数具有许多局部最优点，是优化界中较难优化的函数。这些测试函数的全局最优值为0, ${F_{10}}$的维数不能少于4维，且全局最小值和维数有关。由于部分测试函数有多个最优点，因此，在寻优过程中极易陷入局部最优。

表 2  标准测试函数

测试函数	维数	可行解空间
${F_1} = \displaystyle\sum\nolimits_{i = 1}^D { {x_i}^2}$	1000	[–100, 100]n
${F_2} = {\left( { {x_1} - 1} \right)^2} + {\displaystyle\sum\nolimits_{i = 1}^D {i\cdot \left( {2{x_i}^2 - {x_{i - 1} } } \right)} ^2}$	1000	[–10, 10]n
${F_3} = \displaystyle\sum\nolimits_{i = 1}^D { { {\left| { {x_i} } \right|}^{i + 1} } }$	1000	[–1, 1]n
$\begin{array}{l}{F_4} = - a\cdot\exp \left( { - b\sqrt {\dfrac{1}{D}\displaystyle\sum\nolimits_{i = 1}^D { {x_i}^2} } } \right) - \exp \left( {\dfrac{1}{D}\displaystyle\sum\nolimits_{i = 1}^D {\cos \left( {c{x_i} } \right)} } \right) + a + \exp \left( 1 \right), a = 20,b = 0.2,c = 2\pi \end{array}$	1000	[–32.768, 32.768]n
${F_5} = \displaystyle\sum\nolimits_{i = 1}^D {({x_i}^2 - 10 \cos (2 \pi {x_i})} + 10)$	1000	[–5.12, 5.12]n
${F_6} = \displaystyle\sum\limits_{i = 1}^D {\frac{ { {x_i}^2} }{ {4000} } - \prod\limits_{i = 1}^D {\cos \left( {\frac{ { {x_i} } }{ {\sqrt i } } } \right)} } + 1$	1000	[–600,600]n
$\begin{array}{l}{F_7} = {\sin ^2}\left( {\pi {\omega _1} } \right) + {\displaystyle\sum\nolimits_{i = 1}^{D - 1} {\left( { {\omega _i} - 1} \right)} ^2}\left[ {1 + 10{ {\sin }^2}\left( {\pi {\omega _i} + 1} \right)} \right]\\ \quad\ \ + {\left( { {\omega _D} - 1} \right)^2}\left[ {1 + { {\sin }^2}\left( {2\pi {\omega _D} } \right)} \right]{\omega _i} = 1 + \dfrac{ { {\omega _i} - 1} }{4}\end{array}$	1000	[–10, 10]n
${F_8} = 418.9829D - \displaystyle\sum\nolimits_{i = 1}^D { {x_i}\sin \left( {\sqrt {\left| { {x_i} } \right|} } \right)}$	1000	[–500, 500]n
${F_9} = \displaystyle\sum\nolimits_{i = 1}^{D - 1} {\left[ {100{ {\left( { {x_{i + 1} } - x_i^2} \right)}^2} + { {\left( { {x_i} - 1} \right)}^2} } \right]}$	1000	[–5, 10]n
${F_{10} } = \displaystyle\sum\nolimits_{i = 1}^{D/4} {\left[ { { {\left( { {x_{4i - 3} } + 10{x_{4i - 2} } } \right)}^2} + 5{ {\left( { {x_{4i - 1} } - {x_{4i} } } \right)}^2} + { {\left( { {x_{4i - 2} } - 2{x_{4i - 1} } } \right)}^4} + 10{ {\left( { {x_{4i - 3} } - {x_{4i} } } \right)}^4} } \right]}$	1000	[–4, 5]n
${F_{11} }{\rm{ = } }\displaystyle\sum\nolimits_{i = 1}^D {ix_i^2}$	1000	[–10, 10]n
${F_{12} } = \displaystyle\sum\nolimits_{i = 1}^D {x_i^2 + { {\left( {\displaystyle\sum\nolimits_{i = 1}^D {0.5i{x_i} } } \right)}^2} + { {\left( {\displaystyle\sum\nolimits_{i = 1}^D {0.5i{x_i} } } \right)}^4} }$	1000	[–5, 10]n

下载: 导出CSV 

| 显示表格

3.1   NDR策略与标准算法的实验结果分析

在实验中，适应值函数$f()$的值为当前位置对应的函数值。GA算法和NDRGA算法的参数设置为：交叉概率${P_{\rm{c}}}{\rm{ = }}0.70$，变异概率${P_{\rm{m}}}{\rm{ = }}0.05$，进化迭代次数$G = 1000$，种群$N = 50$，维数$D = 1000$。PSO算法和NDRPSO算法的参数设置为：学习因子${c_1} = {c_2} = 2$，惯性权重${\omega _{\max }} = 0.9$, ${\omega _{\min }} = 0.4$，进化迭代次数$G = 1000$，种群$N = 50$，维数$D = 1000$。对于越界粒子本文采用通用的越界处理办法，将其重新设置为边界值，如表3所示。

表 3  各算法对12个标准测试函数进行优化结果

函数	平均结果及标准方差
	PSO	NDRPSO	GA	NDRGA
F1	4.92e+05±5.09e+04	345.2211±96.7891	1.78e+05±6.12e+03	12.7059±3.2681
F2	1.18e+08±2.47e+07	301.8188±114.0539	3.65e+07±1.85e+06	3.8379±2.8421
F3	6.71e-08±7.10e-08	6.48e-09±8.88e-09	1.11e-07±1.84e-07	3.17e-08±4.51e-08
F4	17.1198±0.5185	7.0752±0.7417	13.2492±0.1323	5.2058±0.5977
F5	9.72e+03±464.6314	115.6225±21.7166	9.68e+03±86.5390	104.5187±18.5246
F6	4.34e+03±366.1741	3.6991±0.7714	1.61e+03±64.0915	1.4019±0.1196
F7	1.66e+04±1.45e+03	13.0269±5.8130	8.62e+03±366.1671	0.4960±0.1577
F8	3.47e+05±7.50e+03	9.58e+03±866.1230	3.70e+05±2.42e+03	9.92e+03±619.0421
F9	9.20e+06±2.18e+06	694.6303±588.9850	3.48e+06±2.40e+05	103.1690±45.9190
F10	1.16e+05±1.50e+04	14.2205±5.1053	2.48e+04±1.50e+03	0.3623±0.2182
F11	2.82e+06±2.62e+05	80.1161±31.8298	7.96e+05±2.70e+04	2.8521±1.2240
F12	1.31e+04±3.41e+03	53.57±12.84	2.18e+19±3.03e+09	27.9986±12.1954

下载: 导出CSV 

| 显示表格

各算法对12个测试函数分别执行20次，其平均结果及标准方差如表3所示。在优化这12个测试函数时，NDRGA算法和NDRPSO算法较其他标准算法相比都能够接近全局最优，尤其是在测试函数${F_3}$, ${F_6}$, ${F_7}$, ${F_{10}}$和${F_{11}}$上，NDRGA和NDRGA在误差允许的范围内已找到全局最优。与GA和PSO相比，NDRGA和NDRPSO的标准方差远低于其他标准算法，只有在测试函数${F_3}$上标准方差几乎等于标准算法，这是由于${F_3}$函数较其他函数相比形状较为平滑且为单峰函数，更易找到全局最优解。总之，NDRGA算法和NDRPSO算法较低的标准方差，证明应用NDR策略的算法具有更好的稳定性。

图1是12个测试函数${F_1}$～${F_{12}}$的收敛比较图。横轴代表适应度计算次数，纵轴代表平均适应度值。从图1中可以清楚地看到，使用降维策略的算法比未使用的具有更强的全局搜索能力，但在个别测试函数中，NDRPSO和NDRGA略有差别。

图 1  各算法对标准测试函数进行优化的收敛曲线

下载: 全尺寸图片 幻灯片

根据收敛曲线走势，NDRPSO在函数${F_1}$～${F_7}$, ${F_9}$中大概进化400次之后曲线保持水平，在函数${F_{10}}$和${F_{11}}$中大概进化500次之后曲线保持水平，不再有下降的趋势，说明此时陷入局部最优，这是由于PSO 算法具有更强的局部搜索能力导致的；而标准PSO 算法在进化100次之后陷入局部最优，说明在应用了降维策略之后确实使算法具有了更强的全局搜索能力。但在函数${F_8}$中，NDRPSO虽然比PSO的全局搜索能力强，但并没有特别明显，这是由于测试函数本身的性质导致的，${F_8}$是一个功能复杂且有许多局部极小值，图2是${F_8}$的2维图像表示，从图2中可以看出此函数具有极多的局部最优值，导致算法极易早熟。

图 2  ${F_8}$的2维图像

下载: 全尺寸图片 幻灯片

而NDRGA算法几乎在每个测试函数中进化1000次之后仍具有继续下降的趋势，说明算法没有被局部最优值所牵绊，但是GA算法大概在进化100次之后陷入局部最优，这也更好地证明了改进后的算法具有更强的全局搜索能力。但在测试函数${F_3}$中NDRGA和GA曲线几乎重合，此现象已通过表2有所表现，这与${F_3}$的曲线平滑度有关，使算法极易找到全局最优解。

同时，在时间复杂性上如图3和图4所示。从图3可以直观的看出，除测试函数${F_1}$和${F_5}$外，在其他测试函数中，NDRPSO的仿真所需时间均少于PSO，说明在降维之后不仅提高了算法的精度，同时还提高了算法的运行速度。但是在测试函数${F_1}$和${F_5}$中却没有提高运行速度，这是由于函数自身的复杂度远低于其他10个函数，因此，在降维之后运行速度几乎没有提高。图4清晰地展示出GA和NDRGA的仿真时间对比结果，不难看出NDRGA的运行速度远高于GA。通过图3和图4，表3所显示的对比结果，更加有效地证明了改进算法的运行性能。

图 3  PSO和NDRPSO仿真时间对比

下载: 全尺寸图片 幻灯片

图 4  GA和NDRGA仿真时间对比

下载: 全尺寸图片 幻灯片

3.2   NDRPSO与其他应用维数策略算法的实验分析结果

协同进化动态粒子群优化算法(Dynamic Multi-Swarm -Cooperative Coevolution, DMS-CC)^[17]、社会学习粒子群优化算法(Social Learning Particle Swarm Optimization, SLPSO)^[25]、动态多种群粒子群优化算法(Dynamic Multi-Swarm Particle Swarm Optimizer, DMS-PSO)^[26]以及竞争学习算法(Competiti- ve Swarm Optimizer, CSO)^[27]，均为针对求解大规模高维复杂问题而提出的算法。将本文所提非线性降维算法与文献[17,25-27]中的算法对比，为了与文献中测试保持一致，因此，采用${F_1}$, ${F_3}$～${F_6}$和${F_8}$这6个测试函数，其中“–”表示文献中没有此函数数据，结果如表4所示。从表4中可以直观地看到，NDRPSO在${F_3}$, ${F_4}$, ${F_5}$, ${F_6}$和${F_8}$这5个测试函数中的寻优结果优于其他4个算法。在搜索前期，NDRPSO将最大线性无关组保留下来，同时加入随机系数，这样便使得种群在不丧失多样性的前提下降低了维数，避免了种群陷入局部最优。而其他4个算法没有改变种群的维数，只是针对大规模种群做的改进，其种群内部的冗余信息极易使搜索陷入局部最优。但是，NDRPSO在测试函数${F_1}$中取得的结果不是很理想，该测试函数的变量之间相关性较小，即函数变量本身之间的冗余信息较少，因此，在相同条件下收敛能力强的算法结果更优。

表 4  各算法的实验对比结果

		${F_1}$	${F_3}$	${F_4}$	${F_5}$	${F_6}$	${F_8}$
DMS-CC	best	13.2	5.88e+05	1.60e+14	2.30e+06	2.20e+04	2.00e+11
SLPSO	best	4.78e-14	3.82e+06	1.90e+14	5.15e+09	9.42e+06	–
DMS-PSO	best	1.66e+01	1.14e+08	4.36e+07	1.68e+09	9.23e+04	4.51e+10
CSO	best	2.43e-09	3.71e+06	4.61e+14	3.25e+09	9.68e+06	2.13e+11
NDRPSO	best	6.54	1.11e-08	2.89	12.91	0.88	2.02e+03

下载: 导出CSV 

| 显示表格

4.   结束语

本文在标准算法的基础上，针对高维测试函数很难寻找最优解的问题，利用最大线性无关组，提出了非线性降维的自然计算方法，并给出了具体的降维操作步骤。为了保证种群的多样性，本算法对种群增加了随机系数。通过12个测试函数证明，应用该策略的算法与没有应用该策略的算法相比具有更快的收敛速度和更好的求解精度。但是，本策略的不足之处在于最大线性无关组的系数是随机生成的，而没有准确的函数表达式，在后续研究中，将对最大线性无关组的系数进行探讨，从而更好地增加种群多样性，以便能够快速跳出局部最优。