arXiv:2611.16541 · v1
A Finite Markov Chain Analysis of the Simplified Swarm Optimisation Update Rule
摘要
Simplified swarm optimisation (SSO) updates each variable by one draw that copies the global or personal best, keeps the current value or redraws uniformly, with probabilities $c_g$, $c_p$, $c_w$ and $c_r$. As a finite Markov chain under frozen memory, its coordinate kernel $c_w I + (1 - c_w)Π$ has an explicit stationary law and exact convergence rate $c_w^t$. The elitist chain has a geometric hitting-time bound, from a non-optimal start a fixed $c_r$ needs at least $\exp(nc_r/2)$ expected evaluations to reach a unique optimum, and a coupling under changing memories gives $O(n\log n)$ and $O(n^2)$ expected generations on OneMax and LeadingOnes for every population size with redraw share of order $1/n$ and no inertia, and within a $\log n$ factor for fixed inertia. With a frozen memory, inertia cannot speed up first entry into any set from stationary positions, though it can from others. Where the three reference values agree, only $c_r$ acts; where they disagree, copy branches recombine the memories, forcing a redraw only where no active branch holds the target value. Branch logging and checkpoint replay show inertia slowed the tested OneMax and LeadingOnes runs and suggest memory-mediated gains on wider gaps. On Jump functions SSO needed 3.8--8.9 times fewer evaluations than the (1+1) evolutionary algorithm with rate $1/n$, but no consistent advantage over rate-adjusted mutation or a $(μ+1)$ genetic algorithm with uniform crossover was established. The analytical redraw rule improved six of eight benchmark--setting pairs and redundancy allocation, but was slower than $c_r = 0.1$ on Jump$_2$.
作者备注：29 pages, 7 figures, 17 tables. Submitted to Swarm and Evolutionary Computation. Code, per-run records and a one-command reproduction workflow: Zenodo, doi:10.5281/zenodo.24153497