「导语」
稀疏大规模多目标问题是优化领域中较难解决的一类问题，近年来在计算机领域（神经网络架构搜索、特征选择、稀疏信号重构等）和工业界（投资组合优化等)都受到了越来越多的关注。以神经网络架构搜索为例，深度网络的泛化性能和训练准确度往往是两个互相排斥的目标，而提高泛化性能可以借助稀疏网络结构得以实现。又例如投资组合优化，如何在多个股票中选择少数几个有潜力的股票进行投资，也涉及稀疏优化。但是由于问题自身的稀疏特性与大规模多目标问题进行叠加，导致大部分的进化算法无法对该问题进行有效求解。少部分考虑稀疏特性的进化优化算法则希望在稠密种群中找到稀疏解，使得求解算法不够高效准确。
为了高效地解决稀疏大规模多目标优化问题，最近德国比勒菲尔德大学联合西湖大学可信及通用人工智能实验室和南方科技大学在计算智能顶级期刊IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS: SYSTEMS上发表题为‘Sparse Large-Scale Multiobjective Optimization by Identifying Nonzero Decision Variables’的文章。该研究一反在稠密种群中寻找稀疏变量和稀疏解的思路，而从全零种群中逐步进化出存在非零变量的稀疏解，使算法能够更高效准确的逼近帕累托前沿。让我们一起来了解一下吧！
原文链接：
https://ieeexplore.ieee.org/document/10605095
代码链接：
https://github.com/XWang1216/MOEA-NZD
近年来，稀疏大规模多目标优化问题（SLMOP）引起了越来越多的关注。与传统的大规模多目标优化问题相比，SLMOP具有一个额外的特性，即它们的帕累托最优解包含相对较少的非零决策变量。然而，如何区分非零决策变量和零决策变量仍然极具挑战。对于许多计算机和工业界的问题，例如，深度神经网络训练[1]、稀疏信号重构(SR)[2]、投资组合优化(PO)[3]和特征选择[4]，特别是大规模问题，寻求稀疏解通常很有价值。以深度神经网络训练为例，稀疏解，即稀疏连接的深度神经网络更不可能过拟合训练数据。因为有文献证明[5]，采用轻量/稀疏的网络结构可以有效对抗过拟合，提高网络的泛化能力。然而，这可能导致预测精度降低。因此，有效地解决SLMOP具有重要的实际意义。遗憾的是，因为没有充分考虑帕累托最优解中的稀疏特性，现有的多目标进化算法(MOEA)尚未令人满意地解决SLMOP。
根据其编码策略，现有的针对解决SLMOP的MOEA可分为两大类：基于两层编码和基于实值编码的方案。基于实值的算法采用与大多数解决实值问题的MOEA似的编码策略。例如，S-ECSO [6]应用强凸稀疏算子来增强解的稀疏性。ST-CCPSO[7]使用累积梯度作为设置零标准来获得稀疏最优解。相比之下，两层编码机制采用两种类型的变量，dec和mask。实值向量dec优化解，而二进制向量mask标识其稀疏位置。鉴于其具有较强的可解释性，许多算法（如SparseEA[8]、PM-MOEA[9]、MOEA/PSL[10]和SLMEA[11]）都在该编码的基础上提出有效的稀疏策略来实现解决方案的稀疏性。
最近，我们发现现有的稀疏大规模多目标进化算法主要侧重于在相对稠密的群体中识别零决策变量，而没有强调优化非零决策变量的重要性。然而，通过仔细研究，我们发现稀疏问题中的零决策变量和非零决策变量之间存在相互影响的关系，即一旦非零决策变量被识别并达到全局最优，其余决策变量均为零决策变量（因为其最优值一定为零）。而在稀疏种群中找到较少的非零变量比在稠密种群中寻找较多的非零变量要简单快速。
因此，考虑到零决策变量和非零决策变量的相互影响关系，一个自然的想法是将所有决策变量设置为零初始化，然后关注非零决策变量。这使得非零决策变量的检测和零与非零决策变量的分离更加有效，因为只需要从高维的零变量中检测出小部分的非零变量。因此，我们引入了一个解决SLMOP的非零检测两阶段优化框架，称为MOEA-NZD。这与现有的稀疏MOEA有很大不同：本方法的第一阶段专注于识别非零决策变量（从全零初始化的种群中），而第二阶段采用不同的策略分别优化非零和零变量。此外，提出了一种针对稀疏问题的聚类方法（ClusteringS）来指导在进化过程的两个阶段中寻找零和非零决策变量。
本章节首先介绍了算法的整体框架，再介绍一个稀疏聚类方法，最后介绍两阶段的优化方法。
图1 整体框架
MOEA-NZD的整体框架如图1所示，包括两个优化阶段。在阶段I中，间歇使用聚类方法ClusteringS来识别非零变量。然后将识别为非零变量的决策变量在定义域和上下分位数之间进行重新初始化，以加速搜索过程。在此阶段，MOEA-NZD通过重新初始化特定的决策变量来高效探索缩小的搜索空间。由于只有选定的决策变量才会重新初始化以进行广泛的探索，该方法能够提高探索效率且节省计算资源。在第二阶段，再次间歇使用ClusteringS来区分零和非零决策变量。此阶段依旧集中于较小的搜索空间，仅优化被ClusteringS定为非零决策变量的变量并将其他变量设置为零。
在本节中，我们介绍一种针对稀疏优化而设计的聚类方法，称为 ClusteringS。它在MOEA-NZD的两阶段中都用于区分零和非零决策变量。在ClusteringS中，所有决策变量都具有两个特征，即非零率（种群中同一维度变量的非零比例）和非零度（种群中同一维度变量的非零变量的中位数）。
具体来说，非零率计算如下：
其中j=1,2,...,D，||Xj||_0表示解矩阵X第j列中非零元素的数量, N为种群规模。决策变量的非零率越高，表示该变量非零的可能性越大。
为了计算非零度，首先计算第j个决策变量不等于零的解中的上四分位数q^j_75、中位数q^j_50和下四分位数q^j_25。然后，可以通过以下方式确定第j个决策变量的非零度：
其中，ub^j和lb^j分别表示第j个决策变量的上限和下限。根据四分位数的定义，以下不等式：
始终成立。因此d^j∈(0,1)。为了扩大零点附近的值之间的差异，我们将d^j投影到上，得到最终的d^j。非零度从统计上表示决策变量由于环境选择的压力而偏离零的程度，值越大表示决策变量非零的概率越大。
获得每个决策变量的两个特征后，使用ClusteringS对变量进行分类。ClusteringS的具体流程与kmeans相似，但是初始点的选择方式不同。在ClusteringS中，四个聚类的初始点是两个特征的最大值和最小值的成对组合，即二维特征空间中的四个角。在聚类过程中，即使某些聚类不包含任何样本，也始终保留该聚类的初始分配的点作为聚类中心。在实际应用过程中，由于随着进化过程的进行，非零率低且非零度高的聚类可能会消失。
图2 kmeans和ClusteringS的聚类结果
在图2中，k-means和ClusteringS分别找到了四个聚类。我们可以看到，k-means识别的聚类大多位于较低的非零度范围内。然而，我们的目的是找到四个具有不同含义的聚类：1）高非零率和高非零度；2）高非零率和非零度；3）低非零率和高非零度；4）低非零率和非零度。
图3 ClusteringS在第一阶段和第二阶段的应用
在第一阶段，只有具有较高非零率和较高非零度的决策变量才会被选为非零变量，如图3(a)所示。在第二阶段，两个非零度值较低的聚类中的变量被设置为0。另一方面，另外两个具有更高度值的聚类被视为非零变量，需要以高突变率进行优化，如图 3（b）所示。
MOEA-NZD与其他MOEA的不同之处在于，在种群初始化时将所有决策变量设置为零。为了加快收敛速度，提出了ACT，它包括激活非零变量和生成子代两个部分。激活非零变量部分负责识别和重新初始化非零决策变量，并非在每次迭代中执行。另一方面，每次迭代过程中都使用传统的NSGA-II算法来生成子代。
在激活非零变量过程中，若该非零决策变量的中位数大于零，则在中对变量进行重新初始化；若该非零决策变量的中位数小于零，则在
对变量进行重新初始化。
*关于特殊情况的讨论可见原文，在此处不进行赘述。
进化过程的第二阶段旨在对零决策变量和非零决策变量进行精细搜索。为了满足这一要求，我们提出了DSO策略。在使用聚类算法的迭代步数时，将ClusertingS中聚类为零变量的设置为零；而在其余的迭代中，使用更高的变异率优化非零决策变量。
具体而言，在多项式变异中，将变异概率由原来的proM/D增加为proM/d，其中d表示由聚类算法找到的非零变量的个数，D时问题维度。
本节首先介绍实验设置。然后，在基准问题和实际应用中将MOEA-NZD与五种最先进的稀疏MOEA进行比较。接下来，我们对比MOEA-NZD与稀疏MOEA和非稀疏MOEA在稀疏和非稀疏多目标优化问题上的性能。最后，进行消融实验和计算效率分析。
基准问题：采用SMOP基准测试函数。SMOP由八个稀疏多目标问题组成。在本研究中，目标数量设置为两个或三个，决策变量数量范围为1000至5000。测试套件包含一个参数θ，它可以改变全局最优的稀疏性。我们遵循先前研究中的设置，并将θ设置为0.1。最大适应度评估次数设置为150 × D。所有结果均在30次独立运行中取平均值，所有表格中以灰色突出显示所比较算法中的最佳平均结果。所有实验均采用Wilcoxon秩和检验，显著性水平为0.05。
性能指标：IGD用于评估MOEA获得的解的收敛性和多样性。IGD测量真实帕累托前沿(PF)中的参考点与近似PF中的解之间的平均距离。因此，IGD值较小的MOEA被认为表现更好。对于实际问题，使用HV来评估解决方案的性能。HV计算由获得的非支配解和参考点形成的超立方体的体积。HV值越大，解决方案质量越好。
表1：MOEA-NZD与其他算法在三目标SMOP上的IGD结果
表1列出了在1000、3000和5000个决策变量的三目标SMOP 上获得的IGD值。结果表明，由于本文提出的ACT和DSO， MOEA-NZD在大多数测试实例上的表现优于大多数同类算法。然而，PM-MOEA在SMOP5上表现出与所提出方法相当的性能，并在SMOP6上表现优于所提出的方法。SMOP5和 SMOP6的景观函数使其帕累托集与其他函数不同。也就是说，对于Pareto最优集中x_M,...,x_D的任意θ(D − M + 1)决策变量，在SMOP5和SMOP6上均为π/3，而其余变量在SMOP5上为0，在SMOP6上为0或π/3，这使得优化算法很难找到零和非零决策变量。PM-MOEA则可以利用其模式挖掘策略发现变量的更多可能性，从而使其更有能力解决此类问题。
图4 IGD收敛速度
图4显示了ST-CCPSO、MOEA/PSL、PM-MOEA、SLMEA、S-NSGA-II和MOEA-NZD在三目标SMOP2、SMOP7和SMOP8上获得的IGD收敛曲线。结果表明，MOEA-NZD能够快速收敛，其IGD值在进化过程开始时急剧下降，并且一直是所有算法中最小的。
图5 两目标前沿面可视图
图5绘制了MOEA-NZD及其同类算法得到的解集。MOEA-NZD得到的解占据了其余解的主导地位，并且均匀分布在近似PF中。这表明MOEA-NZD能够获得高质量的解，并有效地平衡了收敛性和多样性。
我们使用MOEA-NZD和其他对比算法解决稀疏信号重构（SR）和投资组合优化(PO)问题，以证明所提出的算法的工业应用前景和表现。
对于稀疏信号重构问题，目标是在最大化信号稀疏性的同时实现较低的损失，其定义为
投资组合优化的目标是更高的回报和更低的风险，第i个解决方案x的适应度函数可以计算为
表2提供了所用数据集的详细信息，包括其名称、决策变量的数量和其他相关数据。
如表III所示，MOEA/PSL和PM-MOEA在SR问题上的表现与MOEA-NZD相似。此外，S-NSGA-II在PO上的表现与MOEA-NZD相当。然而，在大多数情况下，MOEA-NZD在这两个应用问题上的表现始终良好，证实了它在解决这些实际应用方面的有效性。
在本节中，通过测试MOEA-NZD在具有不同稀疏度的稀疏问题和非稀疏问题上的性能，对其进行了进一步分析。此评估涉及与非稀疏和稀疏 MOEA 的比较。
图6 MOEA-NZD与对比算法在不同稀疏度问题上的对比
在图6（a）中，四个子图展示了MOEA-NZD及其稀疏算法ST-CCPSO、MOEA/PSL、PM-MOEA、SLMEA和S-NSGA-II的性能。左边的三个子图展示了当稀疏度降低（即SMOP的超参数θ增加）时，在SMOP3、SMOP5和SMOP8上的性能变化。具体而言，当给定问题的稀疏度降低时，所有算法的IGD值都会增加，这表明所有稀疏MOEA的性能都会下降。然而，在大多数情况下，所提出的方法MOEA-NZD在不同θ值下的表现最佳。另一方面，图6（a）中的右侧子图展示了稀疏MOEA在稠密问题DTLZ1和DTLZ3上的性能，其中MOEA-NZD表现最佳。
图6（b）显示了MOEA-NZD与三个非稀疏MOEA（MOEA/D、SMS-EMOA和NSGA-III）的比较结果。这些结果表明，所提出的方法MOEA-NZD在具有不同θ值的稀疏问题上表现最佳，即使当问题不太稀疏时，非稀疏MOEA的IGD值会急剧下降。在密集问题DTLZ1和DTLZ3上，MOEA-NZD的表现优于或与所比较的非稀疏MOEA相当。即使MOEA-NZD用全零值初始化种群，所提出的方法MOEA-NZD在解决非稀疏问题时的表现与其基准算法NSGA-III非常相似。这是因为所有决策变量都可以被检测为非零决策变量，因此，MOEA-NZD在进化过程中简化为NSGA-III。
综上所述，与稀疏MOEA和非稀疏MOEA相比，MOEA-NZD在大多数稀疏问题上的表现最佳，表明所提出的策略对不同稀疏程度的稀疏问题均能发挥良好作用。此外，MOEA-NZD在非稀疏问题上的表现与非稀疏MOEA相当甚至更好，表明所提出的策略有利于解决稀疏问题，并且不会对其在解决非稀疏问题上的性能产生负面影响。
在本节中，通过测试 MOEA-NZD 在具有不同稀疏度的稀疏问题和非稀疏问题上的性能，对其进行了进一步分析。此评估涉及与非稀疏和稀疏 MOEA 的比较。
图7 消融实验
我们对所提出的MOEA-NZD进行了消融研究，以评估其提出的两种策略的有效性。我们在1000个决策变量的SMOP2和 SMOP7上比较了MOEA-NZD及其变体MOEA-NZD1、MOEA-NZD2和MOEA-NZD3。变体MOEA-NZD1使用 NSGA-III中的基本子代生成算子，且使用全零变量进行初始化；MOEA-NZD2使用ACT而没有DSO，而MOEA-NZD3使用 DSO而没有ACT。
图7显示了MOEA-NZD及其变体获得的IGD值的收敛曲线。可以看出，MOEA-NZD在两个阶段的收敛速度是所有变体中最快的。具体而言，ACT加快了收敛速度并提高了早期搜索阶段的搜索效率，而DSO在后期阶段利用了更好的解决方案。另外，MOEA-NZD1的表现最差，这表明仅用零值向量初始化种群不能产生良好的性能。相反，基于全零向量初始化的两种策略有助于提高所提方法的性能。总体而言，所提出的两阶段框架展示了探索和开发之间的良好平衡。
图8 稀疏MOEA所消耗的计算时间
图8显示了稀疏MOEA所消耗的计算时间，展示了1000维双目标SMOP2和SMOP5。可以看到，MOEA/PSL和PM-MOEA在一次运行中消耗的时间更多，S-NSGA-II和MOEA-NZD在所有算法中运行速度相对较快。与其原始子代生成策略相比MOEA-NZD中提出的ACT和DSO引入的额外计算复杂度非常低。此外，对ClusteringS的调用不会显著增加所提出方法的计算复杂度。
本文从另一个优化角度出发，即在稀疏优化中强调非零变量，介绍了一种用于解决稀疏大规模多目标问题的新算法MOEA-NZD。该方法利用全零值初始化和聚类方法，引导两阶段的搜索过程。在第一阶段，通过重新初始化非零决策变量来加快收敛速度。第二阶段使用特定优化方法分别处理零决策变量和零决策变量。我们的实证结果证实，MOEA-NZD在基准和实际应用问题上都表现良好。对MOEA-NZD的深入分析表明，它在具有不同稀疏率的稀疏问题上均有较好表现。即使与非稀疏MOEA在非稀疏问题上比较，MOEA-NZD也表现出有竞争力的性能。
参考文献：
[1] J. Wang, Q. Chang, Q. Chang, Y. Liu, and N. R. Pal, “Weight noise injection-based MLPs with group lasso penalty: Asymptotic convergence and application to node pruning,” IEEE Trans. Cybern., vol. 49, no. 12, pp. 4346–4364, Dec. 2019.
[2] H. Li, Q. Zhang, J. Deng, and Z.-B. Xu, “A preference-based multiobjective evolutionary approach for sparse optimization,” IEEE Trans. Neural Netw. Learn. Syst., vol. 29, no. 5, pp. 1716–1731, May 2018.
[3] J. A. Rangel-González et al., “Fuzzy multi-objective particle swarm optimization solving the three-objective portfolio optimization problem,” Int. J. Fuzzy Syst., vol. 22, no. 8, pp. 2760–2768, 2020.
[4] D. Wu, Y. He, X. Luo, and M. Zhou, “A latent factor analysisbased approach to online sparse streaming feature selection,” IEEE Trans. Syst., Man, Cybern., Syst., vol. 52, no. 11, pp. 6744–6758, Nov. 2022.
[5] D. Yao, H. Liu, J. Yang, and X. Li, “A lightweight neural network with strong robustness for bearing fault diagnosis,” Measurement, vol. 159, Jul. 2020, Art. no. 107756.
[6] X. Wang, K. Zhang, J. Wang, and Y. Jin, “An enhanced competitive swarm optimizer with strongly convex sparse operator for large-scale multiobjective optimization,” IEEE Trans. Evol. Comput., vol. 26, no. 5, pp. 859–871, Oct. 2022.
[7] X. Wang, B. Zhang, J. Wang, K. Zhang, and Y. Jin, “A cluster-based competitive particle swarm optimizer with a sparse truncation operator for multi-objective optimization,” Swarm Evol. Comput., vol. 71, Jun. 2022, Art. no. 101083.
[8] Y. Tian, X. Zhang, C. Wang, and Y. Jin, “An evolutionary algorithm for large-scale sparse multiobjective optimization problems,” IEEE Trans. Evol. Comput., vol. 24, no. 2, pp. 380–393, Apr. 2020.
[9] Y. Tian, C. Lu, X. Zhang, F. Cheng, and Y. Jin, “A pattern mining-based evolutionary algorithm for large-scale sparse multiobjective optimization problems,” IEEE Trans. Cybern., vol. 52, no. 7, pp. 6784–6797, Jul. 2022.
[10] Y. Tian, C. Lu, X. Zhang, K. C. Tan, and Y. Jin, “Solving large-scale multiobjective optimization problems with sparse optimal solutions via unsupervised neural networks,” IEEE Trans. Cybern., vol. 51, no. 6, pp. 3115–3128, Jun. 2021.
[11] Y. Tian, Y. Feng, X. Zhang, and C. Sun, “A fast clustering based evolutionary algorithm for super-large-scale sparse multi-objective optimization,” IEEE/CAA J. Automatica Sinica, vol. 10, no. 4, pp. 1048–1063, Apr. 2023.
END
初稿：王翔宇
复审：刘奇奇
终审：金耀初
