Evrimsel algoritma - Evolutionary algorithm
Bir serinin parçası |
Yapay zeka |
---|
In hesaplama zeka (CI), bir evrimsel algoritma ( EA ) bir olan alt kümesi içinde evrimsel hesaplama , genel toplum tabanlı metasezgisel optimizasyon algoritması . Bir EA üreme , mutasyon , rekombinasyon ve seleksiyon gibi biyolojik evrimden esinlenen mekanizmaları kullanır . Aday çözümleri için optimizasyon problemine bir popülasyonda bireylerin rol oynar ve uygunluk fonksiyonu (ayrıca bkz çözümlerin kalitesini belirleyen kaybı fonksiyonu ). Popülasyonun evrimi , yukarıdaki operatörlerin tekrar tekrar uygulanmasından sonra gerçekleşir.
Evrimsel algoritmalar, ideal olarak altta yatan uygunluk ortamı hakkında herhangi bir varsayımda bulunmadıklarından, genellikle her tür problem için iyi yaklaşık çözümler gerçekleştirir . Biyolojik evrimin modellenmesine uygulanan evrimsel algoritmalardan gelen teknikler, genellikle mikroevrimsel süreçlerin araştırılması ve hücresel süreçlere dayalı planlama modelleri ile sınırlıdır . EA'ların çoğu gerçek uygulamasında, hesaplama karmaşıklığı yasaklayıcı bir faktördür. Aslında, bu hesaplama karmaşıklığı uygunluk fonksiyonu değerlendirmesinden kaynaklanmaktadır. Uygunluk yaklaşımı , bu zorluğun üstesinden gelmek için çözümlerden biridir. Ancak, görünüşte basit olan EA, genellikle karmaşık sorunları çözebilir; bu nedenle, algoritma karmaşıklığı ile problem karmaşıklığı arasında doğrudan bir bağlantı olmayabilir.
uygulama
Aşağıdaki, genel bir tek amaçlı genetik algoritma örneğidir .
Birinci Adım: İlk üret nüfusu içinde bireyler rastgele. (Birinci nesil)
İkinci Adım: Aşağıdaki yenileme adımlarını sonlandırana kadar tekrarlayın:
- Popülasyondaki her bireyin uygunluğunu değerlendirin (zaman sınırı, yeterli uygunluk sağlandı, vb.)
- Üreme için en uygun bireyleri seçin . (Ebeveynler)
- Breed üzerinden yeni bireyler çaprazlama ve mutasyon doğurmak operasyonlar yavru .
- Nüfusun en uygun olmayan bireylerini yeni bireylerle değiştirin.
Türler
Benzer teknikler, genetik temsil ve diğer uygulama detayları ve uygulanan özel problemin doğası bakımından farklılık gösterir .
- Genetik algoritma – Bu, en popüler EA türüdür. Bir problemin çözümünü, rekombinasyon ve mutasyon (bazen bir, bazen her ikisi) gibi operatörleri uygulayarak, sayı dizileri (geleneksel olarak ikili, en iyi temsiller genellikle çözülmekte olan problem hakkında bir şeyi yansıtanlar olmasına rağmen) şeklinde arar. . Bu tür EA genellikle optimizasyon problemlerinde kullanılır .
- Genetik programlama - Burada çözümler bilgisayar programları biçimindedir ve uygunlukları bir hesaplama problemini çözme yetenekleriyle belirlenir. Kartezyen genetik programlama , Gen ifadesi programlama , Dilbilgisel Evrim , Doğrusal genetik programlama , Çoklu ifade programlama vb. dahil olmak üzere birçok Genetik Programlama çeşidi vardır .
- Evrimsel programlama – Genetik programlamaya benzer, ancak programın yapısı sabittir ve sayısal parametrelerinin gelişmesine izin verilir.
- Evrim stratejisi – Çözümlerin temsili olarak gerçek sayıların vektörleriyle çalışır ve tipik olarak kendi kendine uyarlanan mutasyon oranlarını kullanır.
- Diferansiyel evrim – Vektör farklılıklarına dayanır ve bu nedenle öncelikle sayısal optimizasyon problemleri için uygundur .
- Nöroevrim – Genetik programlamaya benzer, ancak genomlar yapı ve bağlantı ağırlıklarını tanımlayarak yapay sinir ağlarını temsil eder. Genom kodlaması doğrudan veya dolaylı olabilir.
- Öğrenme sınıflandırıcı sistemi – Burada çözüm bir dizi sınıflandırıcıdır (kurallar veya koşullar). Bir Michigan-LCS, bireysel sınıflandırıcılar düzeyinde gelişirken, bir Pittsburgh-LCS, sınıflandırıcı kümelerinin popülasyonlarını kullanır. Başlangıçta, sınıflandırıcılar yalnızca ikili idi, ancak şimdi gerçek, sinir ağı veya S-ifadesi türlerini içeriyor . Uygunluk tipik olarak ya bir güç ya da doğruluk temelli pekiştirmeli öğrenme ya da denetimli öğrenme yaklaşımı ile belirlenir.
Biyolojik süreçlerle karşılaştırma
Birçok evrimsel algoritmanın olası bir sınırlaması, açık bir genotip-fenotip ayrımının olmamasıdır . Doğada, döllenmiş yumurta hücresi , olgun bir fenotip haline gelmek için embriyogenez olarak bilinen karmaşık bir süreçten geçer . Bu dolaylı kodlamanın genetik aramayı daha sağlam hale getirdiğine (yani ölümcül mutasyonların olasılığını azalttığına) ve ayrıca organizmanın evrimleşebilirliğini iyileştirebileceğine inanılmaktadır . Bu tür dolaylı (üretken veya gelişimsel olarak da bilinir) kodlamalar, evrimin çevredeki düzenlilikten yararlanmasını da sağlar. Yapay embriyogeni veya yapay gelişim sistemleri alanındaki son çalışmalar, bu endişeleri gidermeye çalışmaktadır. Ve gen ekspresyon programlaması , genotipin sabit uzunlukta lineer multigenik kromozomlardan oluştuğu ve fenotipin farklı boyut ve şekillerde çoklu ifade ağaçlarından veya bilgisayar programlarından oluştuğu bir genotip-fenotip sistemini başarılı bir şekilde araştırır.
İlgili teknikler
Sürü algoritmaları şunları içerir:
- Karınca kolonisi optimizasyonu , yollar oluşturmak için feromon iletişimi yoluyla karınca arama fikirlerine dayanmaktadır. Öncelikle kombinatoryal optimizasyon ve grafik problemleri için uygundur .
- Koşucu-kök algoritması (RRA), doğadaki bitki köklerinin ve koşucuların işlevinden esinlenmiştir.
- Yapay arı kolonisi algoritması , bal arısının yiyecek arama davranışına dayanmaktadır. Öncelikle sayısal optimizasyon için önerilmiş ve kombinatoryal, kısıtlı ve çok amaçlı optimizasyon problemlerini çözmek için genişletilmiştir.
- Arı algoritması , bal arılarının yiyecek arama davranışına dayanmaktadır. Yönlendirme ve çizelgeleme gibi birçok uygulamada uygulanmıştır.
- Guguk kuşu araması , guguk kuşu türlerinin kuluçka parazitliğinden esinlenmiştir . Ayrıca Lévy uçuşlarını kullanır ve bu nedenle küresel optimizasyon sorunları için uygundur.
- Parçacık sürüsü optimizasyonu , hayvan sürüsü davranışı fikirlerine dayanmaktadır. Ayrıca öncelikle sayısal optimizasyon problemleri için uygundur .
Diğer popülasyon tabanlı metasezgisel yöntemler
- Av Arama – Her biri diğerlerinin ve özellikle liderlerinin konumuna göre konumlarını avı çevreleyecek şekilde organize eden kurtlar gibi bazı hayvanların grup avından esinlenen bir yöntem. Kombinatoryal optimizasyon yöntemi olarak uyarlanmış sürekli bir optimizasyon yöntemidir.
- Uyarlanabilir boyutlu arama – Doğadan ilham alan metasezgisel tekniklerin aksine, uyarlanabilir boyutlu arama algoritması, temel ilke olarak herhangi bir metafor uygulamaz. Bunun yerine, her yinelemede arama boyutluluk oranı (SDR) parametresinin güncellenmesine dayanan basit bir performans odaklı yöntem kullanır.
- Ateşböceği algoritması , ateşböceklerinin yanıp sönen ışıkla birbirlerini çeken davranışlarından esinlenmiştir. Bu özellikle çok modlu optimizasyon için kullanışlıdır.
- Armoni arama – Müzisyenlerin daha iyi armoniler aramadaki davranış fikirlerine dayanır. Bu algoritma, parametre optimizasyonunun yanı sıra kombinatoryal optimizasyon için de uygundur.
- Gauss uyarlaması – Bilgi teorisine dayalıdır. Üretim verimini, ortalama uygunluk veya ortalama bilgiyi maksimize etmek için kullanılır . Örneğin termodinamik ve bilgi teorisinde Entropi'ye bakın .
- Memetik algoritma – Richard Dawkins'in mem kavramından esinlenen hibrit bir yöntem, genellikle yerel iyileştirmeler gerçekleştirebilen bireysel öğrenme prosedürleriyle birleştirilmiş popülasyona dayalı bir algoritma şeklini alır. Soruna özel bilginin kullanımını vurgular ve yerel ve küresel aramayı sinerjik bir şekilde düzenlemeye çalışır.
Örnekler
2020'de Google , AutoML-Zero'larının sinir ağları kavramı gibi klasik algoritmaları başarıyla yeniden keşfedebileceğini belirtti.
Bilgisayarın simülasyonları Tierra ve Avida biçimlendirme girişiminde makroevrimsel dinamikleri.
Galeri
Sınırlı global optimuma sahip kısıtlı bir Rosenbrock fonksiyonu üzerinde iki popülasyonlu bir EA araştırması .
Kısıtlı bir Rosenbrock işlevi üzerinde iki popülasyonlu bir EA araması . Global optimum sınırlı değildir.
Simionescu'nun fonksiyonunun sınırlı bir optimumunun iki popülasyonlu bir EA araştırması .
Referanslar
Dış bağlantılar
bibliyografya
- Ashlock, D. (2006), Modelleme ve Optimizasyon için Evrimsel Hesaplama , Springer, ISBN 0-387-22196-4 .
- Bäck, T. (1996), Teori ve Pratikte Evrimsel Algoritmalar: Evrim Stratejileri, Evrimsel Programlama, Genetik Algoritmalar , Oxford Üniv. Basmak.
- Bäck, T., Fogel, D., Michalewicz, Z. (1997), Handbook of Evolutionary Computation , Oxford Üniv. Basmak.
- Banzhaf, W., Nordin, P., Keller, R., Francone, F. (1998), Genetik Programlama - Bir Giriş , Morgan Kaufmann, San Francisco
- Eiben, AE, Smith, JE (2003), Evrimsel Hesaplamaya Giriş , Springer.
- Holland, JH (1992), Doğal ve Yapay Sistemlerde Adaptasyon , Michigan Üniversitesi Yayınları, Ann Arbor
- Michalewicz Z., Fogel DB (2004). Nasıl Çözülür: Modern Sezgisel, Springer.
- Benko, Atilla; Dosa, Gyorgy; Tuza, Zsolt (2010). "Bin Paketleme/Teslimat ile Kaplama, algoritmaların evrimi ile çözüldü". 2010 IEEE Fifth International Conference on Bio-Inspired Computing: Theories and Applications (BIC-TA) . s. 298–302. doi : 10.1109/BICTA.2010.5645312 . ISBN'si 978-1-4244-6437-1. S2CID 16875144 .
- Poli, R.; Langdon, WB; McPhee, NF (2008). Genetik Programlama için Alan Kılavuzu . Lulu.com, internetten ücretsiz olarak erişilebilir. ISBN'si 978-1-4092-0073-4. Arşivlenmiş orijinal 2016-05-27 tarihinde . 2011-03-05 alındı .
- Price, K., Storn, RM, Lampinen, JA, (2005). "Diferansiyel Evrim: Küresel Optimizasyona Pratik Bir Yaklaşım" , Springer.
- Ingo Rechenberg (1971): Evolutionsstrategie - Optimierung technischer Systeme nach Prinzipien der biologischen Evolution (Doktora tezi). Fromman-Holzboog (1973) tarafından yeniden basılmıştır.
- Hans-Paul Schwefel (1974): Numerische Optimierung von Computer-Modellen (Doktora tezi). Birkhäuser (1977) tarafından yeniden basılmıştır.
- Simon, D. (2013): Evrimsel Optimizasyon Algoritmaları , Wiley.
- Hesaplamalı Zeka: Kruse, Borgelt, Klawonn, Moewes, Steinbrecher, Held, 2013, Springer, ISBN 978-1-4471-5012-1 tarafından Metodolojik Bir Giriş
- Rahman, Rosshairy Abd.; Kendal, Graham; Ramli, Razamin; Jamari, Zainoddin; Ku-Mahamud, Ku Ruhana (2017). "Kısıtlamaların Ele Alınması için Güç Sezgiselleri ile Evrimsel Algoritma ile Karides Yemi Formülasyonu" . Karmaşıklık . 2017 : 1–12. doi : 10.1155/2017/7053710 .