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

Çok Amaçlı Tabu Araması (MOTS) — Pareto-optimal çözümler için Metaheuristik

Ortaya koyan
Hansen, M. P.; building on Glover (1989) Tabu Search
Yıl
1997
Tür
Metaheuristic multi-objective optimization
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ı Tabu Araması (MOTS), iki veya daha fazla çelişen amaç fonksiyonunu eş zamanlı olarak optimize etmek için klasik Tabu Araması çerçevesini genişleten bir metaheuristik algoritmadır.

Tek bir optimum yerine, Pareto cephesini — bir amaca yönelik iyileştirmenin diğerini kötüleştirmeden yapılamadığı çözüm kümesini — yaklaştırmayı hedefler, bu da onu mühendislik, lojistik ve operasyon araştırmalarındaki karmaşık kombinatoryal ve sürekli optimizasyon problemleri için uygun hale getirir.

Yöntemin mantığı

Birçok tepenin ve vadinin olduğu engebeli bir araziyi keşfettiğinizi hayal edin, ancak farklı arazileri (her amaç için bir tane) gösteren ve birbirleriyle çelişen birkaç haritanız var. MOTS, döngüden kaçınmak için yakın zamanda ziyaret edilen yerlerin kısa süreli bir bellek listesini (tabu listesi) tutarak ve şimdiye kadar bulunan baskın olmayan çözümlerin bir arşivini tutarak bu alanda komşu çözümlere hareket ederek gezinir. Periyodik olarak, stratejik çeşitlendirme, umut vadeden alanların sömürülmesini küresel keşifle dengeleyerek Pareto cephesinin keşfedilmemiş bölgelerine aramayı yönlendirir.

Tarih

Çok Amaçlı Tabu Araması, Fred Glover tarafından 1989'da tanıtılan tek amaçlı Tabu Araması'nı genişletir. Pareto arşivini ve çok amaçlı beklenti kriterlerini içeren ilk sistematik MOTS formülasyonu, M. P. Hansen tarafından 1997 MCDM konferansında sunulmuştur. Gandibleux, Teghem ve diğerlerinin sonraki çalışmaları, kombinatoryal problemler için varyantları biçimlendirmiş ve MOTS o zamandan beri çizelgeleme, lojistik ve mühendislik tasarımı alanlarında evrimsel çok amaçlı algoritmalara rekabetçi bir alternatif olarak uygulanmıştır.

Ne zaman kullanılır?

Maliyet ve kalite, zaman ve risk gibi iki veya daha fazla çelişen amacı olan kombinatoryal veya karma tamsayılı bir optimizasyon problemiyle karşılaştığınızda ve kesin yöntemler hesaplama açısından çözülemez olduğunda MOTS'u kullanın. Kapsamlı listeleme için arama alanı çok büyük olan çizelgeleme, araç rotalama, ağ tasarımı ve portföy seçimi problemlerinde üstündür. Komşuluk yapısının anlamlı olduğu ve hareket operatörlerinin temiz bir şekilde tanımlanabildiği durumlarda, tamamen rastgele aramaya göre MOTS'u tercih edin. MOTS'u KULLANMAYIN: problem tek bir amaca sahipse (basit Tabu Araması yeterlidir); Pareto cephesi kesin olarak listelenebiliyorsa; gradyan bilgisi mevcutsa ve arazi dışbükeyse (bunun yerine matematiksel programlama kullanın); veya gerçek zamanlı kararlar stokastik varyasyon olmadan deterministik, tekrarlanabilir çıktılar gerektiriyorsa.

Sınırlar ve dikkat edilmesi gerekenler

  • Performans, tabu listesi uzunluğu, komşuluk tanımı ve çeşitlendirme stratejisine oldukça duyarlıdır — dikkatli parametre ayarı gerektirir.
  • Gerçek Pareto cephesine yakınsama garantisi yoktur; çözüm kalitesi çalıştırma uzunluğuna ve problem yapısına bağlıdır.
  • Komşuluklar büyük olduğunda veya amaç değerlendirmeleri maliyetli olduğunda, yineleme başına hesaplama açısından pahalıdır.
  • Pareto arşivini sürdürmek ve güncellemek, amaç sayısı ve arşiv boyutu büyüdükçe pahalı hale gelebilir.
  • Paralel uygulama, tabu mekanizmasının sıralı belleğe dayalı doğası nedeniyle önemsizdir.

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

Güçlü yönleri

  • Tabu listesi aracılığıyla yakın zamanda ziyaret edilen çözümlerden tekrar ziyaret etmeyi önler, karmaşık arazilerde döngü riskini azaltır.
  • Beklenti kriterleri, bir hareket olağanüstü bir iyileştirmeye yol açtığında tabu kısıtlamalarının geçersiz kılınmasına izin vererek, belleği esneklikle dengeler.
  • Gradyan bilgisi gerektirmez, bu da onu türevlenemeyen, ayrık veya kara kutu amaç fonksiyonlarına uygulanabilir hale getirir.
  • Tek bir çalıştırmada tüm Pareto cephesinin bir yaklaşımını üretir, çok kriterli karar vermeyi destekler.
  • Esnek komşuluk ve hareket operatörü tasarımı, probleme özgü özelleştirmeye olanak tanır.
  • Çeşitlendirme mekanizmaları, yerel optimumlardan kaçmayı ve daha iyi Pareto cephesi kapsamını sağlar.

Uygulama alanları

  • Çok amaçlı araç rotalama ve lojistik çizelgeleme (maliyeti ve teslimat süresini eş zamanlı olarak en aza indirme)
  • İki amaçlı proje çizelgeleme: öncelik kısıtlamaları altında bitirme süresini ve kaynak maliyetini en aza indirme
  • Portföy optimizasyonu: birden fazla varlık sınıfı arasında beklenen getiriyi riskle dengeleme
  • Ağ tasarımı: kurulum maliyetini en aza indirirken güvenilirliği veya verimi en üst düzeye çıkarma
  • İmalat süreci planlaması: döngü süresini, enerji kullanımını ve kalite metriklerini ortaklaşa optimize etme
  • Çevresel yönetim: ekonomik çıktıyı kirlilik veya ekolojik etkiyle dengeleme

Nasıl çalışır?

Nasıl çalışır?

1

Aramayı bir veya daha fazla başlangıç çözümüyle (rastgele oluşturulmuş veya sezgisel olarak oluşturulmuş) başlatın. Sabit uzunlukta L'lik boş bir tabu listesi ayarlayın ve başlangıç popülasyonundan baskın olmayan çözümlerle Pareto arşivini başlatın.

2

Hareket operatörlerini (değiştirmeler, eklemeler, pertürbasyonlar) uygulayarak mevcut çözüm s'nin komşuluk N(s)'sini oluşturun. İlerleme adaylarını belirlemek için her komşu çözümü her amaç fonksiyonu üzerinde değerlendirin.

3

Tabu filtresini uygulayın: tanımlayıcı hareketleri tabu listesinde görünen komşuları, bir beklenti kriterini — tipik olarak komşunun mevcut tüm arşiv üyelerini baskınlaması veya en az bir amaç üzerindeki bilinen en iyi değeri iyileştirmesi — karşılamadıkça hariç tutun. Bu, döngüyü önler ve keşfi zorlar.

4

Bir sonraki mevcut çözüm olarak en iyi tabu olmayan komşuyu (veya beklenti kriteri kazananını) seçin. Yeni çözüm baskın değilse ekleyerek Pareto arşivini güncelleyin; yeni girdinin baskınladığı herhangi bir arşiv üyesini kaldırın.

5

Arama tıkandığında çeşitlendirme stratejileri uygulayın: uzun vadeli frekans belleği nadiren ziyaret edilen bölgeleri belirler; Pareto cephesinin kapsamını genişletmek için seçkin arşiv çözümlerinden veya rastgele pertürbe edilmiş çözümlerden yeniden başlatın.

6

Bir durdurma kriteri karşılanana kadar — tipik olarak maksimum sayıda yineleme, fonksiyon değerlendirmesi veya geçen CPU süresi — komşuluk, filtre ve arşiv adımlarını tekrarlayın. Yaklaşık Pareto-optimal cephe olarak Pareto arşivini döndürün.

Sık yapılan hatalar

  • Tabu listesini çok kısa ayarlamak döngüye neden olur; çok uzun ayarlamak aramayı aşırı kısıtlar ve iyi çözümleri kaçırır — ampirik kalibrasyon esastır.
  • Çeşitlendirmeyi ihmal etmek, Pareto cephesinin bir bölgesinde erken yakınsamaya yol açar, bu da zayıf bir yaklaşım üretir.
  • MOTS'u üçten fazla amaçla kullanmak performansı düşürür çünkü arşiv yönetimi ve çeşitlilik bakımı hesaplama açısından külfetli hale gelir; çok amaçlı problemler için ayrıştırma tabanlı yöntemler düşünülmelidir.
  • Probleme özgü tasarıma sahip olmayan genel hareket operatörleri kullanmak, özel uygulamalara kıyasla çözüm kalitesini ciddi şekilde sınırlar.
  • Yakınsama geçmişini incelemeden yalnızca son arşivi raporlamak, erken durgunluğu gizleyebilir.

Sık sorulan sorular

MOTS, tabu listesini birden fazla amaç olduğunda nasıl ele alır?

Tabu listesi çözümleri değil, hareketleri depolar, bu nedenle tek amaçlı Tabu Araması ile aynı şekilde çalışır. Temel fark, tabu olmayan komşular arasındaki seçimin çok amaçlı baskınlık veya bir skalerleştirme fonksiyonu kullanması ve beklenti kriterinin, bir hareketin mevcut tüm arşiv üyeleri tarafından baskınlanmayan bir çözüme yol açması durumunda tabu bir harekete izin verecek şekilde yeniden tanımlanmasıdır.

Pareto arşivi nedir ve ne kadar büyük olmalıdır?

Pareto arşivi, arama sırasında bulunan tüm baskın olmayan çözümleri depolar. Bellek ve güncelleme maliyetini yönetilebilir tutmak için maksimum boyutu genellikle sınırlıdır (örneğin, 100-500 çözüm). Arşiv dolduğunda, kalabalık mesafesi veya ızgara tabanlı budama, çeşitliliği korumak için aşırı kalabalık bölgelerden çözümleri kaldırır.

MOTS, çok amaçlı problemler için NSGA-II ile nasıl karşılaştırılır?

NSGA-II, çaprazlama ve mutasyon ile popülasyon tabanlı bir evrimsel yaklaşım kullanır, bu da onu aramanın başlarında küresel keşif için daha iyi hale getirir. MOTS, genellikle daha ince yerel arama kalitesi veren komşuluk hareketlerine ve belleğe dayanır. Uygulamada, MOTS genellikle güçlü komşuluk yapısına sahip kombinatoryal problemler üzerinde daha iyi performans gösterirken, NSGA-II sürekli problemler için daha yaygın olarak kullanılır.

Tipik olarak kaç yineleme gereklidir?

Evrensel bir kural yoktur. Yaygın uygulama, yinelemeler yerine fonksiyon değerlendirmelerine bütçe ayırmaktır — tipik olarak problem boyutuna bağlı olarak 10.000 ila 100.000 değerlendirme — ve çözüm kalitesini ve Pareto cephesi kararlılığını değerlendirmek için birden fazla bağımsız başlangıç çalıştırmaktır.

MOTS, ikiden fazla amacı işleyebilir mi?

Evet, ancak amaç sayısı üçü aştıkça etkinlik azalır (amaç uzayında 'boyutsallık laneti'). Dört veya daha fazla amaç için arşiv boyutu patlar ve çeşitlilik bakımı zorlaşır; ayrıştırma tabanlı veya gösterge tabanlı yaklaşımlar genellikle tercih edilir.

İlgili yöntemler

Kaynaklar

  1. Hansen, M. P. (1997). Tabu search for multiobjective optimization: MOTS. Presented at the 13th International Conference on Multiple Criteria Decision Making (MCDM), Cape Town, South Africa.

    Yayın kaynağını aç
    Kopyalandı.
  2. Glover, F. (1989). Tabu Search — Part I. ORSA Journal on Computing, 1(3), 190–206.

    DOI kaynağını aç
    Kopyalandı.