Basitleştirilmiş sürü optimizasyonu (SSO), her bir değişkeni, küresel veya kişisel en iyi değeri kopyalayan, mevcut değeri koruyan veya $c_g$, $c_p$, $c_w$ ve $c_r$ olasılıklarıyla tek bir çekilişle eşit şekilde yeniden…
02 Özet
Özetle: Basitleştirilmiş sürü optimizasyonu (SSO), her bir değişkeni, küresel veya kişisel en iyi değeri kopyalayan, mevcut değeri koruyan veya $c_g$, $c_p$, $c_w$ ve $c_r$ olasılıklarıyla tek bir çekilişle eşit şekilde yeniden…
Özet
Basitleştirilmiş sürü optimizasyonu (SSO), her bir değişkeni, küresel veya kişisel en iyi değeri kopyalayan, mevcut değeri koruyan veya $c_g$, $c_p$, $c_w$ ve $c_r$ olasılıklarıyla tek bir çekilişle eşit şekilde yeniden çeken bir çekilişle günceller. Dondurulmuş bellek altında sonlu bir Markov zinciri olarak, $c_w I + (1 – c_w)Π$ koordinat çekirdeği açık bir durağan yasaya ve $c_w^t$ tam yakınsama oranına sahiptir. Elitist zincir, geometrik bir çarpma zamanı sınırına sahiptir. Optimal olmayan bir başlangıçtan itibaren sabit bir $c_r$'nin benzersiz bir optimuma ulaşması için en az $exp(nc_r/2)$ beklenen değerlendirmeye ihtiyacı vardır ve değişen bellekler altında birleştirme, $1/n$ sırasındaki yeniden çekme payı ve atalet olmaması durumunda her popülasyon büyüklüğü için OneMax ve LeadingOnes üzerinde $O(nlog n)$ ve $O(n^2)$ beklenen nesilleri ve sabit atalet için bir $log n$ faktörü içinde verir. Bellek dondurulmuşken atalet, sabit konumlardan herhangi bir kümeye ilk girişi hızlandıramaz, ancak diğerlerinden hızlandırabilir. Üç referans değerin uyumlu olduğu durumlarda yalnızca $c_r$ etkilidir; uyumsuz oldukları durumlarda ise kopya dalları bellekleri yeniden birleştirir ve yalnızca hiçbir aktif dalın hedef değeri içermediği durumlarda yeniden çizimi zorunlu kılar. Dal kaydı ve kontrol noktası tekrarı, atalet nedeniyle test edilen OneMax ve LeadingOnes çalışmalarının yavaşladığını göstermektedir ve daha geniş boşluklarda bellek aracılı kazançlar olduğunu düşündürmektedir. Jump fonksiyonlarında SSO, $1/n$ oranına sahip (1+1) evrimsel algoritmaya göre 3,8-8,9 kat daha az değerlendirmeye ihtiyaç duymuştur, ancak orana göre ayarlanmış mutasyona veya tek tip çaprazlamaya sahip bir $(μ+1)$ genetik algoritmaya göre tutarlı bir avantaj sağlanmamıştır. Analitik yeniden çekme kuralı, sekiz ölçüt belirleme çiftinden altısını ve yedeklilik tahsisini iyileştirmiştir, ancak Jump$_2$'de $c_r = 0,1$'den daha yavaştır.
Orijinal Özet (İngilizce)
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(nlog 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$.
Kaynak: arXiv:2611.16541 · PDF
Basitleştirilmiş sürü optimizasyonu (SSO), her bir değişkeni, küresel veya kişisel en iyi değeri kopyalayan, mevcut değeri koruyan veya $c_g$, $c_p$, $c_w$ ve $c_r$ olasılıklarıyla tek bir çekilişle eşit şekilde yeniden çeken bir çekilişle günceller. Dondurulmuş bellek altında sonlu bir Markov zinciri olarak, $c_w I + (1 - c_w)Π$ koordinat çekirdeği açık bir durağan yasaya ve $c_w^t$ tam yakınsama oranına sahiptir. Elitist zincir, geometrik bir çarpma zamanı sınırına sahiptir. Optimal olmayan bir başlangıçtan itibaren sabit bir $c_r$'nin benzersiz bir optimuma ulaşması için en az $exp(nc_r/2)$ beklenen değerlendirmeye ihtiyacı vardır ve değişen bellekler altında birleştirme, $1/n$ sırasındaki yeniden çekme payı ve atalet olmaması durumunda her popülasyon büyüklüğü için OneMax ve LeadingOnes üzerinde $O(nlog n)$ ve $O(n^2)$ beklenen nesilleri ve sabit atalet için bir $log n$ faktörü içinde verir. Bellek dondurulmuşken atalet, sabit konumlardan herhangi bir kümeye ilk girişi hızlandıramaz, ancak diğerlerinden hızlandırabilir. Üç referans değerin uyumlu olduğu durumlarda yalnızca $c_r$ etkilidir; uyumsuz oldukları durumlarda ise kopya dalları bellekleri yeniden birleştirir ve yalnızca hiçbir aktif dalın hedef değeri içermediği durumlarda yeniden çizimi zorunlu kılar. Dal kaydı ve kontrol noktası tekrarı, atalet nedeniyle test edilen OneMax ve LeadingOnes çalışmalarının yavaşladığını göstermektedir ve daha geniş boşluklarda bellek aracılı kazançlar olduğunu düşündürmektedir. Jump fonksiyonlarında SSO, $1/n$ oranına sahip (1+1) evrimsel algoritmaya göre 3,8-8,9 kat daha az değerlendirmeye ihtiyaç duymuştur, ancak orana göre ayarlanmış mutasyona veya tek tip çaprazlamaya sahip bir $(μ+1)$ genetik algoritmaya göre tutarlı bir avantaj sağlanmamıştır. Analitik yeniden çekme kuralı, sekiz ölçüt belirleme çiftinden altısını ve yedeklilik tahsisini iyileştirmiştir, ancak Jump$_2$'de $c_r = 0,1$'den daha yavaştır.
03 PDF
Bu PDF başka bir sitede (arxiv.org) barındırılıyor ve sayfa içinde gösterilemiyor. Yukarıdaki düğmelerle yeni sekmede açabilir ya da indirebilirsiniz.
04 Kaynak göster
@article{yeh2026a,
title = {A Finite Markov Chain Analysis of the Simplified Swarm Optimisation Update Rule},
author = {Wei-Chang Yeh},
journal = {arXiv preprint arXiv:2611.16541},
year = {2026},
url = {https://arxiv.org/abs/2611.16541}
}
Yeh, W. (2026). Basitleştirilmiş Sürü Optimizasyonu Güncelleme Kuralının Sonlu Markov Zinciri Analizi. arXiv. https://arxiv.org/abs/2611.16541
Yorumlar 0
Henüz yorum yok. İlk yorumu siz yazın.
Yorum yazın