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

Çok Amaçlı Benzetimli Tavlama (MOSA)

Ortaya koyan
Serafini, P.; Czyzak, P. and Jaszkiewicz, A.
Yıl
1992–1998
Tür
Metaheuristic / Pareto-based optimizer
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ı Benzetimli Tavlama (MOSA), klasik benzetimli tavlama meta-sezgisini, birbiriyle çelişen iki veya daha fazla amaç fonksiyonu içeren problemlere genişletir.

Tek bir optimuma yakınsamak yerine, MOSA çözüm uzayını stokastik olarak keşfeder ve baskın olmayan (Pareto-optimal) çözümlerden oluşan bir arşiv tutar; bu sayede karar vericilere tek bir belirlenmiş yanıt yerine çeşitli bir ödünleşim cephesi sunar.

Yöntemin mantığı

Klasik benzetimli tavlama, yerel optimumlardan kaçmak için metallerin kontrollü soğutulmasını taklit eder — yüksek sıcaklıkta ara sıra daha kötü çözümleri kabul eder, ardından sıcaklık düştükçe daha seçici hale gelir. MOSA, bu aynı olasılıksal kaçış mekanizmasını eş zamanlı olarak birden fazla amaç üzerinde uygular. Bir aday çözüm bazı amaçları kötüleştirirken diğerlerini iyileştirirse, baskınlık mantığı bunun Pareto arşivine girip girmeyeceğini belirler. Soğutma programı rastgeleliği kademeli olarak azaltır ve aramayı Pareto sınırına yakın bölgelerde yoğunlaştırır. Sonuç, gradyan bilgisi veya dışbükeylik varsayımları gerektirmeden ulaşılan gerçek Pareto cephesinin bir yaklaşımıdır.

Tarih

Benzetimli tavlama, Kirkpatrick ve diğerleri tarafından 1983'te tanıtıldı. Serafini (1992), çoklu amaçlara genişletilmesini resmi olarak öneren ilk kişiler arasındaydı. Czyzak ve Jaszkiewicz (1998), Pareto arşivini merkezi çıktı yapısı olarak belirleyen ve bugün yaygın olarak benimsenen kabul kriteri formülasyonunu sağlayan Pareto Benzetimli Tavlama'yı (PSA) geliştirdi. MOSA o zamandan beri mühendislik tasarımı, çizelgeleme ve lojistikte uygulanmıştır.

Ne zaman kullanılır?

MOSA'yı, iki veya daha fazla çelişkili amaca ve sürekli veya kombinatoryal karar değişkenlerine sahip bir optimizasyon problemiyle karşılaştığınızda kullanın, özellikle amaç yüzeyi dışbükey olmayan, çok modlu veya gradyan içermeyen durumlarda. Tek bir ağırlıklı toplam yerine açık bir ödünleşim cephesinin daha faydalı olduğu çizelgeleme, rotalama, mühendislik tasarımı ve kaynak tahsisi problemlerine çok uygundur. Belirsizlik nicelemesi yerine optimizasyona ihtiyacınız olduğunda, tamamen stokastik Monte Carlo yöntemlerine göre MOSA'yı tercih edin. Problemin tek bir amacı olduğunda (klasik SA yeterlidir), Pareto cephesinin tam olarak bulunması gerektiğinde (küçük problemler için kesin algoritmalar daha iyidir), amaç sayısı kabaca beşten fazla olduğunda (hiperhacim tabanlı yöntemler daha iyi ölçeklenir) veya amaçların değerlendirilmesi çağrı başına son derece pahalı olduğunda (vekil tabanlı yöntemler tercih edilir) MOSA'yı KULLANMAYIN.

Sınırlar ve dikkat edilmesi gerekenler

  • Çözüm kalitesi ve Pareto cephesi kapsamı, başlangıç sıcaklığı, soğutma hızı ve komşuluk operatörü seçimine duyarlıdır, bu da probleme özgü ayarlama gerektirir.
  • Yüksek kaliteli bir Pareto cephesine yakınsama, birçok amaç değerlendirmesi gerektirebilir, bu da pahalı kara kutu simülasyonları için yavaş olmasına neden olur.
  • Pareto arşivini sürdürmek ve güncellemek ek yük getirir ve arşiv büyüyebilir, bu da bellek ve karşılaştırma maliyetlerini artırır.
  • Popülasyon tabanlı yöntemlerin (örneğin NSGA-II) aksine, temel MOSA'nın tek yörüngeli yapısı Pareto cephesinin düzensiz kapsamına neden olabilir.
  • Teorik yakınsama garantileri, pratik olmayan sonsuz yavaş bir soğutma programı gerektirir; sonlu programlar optimalite güvencesinden ödün verir.

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

Güçlü yönleri

  • Gradyan bilgisi gerektirmez ve dışbükey olmayan, süreksiz ve çok modlu amaç yüzeylerini ele alır.
  • Daha kötü çözümlerin olasılıksal kabulü, tamamen açgözlü yaklaşımları tuzağa düşüren yerel Pareto cephelerinden kaçışı sağlar.
  • Tek bir çalıştırmada tam Pareto cephesinin çeşitli bir yaklaşımını üretir, karar vericilere açık ödünleşim seçenekleri sunar.
  • Uygulaması basittir ve soğutma programı, keşif-sömürü dengesini ayarlamak için sezgisel bir parametre sağlar.
  • Minimum yeniden formülasyonla hem sürekli hem de kombinatoryal optimizasyon problemlerine uygulanabilir.

Uygulama alanları

  • Çok amaçlı iş-atölyesi ve akış-atölyesi çizelgeleme (üretim süresini ve gecikmeyi eş zamanlı olarak minimize etme)
  • Maliyet ve güvenilirlik amaçlarıyla ağ tasarımı ve rotalama problemleri
  • Mühendislik tasarım optimizasyonu (örneğin, yapısal bileşenlerde ağırlığı ve gerilimi minimize etme)
  • Beklenen getiriyi ve riski dengeleyen portföy optimizasyonu
  • Çelişen ekonomik ve çevresel amaçlarla arazi kullanımı ve mekansal planlama
  • Maliyet, kapsama ve hizmet kalitesini dengeleyen sağlık kaynak tahsisi

Nasıl çalışır?

Nasıl çalışır?

1

Başlangıç çözümü (rastgele veya sezgisel) oluşturun, geniş keşfe izin verecek kadar yüksek bir başlangıç sıcaklığı T_0 belirleyin, bulunan baskın olmayan çözümlerle Pareto arşivini başlatın ve durdurma kriterlerini (maksimum iterasyon sayısı veya minimum sıcaklık eşiği) tanımlayın.

2

Problemin yapısına uygun bir komşuluk operatörü (örneğin, yer değiştirme, ekleme veya sürekli değişkenler için Gauss pertürbasyonu) kullanarak mevcut çözümü bozun ve bir veya daha fazla aday komşu çözüm üretin.

3

Aday komşu için tüm amaç fonksiyonlarını değerlendirin. Mevcut çözüme ve Pareto arşivindeki çözümlere göre baskın olup olmadığını, baskın olup olmadığını veya baskın olmadığını belirleyin. Baskın olmayan adaylar arşive eklenir; baskın arşiv üyeleri kaldırılır.

4

Çok amaçlı bir kabul kriteri uygulayın. Eğer komşu, mevcut çözüme göre baskın değilse kabul edilir. Eğer baskınsa, P = exp(−ΔF / T) olasılığıyla yine de kabul edilebilir; burada ΔF amaçtaki bozulmayı toplar ve yerel Pareto cephelerinden kaçışı sağlar.

Formül
P(\text{accept}) = \exp\!\left(-\frac{\Delta f}{T}\right)
5

Soğutma programına göre sıcaklığı azaltın, genellikle geometrik: T_{k+1} = α · T_k, α ∈ (0.8, 0.99) ile. Daha düşük sıcaklıklar, daha kötü hareketlerin kabulünü daraltır ve Pareto cephesinin umut vadeden bölgelerine yakın aramayı giderek yoğunlaştırır.

Formül
T_{k+1} = \alpha \cdot T_k, \quad \alpha \in (0,1)
6

Nihai Pareto arşivini sonuç olarak döndürün. Birikmiş olabilecek baskın çözümleri budamak için son işlem yapın ve arşivi, karar vericinin seçimi için Pareto-optimal cephesinin ayrık bir yaklaşımı olarak sunun.

Sık yapılan hatalar

  • Başlangıç sıcaklığının çok düşük ayarlanması, Pareto cephesinin yerel bir bölgesine erken yakınsamaya neden olur; başlangıç kabul oranının %70-90 civarında olması için T_0'ı her zaman kalibre edin.
  • Soğutma hızı α'yı 1.0'a çok yakın kullanmak, çalıştırmayı aşırı derecede uzatır; 0'a çok yakın olması, Pareto cephesi yeterince keşfedilmeden hızlı yakınsamaya neden olur.
  • Kabul olasılığı için ΔF'yi amaç farklılıklarının basit bir toplamıyla tanımlamak, karşılaştırılamaz ölçekleri karıştırır — toplama öncesinde her amacı normalleştirin.
  • Arşivden baskın çözümleri periyodik olarak kaldırmamak, arşivi şişirir ve nihai çıktının kalitesini düşürür.
  • Stokastik varyasyon göz önüne alındığında, tek bir çalıştırmadaki başarıyı değerlendirmek yanıltıcıdır; sonuçları her zaman birden fazla bağımsız çalıştırma üzerinden birleştirin.

Sık sorulan sorular

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

NSGA-II, çaprazlama, mutasyon ve baskın olmayan sıralama kullanarak bir çözüm kümesini eş zamanlı olarak geliştiren popülasyon tabanlı bir evrimsel algoritmadır. MOSA, olasılıksal hareketler kullanarak bir seferde bir çözümü keşfeden yörünge tabanlı bir yöntemdir. MOSA'nın uygulanması daha basit olma eğilimindedir ve kombinatoryal problemler için iyi çalışırken, NSGA-II genellikle sürekli problemler için daha iyi Pareto cephesi kapsamı sağlar ve daha öngörülebilir şekilde ölçeklenir.

Başlangıç sıcaklığı T_0'ı nasıl ayarlamalıyım?

Yaygın bir sezgisel, kısa bir ön faz çalıştırmak ve rastgele komşu hareketlerinin yaklaşık %80'inin kabul edildiği bir T_0 seçmektir. Bu, başlangıçta geniş keşfi sağlar. Amaç fonksiyonu farklılıklarının büyüklüğüne bağlı olarak uygun sıcaklık ölçeği değiştiği için probleme özgü kalibrasyon tavsiye edilir.

MOSA ikiden fazla amacı ele alabilir mi?

Evet, ancak amaç sayısı arttıkça performans düşer. Pareto arşiv yönetimi maliyeti artar ve baskın olmayan çözümlerin oranı hızla büyür, bu da kabul kriterini daha az ayırt edici hale getirir. Dört veya beşten fazla amacı olan problemler için, hiperhacim gösterge tabanlı veya ayrıştırma tabanlı yöntemler (örneğin, MOEA/D) genellikle tercih edilir.

Algoritmayı ne zaman durduracağımı nasıl anlarım?

Yaygın durdurma kriterleri arasında minimum sıcaklığa ulaşma, maksimum iterasyon bütçesini tüketme veya belirli sayıda iterasyon boyunca Pareto arşivinin hiperhacim göstergesinde iyileşme gözlemlememe yer alır. Pratikte, farklı iterasyon bütçelerinde birden fazla çalıştırmanın arşiv kalitesini karşılaştırmak, yakınsamayı teşhis etmenin güvenilir bir yoludur.

MOSA pahalı simülasyon modelleri için uygun mudur?

Genellikle modifikasyon olmadan uygun değildir. Her iterasyon en az bir amaç fonksiyonu değerlendirmesi gerektirir ve MOSA genellikle iyi bir Pareto cephesi yaklaşımı için binlerce iterasyona ihtiyaç duyar. Her değerlendirme pahalı bir simülasyon içerdiğinde, MOSA'nın vekil destekli versiyonları (amaçları yaklaştırmak için metamodeller kullanarak) tercih edilir.

İlgili yöntemler

Kaynaklar

  1. Czyzak, P., Jaszkiewicz, A. (1998). Pareto simulated annealing — a metaheuristic technique for multiple-objective combinatorial optimization. Journal of Multi-Criteria Decision Analysis, 7(1), 34–47.

    DOI kaynağını aç
    Kopyalandı.
  2. Serafini, P. (1992). Simulated annealing for multi-objective optimization problems. In Proceedings of the Tenth International Conference on Multiple Criteria Decision Making, Taipei, Taiwan, pp. 87–96.

    Yayın kaynağını aç
    Kopyalandı.