解析进化算法的搜索机制,揭示其几何结构与优化性能的关系。
Linear Proposal Operators and Stochastic Search Geometry in SOMA and Differential Evolution

- 将变异与选择解耦,建立可分析的线性提案算子框架。
- 推导出SOMA和DE在不同条件下的均值、方差、有效维度等精确表达式。
- 指导设计更高效的算法变体,在多个维度下超越经典方法。
群体与进化算法通常被视为整体过程,其中非线性选择、替换和自适应会掩盖候选解生成中的简单结构。本文提出一种算子-选择分解方法,将目标无关的变异与边界修复、基于适应度的选择分离,并用于研究自组织迁移算法(SOMA)和差分进化(DE)的提案几何结构。结果表明,标准SOMA提案在搜索空间中为仿射形式,且在扩展的移民-领导者状态中为严格线性。在相对领导者坐标系下,该算子可直观解释插值、投影、越界及坐标掩蔽行为。在伯努利扰动掩码下,我们推导出提案均值、协方差、期望平方步长、期望与领导者距离、有效维度和坐标覆盖的闭式表达式。对于标准DE/rand/1/bin,我们给出了有限种群下差分变异的矩,并刻画了强制坐标二项交叉引入的额外协方差与坐标依赖性。通过精确枚举和蒙特卡洛实验验证了分析结果,并量化了掩码条件、边界修复与基于适应度选择的影响。分析进一步启发了几何控制与旋转感知的SOMA变体,以及iSOMA的自适应种群缩减扩展。在完整的无噪声BBOB基准测试中,这些基于算子引导的变体显著优于标准SOMA,且在多个维度-预算区间内具有与主流DE方法相当的性能。结果表明,提案级算子分析可同时支持对群体优化器的理解与设计。
原文摘要 · Abstract (English)
Swarm and evolutionary algorithms are usually analyzed as complete procedural systems in which nonlinear selection, replacement, and adaptation obscure simpler structure within candidate generation. This paper introduces an operator--selection factorization that separates objective-independent variation from boundary repair and fitness-dependent selection, and uses it to study the proposal geometry of the Self-Organizing Migrating Algorithm (SOMA) and Differential Evolution (DE). The canonical SOMA proposal is shown to be affine in the search space and exactly linear in an augmented migrant--leader state. In leader-relative coordinates, the resulting operator provides a direct interpretation of interpolation, projection, overshooting, and coordinate masking. Under Bernoulli perturbation masks, we derive closed-form expressions for the proposal mean, covariance, expected squared step length, expected squared distance from the leader, active dimensionality, and coordinate coverage. For canonical DE/rand/1/bin, we derive the finite-population moments of differential mutation and characterize the additional covariance and coordinate dependence induced by forced-coordinate binomial crossover. Exact enumeration and Monte Carlo experiments verify the analytical identities and quantify the effects of mask conditioning, boundary repair, and fitness-based selection. The analysis further motivates geometry-controlled and rotation-aware SOMA variants, together with an adaptive population-reducing extension of iSOMA. Experiments on the complete noiseless BBOB benchmark show that these operator-guided variants substantially improve upon canonical SOMA and are competitive with established DE methods in several dimension--budget regimes. The results demonstrate how proposal-level operator analysis can support both the interpretation and design of population-based optimizers.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。