Evrimsel algoritma - Evolutionary algorithm

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:

  1. Popülasyondaki her bireyin uygunluğunu değerlendirin (zaman sınırı, yeterli uygunluk sağlandı, vb.)
  2. Üreme için en uygun bireyleri seçin . (Ebeveynler)
  3. Breed üzerinden yeni bireyler çaprazlama ve mutasyon doğurmak operasyonlar yavru .
  4. 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:

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 algoritmaRichard 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

Referanslar

Dış bağlantılar

bibliyografya