Bir bilgisayar mühendisi için programlama dili, öğrendiklerini sınadığı, deneyler yaptığı bir laboratuardır ve mühendisler deneylerini, kestiremedikleri sonuçları gözlemlemek için değil, öngördükleri sonuçları doğrulamak için yapar...

Genetik Algoritma

Genetik algoritma nedir? Süreçleri nelerdir? Nasıl kodlanır?

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ınamaGenetik algoritma ile ilgili örnek uygulama

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.

Genetik algoritma ile pi sayısı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

Yayın tarihi: 03 Ekim 2009 Cumartesi, 16:14
Anahtar kelimeler: genetik algoritma, evrim süreci, genetik algoritmanın adımları

Yorum Gönder

 
Yorumunuzu -1. yoruma yanıt olarak gönderiyorsunuz. Yanıtlamayı iptal etmek için buraya tıklayabilirsiniz.

 

Yorumlar (2)

Celal Karaca
Yanıtla
26 Ocak 2010 Salı, 11:46
#1

Hocam çok güzel bir paylaşım olmuş.Emeğinize sağlık...Teşekkürler...

Hüseyin Atasoy
Yanıtla
28 Ocak 2010 Perşembe, 17:45
#2

Teşekkür ederim.

 
 
Sayfa 38 sorgu ile 0.007 saniyede oluşturuldu.
Atasoy Blog v4 © 2008-2016 Hüseyin Atasoy