Genetik Algoritma Örneği

program-tanıtımları
#1

Genetik algoritmalar, doğada gözlemlenen evrimsel sürece benzer bir şekilde çalışan arama ve eniyileme yöntemidir. Karmaşık çok boyutlu arama uzayında en iyinin hayatta kalması ilkesine göre bütünsel en iyi çözümü arar. Genetik algoritmalar problemlerin çözümü için evrimsel süreci bilgisayar ortamında taklit ederler.

akış şeması

dpaste: dpaste.com/17EFGTT
Wikiwand sayfası: wikiwand.com/Genetik_algoritma
The Evolution of Code: natureofcode.com/chapter-9-the-evolution-of-code (Daniel Shiffman)

demo

#2

Fitness fonksiyonum (131-138 arası) hiç tatmin edici değil, önerileriniz varsa harika olur :slight_smile:

#3

Fitness fonksiyonunda (duz mesafe) bir sorun yok. Daha fazlasi, probleme ozel bilgi vermeyi gerektirir. Ha, sonuca (hedef olmasa bile) gelmek icin harcanmis enerjiyi veya gen sayisini da hesaba katabilirsin.

Noktalarin hedefe ulasamamasi normal; yuksek bir lokal maksimumdalar. Mutasyonu artirman lazim.

#4

Ayrica:

Hedefe gitmeye noktalarin omurleri yetmiyor. 350, hatta 500 yapmak baya yardimci oldu.

Seleksiyon stratejisi zayif. Hedefe cogunluktan daha fazla yaklasabilen bireyler olsa bile, genel nufusun vasatligi icinde kayboluyorlar. (Buraya ulkeyle ilgili elestiri gelecek)

Mesafenin karesini, 0~1 fitness oraninin kubunu bile almama ragmen fayda etmedi. En basarili N birey arasindan secim yapmak lazim olabilir.

Cok da kurcalayamadim, vaktim yok ve kod alistigim stilden daha atıl. Ornegin:

dot.calc_fitness + dot.fitness yerine fitness donduren tek bir fonksiyon kullanilabilir.
Ciftlesme fonksiyonu iki tane ebeveyn alip cocuklarini dondurmeli, ebeveyni coguca donusturmemeli.
gene_n’in ismi herhalde yanlis.

Fitness oranlarina gore ebeveyn secen adaylari havuza at, random sec yontemi, buyuk oran farklarina izin vermiyor. (x’in y’den 1,000,000 kat daha buyuk ihtimalle secilebilmesi icin, en az 1,000,000’luk array gerekiyor. :slight_smile: ) Havuzu kirpma yontemi de buna alternatif tabi.

Ellerine saglik.

1 Like
#5

Programı yazmaya başladığımda -acemilikten olsa gerek- dikdörtgen çizdirip bunu orijin etrafında döndürünce sorunun ne olduğunu bulmak için gereğinden fazla zaman harcadım, o yüzden üzerine pek düşünülmüş bir yapıya sahip bir şey çıkmadı ortaya :p.

Dediğiniz gibi mutasyon oranını arttırarak hedefe ulaşmalarını sağlayabiliyordum ama oran fazla olunca neslin küçük bir kısmı başarılı olabiliyor, tabii sonrasında bahsettiğiniz şeyler de bu sonucu etkiliyor.

Fitness fonksiyonunu sadece mesafeyi dikkate almanın ötesinde noktanın ölmeden önceki son halini de dikkate alması için düzenlemeyi düşünmüştüm, gittiği yönde herhangi bir engel var mı ve/veya duvarlara uzak mı gibisinden. Ama bu olayı tam olarak oturtamadığımdan uygulamaya geçirmek gibi bir girişimim olmadı. Vakit bulduğumda seleksiyon için farklı yollar deneyeceğim.

Zaman ayırıp cevap yazdığınız için teşekkür ederim.

#6

Zannetmiyorum, yillardir bu isi yapan insanlarin da basina geliyor :​)
Ha, “sorunun ne oldugunu bulma” teknikleri deneyimle birlikte feci sekilde gelisiyor (ama her zaman degil). Durup dururken Nature of Code ornekleri yapan biri olarak ilerlemekte problem yasayacagini zannetmiyorum :​).

Asil kafama takilan, ornek kodda bu simulasyonu hizlica cozecek parametreler yok mu? (Yoksa simulasyonu sifirdan sen mi yazdin? Sanki bir yerlerde daha once gormustum diye emin olamadim.) Dur, vaktim oldugunda biraz daha kurcalayayim.

#7

Dot’lara dead_at sayisi ekledim.

(Bu arada, tek gorevi ekrani cizmek olmasi gereken draw_loop kodu hem noktalarin olmesine karar veriyor (if self.is_dead(dot):) hem de noktanin sahip oldugu is_alive degiskenini disaridan degistiriyor. Bu noktada seni OOP’deki encapsulation prensibine yonlendirmek isterim. Normalde tamamen Dot sinifi icerisinde degisiklik yapmam gerekirken cizme koduna kadar bulastim.)

Neyse, fitness fonksiyonunu (1 - (dist/max_dist)) + (dead_at / lifespan) yapip uzun omru favor edince ve seleksiyon icin fitness oraninin karesini kullaninca (self.mating_pool += [dot] * int(n*n)) hedefi vurabilmeye basladilar. Mutation rate %5, lifespan 500 tick.

#8

@aib Geç geri dönüş için özür dilerim, vakit bulamadım.

Üzerine iyi düşünülmemiş bir yapısı var derken, bir değişiklik yapmaya kalkıştığınızda tüm programda değişiklikler yapmanız gerekiyor demek istiyordum :​p

Daha hızlı çözen parametrelerden kastınız nedir? Frame başına düşen tick sayısı mı demek istediniz? Şu hali ile her frame bir tick’e karşılık geliyor. Evet, ben yazdım bunu.

deat_at olayını implement etmeye çalıştım ama bir kaç kere saçma sapan hareketlerde bulunanlar fitness değerleri de iyi olunca herkese çember çizdirmeye başladılar, tabii mutasyon sayesinde sonraki nesiller bu durumdan kurtulabildi ama arada böyle olmasını rahatsız edici bulunca kaldırdım.

Konu hakkında bilgi edinme sürecimde bana eşlik ettiğiniz için teşekkür ederim, sanırım ilk postunuz olmasaydı üzerinde pek bir ek uğraşımın olmayacağı bir proje olacaktı.

İlgilenenler için projeyi biraz temizleyip GitHub üzerinde paylaştım: gh/0x3b6/smart-lines

#9

Ellerine saglik.

Ahah evet. Yanlis anlama, hic bir sikintisi yok; sadece disardan aceleyle girmesi zor.

Kod source control’de olsaydi su gordugum 1-2 seye PR yapardim, agirlikli seleksiyon havuzunu da daha oynanabilir yapmak icin array kullanmayan versiyona cevirirdim. Hedefe ulastirmayi basardigim parametreler de ayri branch olurdu.

Ilk 50 jenerasyonda hedefe ulasan, hatta butun populasyonu hedefe ulastiran parametreler (simulation_options ve fitness/seleksiyon algoritmasinda kullanilan gorunmez 1 carpanlari). Genellikle bu tur ornekler cozume hizlica converge eden parametrelerle beraber geldigi icin sordum. Problem orijinalmis ama; bunlari bulmak bize dusuyor.

Evet, sadece ayakta kalmayi sectigimizde oldugu yerde duranlar bile cikiyor. Fakat hedefe yaklasmakla ayakta kalmak arasinda dengeli bir nokta oldugunu dusunuyorum. 1:1 denedigimde cok kotu sonuc almadim.

Buradaki sikinti lokal maksimumun (alt duvar) global maksimumdan (hedef) cok uzakta olmasi. Nufusun cogunlugu lokal maksimumda takilirken hedefi bulma ihtimali olan uc-bes macerapereste destek olmak lazim.

Mutasyon oranini artirmamin sebebi o; 5-10 gen degisikligiyle olabilecek bir sey degil ikinci tepeyi bulmak.

Uzun omru odullendirmemin sebebi de o. Baslangic-alt duvar arasinda 200 tick varsa, alt duvar-hedef arasinda 300 tick daha olabilir. Lokal maksimumdan uzaklari kesfetmeyi, lokal minimumlari bulup artlarina gecmeyi tesvik etmek lazim.

Uzun omurle ilgili bir sey daha dusunmustum, ama denemedim: Omur boyunca elde edilmis hedefe minimum uzaklik cok guzel bir skor. Hedefi az farkla kacirip arkasindaki duvara toslayan (ve lokal minimumda kalanlara bin kat tercih edilecek) genlere de sans veriyor.

Son olarak optimizasyonu tesvik etmek icin omur terse alinabilir: hedefe maksimum yakinlik /- yasanmis tick sayisi. Yarisa girsin diye gene bagli bir degisken haline de getirilebilir. Ve kesfi hala tesvik etmek istedigimiz icin yeni bir pozitif parametre eklenebilir: Kat edilen toplam yol. Oldugu yerde donmeleri saymamak icin yola/noktalara bir smooting fonksiyonu uygulamak gerekir. Neyse, bu kadar hipotetige gerek yok, yeterice uzattim…

Super! Vaktim oldugunda bakacagim.