Ajan Tabanlı Tabu Arama — Dağıtık Çoklu Ajan Meta-Sezgisel Optimizasyon
- Ortaya koyan
- Glover, F. (tabu search); multi-agent extension by various researchers in the 1990s–2000s
- Yıl
- 1989–1995
- Tür
- Hybrid metaheuristic — agent-based distributed tabu search
- Aile
- Simulation / optimization
Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku
Ne işe yarar?
Ajan Tabanlı Tabu Arama (ABTA), tabu arama meta-sezgisini, her biri bağımsız veya işbirliği yapan tabu arama iş parçacıkları çalıştıran otonom ajanlardan oluşan bir çoklu ajan çerçevesine yerleştirir; bu ajanlar, yerel optimumlardan kaçmak ve büyük kombinatoryal veya sürekli arama uzaylarını tek iş parçacıklı bir uygulamadan daha etkili bir şekilde keşfetmek için umut vadeden çözümleri paylaşır.
Yöntemin mantığı
Klasik tabu arama, kısa süreli bellek mekanizmasına rağmen dar bir bölgeyi keşfetmekte takılıp kalabilir. Birden fazla otonom ajan konuşlandırarak, her biri kendi tabu listesini ve komşuluk yapısını koruyarak, arama çeşitli başlangıç noktalarına yayılır. Ajanlar periyodik olarak seçkin çözümleri paylaşır (yoğunlaştırma) ve kasıtlı olarak keşfedilmemiş bölgelere dağılır (çeşitlendirme). Bu işbirlikçi ancak bağımsız yapı, biyolojik sürü davranışını yansıtır — tek bir ajan tam resmi görmez, ancak topluluk, herhangi bir bireysel arayıcıdan çok daha hızlı yüksek kaliteli çözümler bulur.
Tarih
Tabu arama, Fred Glover tarafından 1986–1989 yıllarında biçimlendirilmiştir. Dağıtık ve paralel varyantlar, araştırmacılar çoklu işlemci mimarilerinden yararlanmaya çalıştıkça 1990'ların başında ortaya çıktı. Verhoeven ve Aarts (1995), işbirlikçi tabu stratejileri de dahil olmak üzere paralel yerel arama üzerine sistematik bir çalışma sundu. Ajan tabanlı çerçeveleme, ajan tabanlı modelleme kelime dağarcığının operasyon araştırmasına girmesiyle 2000'lerde öne çıktı.
Ne zaman kullanılır?
Zorlu kombinatoryal veya karışık tamsayılı optimizasyon problemlerini (çizelgeleme, rotalama, ağ tasarımı, kaynak tahsisi) çözerken, tek iş parçacıklı tabu aramanın tıkandığı ve paralel hesaplama kaynaklarının mevcut olduğu durumlarda Ajan Tabanlı Tabu Arama'yı kullanın. Özellikle arama manzarasının benzer kalitede birçok yerel optimuma sahip olduğu durumlarda etkilidir. Sorun, kesin çözücüler (MILP, dal-ve-sınır) için yeterince küçükse, tek bir değerlendirmenin hesaplama açısından yasaklayıcı olduğu durumlarda (birçok paralel değerlendirmeyi imkansız hale getirerek) veya tekrarlanabilirlik gereksinimlerinin, belirlenmemiş, ajan etkileşimli dinamiklerle çeliştiği durumlarda bundan kaçının.
Sınırlar ve dikkat edilmesi gerekenler
- Ajanlar arasındaki senkronizasyon ek yükü ve iletişim maliyeti, sıkı bağlı sistemlerde veya yavaş ağlarda paralellik kazançlarını ortadan kaldırabilir.
- Tek iş parçacıklı tabu aramadan daha fazla hiperparametre: ajan sayısı, iletişim topolojisi, senkronizasyon frekansı ve çeşitlendirme tetikleyicileri hepsi ayarlanmalıdır.
- Teorik yakınsama garantileri kesin yöntemlerden daha zayıftır; çözüm kalitesi, ayarlamaya ve problem yapısına büyük ölçüde bağlıdır.
- Ajan etkileşimlerinin rastgele başlatmanın ötesinde ek stokastiklik getirmesi nedeniyle tekrarlanabilirlik elde etmek zordur.
Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.
Güçlü yönleri
- Paralel keşif, tek iş parçacıklı tabu aramaya kıyasla büyük kombinatoryal problemler üzerinde çözüme ulaşma süresini önemli ölçüde azaltır.
- Çoklu ajan çerçevesi doğal olarak çeşitlendirmeyi destekler, zayıf yerel optimumlara erken yakınsama riskini azaltır.
- Esnek mimari, farklı komşuluk yapılarına, tabu süresi stratejilerine veya hatta karışık meta-sezgisel yöntemlere sahip heterojen ajanlara izin verir.
- İşbirlikçi çözüm paylaşımı, keşifleri ajanlar arasında aktararak yüksek kaliteli bölgeler etrafında yoğunlaştırmayı hızlandırır.
- Mevcut hesaplama çekirdekleriyle iyi ölçeklenir, bu da onu modern çok çekirdekli ve dağıtık bilgi işlem ortamları için uygun hale getirir.
Uygulama alanları
- Araç rotalama ve lojistik: her biri rota alt problemlerini optimize eden birden fazla ajanın koordinasyonu.
- İş-atölyesi ve esnek üretim çizelgeleme: ajanlar makine alt kümelerini işbirliği içinde ele alır.
- Telekomünikasyon ağı tasarımı: dağıtık kanal atama ve topoloji optimizasyonu.
- Tedarik zinciri planlaması: çok kademeli envanter ve dağıtım optimizasyonu.
- Protein yapısı tahmini: konformasyonel uzaylar üzerinde paralel komşuluk araması.
- Dağıtık bölüm düzeyinde ajanlarla akademik zaman çizelgeleme ve ders planlama.
Nasıl çalışır?
Nasıl çalışır?
Otonom ajanlardan oluşan bir popülasyon tanımlayın. Her ajana bir rol atanır: bazıları yoğunlaştırmaya (umut vadeden bölgeler etrafında derin yerel arama), diğerleri ise çeşitlendirmeye (keşfedilmemiş alanlardan kaçma) odaklanır. Her ajan, yasaklanmış hamlelerin kendi tabu listesini, mevcut bir çözümü ve sorunun türüne (örneğin, kombinatoryal problemler için takas, ekleme veya 2-opt hamleleri) uyarlanmış bir komşuluk yapısını korur.
Ajanları, rastgele oluşturulmuş veya yapıcı bir sezgisel (örneğin, rotalama için en yakın komşu) ile başlatılmış farklı başlangıç çözümleriyle başlatın. Başlangıç çözümleri arasındaki çeşitlilik çok önemlidir — aynı başlangıçlar, gereksiz paralel aramalara yol açar. Her başlangıç çözümü için amaç fonksiyonunu değerlendirin ve tüm ajanlar arasındaki küresel en iyi çözümü kaydedin.
Her ajan kendi tabu arama döngüsünü yürütür: mevcut çözümün komşuluğunu oluşturur, komşu çözümlerin tamamını (veya bir alt kümesini) değerlendirir, bir sonraki hamle olarak en iyi tabu olmayan komşuyu seçer (ilham kriteri, aday aday küresel en iyiyi aşarsa tabu listesini geçersiz kılmaya izin verir) ve ters hamleyi sabit veya uyarlanabilir bir aralıktan çekilen bir süre ile tabu listesine ekleyerek günceller.
Ajanlar tanımlanmış senkronizasyon aralıklarında veya olay tetikleyicilerinde iletişim kurar. Yaygın stratejiler arasında mevcut küresel en iyiyi tüm ajanlara yayınlamak (bunlardan yeniden başlayabilirler), seçkin çözümü ajanların periyodik olarak başvurduğu paylaşılan bir havuza enjekte etmek veya bir topolojideki (halka, tam bağlı veya rastgele) komşu ajanlar arasında uçtan uca çözüm alışverişi yer alır. Çeşitlilik kontrolleri, aynı çözümlere sahip ajanları cezalandırarak erken yakınsamayı önler.
Maksimum iterasyon bütçesi, gerçek zamanlı saat sınırı veya durgunluk kriteri (örneğin, belirli sayıda iterasyon boyunca küresel en iyide iyileşme olmaması) karşılandığında sonlandırın. Nihai çıktı olarak tüm ajanlar tarafından tüm iterasyonlar boyunca bulunan küresel en iyi çözümü seçin. Birden fazla hedef izleniyorsa isteğe bağlı olarak bir Pareto cephesi raporlayın.
Sık yapılan hatalar
- Tüm ajanlara aynı başlangıç çözümlerini atamak, paralel kapasiteyi boşa harcar — çeşitli başlatma sağlayın.
- Aşırı sık iletişim, ajanları aynı çözüm havuzuna zorlar, çeşitlendirme faydalarını ortadan kaldırır ve aramayı etkili bir şekilde tek bir iş parçacığına indirir.
- İlham kriterini tabu listesi tasarımında göz ardı etmek, ajanların özellikle aramanın erken aşamasında bariz şekilde daha iyi çözümleri kaçırmasına neden olabilir.
- Komşuluk değerlendirmesinin bir vekil model olmadan aşırı maliyetli olduğu problemlere ABTA uygulamak, yasaklayıcı çalışma sürelerine yol açacaktır.
Sık sorulan sorular
Ajan Tabanlı Tabu Arama, birden fazla tabu arama iş parçacığı çalıştırmaktan nasıl farklıdır?
Temel fark işbirliğidir. Bağımsız paralel çalıştırmalarda, iş parçacıkları asla bilgi paylaşmaz. ABTA'da, ajanlar aktif olarak çözümleri değiş tokuş eder, paylaşılan bir seçkin havuzunu günceller veya toplu duruma dayalı çeşitlendirme tetikleyicileri benimser — bağımsız çalıştırmalarda bulunmayan ortaya çıkan arama davranışı üretir.
Kaç ajan kullanmalıyım?
Yaygın bir başlangıç noktası, mevcut her CPU çekirdeği için bir ajandır. Araştırmalar, iletişim ek yükü arttıkça çoğu kombinatoryal problem için 8–16 ajanın ötesinde azalan getiriler olduğunu göstermektedir. 4, 8 ve 16 ajanla yapılan pilot deneyler, belirli bir problem için en uygun noktayı belirlemeye yardımcı olur.
ABTA çok amaçlı problemleri işleyebilir mi?
Evet. Ajanlar bir Pareto cephesinin yerel yaklaşımlarını koruyabilir ve paylaşılan bir arşiv aracılığıyla baskın olmayan çözümleri paylaşabilir. Bu bazen Çok Amaçlı Ajan Tabanlı Tabu Arama olarak adlandırılır ve standart tek amaçlı ABTA'dan farklıdır.
Hangi iletişim topolojisi en iyisidir?
Tam bağlı topolojiler iyi çözümleri en hızlı şekilde yayar ancak yüksek iletişim maliyeti oluşturur. Halka veya küçük dünya topolojileri, bilgi yayılımını özerklikle dengeler. Çoğu pratik problem için, varsayılan olarak bir halka veya rastgele seyrek bir topoloji iyi çalışır.
Ne zaman genetik algoritma veya parçacık sürüsünü ABTS'ye tercih etmeliyim?
Problem sürekli, pürüzsüz bir manzaraya sahip olduğunda veya çaprazlama/rekombinasyon operatörlerinin iyi tanımlandığı durumlarda popülasyon tabanlı yöntemleri (GA, PSO) tercih edin. ABTA, tabu belleğinin güçlü bir arama avantajı sağladığı, iyi tanımlanmış komşuluk operatörlerine sahip ayrık, kombinatoryal problemler üzerinde üstündür.
İlgili yöntemler
Kaynaklar
Glover, F. (1989). Tabu search — Part I. ORSA Journal on Computing, 1(3), 190–206.
DOI kaynağını açKopyalandı.Verhoeven, M. G. A., Aarts, E. H. L. (1995). Parallel local search. Journal of Heuristics, 1(1), 43–65.
DOI kaynağını açKopyalandı.