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$.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.
저자 비고
arXiv Comments
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