Çok Amaçlı Karınca Kolonisi Optimizasyonu (ÇAKKO)
- Ortaya koyan
- Gambardella, Taillard & Agazzi; Dorigo & Stützle
- Yıl
- 1999
- Tür
- Population-based metaheuristic
- Aile
- Simulation / optimization
Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku
Ne işe yarar?
Çok Amaçlı Karınca Kolonisi Optimizasyonu (ÇAKKO), klasik Karınca Kolonisi Optimizasyonu çerçevesini, birbiriyle çatışan iki veya daha fazla hedefi eş zamanlı olarak optimize etmek üzere genişleten bir sürü zekası meta-sezgiselidir.
Yapay karıncalar, feromon izleri ve sezgisel bilgiler rehberliğinde aday çözümler oluşturarak, tek bir en iyi cevaba yakınsamak yerine giderek artan bir şekilde Pareto-optimal çözümler arşivi oluştururlar.
Yöntemin mantığı
Tek bir en iyi yolun olmadığı bir arazide yiyecek arayan bir karınca kolonisi hayal edin; bunun yerine, farklı yollar mesafe ile güvenlik veya hız ile enerji arasında ödünleşim yapar. Her karınca, birden fazla kritere göre orantılı olarak feromon bırakır. Nesiller boyunca koloni, hedeflerin önceden belirlenmiş bir ağırlıklandırmasını zorlamadan ödünleşim sınırını – Pareto sınırını – topluca haritalandırır. Temel içgörü, stigmerjinin (feromon yoluyla dolaylı iletişim) çok amaçlı kalite bilgilerini kodlayabileceği ve böylece tam ödünleşim yüzeyinin ortaya çıkan bir yaklaşımını sağlayabileceğidir.
Tarih
Karınca Kolonisi Optimizasyonu, Marco Dorigo tarafından 1992'deki doktora tezinde tanıtılmış ve Maniezzo ve Colorni ile biçimlendirilmiştir. Çok amaçlı uzantılar 1990'ların sonlarında ortaya çıktı; Gambardella, Taillard ve Agazzi'nin MACS-VRPTW'si (1999), farklı hedeflere odaklanan birden fazla karınca kolonisi gösterdi. Doerner, Hartl ve diğerlerinin sonraki çerçeveleri ÇAKKO'yu bir sınıf olarak biçimlendirdi ve Dorigo ve Stützle'nin 2004 tarihli ders kitabı kanonik algoritma tedavisini sağladı. ÇAKKO, ağ yönlendirme, biyoinformatik ve sürdürülebilir lojistik alanlarındaki uygulamalarıyla aktif bir araştırma alanı olmaya devam etmektedir.
Ne zaman kullanılır?
ÇAKKO'yu, problem iki veya daha fazla çatışan hedefe sahip olduğunda, bir kombinatoryal veya ayrık çözüm uzayına (örneğin, yönlendirme, zamanlama, ağ tasarımı) sahip olduğunda ve hedefleri bir skalar hale getirmeyi haklı çıkaracak güçlü bir öncelik olmadığında kullanın. ACO'nun tek hedefler üzerinde zaten iyi performans gösterdiği lojistik, tedarik zinciri ve iş akışı zamanlama problemlerinde üstündür. Problem sürekliyse ve gradyan tabanlı çok amaçlı yöntemler (örneğin, gerçek kodlamalı NSGA-II veya Bayes optimizasyonu) daha verimliyse; hesaplama bütçesi ciddi şekilde kısıtlıysa, çünkü ÇAKKO birçok değerlendirme gerektirir; veya tam çok amaçlı programlama (örneğin, çok amaçlı MILP) çözülebilirse kesin bir Pareto sınırı gerektiğinde ÇAKKO'dan kaçının.
Sınırlar ve dikkat edilmesi gerekenler
- Birkaç hiperparametrenin (α, β, ρ, koloni boyutu, arşiv kapasitesi) dikkatli ayarlanmasını gerektirir ve bu ayarlara duyarlılık yüksek olabilir.
- Yakınsama, tamsayı veya dinamik programlama yöntemlerinin çözülebildiği küçük, iyi yapılandırılmış problemler için kesin çözücülerden daha yavaştır.
- Pareto sınırının yaklaşım kalitesi ve çeşitliliği garanti edilmez; stokastik yapılandırma nedeniyle çalıştırmalar arasında sonuçlar değişir.
- Yüksek boyutlu hedef uzaylarına (>3 hedef) ölçeklendirme zordur ve özel ayrıştırma stratejileri gerektirebilir.
- Keyfi problem örnekleri için yakınsama kanıtı yoktur; matematiksel programlamaya kıyasla teorik garantiler sınırlıdır.
Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.
Güçlü yönleri
- Gradyan yöntemlerinin başarısız olduğu kombinatoryal ve permütasyon tabanlı çözüm uzaylarını doğal olarak ele alır.
- Tek bir çalıştırmada tam Pareto sınırının bir yaklaşımını üretir, karar vericilere açık ödünleşim bilgisi sağlar.
- Sürü çeşitliliği erken yakınsamayı önler ve bağlantısız Pareto bölgelerinin keşfini destekler.
- Feromon belleği, iterasyonlar boyunca örtük öğrenme sağlar ve keşfi göz ardı etmeden yönlendirilmiş yoğunlaşmayı sağlar.
- Kolayca paralelleştirilebilir: birden fazla karınca kolonisi veya hedefe özgü koloniler eşzamanlı olarak çalışabilir.
- Çoklu yerel optimumlar gibi probleme özgü arazi özelliklerine karşı dayanıklıdır.
Uygulama alanları
- Zaman pencereleri ve kapasite kısıtlamaları ile çok amaçlı araç yönlendirme ve lojistik zamanlaması.
- Maliyeti, gecikmeyi ve güvenilirliği eş zamanlı olarak optimize eden ağ topolojisi tasarımı.
- İş bitirme süresini, enerji tüketimini ve makine kullanımını dengeleyen esnek iş istasyonu zamanlaması.
- Biyoinformatik: protein yapısı tahmini ve çok etiketli sınıflandırma için özellik seçimi.
- Ekonomik maliyeti, karbon emisyonlarını ve sosyal kriterleri optimize eden sürdürülebilir tedarik zinciri tasarımı.
- Çok amaçlı iş akışı zamanlaması, bulut bilişim ortamlarında.
Nasıl çalışır?
Nasıl çalışır?
Feromon matrislerini (her hedef için bir veya paylaşılan ağırlıklı bir matris) tekdüze değerlerle başlatın. Her çözüm bileşeni için sezgisel bilgiyi η tanımlayın. Arama sırasında bulunan baskın olmayan çözümleri depolamak için boş bir Pareto arşivi oluşturun.
Her karınca, çözüm bileşenlerini olasılıksal olarak seçerek adım adım tam bir çözüm oluşturur. Geçiş olasılığı, feromon gücü τ ve sezgisel çekicilik η'yı ayarlama üsleri α ve β'ya yükselterek kullanır. Farklı ÇAKKO varyantları, hedef başına feromon matrisleri atar veya karıncalar arasında değişen skalarlaştırma ağırlıkları kullanır.
Formül
p_{ij}^k = \frac{[\tau_{ij}]^\alpha \cdot [\eta_{ij}]^\beta}{\sum_{l \in \mathcal{N}_i^k} [\tau_{il}]^\alpha \cdot [\eta_{il}]^\beta}Oluşturulan her çözümü tüm hedef fonksiyonlarında eş zamanlı olarak değerlendirin. Mevcut arşiv üyelerine göre baskınlık ilişkisini belirleyin: bir çözüm, tüm hedeflerde en azından diğerine eşit ve en az birinde kesin olarak daha iyiyse diğerini baskın kılar.
Baskın olmayan çözümleri ekleyerek ve yeni çözümler tarafından baskın hale getirilen herhangi bir arşiv üyesini kaldırarak Pareto arşivini güncelleyin. Arşivin hedef uzayının dar bölgelerinde aşırı yoğunlaşmasını önlemek için çeşitlilik koruma mekanizmaları (örneğin, kalabalık mesafesi, ızgara tabanlı yoğunluk) uygulayın.
Eski bilginin solmasına izin vermek için tüm feromon izlerini (1 − ρ) faktörüyle buharlaştırın. Arşiv (elit) çözümlerine ait çözüm bileşenlerine yeni feromon bırakın. Bırakılan Δτ miktarı, hedefe özgü kaliteyi veya kalabalık tabanlı sıralamayı yansıtır ve iyi yayılmış Pareto-optimal çözümlerle ilişkili bileşenleri güçlendirir.
Formül
\tau_{ij} \leftarrow (1 - \rho)\,\tau_{ij} + \sum_{k: s^k \in \mathcal{A}} \Delta\tau_{ij}^kSabit sayıda iterasyon veya bir yakınsama kriteri karşılanana kadar feromon güncellemesi yoluyla yapıyı tekrarlayın. Karar vericinin seçmesi için tam ödünleşim spektrumunu temsil eden, yaklaştırılmış Pareto sınırı olarak son Pareto arşivini döndürün.
Sık yapılan hatalar
- Tek bir paylaşılan feromon matrisinin hedefe özgü farklılaştırma olmadan kullanılması genellikle yanlı, kötü yayılmış Pareto sınırları üretir.
- Arşiv çeşitliliği yönetimini ihmal etmek, bir bölgede kalabalık bir sınır ve başka yerlerde büyük boşluklara yol açarak ödünleşimlerin yanıltıcı bir resmini verir.
- Buharlaşma oranını ρ çok yüksek ayarlamak feromonun yıkanmasına ve birikmiş öğrenmenin kaybolmasına neden olur; çok düşük ayarlamak suboptimal çözümler etrafında durgunluğa yol açar.
- ÇAKKO sonuçlarını istatistiksel tekrarlama (birden fazla tohum, hiperhacim göstergesi) olmadan çalıştırmalar arasında karşılaştırmak yanıltıcı kalite değerlendirmeleri üretir.
- Hedef değerlerini baskınlık veya feromon bırakma hesaplamalarından önce normalleştirmeyi unutmak, hedeflerin çok farklı ölçeklere sahip olduğu durumlarda aramayı bozar.
Sık sorulan sorular
ÇAKKO, tek hedefli ACO'nun farklı ağırlık kombinasyonlarıyla birden çok kez çalıştırılmasından nasıl farklıdır?
Ağırlıklı tek hedefli ACO çalıştırmaları, ağırlıkların önceden belirtilmesini gerektirir ve her çalıştırma yalnızca bir Pareto-optimal noktayı yaklaştırır. ÇAKKO, tek bir çalıştırmada ödünleşim yüzeyinin bir arşivini oluşturur ve feromon güncellemesi, tek bir skalar optimum yerine çeşitli yüksek kaliteli çözümleri güçlendirir.
Yeni bir problem için hangi ÇAKKO varyantını kullanmalıyım?
Hedefler ayrılabilirse ve her birinin doğal bir sezgisi varsa, çoklu koloni yaklaşımı (her hedef için ortak bir Pareto arşivini paylaşan bir koloni) iyi bir başlangıç noktasıdır. Hedefler sıkı bir şekilde bağlıysa, ayrıştırma tabanlı skalarlaştırma ile tek bir koloni (ÇAKKO/D tarzı) genellikle daha verimli yakınsar. Öncelikle kendi problem alanınız için literatürü kontrol edin.
Tipik olarak kaç karınca ve iterasyon gereklidir?
Evrensel bir cevap yoktur, ancak yaygın bir başlangıç yapılandırması orta büyüklükteki kombinatoryal problemler için 20-100 karınca ve 500-2000 iterasyondur. Daha büyük çözüm uzayları ve daha fazla hedef daha fazla iterasyon gerektirir. Her zaman birden fazla bağımsız tekrar çalıştırın ve tohumlar üzerinden ortalaması alınan hiperhacim veya IGD göstergelerini raporlayın.
ÇAKKO sürekli optimizasyon problemlerini ele alabilir mi?
Standart ACO ayrık uzaylar için tasarlanmıştır. Sürekli ÇAKKO varyantları mevcuttur (örneğin, ACOR tabanlı), ancak sürekli problemler üzerinde genellikle NSGA-II veya MOEA/D'den daha düşük performans gösterirler. ÇAKKO'yu, graf tabanlı yapısının doğal bir avantaj sağladığı kombinatoryal veya karma tamsayılı problemler için saklayın.
Pareto arşivi boyutu nasıl ayarlanmalıdır?
Arşiv boyutu, feromon bırakma için kullanılan elit çözümlerin sayısını sınırlar. Çok küçük bir arşiv çeşitliliği kaybeder; çok büyük bir arşiv feromon takviyesini yavaşlatır. Tipik değerler 10 ila 100 çözüm arasında değişir; boyutundan bağımsız olarak iyi yayılmış bir arşiv tutmak için bir kalabalık mesafesi veya ızgara tabanlı strateji kullanın.
İlgili yöntemler
Kaynaklar
Gambardella, L. M., Taillard, E., & Agazzi, G. (1999). MACS-VRPTW: A multiple ant colony system for vehicle routing problems with time windows. In D. Corne, M. Dorigo, & F. Glover (Eds.), New Ideas in Optimization (pp. 63–76). McGraw-Hill.
Yayın kaynağını açKopyalandı.Dorigo, M., & Stützle, T. (2004). Ant Colony Optimization. MIT Press.
ISBN: 9780262042192Kopyalandı.