A Finite Markov Chain Analysis of the Simplified Swarm Optimisation Update Rule
Organizations: Department of Industrial Engineering and Engineering Management, National Tsing Hua University, No. 101, Section 2, Kuang-Fu Road, Hsinchu 30013, Taiwan
Abstract
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 , , and . As a finite Markov chain under frozen memory, its coordinate kernel has an explicit stationary law and exact convergence rate . The elitist chain has a geometric hitting-time bound, from a non-optimal start a fixed needs at least expected evaluations to reach a unique optimum, and a coupling under changing memories gives and expected generations on OneMax and LeadingOnes for every population size with redraw share of order and no inertia, and within a 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 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 , but no consistent advantage over rate-adjusted mutation or a 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 on Jump.
Evolutionary Optimization
Evolutionary optimization searches for strong solutions through population-based variation, selection, and adaptation.
See all 305 papers