Evrimsel bir algoritma (EA), yapay zekada evrimsel bir hesaplamanın bir alt kümesidir. Evrimsel hesaplama, biyolojik evrimden ilham alan küresel optimizasyon için bir algoritma ailesidir. Bilgi çağının büyük verilerle hızlı gelişimi, optimizasyon problemlerinin boyutunda ve karmaşıklığında bir artışa neden olmuştur. Bir EA bağlamında, bu nihayetinde arama alanının fitness değerlendirmesi ile genişletilmesine (en iyi çözüm arama için kullanılır), bireylerin son derece yüksek olması için hesaplama maliyeti [1].
EA varyantlarına derin dalış, aşağıdaki farklı türleri gözlemliyoruz,
Bu yazıda, çoğunlukla iki türüyle paralel EA varyantına odaklanacağız ve daha sonra değerlendirme zamanındaki önyargı sorununu anlamak için derinlere dalacağız.
Geleneksel nesiller, sıralı EA'dan türetilmiştir, ancak paralelliği teşvik etmek için formüle edilmiştir [2]. Bununla birlikte, bu algoritmalar senkronizasyon gerektirir ve genellikle fitness değerini değerlendirmek için bireyler arasında zaman varyansı olduğunda, rölanti süresi sorunuyla karşı karşıya kalırlar. Bu genellikle CPU kaynaklarının israfını ve paralelleşmenin bir engeliyle sonuçlanır. Bu sorunu çözmek için, bireysel bir çocuğun bir kereye mahsus bir modeline dayanan sabit durum modeline dayanan asenkron EAS [2] var. Bir kişinin uygunluk değerlendirmesi tamamlandığı anda, derhal mevcut popülasyondaki bir yer için senkronizasyona ihtiyaç duymadan rekabet edebilir. Bu işlem sonunda, hesaplamalı kaynakların etkin kullanılmasına yardımcı olur ve verimli paralel işleme neden olur. Bununla birlikte, asenkron eas, sözde değerlendirme süresi önyargısı sorunu ile karşı karşıya kalır.
Değerlendirme-zaman önyargısı [3], nüfusundaki diğer bireylere kıyasla kendilerini hızlı bir şekilde değerlendiren bireylerin bir EA'da üreme avantajına sahip olduğu komik olgudur. Bu, sonunda, hızlı değerlendiren bireylerin yavrular üretmek için daha fazla fırsata sahip olduğu için uzun süre değerlendiren bireyleri bir dezavantaja sokar. Bu, aynı zamanda hızlı değerlendiren bölgelere yönelik ve arama alanının uzun değerleme bölgelerine doğru önyargılı olan ve bu nedenle erken bir yakınsama ile sonuçlanan çözüm aramasına yol açar. Bununla birlikte, bazen değerlendirme süresi önyargıları bir algoritmada yardımcı olabilir, eğer tüm daha hızlı değerlendiren bireyler daha iyidir, ancak aynı zamanda tüm bunlar daha kötüse yakınsama engelleyebilir [4]. Dikkate dayanarak, düz bir fitness manzarasında yapılan bir deneyde, değerlendirme, önyargının belirli koşullar altında küçük veya ihmal edilebilir olabileceğini gösteren daha hızlı veya daha yavaş bölgelere yönelik önyargı kanıtı göstermedi [2]. Bir çözüm olarak ve senaryona bağlı olarak, bazen uzun değerlendirme sürelerine atanarak yüksek kaliteli çözeltileri cezalandırmak, EA'nın erken birleşmesini önlemeye ve performansını iyileştirmeye yardımcı olabilir [5].
Aşağıda resimli, değerlendirme zamanı-önyargı sorununu çözmek için gerçekleştirilen iki erken araştırma çalışmasıdır ve daha fazla araştırma yönü için temelleri belirledi,
Yarı-Olumsuz Asenkron Evrimsel Algoritma (QGEA)
QGEA [6] Senkron ve asenkron EA'nın bazı yönlerini her iki dünyanın en iyisi için yeni bir algoritma olarak birleştirir. Önerilen bu algoritma, boş zamanlar ne de hızlı çözümlere yönelik önemli önyargılara neden olacak bir ara çözüm olarak hizmet vermektedir. QGEA, rölantide en aza indiren popülasyondaki bireyleri değerlendirmek için asenkron değerlendirme şemasını kullanır. Bununla birlikte, değerlendirilen bireyler doğrudan ana nüfusa eklenmez. Bunun yerine, ayrı bir çocuk nüfusu oluşturulur ve bir seferde bir kez eklenirler. Çocuk nüfusunun tam kapasitesi ulaşıldığında, ana nüfusun yerine geçer ve daha sonra yeni bir çocuk popülasyonu oluşturulur. Bu algoritma ile geleneksel EA arasındaki fark, her bir ebeveynden daha fazla çocuk ürettiği gerçeğinde yatıyor, bu da tüm işlemcilerin işgal edilmesine yardımcı olan. Nüfusun değişikliği, her tanımlanmış sayısının adımlarından sonra nüfusun tamamen değiştirilmesiyle reelasyonel bir şekilde gerçekleşir.
Interloaving Nesiller (IGEA) ile Evrimsel Algoritma
IGEA [4], standart nesil EA'ya eşdeğerdir, ancak fitness değerlendirmelerinin farklı nesillerden kaynaklanarak, hesaplama kaynaklarının daha iyi kullanılmasına izin verir, böylece değerlendirme süresinin önyargısızlığı önlenmesi ve daha iyi bir paralelleştirme potansiyeli sergilemesini sağlar. Algoritmanın ana fikri, bir sonraki nesilden gelen bazı kişilerin, mevcut nesil tamamen değerlendirilmeden önce üretilebileceği gerçeğindedir. CPU rölanti süresini standart bir EA'da olduğu gibi yapmak yerine, Igea, üretilen bireylerin boşta CPU'lar tarafından değerlendirilmesi yoluyla ortadan kaldırmaya çalışır ve böylece işlemci düğümlerinin, bireylerin yavaş değerlendirilmesine kadar beklemesini gerektirmez. Igea, virgül versiyonu (î », î») ve artı sürümü (î »+ î») iki varyant vardır. Virgül versiyonunun bir nüfusuna sahiptir »ve her nesilde bir sonraki nesilde kullanılacak î» yavrular üretir. Artı sürümü î »ebeveynlerden î» yavrular üretir, ardından î »Birleştirilmiş yavrulardan ve ana popülasyondan gelen bireyler yeni nesiller için seçilir.
Bununla birlikte, deneysel değerlendirmelerine dayanarak, erken yaklaşımların her ikisi de belirli sınırlamalar sergiler, QGEA yaklaşımı değerlendirme zamanı önyargısı sorununu çözmez ve aynı zamanda çok düşük bir yakınsama oranı sergiler. Igea yaklaşımı, asenkron EA şemasına dayanmaz ve bu nedenle değerlendirme süresi önyargısı göstermez. Nesillerin aralıkları yalnızca bireylerin seçimi, yürütmeden önce tüm bireylerin değerlendirilmesini gerektirmediğinde çalışabilir. Bu nedenle, IGEA yaklaşımı, standart jenerasyonel EA nesillerini birbirine bağlayarak değerlendirme süresi önyargısı sorununu ortadan kaldırmayı amaçlamaktadır, ancak aynı zamanda asenkron EA için gibi sınırsız paralelliğin kullanımına izin vermez.
Son zamanlarda geçen yılda, bu alanda yayınlanan iki araştırma çalışması yaptık. Değerlendirme süresi önyargının etkisini azaltmak için yeni bir ebeveyn seçim stratejisi, her bir çözeltinin arama ilerlemesi [7] 'de önerildi. Bu önerilen yöntem, asenkron NSGA-III [8] kullanılarak deneysel olarak değerlendirildiğinde, bilgi işlem süresini ve değerlendirme süresinin önyargısının etkisini azaltmaya yardımcı olur. Başka bir araştırma çalışması [9] Igea [4] üzerine inşa edilmiştir [4] ve CPU kullanımının, geçici yavruların öncelikli olarak değerlendirilmesi yoluyla CPU kullanımının iyileştirilmesine odaklanan bir çözüm önermektedir.
Özetleme, literatürden gözlendiği gibi, değerlendirme süresi önyargısının toplam ortadan kaldırılmasına yönelik somut bir çözüm yoktur. Dolayısıyla, Asenkron Eas'ta değerlendirme süresi önyargısı sorununun etkili bir şekilde ortadan kaldırılması ve açık araştırma sorunundaki çalışmaya ilişkin araştırma, değerlendirme süresinin belirli bir problem türü verilen bir EA'nın performansını nasıl etkileyeceğini tahmin etmek için açık araştırma sorusu üzerindeki araştırma Koşullar, araştırmanın bir sıcak nokta konusu olmaya devam ediyor.
[1] Gong, YJ, Chen, WN, Zhan, ZH, Zhang, J., Li, Y., Zhang, Q. ve Li, JJ, 2015. Dağıtılmış Evrimsel Algoritmalar ve Modelleri: Eyalet Anketi -Sanat. Uygulamalı Yumuşak Bilgi İşlem, 34, PP.286Â € "300.
[2] Scott, e.o. ve de Jong, K.A., 2015, Ocak. Basit asenkron evrimsel algoritmaları anlama. 2015 ACM konferansının, genetik algoritmaların temelleri konferansında XIII (PP. 85 € "98).
[3] Scott, e.o. ve de Jong, K.A., 2015, Temmuz. Asenkron evrimsel algoritmalarda değerlendirme süresi önyargısı. 2015 Yıllık Konferansının Genetik ve Evrimsel Hesaplama Konferansı'nın Yardımcılığının Bildirilerinde (PP. 1209 "1212).
[4] Pilát, M. ve Neruda, R., 2017, Temmuz. Aralıklı nesillerle paralel evrimsel algoritma. Genetik ve evrimsel hesaplama konferansının işlemlerinde (PP. 865 "872).
[5] Yagoubi, M., Thobois, L. ve Schoenauer, M., 2011, Haziran. Heterojen değerlendirme maliyetleri ile asenkron evrimsel çok amaçlı algoritmalar. 2011'de IEEE Evrimsel Hesaplama Kongresi (CEC) (PP. 21 21 "28) . IEEE.
[6] Scott, e.o. ve de Jong, K.A., 2016, Temmuz. Yarı-tehlikeli ve kararlı halde asenkron evrimsel algoritmalarda değerlendirme süresi önyargıları. Genetik ve Evrimsel Hesaplama Konferansı 2016'nın işlemlerinde (PP. 845 "852).
[7] Harada, T., 2020, Aralık. Asenkron paralel çok amaçlı evrimsel algoritmalarda değerlendirme zamanındaki önyargılardan kaçınmak için ilerleme bağımlı ebeveyn seçimi. Hesaplamalı zeka (SSCI) 'de 2020 IEEE Sempozyumu Serisinde (PP. 1013 "1020). IEEE.
[8] Deb, K. ve Jain, H., 2013. Referans noktaya dayalı nondominal sıralama yaklaşımını kullanarak evrimsel birçok nesnel optimizasyon algoritması, Bölüm I: Kutu kısıtlamaları ile ilgili sorunları çözme. IEEE Evrimsel Hesaplama, 18 (4), PP.577Â € "601.
[9] Noguchi, H., Sonoda, A., Harada, T. ve Thawonmas, R., 2020, Eylül. Geçiş üretimi, geçici yavruların öncelikli değerlendirmesiyle evrimsel algoritma. 2020 yılında 59. Yıllık Enstrüman Derneği ve Japonya'nın Kontrol Mühendisleri Konferansı (Sice) (s. 832 "837). IEEE.
Evrimsel algoritmalardaki değerlendirme süresi önyargıları, bu hikayeye vurgulayarak ve cevaplayarak insanların konuşmaya devam ettiği ortamda AI'ye doğru yayınlandı.
AI'ye doğru yayınlandı
Kaynak: TowardsAI