Skip to main content
Back

Noisy Optimization Finally Works With Statistical Linkage Learning Breakthrough

A team of evolutionary computation researchers show how Statistical Linkage Learning can rescue Partition Crossover when objective functions are corrupted by noise.

Pro

Paper, Full Access
  • New preprint extends Partition Crossover to noisy black-box problems where standard dependency checks fail.
  • Uses Statistical Linkage Learning to infer variable dependencies from population statistics instead of fitness probes.
  • Introduces a clustering algorithm that turns SLL linkage trees into PX-equivalent crossover masks.
  • Proves that sufficiently good SLL decomposition yields masks identical to noise-free PX masks.
  • Outperforms state-of-the-art linkage-aware optimizers at high noise, matches them at low noise.
  • Available on arXiv; no public code release announced yet.

A classic trick in evolutionary optimization is to figure out which variables interact with each other, then recombine two candidate solutions along the boundaries of those interactions. It works beautifully when the objective function is clean, but collapses the moment noise enters the picture. A new preprint from Michal Przewozniczek and collaborators proposes a way to keep the technique working even when the underlying variable dependencies are hidden behind noise.

Why Partition Crossover breaks under noise

Partition Crossover (PX) is one of the sharper tools in the pseudo-Boolean optimization toolbox. Given two parent solutions, it decomposes the problem into independent subfunctions, then picks the best value of each subfunction from either parent. The child is provably at least as good as both parents, and often exponentially better than random recombination.

The catch is that PX needs to know which variables depend on which. Standard dependency detection compares fitness values before and after flipping bits, and noise makes those comparisons unreliable. In noisy problems, the dependencies that matter for optimization can be indistinguishable from statistical artifacts, which renders operators like PX unusable.

Swapping deterministic checks for a statistical proxy