arXiv:2504.17799cs.NEcs.AI2025-04

通过引入子函数结构信息,改进了优化问题的局部最优网络分析。

Subfunction Structure Matters: A New Perspective on Local Optima Networks

  • 基于变量交互信息构建更精准的局部最优网络
  • 新方法揭示了传统黑箱方法忽略的优化动态细节
  • 适合研究可分解优化问题的算法设计者

局部最优网络(LON)用于刻画优化问题的适应度景观。现有方法通常以黑箱方式构建LON,未利用问题本身的结构信息,分析时也忽视变量间相互作用等先验知识。本文提出新思路:将子函数结构信息融入LON构建与分析过程,该信息可预先已知或在搜索中学习获得。针对多个基准伪布尔问题,采用三种方法构建LON:标准算法、确定性灰箱交叉算法,以及基于变量交互学习信息选择扰动的算法。提出衡量子函数变化的新指标,并与文献中其他LON指标对比。结果表明,融合问题结构信息的LON能提供更丰富的优化动态洞察,对理解现代关联学习优化器求解难度至关重要。建议将问题结构纳入景观分析范式,尤其适用于具有已知或疑似子函数结构的问题。

原文摘要 · Abstract (English)

Local optima networks (LONs) capture fitness landscape information. They are typically constructed in a black-box manner; information about the problem structure is not utilised. This also applies to the analysis of LONs: knowledge about the problem, such as interaction between variables, is not considered. We challenge this status-quo with an alternative approach: we consider how LON analysis can be improved by incorporating subfunction-based information - this can either be known a-priori or learned during search. To this end, LONs are constructed for several benchmark pseudo-boolean problems using three approaches: firstly, the standard algorithm; a second algorithm which uses deterministic grey-box crossover; and a third algorithm which selects perturbations based on learned information about variable interactions. Metrics related to subfunction changes in a LON are proposed and compared with metrics from previous literature which capture other aspects of a LON. Incorporating problem structure in LON construction and analysing it can bring enriched insight into optimisation dynamics. Such information may be crucial to understanding the difficulty of solving a given problem with state-of-the-art linkage learning optimisers. In light of the results, we suggest incorporation of problem structure as an alternative paradigm in landscape analysis for problems with known or suspected subfunction structure.

优化分析局部最优子函数结构

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。