İçeriğe atla
Arama sonuçlarına dön

Rastgele Parçacık Sürü Optimizasyonu — Rastgele Sürü Tabanlı Küresel Arama

Ortaya koyan
Kennedy, J. and Eberhart, R. (base PSO); stochastic extensions by Clerc, Kennedy and community
Yıl
1995–2002
Tür
Metaheuristic optimization — stochastic swarm intelligence
Aile
Simulation / optimization

Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku

Yazı boyutu

Ne işe yarar?

Rastgele Parçacık Sürü Optimizasyonu (Rastgele PSO), standart PSO çerçevesini, yerel optimumlardan kaçmak ve arama boyunca popülasyon çeşitliliğini korumak için açık rastgelelik unsurları — rastgele atalet ağırlıkları, olasılıksal hız sıfırlamaları veya gürültü enjeksiyonları — ekleyerek genişleten bir sürü zekası meta-sezgisidir.

Mühendislik, operasyon araştırması ve simülasyon tabanlı tasarım alanlarındaki sürekli, karma ve gürültülü optimizasyon problemlerine yaygın olarak uygulanır.

Yöntemin mantığı

Yiyecek arayan bir kuş sürüsünü hayal edin, burada her kuş kişisel en iyi konumunu hatırlar ve ayrıca grubun en iyi bilinen noktasını takip eder. Standart PSO'da r1 ve r2 rastgele katsayıları zaten rastgelelik katmaktadır, ancak Rastgele PSO bu rastgeleliği kasıtlı olarak artırır veya yapılandırır — atalet ağırlığını her yinelemede rastgele değiştirerek, konumlara Gauss gürültüsü ekleyerek veya durağan parçacıkları olasılıksal olarak sıfırlayarak — böylece sürü erken bir suboptimal bölgeye yakınsamak yerine geniş çapta keşfetmeye devam eder.

Tarih

Parçacık Sürü Optimizasyonu, 1995 yılında Kennedy ve Eberhart tarafından, kuş sürülerinin ve balık okullarının sosyal davranışlarından esinlenerek tanıtıldı. Clerc ve Kennedy (2002), daralma katsayısı varyantını biçimlendirdi ve kararlılığını analiz ederek teorik temelleri attı. Rastgele atalet ağırlıkları, gürültü ile zenginleştirilmiş hızlar, olasılıksal sıfırlamalar gibi rastgele uzantılar, araştırmacılar erken yakınsamayı orijinal algoritmanın ana pratik zayıflığı olarak belirledikçe, 1990'ların sonları ve 2000'lerde ortaya çıktı.

Ne zaman kullanılır?

Arama manzarası çok modlu, gürültülü veya yüksek boyutlu olduğunda ve standart PSO erken yakınsamaya eğilim gösterdiğinde Rastgele PSO kullanın. Özellikle hedef fonksiyonunun rastgele veya değerlendirilmesinin pahalı olduğu simülasyon tabanlı optimizasyon ve birçok yerel minimuma sahip mühendislik tasarım problemleri için uygundur. Çeşitlilik bakımının kritik olduğu durumlarda deterministik varyantlara tercih edin. Düz, tek modlu bir hedefe sahip ve ucuz değerlendirmeleri olan problemler için KULLANMAYIN — gradyan tabanlı veya kesin yöntemler daha hızlı ve daha doğru olacaktır. Ayrıca, rastgele bir tohum politikası olmaksızın her çalıştırmanın tekrarlanabilirliğinin önemli olduğu durumlarda, rastgele gürültünün kesin tekrarlamayı karmaşıklaştırması nedeniyle bundan kaçının.

Sınırlar ve dikkat edilmesi gerekenler

  • Hiperparametre hassasiyeti: gürültü parametreleri ve atalet ağırlığı dağılımı yakınsama hızını ve çözüm kalitesini güçlü bir şekilde etkiler.
  • Keyfi dışbükey olmayan problemler için sonlu zamanda küresel optimumu bulma garantisi yoktur.
  • Rastgele yeniden başlatmalar umut vadeden parçacıkları atabilir, ara sıra fitness değerlendirmelerini boşa harcayabilir.
  • Performans, problem özelindeki yöntemlere kıyasla çok yüksek boyutlu uzaylarda (boyutluluk laneti) düşer.
  • Çözüm kalitesine güven oluşturmak için birden fazla çalıştırma gerekebilir, bu da toplam hesaplama maliyetini artırır.

Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.

Güçlü yönleri

  • Kontrollü rastgelelik yoluyla popülasyon çeşitliliğini korur, standart PSO'ya kıyasla erken yakınsamayı önemli ölçüde azaltır.
  • Gradyan bilgisi gerektirmez ve pürüzsüz olmayan, süreksiz veya kara kutu hedef fonksiyonlarını işler.
  • Kolayca paralelleştirilebilir: her parçacık değerlendirmesi bir yineleme içinde bağımsızdır.
  • Esnektir: rastgelelik derecesi (gürültü seviyesi, atalet dağılımı) keşif ve sömürü arasında denge kurmak için ayarlanabilir.
  • Değerlendirmelerin doğal olarak gürültü taşıdığı rastgele veya simülasyon tabanlı fitness fonksiyonlarını doğal olarak işler.
  • Kavramsal olarak az sayıda hiperparametre ile basittir (sürü boyutu N, bilişsel c1, sosyal c2 katsayıları ve gürültü parametreleri).

Uygulama alanları

  • Mühendislik tasarım optimizasyonu: aerodinamik şekil ayarlaması, anten dizisi tasarımı, belirsizlik altındaki yapısal optimizasyon.
  • Sinir ağı eğitimi: gürültülü veri kümelerinde ileri beslemeli ve tekrarlayan ağlar için ağırlık optimizasyonu.
  • Tedarik zinciri ve çizelgeleme: rastgele iş istasyonu çizelgeleme, talep belirsizliği altında envanter optimizasyonu.
  • Finansal portföy optimizasyonu: rastgele piyasa modelleri ile riske ayarlanmış getiriyi maksimize etme.
  • Simülasyon tabanlı optimizasyon: ajan tabanlı veya sistem dinamik modellerini ampirik verilere kalibre etme.
  • Doğrulama kaybı yüzeyinin gürültülü olduğu makine öğrenmesi boru hatları için hiperparametre ayarlama.

Nasıl çalışır?

Nasıl çalışır?

1

Uygun arama uzayına üniform olarak rastgele örneklenmiş konumlar x_i ve hızlar v_i ile N parçacıktan oluşan bir sürü başlatın. Her parçacık için hedef fonksiyonu f(x_i)'yi değerlendirin ve kişisel en iyi p_i = x_i ve küresel en iyi g = argmin f(x_i) olarak ayarlayın.

2

Her parçacık hızını rastgele kuralı kullanarak güncelleyin: v_i(t+1) = omega * v_i(t) + c1*r1*(p_i - x_i) + c2*r2*(g - x_i), burada r1, r2 ~ Uniform(0,1) her yinelemede taze rastgele çekilişlerdir. Rastgele PSO'da, omega'nın kendisi bir dağılımdan (örn. Uniform(0.4, 0.9)) çekilebilir veya çeşitliliği korumak için bir Gauss gürültüsü terimi epsilon ~ N(0, sigma^2) eklenir.

Formül
v_i(t+1) = \omega v_i(t) + c_1 r_1 (p_i - x_i(t)) + c_2 r_2 (g - x_i(t))
3

Her parçacığı yeni aday konumuna taşıyın: x_i(t+1) = x_i(t) + v_i(t+1). Parçacıkları uygun alan içinde tutmak için sınır işleme (yansıtma, sınırlama veya toroid sarma) uygulayın.

Formül
x_i(t+1) = x_i(t) + v_i(t+1)
4

Varyanta bağlı olarak ek rastgele mekanizmalar uygulayın: (a) her yinelemede rastgele çekilen rastgele atalet ağırlığı, (b) yerel çekim havzalarından kaçmak için kişisel en iyilerin Gauss pertürbasyonu veya (c) iyileşme oranı bir eşiğin altına düşen parçacıkların rastgele yeniden başlatılması, keşif kapasitesini geri yükler.

5

T yinelemesi boyunca yakınsama kontrolüne kadar veya bir durdurma kriteri karşılanana kadar (örn. K ardışık yineleme boyunca fitness iyileşmesi < epsilon) tüm parçacıklar için f(x_i(t+1))'i değerlendirin; kişisel en iyileri ve küresel en iyiyi güncelleyin. Çözüm olarak küresel en iyi g'yi döndürün.

Sık yapılan hatalar

  • Gürültü varyansını çok yüksek ayarlamak algoritmayı neredeyse rastgele aramaya dönüştürür; çok düşük ayarlamak standart PSO'ya göre fayda sağlamaz — önce bir doğrulama problemi üzerinde kalibre edin.
  • Rastgele pertürbasyon adımında sınır işlemeyi göz ardı etmek, parçacıkları uygun bölgenin dışına iterek geçersiz veya anlamsız çözümler üretebilir.
  • Rastgele PSO'yu deterministik taban çizgilerine karşı tek bir çalıştırmada karşılaştırmak yanıltıcıdır; her zaman birden fazla bağımsız çalıştırma üzerinden istatistikleri (ortalama, standart sapma) bildirin.
  • Tüm parçacıklar arasında sabit bir rastgele tohum kullanmak çeşitlilik faydasını ortadan kaldırır — her parçacığın bağımsız rastgele akışlar kullandığından emin olun.

Sık sorulan sorular

Rastgele PSO, standart PSO'dan nasıl farklıdır?

Standart PSO zaten her yinelemede üniform olarak çekilen rastgele r1 ve r2 katsayılarını kullanır. Rastgele PSO, daha güçlü çeşitlilik bakımı sağlamak için bu rastgeleliği kasıtlı olarak yapılandırır veya artırır — örneğin, her yinelemede atalet ağırlığı omega'yı bir olasılık dağılımından örnekleyerek, parçacık konumlarına Gauss gürültüsü ekleyerek veya durağan parçacıkları olasılıksal olarak yeniden başlatarak.

Kaç parçacık kullanmalıyım?

Yaklaşık 30 boyuta kadar olan problemler için yaygın bir başlangıç noktası 20-50 parçacıktır. Daha büyük sürülerin (50-200) yüksek boyutlu veya yüksek derecede çok modlu uzaylarda kapsama alanını iyileştirmesi, yineleme başına daha fazla fonksiyon değerlendirmesi maliyetiyle mümkündür.

Rastgele pertürbasyonlar için gürültü varyansını nasıl seçmeliyim?

Problem sınıfınızın temsili bir örneği üzerinde kalibre edin. Pratik bir sezgi, eklenen gürültünün standart sapmasını boyut başına arama uzayı genişliğinin kabaca %1-5'i olarak ayarlamak ve ardından yakınsama tanılarına göre ayarlamaktır — çeşitlilik metriği, bütçe tükenmeden sıfıra yakın çökmemelidir.

Neden Rastgele PSO'yu Diferansiyel Evrim veya Genetik Algoritmalar yerine tercih etmeliyim?

Rastgele PSO, sürekli, düşük ila orta boyutlu problemler üzerinde daha hızlı yakınsama eğilimindedir ve uygulaması çok basittir. Diferansiyel Evrim ve Genetik Algoritmalar genellikle kombinatoryal veya ayrık yapıları daha iyi işler. Probleminiz tamamen sürekli ve çok modlu ise, Rastgele PSO güçlü bir ilk tercihtir.

Rastgele PSO çok amaçlı problemler için uygun mudur?

Burada açıklanan tek amaçlı varyant, çok amaçlı problemler için doğrudan tasarlanmamıştır. Bunlar için, Pareto-non-dominant çözümlerin açık bir arşivini koruyan Çok Amaçlı PSO (MOPSO) veya NSGA-II kullanın.

İlgili yöntemler

Kaynaklar

  1. Kennedy, J., Eberhart, R. (1995). Particle swarm optimization. Proceedings of ICNN'95 - International Conference on Neural Networks, Vol. 4, pp. 1942-1948. IEEE.

    DOI kaynağını aç
    Kopyalandı.
  2. Clerc, M., Kennedy, J. (2002). The particle swarm - explosion, stability, and convergence in a multidimensional complex space. IEEE Transactions on Evolutionary Computation, 6(1), 58-73.

    DOI kaynağını aç
    Kopyalandı.