Genetik Algoritma

Genetik algoritma, temelde doğal evrim sürecini örnek alarak geliştirilen ilginç ve başarılı sonuçlar üretebilen, algoritmanın amacını çok iyi anlatan tanımıyla da bir arama ve optimizasyon yöntemidir. Çok çeşitli kullanım alanlarına sahiptir. Yöntemden çok önemli olan aslında yöntemin probleme uyarlanışıdır.

Bu algoritmanın işleyişini iyi anlamak için öncelikle baz alınan doğal evrim sürecini anlamak gerekir. Evrim, canlıların uzun vadede ortamlara adaptasyonlarını sağlayan onları zamanla "en iyi"leştiren bir süreç. Evrimin temel yasalarından biri, bu algoritmanın da temel dayanağını oluşturur; her zaman sadece "en iyi" olan yaşar ve çoğalır. Başarısız bireyler üreyemez ve elenir. İşte bu yüzden de kötüye gidiş zorlaşır ve zamanla daha iyiye gidilir..

Bu algritmanın uyarlanabilir yüzeysel bazı standartlar (evrimin ilkeleri) dışında tüm problemlerde kullanılabilecek belirgin standartları yoktur. Algoritma probleme göre şekillenir.

Bilgisayar dilinde, bu doğal süreci gerçeklemek için diziler ve alt diziler kullanılır. Diziler popülasyonu, bireyleri ve bireylerin genlerini barındırırlar. Burada bireylerden kasıt, çözüm uzayındaki yani çözümü içerisinde barındıran küme içerisindeki tüm elemanlardır. Her bir eleman, bütün elemanları kapsayabilecek uzunluktaki bitler dizisi ile temsil edilir. Bireyler popülasyonu oluşturur ve her bireyin bir uygunluk değeri vardır. Şimdi genetik algoritmanın adımlarını başlıklar altında yazalım.

Çözümleri Kodlama

Çözümler, herbiri aynı boyutta olan ve tüm arama uzayını kapsayabilecek uzunluktaki bit dizileridir. Kullanılan farklı kodlama biçimleri de vardır.

İlk Populasyonu Oluşturma

Populasyon, belli sayıda bireyden yani çözüm grubundan oluşur. (Birey yerine kromozom kavramı da kullanılmakta.) Başlangıç populasyonunu oluşturacak bireyler, rastgele oluşturulabilir. Ancak yukarıda da yazdığım gibi ikili veri kodlaması kesin bir kural değildir, farklı kodlama tipleri de vardır...

Uygunluk Değeri

İlk populasyon oluşturulduktan sonra, artık her oluşturulan bireyin ugunluk değeri hesaplanmalıdır. Uygunluk değeri, bireylerin çözüme yakınlıkları ile doğru orantılıdır. Bu değer ne kadar yüksekse, ona sahip olan bireyin yaşayıp üreme şansı o kadar çoktur.

Seçilim

Uygunluk değeri yüksek bireyler, çağrazlanmak üzere seçilirler. Rulet tekerleği, sıralama veya turnuva seçimleri gibi değişik seçim yöntemleri vardır. En kolay seçim yöntemi, bireyleri uygunluk değerlerine göre sıralayıp en yüksek değerlere sahip bireylere şans tanımaktır(sıralama seçimi).

Çaprazlama

Çaprazlama, iyileştirme sürecini etkileyen önemli bir adımdır. Rastgele iki birey seçilir ve aralarında çaprazlama yapılır. Yine tek noktalı çaprazlama, iki noktalı çaprazlama gibi farklı çaprazlama yöntemleri vardır.

Mutasyon

Var olan genleri, yani gen havuzunu zenginleştirmek için uygulanır. Bu işlemin uygulanmaması, daha sonra da ayrıntılarıyla yazacağım gibi, yerel optimum değerlere takılma sorunu yaratabilir. Mutasyon, ikili kodlamada bir bireyin geninde herhangi bir bit değerini diğeri ile değiştirmek suretiyle yapılır.

Bu işlemler sırayla uygulandıktan sonra değerlendirilmeye hazır yeni bir populasyon oluşmuş olur. Bu adımlar ilk başta belirlenecek durdurma kriteri sağlanana kadar yenilenir...

Genetik algoritmanın her zaman doğru sonuç vermesi beklenmez. Zaten algoritmanın amacı doğruyu değil zamanla en doğruyu bulmaktır.

Algoritmayı Sınama

Sıra geldi algoritmayı denemeye. Eğer bu yöntemle bir şeyler yapmaya heveslenirseniz, yöntemi uyarlayabileceğiniz bir problem düşünmeye başlamalısınız. Gezgin satıcı, sayı tablosu gibi ünlü poblemler var. Ben algoritmayı sınamak için denklem kökü çözen bir program yazdım...

Birkaç kavramı daha bu ilk örnek üzerinde açıklayalım. Çözüm uzayı, olası çözümleri içinde barındıran kümedir. Bu küme programda, -32,767 ve +32,767 sayıları arasında bulunan virgülden sonra 3 hanesi olan tüm sayıları kapsamakta. Bu kadar elemanı kapsamak için birey başına kullanılması gereken gen sayısı 2^16 dır. Bir biti negatif ve pozitifliği ayarlamak için kullandım. Ondalıklı sayıları dahil etmek için elde attiğim sayıları sürekli 1000e böldüm. Böylece asıl arama uzayımızın kapsamı ortaya çıkmış oldu; -32,767 ve +32,767 arası.

Programda sınadığım denklemin karmaşıklığının hiçbir önemi olmadığını belirtmeliyim. Burada asıl önemli olan çözümün arama uzayı içerisinde bulunup bulunmadığıdır. Program tüm reel sayıları kodlayamayacağı için uygunluk fonksiyonunun binde birlik sapmaları gözardı etmesini sağladım. Bu yüzden çözüm -9,965 olsa da ulaşılan -9,766 değeri de çözüm olarak kabul edilmiştir. Program aslında 0 hata ile çözüme ulaşabilir. Fakat özellikle örneklemek istediğim şey programın belli sapmalara tölerans tanımasını sağlayarak kodlanamayacak çözümlere yaklaşılabileceği.

Bir diğer denklemde ise pi sayısının ilk 6 rakamını belli bir hata oranı ile bulmayı amaçladım. Yanda ekran görüntüsü bulunan programda çözüm kabul edilebilecek sayı ile çözüm arasında en çok 1/100000 fark olabilir. Bu pay eğer tanınmazsa, program sonsuz döngüye girer, çünkü pi sayısının virgülden sonra doğru olan ilk 6 rakamına ulaşılsa bile bu sinüs fonksiyonunda 0 değerini döndürmeyecektir. Fakat hedeflenen değer sıfırdır. Uygunluk fonksyonuna yerleştirilen bu esneklik sayesinde -0.00001 ve +0.00001 arasında sonuç döndüren tüm x reel değerleri çözüm olarak kabul edilebilmektedir.

Bu örnek aynı zamanda, programın belli bir optimum değere rastlaması halinde nasıl o değer çevresinde dolandığına da iyi bir örnek niteliğinde. Program üzerinde hiçbir değişiklik yapılmadan tekrar çalıştırıldığında pi sayısının katlarını da döndürebilmektedir. Çünkü sınanan aralıkta problemin birden çok doğru sonucu vardır. Hangi sonucun döndürüleceği ise tamamen rastlantılara bağlıdır ve algoritmanın arama uzayında nereden arama yapmaya başladığı ile ilgilidir. Ayrıca bu örnek üzerinde mutasyon oranlarının ve seçilim stratejilerinin değiştirilmesi ile çözüme ulaşmada algoritmanın nasıl etkilendiği de rahatça gözlemlenebilmiştir.

Sonuçta program, asıl çözüm olan 3,141592 sayısından 0,000001 fazla olan bir çözüm elde etmiş ve 6787. nesilde en iyi birey algoritmayı durduracak niteliğe sahip olabilmiştir.

Gözlemler ve Çıkarımlar

• Mutasyon fonksiyonunda olasılık, mutasyona uğratılacak gen sayısı ile ayarlanabilir. Ayrıca bu fonksiyonda rastgele seçilen genin mutasyona uğramama ihtimali de vardır(%50).
• Yine mutasyon fonksiyonunda, her seferinde mutasyona uğratılan gen sayısının fazla olması, genetik algoritmanın asıl işlevi olan "iyiye gidiş"i bir tarafa bırakıp, onu rastsal bir arama haline getirir.
• Arama uzayı genişliği bireylerin kaçar bit ile kodlandığına bağlıdır ve sınırlı sayıda bit ile sonsuz elemanlı bir çözüm uzayı kodlanamaz. Bu nedenle bazen genetik algoritmaların belli bir sapmaya tolerans tanımalarının sağlanması gerekebilir.
• Seçilim fonksiyonu değişik yöntemlere dayandırılabilir. Sadece yavruların yaşamlarını sürdürmesi sağlanabileceği gibi yavrularla birlikte korunan en iyi çözümlerin yani çeşitli sayılarda ebeveynlerin de yaşaması sağlanabilir. Bu, üzerinde düşünülmesi gereken bir ayardır. Çeşitli değişiklikler yapılarak gözlemlenebileceği gibi, fazla sayıda bireyi mutasyon ve çaprazlamaya tabi tutmadan korumak, yerel optimum çözümlere takılma ihtimalini güçlendirebilir. Hiçbir bireyi korumamak ise, algoritmayı tüm arama uzayında rastgele çözüm bulma çabasına dönüştürebilir...
• Arama uzayının genişliğinin, çözüme ulaşma süresine nasıl yansıyacağını tahmin etmek zor değil; çözüm olabilecek değerler arttıkça iyileşme süreci de uzamaktadır. Aslında tüm genetik algoritmayı büyüteçle bir sayfada arama yapmaya benzetebiliriz. Arama yapılacak yer ne kadar genişse, arama süresi de o kadar fazladır.
• Populasyon büyüklüğünün sürece etkisi de önemlidir. Birey sayısı arttıkça çözüme ulaşma süresi kısalır. Yine büyüteç örneğine dönersek, büyüteçin camı ne kadar genişse, anlık olarak göz önünde tutulup değerlendirilebilecek o kadar fazla veri olur...

Leave Comment

Comments (2)