Bir Evrimsel Algoritma (EA), yapay zekadaki evrimsel hesaplamanın bir alt kümesidir. Evrimsel hesaplama, biyolojik evrimden esinlenen küresel optimizasyona yönelik bir algoritma ailesidir. Big Data ile bilgi çağının hızlı gelişimi, optimizasyon problemlerinin boyutunda ve karmaşıklığında artışa neden olmuştur. Bir EA bağlamında, bu sonuçta, bireylerin uygunluk değerlendirmesi (optimal çözüm araması için kullanılır) hesaplama maliyetinin son derece yüksek olmasıyla birlikte arama alanının genişlemesiyle sonuçlanır. [1].
EA varyantlarının derinliklerine indiğimizde, aşağıdaki farklı türleri gözlemliyoruz:
Bu makalede, esas olarak iki türü olan Paralel EA varyantına odaklanacağız ve ardından değerlendirme zaman sapması sorununu derinlemesine anlamaya çalışacağız.
Geleneksel nesilsel EA'lar sıralı EA'dan türetilmiştir ancak paralelliği indüklemek için formüle edilmiştir [2]. Bununla birlikte, bu algoritmalar senkronizasyon gerektirir ve bireyler arasında uygunluk değerlerini değerlendirmek için zaman farkı olduğunda genellikle boşta kalma süresi problemiyle karşı karşıya kalırlar. Bu genellikle CPU kaynaklarının israfına ve paralelleştirmenin engellenmesine neden olur. Bu sorunu çözmek için, her seferinde bir bireysel yavru neslinin ve ardından onların uygunluk değerlendirmesinin yapıldığı bir kararlı durum modeline dayanan eşzamansız EA'lara [2] sahibiz. Bir birey için uygunluk değerlendirmesi tamamlanır tamamlanmaz, senkronizasyona ihtiyaç duymadan mevcut popülasyondaki bir yer için hemen rekabet edebilir. Bu süreç sonunda hesaplama kaynaklarının etkin kullanımına yardımcı olur ve verimli paralel işlemeyi teşvik eder. Bununla birlikte, eşzamansız EA'lar, Değerlendirme-Zaman sapması denen sorunla karşı karşıyadır.
Değerlendirme-Zaman Önyargısı [3], kendini popülasyondaki diğer bireylere göre hızlı değerlendiren bireylerin bir EA'da üreme avantajına sahip olduğu kalıtsal olgudur. Bu, nihayetinde uzun süre değerlendiren bireyleri dezavantajlı bir duruma sokar, çünkü hızlı değerlendiren bireyler yavru üretme konusunda daha fazla fırsata sahiptir. Bu aynı zamanda, hızlı değerlendirilen bölgelere yönelik ve arama alanının uzun değerlendirme bölgelerinden uzaklaşan ve böylece erken bir yakınsama ile sonuçlanan çözüm arayışına da yol açar. Bununla birlikte, daha hızlı değerlendiren bireylerin tümü daha iyiyse, bazen değerlendirme zamanı sapması bir algoritmada yararlı olabilir, ancak aynı zamanda hepsi daha kötüyse yakınsamayı engelleyebilir [4]. Dikkate değer bir şekilde, düz bir uygunluk ortamında yürütülen bir deneyde, değerlendirme, daha hızlı veya daha yavaş bölgelere yönelik önyargı kanıtı göstermedi, bu da önyargının belirli koşullar altında küçük veya ihmal edilebilir olabileceğini gösterdi [2]. Bir çözüm olarak ve senaryoya bağlı olarak, bazen yüksek kaliteli çözümleri uzun değerlendirme süreleriyle cezalandırmak, EA'nın erken yakınsamasını önlemeye ve performansını artırmaya yardımcı olabilir [5].
Aşağıda, değerlendirme zaman sapması sorununu çözmek için yürütülen ve daha ileri araştırma yönlerinin temellerini atan iki erken araştırma çalışması gösterilmektedir.
Yarı-Kuşak Eşzamansız Evrimsel Algoritma (QGEA)
QGEA [6], eşzamanlı ve eşzamansız EA'nın bazı yönlerini, her iki dünyanın en iyisi için yeni bir algoritma olarak birleştirir. Önerilen bu algoritma, ne boşta kalma süresi ne de hızlı çözümlere yönelik önemli bir önyargıya neden olacak bir ara çözüm olarak hizmet eder. QGEA, boşta kalma süresini en aza indiren popülasyondaki bireyleri değerlendirmek için asenkron değerlendirme şemasını kullanır. Bununla birlikte, değerlendirilen bireyler doğrudan ebeveyn popülasyonuna eklenmez. Bunun yerine, ayrı bir çocuk popülasyonu oluşturulur ve oraya birer birer eklenirler. Çocuk nüfusunun tam kapasitesine ulaşıldığında, ebeveyn nüfusun yerini alır ve yeni bir çocuk popülasyonu yaratılır. Bu algoritma ile geleneksel EA arasındaki fark, her ebeveyn grubundan daha fazla çocuk oluşturması ve bu da tüm işlemcileri meşgul tutmaya yardımcı olması gerçeğinde yatmaktadır. Popülasyondaki değişiklikler, tanımlanmış her adımdan sonra popülasyonun tamamen değiştirilmesiyle nesilsel bir şekilde gerçekleşir.
Interleaving Generations (IGEA) ile Evrimsel Algoritma
IGEA [4], standart nesil EA'ya eşdeğerdir ancak farklı nesillerden uygunluk değerlendirmelerini araya ekleyerek hesaplama kaynaklarının daha iyi kullanılmasına izin verir, böylece değerlendirme zamanı sapmasını önler ve daha iyi bir paralelleştirme potansiyeli sergiler. Algoritmanın ana fikri, yeni nesilden bazı bireylerin mevcut nesil tamamen değerlendirilmeden üretilebilmesinde yatmaktadır. Standart bir EA'da olduğu gibi CPU boşta kalma süresine maruz kalmak yerine, IGEA bunu, boştaki CPU'lar tarafından oluşturulan bireylerin değerlendirilmesi yoluyla ortadan kaldırmaya çalışır ve böylece işlemci düğümlerinin, daha yavaş değerlendiren bireylerin değerlendirmelerini tamamlamasını beklemesini gerektirmez. IGEA'nın iki çeşidi vardır, virgül sürümü (Î », λ) ve artı sürümü (Î »+ λ). Virgül versiyonu Î »popülasyonuna sahiptir ve her nesilde bir sonraki nesilde kullanılmak üzere λ yavrular üretir. Artı sürüm, Î »ebeveynlerden λ yavrular üretir, ardından Î »birleşik yavru ve ebeveyn popülasyonundan bireyler gelecek nesil için seçilir.
Bununla birlikte, deneysel değerlendirmelerine dayanarak, her iki erken yaklaşım da belirli sınırlamalar sergilemektedir, QGEA yaklaşımı, değerlendirme-zaman sapması sorununu çözmemekte ve çok düşük bir yakınsama oranı sergilemektedir. IGEA yaklaşımı eşzamansız ÇD şemasına dayanmamaktadır ve bu nedenle değerlendirme zamanı sapması sergilememektedir. Nesillerin serpiştirilmesi, ancak bireylerin seçilmesinin, tüm bireylerin infazdan önce değerlendirilmesini gerektirmediği durumlarda işe yarayabilir. Bu nedenle, IGEA yaklaşımı, standart nesilsel EA nesillerini serpiştirerek değerlendirme-zaman yanlılığı sorununu ortadan kaldırmayı amaçlamakta, ancak aynı zamanda asenkron EA'lar gibi sınırsız paralellik kullanımına izin vermemektedir.
Daha yakın zamanlarda, bu alanda iki araştırma daha yayınladık. [7] 'de her bir çözümün arama ilerlemesini hesaba katarak değerlendirme zamanı önyargısının etkisini azaltmak için yeni bir ana seçim stratejisi önerilmiştir. Asenkron NSGA-III [8] kullanılarak deneysel olarak değerlendirildiğinde önerilen bu yöntem, hesaplama süresini ve değerlendirme-zaman sapmasının etkisini azaltmaya yardımcı olur. Başka bir araştırma çalışması [9], IGEA [4] üzerine inşa edilmekte ve IGEA'daki geçici yavruların öncelik değerlendirmesi kavramı yoluyla CPU kullanımını iyileştirmeye odaklanan bir çözüm önermektedir.
[1] Gong, YJ, Chen, WN, Zhan, ZH, Zhang, J., Li, Y., Zhang, Q. ve Li, JJ, 2015. Dağıtılmış evrimsel algoritmalar ve modelleri: Durumun bir araştırması -Sanat. Applied Soft Computing, 34, s.286–300.
[2] Scott, E.O. ve De Jong, K.A., 2015, Ocak. Basit eşzamansız evrimsel algoritmaları anlama. Genetik Algoritmaların Temelleri XIII 2015 ACM Konferansı Bildirilerinde (s. 85–98).
[3] Scott, E.O. ve De Jong, K.A., 2015, Temmuz. Eşzamansız evrimsel algoritmalarda değerlendirme zamanı önyargısı. 2015 Yıllık Genetik ve Evrimsel Hesaplama Konferansı Tamamlayıcı Yayını Bildirilerinde (s. 1209-1212).
[4] Pilât, M. ve Neruda, R., 2017, Temmuz. Serpiştirme nesilleriyle paralel evrimsel algoritma. Proceedings of the Genetic and Evolutionary Computation Conference (s. 865-872).
[5] Yagoubi, M., Thobois, L. ve Schoenauer, M., 2011, Haziran. Heterojen değerlendirme maliyetleri ile eşzamansız evrimsel çok amaçlı algoritmalar. 2011'de IEEE Evrimsel Hesaplama Kongresi (CEC) (s. 21-28). IEEE.
[6] Scott, E.O. ve De Jong, K.A., 2016, Temmuz. Yarı nesilsel ve sabit durumlu eşzamansız evrim algoritmalarında değerlendirme zamanı önyargısı. Proceedings of the Genetic and Evolutionary Computation Conference 2016 (s. 845-852).
[7] Harada, T., 2020, Aralık. Eşzamansız Paralel Çok Amaçlı Evrimsel Algoritmalarda Değerlendirme Zamanı Önyargısını Önlemek için Arama İlerlemesine Bağlı Ana Seçim. 2020'de IEEE Sempozyum Serisi Hesaplamalı Zeka (SSCI) (s. 1013-1020). IEEE.
[8] Deb, K. ve Jain, H., 2013. Referans noktasına dayalı baskın olmayan sıralama yaklaşımını kullanan evrimsel çok amaçlı optimizasyon algoritması, bölüm I: kutu kısıtlamalarıyla problem çözme. Evrimsel hesaplama üzerine IEEE işlemleri, 18 (4), s. 577-601.
[9] Noguchi, H., Sonoda, A., Harada, T. ve Thawonmas, R., 2020, Eylül. Belirsiz Yavruların Öncelik Değerlendirmesi ile Araya Giren Nesil Evrimsel Algoritma. 2020'de Japonya Enstrüman ve Kontrol Mühendisleri Derneği'nin (SICE) 59. Yıllık Konferansı (s. 832 --- 837). IEEE.
Evrimsel Algoritmalarda Değerlendirme-Zaman Önyargısı, ilk olarak, insanların bu hikayeyi vurgulayarak ve yanıtlayarak konuşmaya devam ettikleri Ortamda AI'ya Doğru'da yayınlandı.
AI'ya Doğru aracılığıyla yayınlandı
Kaynak: TowardsAI