Çok Amaçlı Tabu Araması (MOTS) — Pareto-optimal çözümler için Metaheuristik
Multi-objective Tabu Search (MOTS) — Metaheuristic optimization for multiple conflicting objectives · Ayrıca şöyle bilinir: MOTS, Multi-criteria Tabu Search, Pareto Tabu Search, TSMOO
Ç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.
Tam yöntemi oku
Bu bölümü okumak için ücretsiz hesapla giriş yapın.
Yöntem haritası
İlişkili yöntemlerin komşuluğu — keşfetmek için bir düğüm seçin.
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.
Güçlü yönler & sınırlılıklar
- 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.
- 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.
SSS
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.
Kaynaklar
- 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. link ↗
- Glover, F. (1989). Tabu Search — Part I. ORSA Journal on Computing, 1(3), 190–206. DOI: 10.1287/ijoc.1.3.190 ↗
Bu sayfayı kaynak gösterin
ScholarGate. (2026, June 3). Multi-objective Tabu Search (MOTS) — Metaheuristic optimization for multiple conflicting objectives. ScholarGate. https://scholargate.app/tr/simulation/multi-objective-tabu-search
Hangi yöntem?
Bu yöntemi en yakın akrabalarının yanına koyup yan yana okuyun — kütüphane kitapları masaya serer; seçim sizindir.
- Çok Amaçlı Karınca Kolonisi Optimizasyonu (ÇAKKO)Simülasyon↔ karşılaştır
- Çok Amaçlı Genetik Algoritma (MOGA)Simülasyon↔ karşılaştır
- Çok Amaçlı Parçacık Sürü Optimizasyonu (MOPSO)Simülasyon↔ karşılaştır
- Çok Amaçlı Benzetimli Tavlama (MOSA)Simülasyon↔ karşılaştır
- Tabu SearchOptimizasyon↔ karşılaştır