Parçacık Sürü Optimizasyonu (PSO)
- Yıl
- 1995
- Tür
- Population-based metaheuristic / swarm intelligence
Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku
Ne işe yarar?
Parçacık Sürü Optimizasyonu (PSO), 1995 yılında Kennedy ve Eberhart tarafından tanıtılan, kuş sürüleri ve balık okullarının kolektif hareketinden esinlenen popülasyon tabanlı bir meta-sezgisel algoritmadır.
Her bir aday çözüm – parçacık olarak adlandırılır – kendi en iyi deneyimine ve tüm sürünün en iyi deneyimine dayanarak hızını ve konumunu güncelleyerek arama uzayında hareket eder, bu da sürekli optimizasyon problemlerinde hızlı yakınsamayı sağlar.
Yöntemin mantığı
Büyük bir alanda en zengin yiyecek kaynağını arayan bir kuş sürüsü hayal edin. Tek bir kuşun haritası yoktur, ancak her biri kişisel olarak ziyaret ettiği en iyi noktayı hatırlar ve yakındaki herhangi bir kuş tarafından bulunan en iyi noktadan haberdardır. Her kuş, uçuşunu kısmen kendi hatırladığı en iyi konuma ve kısmen de sürünün kolektif en iyisine doğru yönlendirir, hızını buna göre ayarlar. Birçok böyle ayarlama sonucunda tüm sürü en zengin alana yakınsar. PSO tam olarak bu şekilde çalışır: her parçacık bir aday çözümdür, konumu çözümün kendisidir ve sürü bireysel ve sosyal hafızayı birleştirerek kolektif olarak optimuma doğru ilerler.
Tarih
PSO, James Kennedy ve Russell Eberhart tarafından 1995 IEEE Uluslararası Sinir Ağları Konferansı'nda tanıtıldı ve doğrudan kuş sürüleri ve balık okullarındaki sosyal davranış simülasyon modellerinden yararlanıldı. Temel 1995 tarihli makale, algoritmanın merkezinde yer alan hız ve konum güncelleme denklemlerini oluşturdu. 1998'de Shi ve Eberhart, atalet ağırlığı parametresini hız güncellemesine dahil ederek yakınsama kontrolünü önemli ölçüde iyileştirdi ve sonraki araştırmalar tarafından benimsenen standart modifikasyon haline geldi. PSO, basitliği ve rekabetçi yakınsama hızı nedeniyle sürekli optimizasyon için genetik algoritmalara pratik bir alternatif olarak hızla ilgi gördü ve o zamandan beri mühendislik, makine öğrenmesi hiperparametre ayarı, sinyal işleme ve bilimsel modelleme alanlarında uygulanmıştır.
Ne zaman kullanılır?
PSO, uygunluk fonksiyonunun arama uzayının herhangi bir noktasında değerlendirilebildiği ancak türevlenemeyen, çok modlu veya analitik olarak hesaplanması pahalı olabilen sürekli optimizasyon problemleri için uygundur. Herhangi bir normal varsayımına ve minimum örneklem büyüklüğüne ihtiyaç duymaz, bu da onu alanlar arasında uygulanabilir kılar. Yöntem, arama uzayı sınırları önceden bilindiğinde, atalet ağırlığı ve ivme katsayıları dikkatlice ayarlandığında ve yeterli sayıda iterasyon ayrıldığında en iyi şekilde çalışır. İterasyon sayısı çok düşükse (önemsiz olmayan problemler için birkaç yüzden az), erken yakınsama olasıdır ve Bayes optimizasyonu daha güvenli bir alternatif olabilir.
Sınırlar ve dikkat edilmesi gerekenler
- Sürekli arama uzayları için tasarlanmıştır; modifikasyon olmadan ayrık veya kombinatoryal problemlere doğrudan uygulanamaz.
- Erken yakınsama bilinen bir risktir: atalet ağırlığı ve katsayılar kötü seçilirse sürü yerel bir optimum etrafında kümelenebilir.
- Yakınsama hızı ve çözüm kalitesi, atalet ağırlığı ve ivme katsayılarının seçimine duyarlıdır.
- Sonlu sayıda iterasyonda küresel optimumu bulma konusunda teorik bir garanti yoktur.
Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.
Güçlü yönleri
- Birçok popülasyon tabanlı yönteme kıyasla sürekli arama uzaylarında hızlı yakınsama.
- Ayarlanacak çok az parametre – öncelikle atalet ağırlığı ve iki ivme katsayısı.
- Gradyan veya türev bilgisi gerektirmez, bu da onu türevlenemeyen ve kara kutu uygunluk fonksiyonları için uygulanabilir kılar.
- Yüksek boyutlu sürekli problemlere doğal olarak ölçeklenir.
- Kavramsal olarak basittir ve uygulaması kolaydır.
Uygulama alanları
- Makine öğrenmesi modelleri için sürekli parametre uzaylarında hiperparametre ayarı.
- Mühendislik tasarımı optimizasyonu – yapısal, aerodinamik ve elektrik sistemi tasarımı.
- Sinir ağı ağırlık eğitimi ve mimari arama.
- Sinyal işleme ve anten tasarımı.
- Ekonomik sevkiyat ve güç sistemi optimizasyonu.
- Bilimsel ve simülasyon modellerinde parametre tahmini.
Nasıl çalışır?
Nasıl çalışır?
Parçacık sürüsü, tanımlanmış arama uzayında rastgele konumlara yerleştirilir ve her parçacığa rastgele bir başlangıç hızı atanır. Her parçacık ayrıca kişisel en iyi konumunu – şimdiye kadar karşılaştığı en iyi çözümü – kaydeder ve sürü, herhangi bir parçacık tarafından bulunan küresel en iyi konumu izler. Atalet ağırlığı, bilişsel katsayı ve sosyal katsayı, çalıştırma başlamadan önce ayarlanır, çünkü bunların dengesi, sürünün geniş çapta mı keşfedeceğini yoksa bilinen iyi bölgeleri mi sömüreceğini doğrudan yönetir.
Her parçacık için mevcut konumunda bir uygunluk fonksiyonu hesaplanır. Bu, probleme özgü tek adımdır: PSO, uygunluk fonksiyonunun formu üzerinde, sürekli arama uzayının herhangi bir noktasında değerlendirilebilmesi gerekliliği dışında herhangi bir kısıtlama getirmez. Her parçacığın kişisel en iyisi ve sürünün küresel en iyisi, yeni bir konum daha iyi bir uygunluk değeri sağladığında güncellenir.
Her parçacığın hızı üç bileşen kullanılarak güncellenir: atalet terimi (ölçeklenmiş önceki hız, momentumu teşvik eder), bilişsel terim (parçacığın kendi kişisel en iyisine doğru çekim) ve sosyal terim (sürünün küresel en iyisine doğru çekim). Yeni konum daha sonra güncellenmiş hızı mevcut konuma ekleyerek hesaplanır. Atalet ağırlığı, keşif ve sömürü arasındaki dengeyi kontrol eder: daha yüksek bir değer geniş keşfi desteklerken, daha düşük bir değer bilinen iyi bölgelerin ince taneli sömürüsünü teşvik eder.
Değerlendirme ve güncelleme adımları, belirtilen sayıda iterasyon için tekrarlanır. Sürü, giderek daha umut verici bölge etrafında aramasını daraltır. Çalışma, iterasyon sınırı aşıldığında sona erer, bu noktada küresel en iyi konum çözüm olarak raporlanır. Yeterli bir iterasyon sayısı – genellikle önemsiz olmayan problemler için en az birkaç yüz ila bin – sürünün yakınsamasına izin vermek için gereklidir; çok erken durmak, suboptimal bir sonuç döndürme riski taşır.
Sık yapılan hatalar
- Çok az iterasyon çalıştırmak – önemsiz olmayan problemler için yetersiz iterasyonlar, sürünün yakınsamasını engeller; hesaplama bütçesi çok kısıtlıysa Bayes optimizasyonunu tercih edin.
- Parçacıkların sonsuza dek keşfetmesini sağlayan ve yakınsamayı geciktiren çok yüksek bir atalet ağırlığı seçmek; çok düşük olması yerel bir optimum etrafında erken kümelenmeye neden olur.
- Arama uzayı sınırlarını göz ardı etmek – parçacıkların amaçlanan sınırların dışına sürüklenmesi ilgisiz bölgeleri keşfeder ve küresel en iyiyi bozar.
- PSO'yu adaptasyon olmadan ayrık veya kombinatoryal problemler için uygun olarak kabul etmek – standart hız ve konum güncelleme denklemleri sürekli bir alanı varsayar.
- Uygunluk ilerlemesi iterasyonlar boyunca izlenmezse erken yakınsama tespit edilemez; her zaman küresel en iyi uygunluğu iterasyon sayısına karşı izleyin.
Sık sorulan sorular
PSO, genetik algoritmadan nasıl farklıdır?
Her ikisi de optimizasyon için popülasyon tabanlı meta-sezgisel yöntemlerdir, ancak mekanizmalarında farklılık gösterirler. Genetik algoritma, biyolojik evrimden esinlenen seçilim, çaprazlama ve mutasyon operatörleri aracılığıyla bir popülasyonu geliştirir. PSO bunun yerine parçacıkları kişisel ve sosyal hafızaya dayalı olarak hızları güncelleyerek sürekli bir uzayda hareket ettirir – çaprazlama veya mutasyon yoktur. PSO tipik olarak ayarlanacak daha az parametreye sahiptir ve sürekli problemler üzerinde genellikle daha hızlı yakınsar, oysa genetik algoritmalar ayrık veya kombinatoryal uzaylara daha doğal bir şekilde uyarlanabilir.
Temel parametreler nelerdir ve nasıl ayarlanmalıdır?
Üç temel parametre, önceki hızın ne kadarının korunduğunu kontrol eden atalet ağırlığı (w), bir parçacığın kişisel en iyisine doğru çekimi ölçeklendiren bilişsel katsayı (c1) ve küresel en iyisine doğru çekimi ölçeklendiren sosyal katsayıdır (c2). Literatürden yaygın bir başlangıç noktası, w'nin yaklaşık 0.7–0.9, c1 ve c2'nin ise yaklaşık 1.5–2.0 olmasıdır. Atalet ağırlığı genellikle iterasyonlar boyunca doğrusal olarak azaltılır, böylece sürü başlangıçta keşiften daha sonra sömürüye doğru kaydırılır.
PSO ayrık veya kombinatoryal problemleri işleyebilir mi?
Standart PSO sürekli arama uzayları için tanımlanmıştır ve reel değerli koordinatları varsayan hız ve konum güncellemelerini uygular. İkili PSO gibi ayrık veya kombinatoryal varyantlar mevcuttur – ancak bunlar güncelleme denklemlerine önemli modifikasyonlar gerektirir. Rota belirleme veya zamanlama gibi tamamen kombinatoryal problemler için Karınca Kolonisi Optimizasyonu genellikle daha doğal bir seçimdir.
Sürünün erken yakınsadığını nasıl anlarım?
Küresel en iyi uygunluk değerini iterasyonlar boyunca izleyin. Eğri, iterasyon bütçesi tükenmeden uzun süre önce düzleşirse ve bildirilen çözüm tatmin edici değilse, muhtemelen erken yakınsama meydana gelmiştir. Yaygın çözümler arasında atalet ağırlığını artırmak, sürüyü yeni rastgele konumlardan yeniden başlatmak veya sürü boyutunu artırmak yer alır. Hesaplama bütçesi daha fazla iterasyona izin vermiyorsa, Bayes optimizasyonu daha verimli bir alternatif olabilir.
İlgili yöntemler
Kaynaklar
Kennedy, J. & Eberhart, R. (1995). Particle Swarm Optimization. IEEE International Conference on Neural Networks (ICNN), 1942-1948.
DOI kaynağını açKopyalandı.Shi, Y. & Eberhart, R. (1998). A Modified Particle Swarm Optimizer. IEEE Congress on Evolutionary Computation (CEC).
Yayın kaynağını açKopyalandı.