[论文] Pascal-Weighted 遗传算法：二项结构的重组框架

Source: arXiv - 2512.01249v1

概览

Otman A. Basir 的论文提出了 Pascal‑Weighted Genetic Algorithms (PWR)——一种新型的多父代交叉算子族，使用二项式（帕斯卡三角）权重对多个父代进行混合。通过塑造遗传概率，PWR 在降低破坏性跳变的同时保留有用的构件块，从而在一系列优化问题上实现更快、更可靠的收敛。

主要贡献

• 二项式结构的重组：引入一种基于归一化帕斯卡系数的凸组合权重的数学严谨方法。
• 方差转移分析：推导闭式表达式，展示 PWR 相较于经典的双父代交叉如何抑制后代方差。
• 模式保留理论：将经典模式定理扩展到多父代、加权重组，证明对有用模式的更高保留率。
• 表示无关的扩展：提供了针对实值向量、二进制/对数编码以及排列染色体（如 TSP 路径）的具体公式。
• 四个多样基准的实证验证：PID 控制器调参、FIR 滤波器设计、无线功率调制以及旅行商问题。
• 性能提升：相较于标准算子（单点、均匀、PMX 等），最终目标质量提升 9‑22 %，收敛曲线更平滑。

方法论

1. 权重生成 – 对于选定的父代数目 k，算法计算归一化的帕斯卡系数
   [ \hat{w}_i = \frac{\binom{k-1}{i-1}}{2^{k-1}} . ]
   这些权重形成对称的钟形分布，在父代列表的中心达到峰值。

2. 后代构造 –

   • 实值：
     [ x^{\text{off}} = \sum_{i=1}^{k} \hat{w}_i , x^{(i)} . ]
   • 二进制/对数：对每个基因从伯努利分布中抽样，其成功概率为父代位的加权和。
   • 排列：加权投票方案决定每个元素的位置，随后进行修复步骤以保证得到有效的路径。

3. 在 GA 循环中的集成 – PWR 替代常规的双父代交叉步骤；选择、变异和精英保留保持不变，使该算子可直接作为任何现有 GA 框架的插件使用。

4. 理论分析 – 利用期望的线性性和二项式系数的性质，作者推导出：

   • 期望后代均值等于父代池的均值（无偏）。
   • 相较于均匀加权，后代方差降低了 (1/2^{k-1}) 倍，解释了搜索动态的平滑性。

5. 实验设置 – 每个基准进行 30 次独立 GA 试验（种群 = 200，代数 = 500），比较 PWR（k = 3, 5）与标准交叉基线。性能通过领域特定指标衡量（PID 的 ITAE、FIR 的幅度误差、无线的 SINR、TSP 的路径长度）。

结果与发现

在所有测试中，PWR 的多父代平均导致 后代方差更低，这转化为更稳健的进展以及更高的有前景模式保留概率。当搜索空间崎岖或适应度景观包含大量局部最优（如 TSP）时，收益尤为显著。

实际意义

• 即插即用的提升：开发者只需将现有交叉例程替换为 PWR 模块，代码改动极少；该算子兼容任何支持自定义重组的 GA 库。
• 对噪声或实时优化的鲁棒性：方差降低特性使 PWR 在控制系统调参（PID）或在线无线资源分配等评估噪声较大的场景中具有吸引力。
• 可扩展到高维问题：加权求和是线性的，计算开销仅随父代数目增长，而与染色体长度无关，运行时间与经典交叉相当。
• 更好利用并行性：多父代选择天然适合 GPU/CPU 批处理——在一次 kernel 启动中为每个后代选取 k 个父代。
• 可用于混合元启发式：PWR 可与差分进化、粒子群或记忆局部搜索结合，在细粒度利用前提供更平滑的全局搜索骨架。

局限性与未来工作

• 父代数目敏感性：超过 k = 5 后收益递减；父代过多会过度平滑搜索，削弱多样性。
• 排列修复成本：在大规模 TSP 实例中，修复步骤带来额外开销；可探索更高效的针对排列的加权方案。
• 理论界限局限于简单适应度模型：方差分析假设适应度为可加成分；将理论扩展到高度表观或受约束的问题仍是开放课题。
• 未来方向 包括基于种群多样性指标的自适应 k 选择、与自适应变异率的集成，以及在深度学习超参数优化或神经架构搜索上的测试。

作者

• Otman A. Basir

论文信息

• arXiv ID: 2512.01249v1
• 分类: cs.NE, cs.AI, eess.SY
• 发布日期: 2025 年 12 月 1 日
• PDF: Download PDF