Agen Tabanlı Genetik Algoritma — Otonom Ajanlar Aracılığıyla Dağıtılmış Evrimsel Arama
- Ortaya koyan
- Adamidis, P. & Petridis, V. (early formal treatment); broader community development in 1990s
- Yıl
- 1990s
- Tür
- Hybrid evolutionary-agent simulation
- Aile
- Simulation / optimization
Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku
Ne işe yarar?
Bir Agen Tabanlı Genetik Algoritma (ABGA), bir genetik algoritmanın popülasyonunu, her biri yerel bir alt popülasyonu koruyan ve onu bağımsız olarak evrimleştiren otonom ajanlar ağına böler.
Ajanlar, yakınlığa veya iletişim kurallarına dayanarak periyodik olarak bireyleri (göç) değiş tokuş eder, arama uzayının paralel keşfine olanak tanırken popülasyon çeşitliliğini korur ve erken yakınsamayı önler.
Yöntemin mantığı
Geleneksel bir genetik algoritma, tüm popülasyonu tek bir havuz olarak ele alır, bu da baskın bir genotipin hakim olmasıyla yerel optimumlara hızlı yakınsamaya neden olabilir. Bunun yerine, agen tabanlı bir yaklaşım, yarı otonom ajanlara dağıtılmış alt popülasyonları, bir komşuluk topolojisinde düzenlenmiş şekilde kullanır. Her ajan kendi seçim, çaprazlama ve mutasyon işlemlerini yerel olarak çalıştırır, ardından ara sıra en yüksek uygunluğa sahip bireyleri komşu ajanlarla paylaşır. Bu, biyolojik türleşmenin coğrafi olarak izole edilmiş ancak ara sıra bağlı popülasyonlarda nasıl meydana geldiğini yansıtır, farklı evrimsel baskıların paralel olarak etki etmesine ve nişler boyunca çözümlerin yeniden birleşmesine izin verir.
Tarih
Dağıtılmış ve paralel genetik algoritmalar, araştırmacıların erken yakınsamayı aşmak ve paralel donanımdan yararlanmak istemesiyle 1990'ların başında ortaya çıktı. Adamidis ve Petridis (1996), farklı evrimsel davranışlara sahip işbirliği yapan ajan popülasyonlarını biçimlendirdi. Agen tabanlı çerçeve, 1990'ların sonları ve 2000'lerde, agen tabanlı modellemenin hesaplamalı bilim genelinde yayılmasıyla, şu anda karmaşık optimizasyonda yaygın olarak uygulanan otonom, topoloji güdümlü etkileşim modelini biçimlendirerek ivme kazandı.
Ne zaman kullanılır?
Uygunluk manzarası engebeli veya çok modlu olduğunda ve standart GA'lar tutarlı bir şekilde erken yakınsadığında; eşzamanlı ajan süreçlerini barındırabilen paralel veya dağıtılmış donanım mevcut olduğunda; veya problem yapısı doğal olarak yarı bağımsız alt problemlere (örneğin, bölgesel tedarik zincirleri, çok sektörlü politikalar) eşlendiğinde bir ABGA kullanın. Heterojen evrimsel baskılar altında algoritma davranışını keşfetmek için de uygundur. Tek modlu tek bir manzaraya sahip olduğunda (daha basit GA yeterlidir), ajanlar arası iletişimin ek yükü hesaplamayı domine ettiğinde, popülasyon boyutları anlamlı bir şekilde bölünecek kadar küçük olmadığında veya kesin tekrarlanabilirlik için merkezi bir popülasyon gerektiğinde KULLANMAYIN.
Sınırlar ve dikkat edilmesi gerekenler
- Göç politikası ayarı (oran, topoloji, sıklık), dikkatli kalibrasyon gerektiren ve probleme bağlı olan hiperparametreler ekler.
- Ajanlar arasındaki iletişim ek yükü, yüksek gecikmeli veya gevşek bağlı bilgi işlem ortamlarında paralellik faydalarını geçersiz kılabilir.
- Teorik yakınsama garantileri standart GA'lardan daha zayıftır; ABGA dinamiklerinin resmi analizi açık bir araştırma alanıdır.
- Sonuçları tekrarlamak, tüm ajanlar arasında ajan topolojisini, göç programını ve rastgele tohumları sabitlemeyi gerektirir, bu da çoğaltmayı karmaşıklaştırır.
- Alt popülasyon boyutları çok küçükse, bireysel ajanlar göçten bağımsız olarak genetik sürüklenmeye eğilimlidir.
Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.
Güçlü yönleri
- Panmiktik GA'lardan daha yüksek popülasyon çeşitliliğini korur, engebeli uygunluk manzaralarında erken yakınsamayı azaltır.
- Büyük ölçekli optimizasyon problemleri için paralel veya dağıtılmış bilgi işlem altyapısından doğal olarak yararlanır.
- Ajan başına heterojen operatör ayarları, farklı stratejiler arasında eşzamanlı keşif ve sömürüye izin verir.
- Ajanlar arasında uygun bireylerin göçü, yeni yüksek kaliteli çözümler keşfedebilen çapraz niş yeniden birleşmesini sağlar.
- Modüler mimari, alan özgü sezgileri bireysel ajan evrim döngülerine entegre etmeyi kolaylaştırır.
- Alt popülasyonlar anlamlı bir şekilde bölünebildiğinde problem boyutluluğu ile iyi ölçeklenir.
Uygulama alanları
- Zamanlama ve lojistik: coğrafi alt problemlerin ajanlara doğal olarak eşlendiği dağıtılmış iş çizelgeleme veya araç rotalama problemleri.
- Mühendislik tasarımı optimizasyonu: paralel niş keşfinden yararlanan çok modlu arama alanlarına sahip yapısal veya aerodinamik tasarım.
- Politika simülasyonu: ajanların bölgesel veya sektörel aktörleri temsil ettiği sosyal simülasyon modellerinde politika parametresi optimizasyonu.
- Makine öğrenimi hiperparametre araması: dağıtılmış bilgi işlem kümeleri genelinde model yapılandırmalarının paralel evrimsel ayarlanması.
- Biyoenformatik: yüksek boyutlu, engebeli uygunluk manzaralarında protein yapısı tahmini ve gen ağı çıkarımı.
- Oyun yapay zekası ve robotik: ortak evrimsel dinamiklere sahip çoklu ajan ortamlarında ajan davranış stratejilerini evrimleştirmek.
Nasıl çalışır?
Nasıl çalışır?
Ajan topolojisini tanımlayın: ajanların sayısını (alt popülasyonlar), komşuluk yapılarını (halka, ızgara, küçük dünya grafiği veya tam bağlı) ve ajanların bireyleri ne zaman ve nasıl değiş tokuş edeceğini yöneten iletişim protokolünü belirtin. Her ajan, kendi kromozom havuzuna sahip otonom bir hesaplama varlığıdır.
Her ajanın yerel alt popülasyonunu rastgele oluşturulmuş kromozomlarla (veya tohumlanmış çözümlerle) başlatın. Yerel popülasyon boyutunu, genetik operatörleri (çaprazlama türü ve oranı, mutasyon oranı) ve seçim mekanizmasını (turnuva, rulet, sıralı) her ajan için bağımsız olarak veya tüm ajanlar arasında tekdüze olarak ayarlayın.
Her ajan, yerel alt popülasyonu üzerinde bağımsız olarak birkaç nesil seçim, çaprazlama ve mutasyon çalıştırır. Paralel (veya sıralı simülasyonda yarı paralel) çalışan ajanlar, potansiyel olarak farklı operatör yapılandırmaları altında çözüm uzayının farklı bölgelerini keşfeder, sistem genelinde çeşitliliği korur.
Belirlenen göç aralıklarında, ajanlar en uygun bireylerinin bir alt kümesini göç politikasına (örneğin, en iyiyi gönder, en kötüyü al-değiştir) göre komşu ajanlarla paylaşır. Göç oranı ve topolojisi, yerel sömürü ve küresel keşif arasındaki dengeyi şekillendirir; çok sık göç çeşitliliği azaltır, çok seyrek göç dağıtılmış mimariden boşa harcar.
Tüm içe aktarılan ve yerel olarak evrimleşen kromozomlar, paylaşılan uygunluk fonksiyonuna göre değerlendirilir. Ajanlar, alınan bireyleri popülasyonlarına entegre etmek için göç sonrası yerel seçim baskısı uygulayabilir, potansiyel olarak daha az uygun yerlileri atabilir. Uygunluk değerlendirmesi baskın hesaplama maliyetidir.
Küresel bir durdurma kriteri karşılandığında (maksimum nesil, ajanlar arasındaki en iyi uygunluğun yakınsaması veya geçen süre) sonlandırın. Nihai çıktı olarak tüm ajanlar arasında bulunan en iyi çözümü toplayın. Popülasyon çeşitliliğini ve göç etkinliğini teşhis etmek için her ajan için yakınsama eğrilerini raporlayın.
Sık yapılan hatalar
- Göç oranını çok yüksek ayarlamak, alt popülasyon çeşitliliğini fiili tek bir havuza indirir, agen mimarisinin ana avantajını ortadan kaldırır.
- Komşuluk topolojisi tasarımını göz ardı etmek: tam bağlı bir topoloji hızlı yakınsamaya neden olur; yetersiz göç sıklığına sahip bir halka, ajanları izole ve durgun bırakabilir.
- Yalnızca yerel olarak ve paylaşılan bir küresel uygunluk fonksiyonu olmadan uygunluk değerlendirmesi, ajanların uyumsuz hedefleri optimize etmesine yol açar.
- ABGA'yı çok amaçlı GA ile karıştırmak: ABGA, arama verimliliği için bir mimari varyantıdır, doğası gereği çok amaçlı bir yöntem değildir — çok amaçlı ABGA ek Pareto makineleri gerektirir.
- Bireysel ajan yakınsamasında durmak yerine küresel yakınsamada durmak, diğer ajanlarda hala gelişmekte olan daha iyi çözümleri kaçırabilir.
Sık sorulan sorular
Bir ABGA, standart bir paralel GA'dan nasıl farklıdır?
Standart bir paralel GA tipik olarak tek bir merkezi popülasyonun uygunluk değerlendirmesini işlemcilere dağıtır. Bir ABGA, her ajana kendi evrimsel döngüsüne sahip otonom bir alt popülasyon verir; etkileşim yalnızca açık göç yoluyla gerçekleşir, paylaşılan bir havuz aracılığıyla değil. Bu ayrım, her ajan için bağımsız seçilim baskılarını korur.
Hangi göç topolojisini seçmeliyim?
Halka ve ızgara topolojileri standart başlangıç noktalarıdır: göç akışını sınırlar ve çeşitliliği korurlar. Küçük dünya topolojileri (halkaya eklenen birkaç uzun menzilli bağlantı), çeşitliliği çökertmeden iyi çözüm yayılımını hızlandırır. Tam bağlı topolojilerden genel olarak kaçınılmalıdır, ancak hızlı yakınsama davranışı istiyorsanız.
Kaç ajan ve hangi alt popülasyon boyutu uygundur?
Yaygın bir sezgi, her biri 20-50 bireyden oluşan alt popülasyon boyutlarına sahip 4-16 ajandır, bu da standart bir GA'nın kullanacağı popülasyon boyutuna karşılık gelir. Çok az ajan, mimarinin çeşitlilik avantajını geçersiz kılar; çok küçük alt popülasyonlara sahip çok fazla ajan, sürüklenmeden muzdariptir. Belirli problem üzerinde ampirik ayarlama gereklidir.
ABGA çok amaçlı optimizasyon için kullanılabilir mi?
Evet, ancak ek Pareto makineleri (her ajan içinde NSGA-II sıralaması gibi) eklenmelidir. Agen mimarisi daha sonra daha çeşitli bir Pareto ön cephesi yaklaşımını korumaya yardımcı olur. Bu, çok amaçlı ABGA varyantlarının temelini oluşturur.
Bir ABGA'nın küresel optimumu bulması garanti edilir mi?
Hayır. Tüm GA'lar gibi, ABGA'lar da sezgiseldir ve küresel optimallik garantisi sağlamazlar. Geliştirilmiş çeşitlilik koruması, pratikte yerel optimumlardan kaçınma olasılığını artırır, ancak yakınsama garantileri standart GA'lardan daha güçlü değildir ve aktif bir teorik araştırma sorusudur.
İlgili yöntemler
Kaynaklar
Adamidis, P., & Petridis, V. (1996). Co-operating populations with different evolution behaviors. Proceedings of the IEEE International Conference on Evolutionary Computation (ICEC 1996), 188-191. IEEE.
Yayın kaynağını açKopyalandı.Genetic algorithm. Wikipedia.
Yayın kaynağını açKopyalandı.