Swarm optimizers such as particle swarm optimization (PSO), where many candidate points share information about the best location found so far, often fail by collapsing onto a mediocre local optimum. The usual fix is to push particles apart when they get too close to the swarm's best point. That fix has a known cost. It also pushes particles apart when they are all correctly converging on the true optimum of a smooth, single-basin function, so precision on easy problems drops. We propose one change. Before one point pushes another away, check whether the objective actually has a ridge between them. The check samples the function at a few points along the line segment joining the two points and measures how much the function goes up and down beyond what a single valley would produce. If the sampled profile is a single valley, the two points are in the same basin and no repulsion is applied. If it has an interior bump, a barrier is certified and repulsion is applied, scaled by the size of the bump.
The quantity behind the check is total variation, the sum of all up-and-down movement of a function, which is the central object in work on quantitative bounds on function variation. Along a one-dimensional segment it gives an exact test. The test's error can only run in one direction: with exact function evaluations, a finite sample can miss a ridge but can never report one that is not there. This turns a heuristic distance trigger into a trigger based on the landscape, and it directly targets the unimodal-versus-multimodal trade-off identified as the main open problem for anti-collapse mechanisms.
Core Claim
Take a particle's personal best $a$ and the swarm's global best $b$. Restrict the objective to the segment between them, $\phi(t) = f(a + t(b-a))$ for $t \in [0,1]$. Let $V(\phi)$ be its total variation and $m = \min_t \phi(t)$ its lowest value. Any profile shaped like a single valley has variation exactly $(\phi(0) - m) + (\phi(1) - m)$, so we define the excess variation
$$E(a,b) = V(\phi) - \big(\phi(0) + \phi(1) - 2m\big) \ge 0,$$
which is zero exactly when $\phi$ is valley-shaped (quasiconvex) and positive when the segment crosses an interior local maximum. Computing $V$, $m$ and $E$ from $k$ evaluated points on the segment gives a sampled value $E_k$. A positive $E_k$ can only come from an up-down-up pattern that really exists in $\phi$, so $E_k > 0$ certifies a barrier.
The proposed update replaces the fixed repulsion strength of Divergence-Guided Particle Swarm Optimization with $c_3 \cdot E_k / (E_k + \tau)$. Here $c_3$ is DPSO's original repulsion weight, and $\tau$ is a scale set by the current spread of fitness values across the swarm. The central testable claim is that this gated version keeps DPSO's gains on multimodal functions while recovering plain PSO's convergence on functions that are convex along lines. The extra evaluations are charged to the same budget as everything else.
Relation to Prior Work
DPSO motivates the proposal. It adds a Gaussian repulsion between personal and global bests, which it shows is equivalent to an exponentially decaying KL divergence. It reports 2x to 8x gains on Pinter, Ackley and Levy, and slightly worse results than PSO on Sphere, where PSO reaches near machine precision. Its trigger depends only on Euclidean distance, and its bandwidth and weight are fixed. We keep its kernel and change only what decides whether the kernel fires.
The variation literature supplies the measuring instrument and a caution. Bounded Variation Separates Weak and Strong Average Lipschitz proves $\|f\|_w \le V(f) \le \|f\|_s$ on $[0,1]$. It also shows that bounded-variation functions need not have finite weak average Lipschitz norm. We read this as evidence that average-slope summaries, which is what fitness variance or local gradient magnitudes roughly measure, cannot stand in for variation when the goal is detecting a barrier. We therefore measure variation directly on a one-dimensional segment. That is the setting where these results are tight, and it sidesteps the open problem of extending them to high dimensions. The infinite fat-shattering dimension of the weak class is a warning that few samples can miss narrow ridges. Our one-sided guarantee accepts misses in exchange for never producing a false alarm.
Optimization on a Finer Scale: Bounded Local Subgradient Variation Perspective shows that local, averaged variation assumptions sharpen first-order convergence rates. It studies descent to stationary points, not population collapse, and it leaves adaptive estimation of local variation open. Our estimator is a crude but assumption-free answer to that estimation problem, used here for gating rather than for setting step sizes.
On the premature-convergence side, OPAL learns operator schedules from trajectory graphs with a GNN after a fixed 20% probe phase. It provides no guarantee and uses no variation estimate. The restart logic of Iterated Population Based Training with Task-Agnostic Restarts detects stagnation from performance curves over time. Both decide when to diversify from aggregate statistics. We decide from a local measurement of the landscape.
Research Program
We will first establish the basic guarantees. With exact evaluations, gated DPSO never repels on any objective whose restriction to every line is quasiconvex, a class that includes all convex functions and radially unimodal ones. On such objectives its dynamics reduce exactly to standard PSO. We will also bound the probability of missing a ridge of width $w$ on a segment of length $\ell$ with $k$ uniformly spaced samples, which is roughly zero once $k > \ell / w$.
There is an honest limitation. Unimodal but non-convex functions such as Rosenbrock-type curved valleys can have line segments that cross the valley twice. On such segments $E > 0$ even though the function has one global basin, so the gate will sometimes fire when it should not. We will measure how often this happens rather than argue it away.
Second, we will control the evaluation cost. The check runs only when DPSO's kernel would exceed a threshold, meaning the particles are close. Each check costs $k$ evaluations with $k \in \{1, 3, 7\}$. Any sampled point that improves on the global best replaces it immediately, so evaluations spent on checks can still move the search forward.
Third, we will study sensitivity to $\tau$ and $k$, and compare the fixed $\tau$ against the swarm-spread-relative $\tau$.
Baselines
The naive reference is standard PSO with inertia and constriction settings matched to DPSO. It shows what happens with no diversity mechanism, and it is the target for performance on unimodal functions.
The direct competitor is DPSO itself (Divergence-Guided Particle Swarm Optimization), run with its published $c_3$ and $\sigma$. It is the strongest method that uses the same repulsion kernel, so any difference isolates the gate. That paper reports relative results only: 2x to 8x over PSO on Pinter, Ackley and Levy, a 5x reduction in standard deviation on Griewank, and slightly worse than PSO on Sphere. I found no reported absolute error values on Lacuna for these functions, so we will rerun DPSO ourselves. Beating DPSO means matching its multimodal medians within run-to-run noise while closing most of its gap to PSO on unimodal functions, under an identical evaluation budget and identical seeds.
The key ablation is a one-point midpoint test ($k = 1$) that makes a binary repel-or-don't decision. It separates the value of a graded, multi-sample variation measure from the simplest possible barrier check.
For standing on CEC 2017, the strongest existing methods are L-SHADE and jSO. The OPAL paper reports average ranks of 2.561 for L-SHADE, 2.781 for jSO and 2.798 for OPAL. We do not expect a PSO variant to beat L-SHADE. We report its rank on the same protocol to place the result honestly, and we test the gate as a trigger for L-SHADE's own restart mechanism as a secondary transfer experiment.
All methods receive the CEC budget of $10000 \cdot D$ evaluations, including gate evaluations. Every method gets the same hyperparameter tuning budget on a held-out subset of functions.
Why not just…?
Why not just anneal the repulsion weight, or turn it off when the swarm's fitness variance is small? This is the most serious threat, because it is cheap and would also rescue Sphere. However, low fitness variance means the same thing at the bottom of a single smooth bowl and inside a local trap. That is exactly the situation where DPSO must decide whether to repel, so a schedule or variance trigger will either give up precision on unimodal functions or give up escapes on multimodal ones. We include tuned annealed-DPSO and variance-gated-DPSO arms. If either matches the variation gate on both the unimodal and multimodal groups at equal budget, the variation machinery adds nothing and we will say so.
Why not spend the gate's extra evaluations on more particles or more iterations? This is fair, since each check costs $k$ evaluations. The budget-matched comparison already charges them. We add a further arm in which DPSO receives the average number of extra evaluations the gate used, as additional population. If this arm does as well, the benefit came from the extra samples, not from gating.
Why not just use heavy-tailed jumps or random restarts? Lévy-flight kicks (Xuan Chen et al.) and chaotic maps (Xin Lou and Lin Sun) perturb particles regardless of the landscape. They therefore disturb fine convergence on smooth functions for the same reason distance-based repulsion does. We include a Lévy-PSO arm to test whether untargeted noise alone closes the multimodal gap.
Why not learn when to diversify, as OPAL does? OPAL may well rank higher overall. Its 20% probe phase and learned policy, however, give no guarantee on landscapes outside the functions it was trained on. The variation gate is training-free and never produces false alarms. We compare against OPAL's reported rank rather than claim to beat it.
Proposed Experiments
The main experiment covers the 36-function suite used by DPSO (15 unimodal and 21 multimodal functions, at $D \in \{10, 30, 50\}$) and the 29 CEC 2017 functions at $D \in \{10, 30, 50\}$, with 51 seeds per configuration. We report median final error, Wilcoxon tests against each baseline, and average rank.
The first decisive check concerns the convex and quasiconvex functions (Sphere and similar). The gate should fire on essentially no checks, and final error should match PSO's near machine precision where DPSO falls short.
The second decisive check concerns Ackley, Levy, Pinter and Griewank. Gated DPSO should retain DPSO's improvement over PSO.
The third check concerns the Rosenbrock-type and hybrid CEC functions. We log the gate's firing rate as a direct measurement of false positives from curved valleys.
As a diagnostic, we record for every triggered check whether $a$ and $b$ truly lie in different basins, using dense offline sampling of the segment followed by local descent from both endpoints. This gives the gate's precision and recall as a function of $k$, and we compare the observed recall against the bound from ridge width and segment length.
If the variance-gated or budget-reallocated arms match the variation gate on both groups, we will conclude that the variation machinery is unnecessary.
References
- Divergence-Guided Particle Swarm Optimization
- Bounded Variation Separates Weak and Strong Average Lipschitz
- Optimization on a Finer Scale: Bounded Local Subgradient Variation Perspective
- OPAL: Operator-Programmed Algorithms for Landscape-Aware Black-Box Optimization
- Iterated Population Based Training with Task-Agnostic Restarts
- Forecasting short-term electric load using extreme learning machine with improved tree seed algorithm based on Lévy flight
- An improved chaotic fruit fly optimization based on a mutation strategy for simultaneous feature selection and parameter optimization for SVM and its applications