Genetik Algoritmalar Knuth problemi gibi problemler için uygun mu?
Hepimiz Genetik Algoritmaların optimal veya optimale yakın bir çözüm sağlayabileceğini biliyoruz. Bu nedenle, NP-zor olanlar gibi bazı problemlerde, zaman ve optimal çözüm arasında bir değiş tokuşla, neredeyse optimal çözüm yeterince iyidir.
En uygun çözümü bulmanın garantisi olmadığına göre GA, Knuth problemini çözmek için iyi bir seçim olarak kabul edilir mi?
Yapay zekaya göre: Modern bir yaklaşım (üçüncü baskı), bölüm 3.2 (s. 73):
Knuth, 4 sayısından başlayarak, bir dizi faktöriyel, karekök ve taban işlemlerinin istenen herhangi bir pozitif tam sayıya ulaşacağını tahmin etti.
Örneğin, 4'ten 5'e ulaşılabilir:
kat (sqrt (sqrt (sqrt (sqrt (sqrt ((4!)!))))))
Öyleyse, bir sayı (5) varsa ve belirtilen sayıya ulaşmak için bahsedilen 3 kişinin işlemlerinin sırasını bilmek istiyorsak, kromozomun her bir geni, belirli bir işlemi temsil eden bir sayı olacaktır. (işlem yok) ve uygunluk işlevi, verilen sayı ile her bir kromozom için işlemleri belirli bir sırayla uygulayarak elde ettiğimiz sayı arasındaki mutlak fark olacaktır (en az). İterasyonların (nesillerin) sayısının optimal bir çözüm olmadan yapıldığını ve elimizdeki en yakın sayının 4 (uygunluk 1 ile) olduğunu düşünelim, sorun şu ki 4'e hiçbir işlem uygulamadan 4 elde edebiliriz, 5 için ise ihtiyacımız var. birçok işlem, dolayısıyla optimal çözüm, çözüme yakın bile değildir.
Öyleyse, GA bu tür problemler için uygun değil mi? Veya önerilen kromozom gösterimi ve uygunluk işlevi yeterince iyi değil mi?
Yanıtlar
Sorunuza daha doğrudan cevap vermeye çalışmadan önce, bir şeyi açıklığa kavuşturmama izin verin.
İnsanlar genellikle genetik algoritmalar (GA'lar) terimini kullanırlar , ancak çoğu durumda gerçekte kastettikleri şey , popülasyon tabanlı (yani birden fazla çözüm aynı anda korunur) optimizasyon algoritmalarından oluşan evrimsel algoritmalardır (EA'lar) ve esinlenerek yaklaşımlar Darwinizm ve en güçlünün hayatta kalması . GA'lar, kromozomların ikili olduğu ve hem mutasyon hem de çapraz işlemin olduğu bu yaklaşımlardan biridir. Evrim stratejileri veya genetik programlama gibi başka yaklaşımlar da vardır .
Sizin de fark ettiğiniz gibi, EA'lar meta-sezgiseldir ve yakınsama özellikleriyle ilgili bazı araştırmalar [ 1 ] olmasına rağmen , pratikte yakınlaşmayabilirler. Bununla birlikte, başka herhangi bir potansiyel yaklaşım başarısız olduğunda, EA'lar kesinlikle faydalı olabilir.
Sizin durumunuzda, sorun gerçekten diğer küçük işlevlerden oluşan bir işlevin kapalı form (veya analitik ) ifadesini bulmaktır . Bu gerçekten genetik programlamanın (özellikle ağaç temelli GP) için yaratıldığı şeydir . Aslında, Knuth problemi, GP'nin uygulandığı tipik bir problem olan sembolik regresyon probleminin belirli bir örneğidir. Yani, GP muhtemelen denemeniz gereken ilk yaklaşımdır.
Bu arada, DEAP'de Knuth sorununu çözmeye çalışan basit bir program uyguladım. Buradan kontrol edin . Şimdiye kadar bulduğu en iyi çözümün uygunluğu (bir miktar tohumla) 4'tür ve çözüm floor(sqrt(float(sqrt(4))))(burada float, tür güvenliğini sağlamak için girişi bir kayan noktalı sayıya dönüştürür). Farkı uygunluk işlevi olarak kullandım ve GP algoritmasını 100 nesil boyunca her nesil için 100 bireyle çalıştırdım (ki bu çok değil !). Hiper parametrelerde fazla ince ayar yapmadım, bu yüzden belki doğru çekirdek ve hiper parametrelerle doğru çözümü bulabilirsiniz.
Endişelerinizi gidermek için prensip olarak bu kodlamayı kullanabilirsiniz, ancak not ettiğiniz gibi GA gerçekten de geri dönebilir $4$ en iyi çözüm olarak (ki bu aslında çok da uzak değil $5$), ki her nesilde, tam da bu değere sahip kişileri öldürmemi önleyebilirsiniz.
Bu problemi uygulamak ve düşünmek için çok fazla zaman harcamadım, ancak yukarıda da söylediğim gibi, genetik programlama ve sadece Knuth'un işlemlerini kullansam bile, yerel optimada takılıp kalabilir. Benim (veya sizin) uygulamanızı çarpma ve toplama gibi diğer işlemlerle artırmayı deneyebilir ve bir şeyin iyileşip iyileşmediğini görebilirsiniz.