[Paper] S-LCG：基于结构化线性同余生成器的搜索与优化确定性算法

Source: arXiv - 2605.05198v1

Overview

一种名为 S‑LCG（结构化线性同余生成器）的新确定性优化算法已被提出。通过将经典的伪随机数生成器重新用于结构化搜索引擎，作者在广泛的基准和工程问题上实现了高质量的解，同时保持实现简洁且完全可复现。

关键贡献

• 确定性搜索框架 基于特殊结构的线性同余生成器（LCG）。
• 两层架构：外层循环自适应平衡探索与利用，内层循环评估候选解。
• 无记忆、非重叠序列 通过不同种子实现，消除冗余评估。
• 位拆分表示 将 LCG 状态映射到多维点，缓解普通 LCG 的经典 “Marsaglia lattice” 偏差。
• 恒定信息获取率，降低过早收敛，无需复杂的种群规模调度。
• 最小超参数集 —— 仅需调节单一敏感参数。
• 广泛的实证验证 在 26 个基准函数（2‑30 维）和三个真实约束工程设计问题上，优于八种最先进的二进制元启发式算法和标准遗传算法（GA）。

方法论

1. 结构化 LCG 核心 – 该算法从传统的 LCG 开始：

   [ x_{k+1} = (a \cdot x_k + c) \bmod m ]

   但在此基础上加入了结构，将每个生成的整数视为二进制字。该字被划分为若干位块；每个块被解释为决策空间中的一个坐标。这种“位拆分”把一维序列转换为多维点集，同时保留生成器的确定性特征。

2. 两层控制

   • 外层循环（探索‑利用控制器）：单一标量参数 (\lambda) 决定生成器种子被扰动的激进程度。较小的 (\lambda) 值保持搜索紧凑（利用）；较大的值则注入新种子（探索）。控制器根据近期的改进率自适应调整 (\lambda)。
   • 内层循环（解评估器）：对于每个种子，结构化 LCG 产生一批候选点。由于 LCG 是无记忆的，每个种子产生唯一且不重叠的批次，保证没有候选点被重复评估。

3. 基于代理的接受机制 – 算法通过观察生成器的确定性轨迹，隐式构建目标函数的平滑代理。当新点提升了代理时，外层循环收紧 (\lambda)；否则放宽 (\lambda)，在不使用显式的基于种群的交叉或变异算子的情况下，将搜索引导至有前景的区域。

4. 约束处理 – 对于受约束的工程问题，向目标函数添加一个简单的惩罚函数。由于生成器已经通过对位拆分值的缩放满足了边界约束，只需对不等式/等式约束进行惩罚。

整个过程可以用几十行 Python 或 C 代码实现，除基本数学工具外无需任何外部库。

结果与发现

• 统计显著性：Wilcoxon 符号秩检验证实，S‑LCG 相较竞争者的改进并非偶然产生。
• 工程案例研究：该算法成功解决了三个受约束的设计问题（如桁架尺寸、压力容器设计），在远少于 GA 基线的目标函数评估次数下获得了可行且接近最优的解。
• 对维度的鲁棒性：即使搜索空间扩展至 30 维，成功率仍保持在 80 % 以上，表明位拆分方案能够有效抵御在高维情况下普通 LCG 常出现的格子效应。

实际意义

• 确定性可复现 – 因为搜索完全由初始种子和单一自适应参数决定，开发者可以在不同机器和语言之间复现完全相同的运行——这对安全关键或受监管的行业具有吸引力。
• 轻量级实现 – 不需要大规模种群、交叉算子或复杂的变异调度。这意味着更低的内存占用和更快的运行时间，使 S‑LCG 适用于嵌入式优化（例如，设备端超参数调优、实时控制参数更新）。
• 易于集成到现有流水线 – 算法输出一个简单的候选向量列表；可以直接嵌入任何现有的评估循环（仿真、CFD、机器学习模型训练），无需重新设计周边代码。
• 可进行混合 – 由于 S‑LCG 已经提供了高质量的确定性骨干，它可以与随机细化方法（例如局部梯度下降）结合，以进一步加速平滑问题的收敛。
• 降低超参数负担 – 只需调节一个可调参数（(\lambda) 适应率），通常可以设为默认值。这降低了缺乏元启发式调优深度经验的团队的门槛。

限制与未来工作

• 可扩展性超出30维 – 虽然在30个变量以内的结果令人鼓舞，但作者指出在更高维度问题上成功率会逐渐下降；未来的研究可以探索自适应位块大小或层次分解。
• 约束处理过于简化 – 目前基于惩罚的方式可能在高度非凸的可行区域中表现不佳；将更复杂的保持约束的变换集成进来是一个待探索的方向。
• 基准多样性 – 本研究聚焦于连续、无约束的基准函数以及少数工程设计；在组合或混合整数问题上进行测试将扩大其适用范围。
• 理论收敛保证 – 尽管实证证据充分，但仍缺乏收敛的形式化证明（或对期望最优距离的界限）。

总体而言，S‑LCG 提供了一种新颖、确定性的元启发式优化方法，能够很好地满足开发者和工程师对可复现、低开销搜索手段的实际需求。

作者

• Ahmed Qasim Mohammed
• Haider Banka
• Anamika Singh

论文信息

• arXiv ID: 2605.05198v1
• 分类: math.OC, cs.NE
• 发布日期: 2026年5月6日
• PDF: 下载 PDF