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

Çok Amaçlı Parçacık Sürü Optimizasyonu (MOPSO)

Ortaya koyan
Coello Coello, C. A., Pulido, G. T., & Lechuga, M. S.
Yıl
2004
Tür
Population-based swarm metaheuristic
Aile
Simulation / optimization

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

Yazı boyutu

Ne işe yarar?

Çok Amaçlı Parçacık Sürü Optimizasyonu (MOPSO), orijinal Parçacık Sürü Optimizasyonu'nu (PSO) birden fazla çelişen amaç fonksiyonunu eş zamanlı olarak ele alacak şekilde genişleten bir sürü zekası meta-sezgisidir.

Harici bir Pareto arşivi tutar ve önsel tercih bilgisine ihtiyaç duymadan aday çözümler popülasyonunu gerçek Pareto cephesine doğru yönlendirmek için baskınlık tabanlı seçimi kullanır.

Yöntemin mantığı

Farklı yüksekliklerdeki birden fazla tepeye sahip bir arazide topluca yiyecek arayan bir kuş sürüsü hayal edin; bu tepelerin hepsi aynı anda tırmanılamaz — bir tepede irtifa kazanmak genellikle diğerinde zemin kaybetmek anlamına gelir. MOPSO, bu çok boyutlu ödünleşim uzayında bir parçacık sürüsü başlatır. Her parçacık kendi en iyi baskın olmayan konumunu hatırlar ve şimdiye kadar bulunan küresel olarak en iyi baskın olmayan çözümlerin harici bir arşivinden öğrenir. Kişisel hafıza, sosyal öğrenme ve kontrollü rastgeleliği harmanlayarak, sürü, tek bir uzlaşma yerine verimli ödünleşimlerin tüm spektrumunu ortaya koyarak tam Pareto cephesini aşamalı olarak haritalandırır.

Tarih

Parçacık Sürü Optimizasyonu, kuş sürülerinin sosyal davranışlarından esinlenerek Kennedy ve Eberhart tarafından 1995 yılında tanıtıldı. İlk yaygın olarak benimsenen çok amaçlı uzantı olan MOPSO, 2004 yılında Coello Coello, Pulido ve Lechuga tarafından harici bir Pareto arşivi ve hiperküp tabanlı lider seçimi sunularak önerildi. OMOPSO, dMOPSO ve SMPSO dahil olmak üzere sonraki varyantlar, arşiv yönetimini, adaptif parametreleri ve kısıt işlemeyi iyileştirerek MOPSO'yu NSGA-II ile birlikte ana akım bir Pareto cephesi yaklaştırma algoritması olarak konumlandırdı.

Ne zaman kullanılır?

MOPSO'yu, iki veya daha fazla çelişen amaca sahip sürekli bir optimizasyon problemiyle karşılaştığınızda ve tek bir çözüm yerine tam Pareto cephesini yaklaştırmanız gerektiğinde kullanın. Amaç değerlendirmelerinin orta derecede pahalı olduğu ve karar uzayının sürekli olduğu mühendislik tasarımı, tedarik zinciri, enerji sistemleri ve hiperparametre ayarlamasında üstündür. Kombinatoryal veya karma-tamsayı problemleri için NSGA-II veya NSGA-III'ü tercih edin ve amaçlar düzgün ve türevlenebilir olduğunda gradyan tabanlı çok amaçlı yöntemleri tercih edin. Amaç sayısı beş ila yediyi aştığında MOPSO kullanmayın — çok amaçlı problemler özel çok amaçlı algoritmalar (örneğin, NSGA-III, MOEA/D) gerektirir. Ayrıca, her fonksiyon değerlendirmesi aşırı derecede pahalı olduğunda (100'den az değerlendirme mevcut olduğunda) kaçının — bu durumda vekil destekli yöntemler tercih edilir.

Sınırlar ve dikkat edilmesi gerekenler

  • Performans atalet ağırlığı (w) ve ivme katsayılarına (c1, c2) duyarlıdır; kötü ayarlanmış parametreler erken yakınsamaya veya aşırı sürüklenmeye neden olur.
  • Arşiv yönetimi ve lider seçimi, probleme bağımlı ek hiperparametreler (arşiv boyutu, kalabalıklaşma metriği) getirir.
  • Yakınsama ve çeşitlilik garantileri sezgiseldir, matematiksel değildir — yaklaştırılmış Pareto cephesi, gerçek cephenin bölgelerini kaçırabilir.
  • Baskınlık tabanlı seçimde boyutluluk laneti nedeniyle beş ila yedi'den fazla amaçla mücadele eder.
  • Probleme özgü kodlama ve hız sınırlama adaptasyonları olmadan ayrık veya kombinatoryal arama uzaylarına doğrudan uygulanamaz.

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

Güçlü yönleri

  • Tek bir çalıştırmada tam Pareto cephesini doğal olarak yaklaştırır, karar vericilere zengin bir verimli ödünleşim çözümleri kümesi sunar.
  • Gradyan bilgisi gerektirmez, bu da onu türevlenemeyen, gürültülü veya kara kutu amaç fonksiyonlarına uygulanabilir kılar.
  • Basit hız-konum güncelleme mekanizması hesaplama açısından hafiftir ve paralel olarak uygulanması kolaydır.
  • Harici Pareto arşivi, arama boyunca bulunan en iyi çözümleri korur, yüksek kaliteli baskın olmayan noktaların kaybını önler.
  • Esnek çerçeve, kısıt işleme, adaptif parametre kontrolü ve yerel arama ile hibridizasyonu barındırır.

Uygulama alanları

  • Çok amaçlı mühendislik tasarımı: yapısal ve mekanik bileşenlerde ağırlık, maliyet ve gerilimin eş zamanlı minimizasyonu.
  • Enerji sistemleri: elektrik şebekesi planlaması ve yenilenebilir enerji planlamasında maliyet, güvenilirlik ve emisyonlar arasındaki Pareto-optimal ödünleşimler.
  • Tedarik zinciri yönetimi: çok kademeli ağlarda hizmet seviyesi, envanter maliyeti ve teslim süresinin ortak optimizasyonu.
  • Makine öğrenimi hiperparametre ayarlaması: model doğruluğunu çıkarım süresi veya bellek ayak izi ile dengeleme.
  • Su kaynakları yönetimi: enerji üretimi, sel kontrolü ve ekolojik akışın çelişen amaçları için rezervuar salım politikalarını optimize etme.
  • Portföy optimizasyonu: finansal varlık tahsisi için beklenen getiriye karşı riskin verimli sınırını yaklaştırma.

Nasıl çalışır?

Nasıl çalışır?

1

Karar uzayında rastgele konum ve hızlara sahip N parçacıklı bir popülasyon oluşturun. Her parçacık için tüm amaç fonksiyonlarını değerlendirin ve harici Pareto arşivini tüm baskın olmayan başlangıç çözümleriyle doldurun. Her parçacığa başlangıç konumuna eşit bir kişisel en iyi (pbest) atayın.

2

Mevcut sürüdeki her parçacık için tüm amaç fonksiyonu değerlerini hesaplayın. Baskınlık karşılaştırmalarını uygulayın: eğer x tüm amaçlarda daha kötü değilse ve en az birinde kesinlikle daha iyiyse, x çözümü y'ye baskın gelir. Yeni konum depolanan kişisel en iyiye baskın gelirse veya ona göre baskın değilse, her parçacığın pbest'ini güncelleyin.

3

Tüm yeni baskın olmayan çözümleri harici arşive ekleyin. Artık yeni gelenler tarafından baskın kılınan arşiv üyelerini kaldırın. Eğer arşiv kapasite sınırını aşarsa, Pareto cephesi yaklaşımında çeşitliliği korumak için yoğunluk tabanlı bir budama stratejisi (örneğin, hiperküp kalabalıklaşması veya en yakın komşu mesafesi) uygulayın.

4

Her parçacık için harici arşivden küresel en iyi bir lider (gbest) seçin. Lider genellikle kalabalıklaşma mesafesine dayalı bir turnuva veya rulet mekanizması kullanılarak daha az kalabalık arşiv bölgelerinden seçilir, bu da sürünün tek bir bölgeye erken yakınsama yerine az keşfedilmiş Pareto cephesi segmentlerine çekilmesini sağlar.

5

Her parçacık için hız ve konumu PSO güncelleme kuralını kullanarak güncelleyin: v = w*v + c1*r1*(pbest - x) + c2*r2*(gbest - x), burada w keşif/sömürü dengesini kontrol eden atalet ağırlığı, c1 ve c2 bilişsel ve sosyal ivme katsayıları, r1 ve r2 ise tekdüze rastgele sayılardır. Parçacıkları uygulanabilir karar uzayında tutmak için sınır işlemeyi uygulayın.

Formül
v_{id}^{t+1} = w v_{id}^t + c_1 r_1 (pbest_{id} - x_{id}^t) + c_2 r_2 (gbest_d - x_{id}^t)
6

Bir durdurma kriteri karşılanana kadar (maksimum iterasyon, maksimum fonksiyon değerlendirmesi veya Pareto cephesi durgunluğu) değerlendir–güncelle-arşivle–liderleri seç–parçacıkları hareket ettir adımlarını tekrarlayın. Son harici arşivi yaklaştırılmış Pareto-optimal küme olarak döndürün; karar verici daha sonra tercih edilen bir ödünleşim çözümünü seçmek için bunu inceler.

Sık yapılan hatalar

  • Arşiv kapasitesini çok küçük ayarlamak, Pareto cephesi çeşitliliğini yok eden agresif budamaya neden olur; çok büyük olması lider seçimini yavaşlatır ve bellek maliyetini artırır.
  • Tüm sürü için tek bir küresel en iyi lider kullanmak erken yakınsamaya yol açar; her zaman çeşitlilik odaklı bir lider seçim mekanizması kullanın (örneğin, kalabalıklaşma mesafesi turnuvası).
  • Sınır işlemeyi ihmal etmek, parçacıkların uygulanabilir bölgeden kaçmasına izin verir, bu da arşivi kirleten uygulanamaz çözümler üretir.
  • Yalnızca nihai arşivi yakınsama ve çeşitlilik metrikleri (örneğin, hiperhacim göstergesi, jenerasyonel mesafe) olmadan raporlamak, çalıştırmalar veya yöntemler arasında sonuçları karşılaştırmayı imkansız hale getirir.
  • MOPSO'yu, problem amaçlarının gerçekten çelişkili olduğunu doğrulamadan bir kara kutu optimize edici olarak ele almak — eğer amaçlar hizalıysa, standart tek amaçlı PSO veya gradyan inişi yeterlidir.

Sık sorulan sorular

MOPSO, NSGA-II'den nasıl farklıdır?

Her ikisi de bir çözüm popülasyonu ve baskınlık tabanlı seçim kullanarak Pareto cephesini yaklaştırır, ancak mekanik olarak farklılık gösterirler. NSGA-II, kalabalıklaşma mesafesi sıralaması ile birleştirilmiş ebeveyn-yavru popülasyonu üzerinde çaprazlama ve mutasyon operatörleri kullanır. MOPSO, kişisel ve arşiv tabanlı liderler tarafından yönlendirilen hız tabanlı parçacık hareketi kullanır. MOPSO, sürekli uzaylar için genellikle iterasyon başına daha hızlıdır; NSGA-II, permütasyon ve kombinatoryal problemlere daha doğal olarak uygundur.

Hangi arşiv boyutunu kullanmalıyım?

İki veya üç amaçlı problemler için yaygın bir varsayılan 100-200 çözümdür. Daha büyük arşivler Pareto cephesi kapsamını iyileştirir ancak lider seçimini yavaşlatır. Dört veya daha fazla amaçlı problemler için arşiv boyutu, Pareto cephesinin beklenen karmaşıklığı ile ölçeklenmelidir; adaptif arşiv yönetim şemaları yardımcı olabilir.

MOPSO kısıtlamaları ele alabilir mi?

Evet, ceza fonksiyonları, uygulanabilirlik kuralları (baskınlık karşılaştırmalarında uygulanamaz çözümlere göre uygulanabilir çözümleri tercih etme) veya onarım operatörleri aracılığıyla. Coello Coello'nun orijinal formülasyonu, uygulanabilirlik turnuvalarına dayalı basit bir kısıt işleme mekanizması içerir.

MOPSO kaç amaç fonksiyonunu etkili bir şekilde ele alabilir?

MOPSO, iki ila dört amaç için iyi çalışır. Beş ila yedi amacın ötesinde, baskınlık baskısı drastik olarak zayıflar — neredeyse tüm çözümler karşılıklı olarak baskın olmayan hale gelir — ve özel çok amaçlı optimize ediciler (NSGA-III, MOEA/D veya ayrıştırma tabanlı yöntemler) standart MOPSO'dan daha iyi performans gösterir.

MOPSO sonuçlarını değerlendirmek için hangi metrikleri kullanmalıyım?

Hiperhacim göstergesini (yaklaştırılmış cephe tarafından baskın kılınan amaç uzayının hacmini ölçer — daha yüksek daha iyidir), jenerasyonel mesafeyi (bir referans Pareto cephesine yakınlık) ve yayılım veya delta metriklerini (dağılım tekdüzeliği) raporlayın. Güvenilir kıyaslama için istatistiksel karşılaştırma ile birden fazla bağımsız çalıştırma gereklidir.

İlgili yöntemler

Kaynaklar

  1. Coello Coello, C. A., Pulido, G. T., & Lechuga, M. S. (2004). Handling multiple objectives with particle swarm optimization. IEEE Transactions on Evolutionary Computation, 8(3), 256–279.

    DOI kaynağını aç
    Kopyalandı.
  2. Kennedy, J., & Eberhart, R. (1995). Particle swarm optimization. Proceedings of the IEEE International Conference on Neural Networks (ICNN), Perth, Australia, 4, 1942–1948.

    DOI kaynağını aç
    Kopyalandı.