Hücresel evrimsel algoritma - Cellular evolutionary algorithm

Bir hücresel evrimsel algoritma ( CEA ), bir tür evrimsel algoritma bireyler keyfi çiftleşme neden olan (EA), fakat temel EA uygulandığı üzerinde yakın komşuları ile her bir etkileşime girer (seçimi, varyasyon, değiştirme).

Popülasyonun şekline bağlı olarak kareden (solda) tek boyutlu halkaya (sağda) kadar bir cEA'nın örnek evrimi. Daha koyu renkler daha iyi çözümler anlamına gelir. Geleneksel kareden farklı şekillerin çeşitliliği (daha yüksek keşif) daha uzun süre nasıl koruduğunu gözlemleyin. 0-50-100-150 nesillerinde cEA'nın dört anlık görüntüsü.

Hücresel model, bir deneme amaçlı (optimizasyon, öğrenme, arama) problem çözümünü kodlayan bireyin bakış açısından doğal evrimi simüle eder. Bu modelin temel fikri, EA popülasyonuna, her bir tepe noktasının en yakın komşularıyla iletişim kuran bir birey olduğu bağlantılı bir grafik olarak tanımlanan özel bir yapı sağlamaktır. Özellikle, bireyler kavramsal olarak toroidal bir ağa yerleştirilir ve yalnızca yakın bireylerle yeniden birleşmelerine izin verilir. Bu bizi mesafeyle izolasyon olarak bilinen bir tür konuma götürür . Bir bireyin potansiyel eşleri kümesine komşuluk denir . Bu tür bir algoritmada, benzer bireylerin nişler oluşturma eğiliminde oldukları ve bu grupların ayrı alt popülasyonlar (adalar) gibi çalıştıkları bilinmektedir. Her neyse, bitişik gruplar arasında net bir sınır yoktur ve yakın nişler, rekabetçi nişler tarafından kolayca kolonize edilebilir ve belki de süreç sırasında çözüm içeriklerini birleştirebilir. Aynı zamanda daha uzaktaki nişler daha yavaş etkilenebilir.

Giriş

Hücresel evrimsel bir algoritma (cEA), diğer topolojiler de mümkün olmasına rağmen, genellikle bireylerin yapılandırılmış iki boyutlu bir ızgarasını geliştirir. Bu ızgarada, benzer bireylerden oluşan kümeler, evrim sırasında doğal olarak yaratılır ve sınırları içinde keşif yapılmasını desteklerken, sömürü esas olarak doğrudan rekabet ve içlerinde birleşerek gerçekleştirilir.

Hücresel EA'larda örnek mahalle modelleri: doğrusal, kompakt, elmas ve ... diğerleri!

Izgara genellikle 2D toroidal yapıdadır, ancak boyutların sayısı kolayca genişletilebilir (3D'ye) veya azaltılabilir (1D'ye, örneğin bir halka). Izgaranın belirli bir noktasının mahallesi (bir bireyin yerleştirildiği yer), Manhattan'ın ondan popülasyondaki diğerlerine olan uzaklığı cinsinden tanımlanır . Izgaranın her noktası, yakındaki bireylerin mahalleleriyle örtüşen bir mahalleye sahiptir. Temel algoritmada, tüm mahalleler aynı boyuta ve aynı şekillere sahiptir. En yaygın kullanılan iki mahalle, Von Neumann veya NEWS (Kuzey, Doğu, Batı ve Güney) olarak da adlandırılan L5 ve Moore mahallesi olarak da bilinen C9'dur . Burada L , Doğrusal , C ise Kompakt anlamına gelir .

CEA'larda bireyler, komşularla yalnızca varyasyon operatörlerinin uygulandığı üreme döngüsünde etkileşime girebilirler. Bu üreme döngüsü, her bir bireyin mahallesi içinde yürütülür ve genellikle, belirli bir kritere göre komşuları arasından iki ebeveynin seçilmesinden, varyasyon operatörlerinin bunlara uygulanmasından (örneğin rekombinasyon ve mutasyon) ve dikkate alınan bireyin yerine Örneğin, belirli bir kritere göre yakın zamanda oluşturulmuş yavrular, örneğin, yavru, dikkate alınan bireyden daha iyi bir çözümü temsil ediyorsa, değiştirin.

Eşzamanlı ve eşzamansız

Normal bir senkronize CEA'da, algoritma, yeni bir geçici popülasyon oluşturmak için popülasyondaki bilgileri kullanarak ilk sol üstteki bireyden sağa ve ardından birkaç satıra ilerler. Sağ alttaki son bireyle bitirdikten sonra, geçici popülasyon yeni hesaplanan bireylerle doludur ve değiştirme adımı başlar. İçinde eski popülasyon, bazı kriterlere göre tamamen ve eşzamanlı olarak yeni hesaplananla değiştirilir. Genellikle, ikame en iyi kişiyi her iki popülasyonla aynı konumda tutar, yani elitizm kullanılır.

Kullanılan popülasyonun güncelleme politikasına göre, asenkron bir cEA da tanımlayabileceğimizi fark etmeliyiz. Bu aynı zamanda hücresel otomatlarda iyi bilinen bir sorundur . Eşzamansız cEA'larda, ızgaradaki bireylerin güncelleme sırası, kullanılan kritere bağlı olarak değişir: çizgi tarama, sabit rasgele tarama, yeni rastgele tarama ve tek tip seçim. Bunlar, popülasyonu güncellemenin en yaygın dört yoludur. Hepsi, komşularının hesaplamaları için yeni hesaplanan bireyi (veya daha iyiyse orijinali) hemen kullanmaya devam ediyor. Bu, popülasyonun herhangi bir zamanda farklı evrim durumlarında bireysel kalmasını sağlar ve çok ilginç yeni bir araştırma hattı tanımlar.

Mahallenin yarıçapının topolojiye oranı, cEA'nın keşif / kullanım kapasitesini tanımlar. Bu, algoritmanın çalıştırılması sırasında bile ayarlanabilir ve araştırmacıya çok karmaşık manzaralarda arama yapmak için benzersiz bir mekanizma sağlar.

Mahallelerin örtüşmesi, CEA'ya örtük bir çözüm göçü mekanizması sağlar. En iyi çözümler tüm popülasyona sorunsuz bir şekilde yayıldığından, popülasyondaki genetik çeşitlilik yapılandırılmamış EA'lara göre daha uzun süre korunur. En iyi çözümlerin nüfus içinde bu yumuşak dağılımı , arama sırasında cEA'ların gerçekleştirdiği keşif ve sömürü arasındaki iyi ödünleşimin ana sorunlarından biridir . O halde , mahalleler arasındaki örtüşme derecesi boyuta göre büyüdükçe, kullanılan mahallenin boyutunu değiştirerek (örneğin) bu ödünleşimi (ve dolayısıyla evrim boyunca genetik çeşitlilik düzeyini ayarlayabilir) ayarlayabileceğimizi görmek kolaydır. mahallenin.

Bir cEA, CA'nın alfabesinin problemin potansiyel çözüm sayısına eşit olduğu, olasılığa dayalı yeniden yazılabilir kurallara sahip bir hücresel otomat (CA) olarak görülebilir . Dolayısıyla, cEA'ları bir tür CA olarak görürsek, CA'ların alanından cEA'lara bilgi aktarmak mümkündür ve aslında bu ilginç bir açık araştırma hattıdır.

Paralellik

Hücresel EA'lar paralelliğe çok uygundur, bu nedenle genellikle paralel metasezgisel literatürde bulunur . Özellikle ince taneli paralellik, her bireye bağımsız yürütme aşamaları atamak için kullanılabilir, böylece tüm cEA'nın eşzamanlı veya gerçekten paralel bir donanım platformunda çalışmasına izin verir. Bu şekilde, cEA'ları FPGA'larda veya GPU'larda çalıştırırken büyük zaman azaltmaları elde edilebilir .

Bununla birlikte, cEA'ların geleneksel EA'lardan farklı birçok bakımdan bir arama modeli olduğunu vurgulamak önemlidir. Ayrıca, sıralı ve paralel platformlarda çalıştırılabilirler, bu da model ve uygulamanın iki farklı kavram olduğu gerçeğini pekiştirir.

CEA'ların anlaşılması, tasarımı ve uygulanmasına yönelik temellerin tam bir açıklaması için buraya bakın .

Ayrıca bakınız

Referanslar

  • E. Alba, B. Dorronsoro, Hücresel Genetik Algoritmalar , Springer-Verlag, ISBN  978-0-387-77609-5 , 2008
  • AJ Komşu, JJ Durillo, F. Luna, B. Dorronsoro, E. Alba, MOCell: Çok Amaçlı Optimizasyon için Yeni Bir Hücresel Genetik Algoritma, International Journal of Intelligent Systems, 24: 726-746, 2009
  • E. Alba, B. Dorronsoro, F. Luna, AJ Neighbor, P. Bouvry, L. Hogie, A Cellular Multi-Objective Genetic Algorithm for Optimal Broadcasting Strategy in Metropolitan MANETs , Computer Communications, 30 (4): 685-697, 2007
  • E. Alba, B. Dorronsoro, Hücresel GA ile Kapasiteli VRP için Şimdiye Kadarki En İyi Dokuz Yeni Çözümün Hesaplanması , Bilgi İşleme Mektupları, Elsevier, 98 (6): 225-230, 30 Haziran 2006
  • M. Giacobini, M. Tomassini, A. Tettamanzi, E. Alba, The Selection Intensity in Cellular Evolutionary Algorithms for Regular Lattices, IEEE Process on Evolutionary Computation, IEEE Press, 9 (5): 489-505, 2005
  • E. Alba, B. Dorronsoro, Dinamik Hücresel Genetik Algoritmalarda Keşif / Sömürü Değişimi, Evrimsel Hesaplamada IEEE İşlemleri, IEEE Press, 9 (2) 126-142, 2005

Dış bağlantılar