《Swarm and Evolutionary Computation》：An Jaccard similarity coefficient-based evolutionary algorithm for sparse large-scale multi-objective optimization problems
编辑推荐：
本文针对稀疏大规模多目标优化问题(SLMOPs)中传统进化算法面临的挑战，提出了一种基于Jaccard相似系数(JSC)的进化算法(JSCEA)。该算法通过JSC识别优良解中的关键稀疏模式并传递给后代，有效提升了在有限计算资源下的优化效率。在多个基准测试和实际应用中的实验结果表明，JSCEA在高达10,000维变量的问题上表现出竞争优势，为高效解决复杂稀疏优化问题提供了新思路。
在现实世界的许多领域，我们常常需要同时优化多个相互冲突的目标，这类问题被称为多目标优化问题(MOPs)。例如，在云计算中，我们希望同时最小化任务执行时间和成本；在推荐系统中，则希望在有限的展示窗口内为用户推荐最相关的物品。随着问题规模的扩大，决策变量的数量可能达到数百甚至数千个，形成大规模多目标优化问题(LMOPs)。更棘手的是，在许多实际问题中，帕累托最优解中的大部分决策变量实际上为零，这类问题被称为稀疏大规模多目标优化问题(SLMOPs)。
传统多目标进化算法(MOEAs)在处理SLMOPs时面临巨大挑战。随着决策空间维度的增加，算法需要更多的运行时间来探索最优解，同时还会引入更多的局部最优区域，使得算法难以高效导航高维解空间。虽然研究者已经提出了各种稀疏进化算法(SEAs)来应对这些挑战，但大多数现有SEAs主要关注准确识别非零变量位置，而忽略了优化过程中目标函数值的变化。
由国防科技大学系统工程学院的研究团队发表在《Swarm and Evolutionary Computation》上的这项研究，提出了一种创新的Jaccard相似系数进化算法(JSCEA)，专门用于解决SLMOPs。该算法的核心思想是利用Jaccard相似系数来识别有希望解之间的关键稀疏模式，并将这些模式传递给后代，从而加速目标函数值的优化。
JSCEA采用了三项关键技术：基于Jaccard相似系数的优良解选择策略、自适应档案更新机制以及种群更新机制。算法首先使用两层编码策略（二进制Mask层和实值Dec层）表示解，然后通过计算当前种群中非支配解（作为指导解）与候选解之间Mask的Jaccard相似度，筛选出与优良解具有高稀疏相似度的个体存入档案。档案大小随迭代自适应增加，确保充分利用历史知识。最后，通过将档案中个体的稀疏模式传递给种群，并结合交叉变异等进化操作，引导种群向更优的方向进化。
3.1. 基于JSC的优良解选择策略
该策略的核心是识别那些与当前非支配解具有相似稀疏分布的个体。Jaccard相似系数用于度量两个解在二进制Mask向量上的相似度，计算为两个集合的交集大小与并集大小之比。通过计算每个候选解与所有非支配解的总JSC值，算法能够筛选出那些共享关键基因的个体，这些个体更有可能引导种群快速收敛。
3.2. 自适应档案更新
为了解决TELSO等算法可能因样本过小导致的偏差问题，JSCEA引入了自适应档案。档案大小k随迭代次数增加而线性增长，使得在进化后期能够保留更多高质量的解。这种设计确保了在种群质量提升的过程中，档案能够动态地容纳更多有价值的稀疏分布信息。
3.3. 更新种群
在种群更新阶段，JSCEA将档案中个体的Mask模式随机分配给种群中的部分个体，实现稀疏分布知识的迁移。随后，对实值Dec部分进行常规的交叉和变异操作，保证算法的探索能力。这种结合了稀疏模式学习和进化搜索的机制，使JSCEA能够有效平衡收敛速度和种群多样性。
研究团队在八个SMOP基准测试问题和三个实际应用（关键节点检测CN、社区发现CD和特征选择FS）上对JSCEA进行了全面评估。实验设置了1000、5000和10000三种决策变量维度，并将最大函数评估次数设置为维度大小D，以模拟计算资源受限的场景。
4.1. 与SLMOEAs的性能比较
与MSKEA、NUCEA、SparseEA和TELSO等先进算法相比，JSCEA在大多数测试问题上取得了最优的IGD（反向世代距离）和HV（超体积）值。特别是在5000维问题上，JSCEA在所有测试案例中均表现最佳，证明了其在高维决策空间中的优势。平行坐标图显示，JSCEA能够有效维持清晰的稀疏结构，将大多数决策变量正确设置为零，而对比算法产生的解则稀疏性不足。
4.2. 计算资源充足下的性能比较
当最大函数评估次数增加到10*D时，JSCEA在SMOP1、SMOP2、SMOP4、SMOP7和SMOP8问题上表现出更强且更稳定的收敛行为。虽然在SMOP3和SMOP6上初期收敛速度略慢，但随着评估次数增加，JSCEA最终能达到竞争性的性能水平，显示了其良好的全局搜索能力。
4.3. 实际应用上的实验
在三个真实世界问题上的实验进一步验证了JSCEA的实用性。在社区检测、关键节点检测和特征选择任务中，JSCEA在最高维度的场景下均取得了显著优于对比算法的HV值，表明其稀疏分布保持策略在处理大规模实际问题时的有效性。
该研究提出的JSCEA算法为解决稀疏大规模多目标优化问题提供了一种有效的新途径。通过利用Jaccard相似系数来识别和传播关键稀疏模式，JSCEA在有限计算资源下实现了快速高效的优化。实验结果表明，该算法在高达10,000维的基准问题和实际应用中均具有竞争优势。
需要注意的是，JSCEA主要针对具有明显稀疏特性的SLMOPs设计。对于稀疏特性较弱的问题，其优势可能不那么明显。未来的研究方向包括开发自适应稀疏调整机制以扩展其适用性，以及结合分布式和并行学习策略来提升算法在超大规模问题上的可扩展性。这些改进有望将JSCEA应用于更广泛的工业优化任务，如大规模神经网络参数调优等。
