Basit yazı arama algoritmsı

Uzunca bir metinde bir kelime aradığımız çok olmuştur. Bu aramalar için geliştirilmiş çok çeşitli algoritmalar var. Bu yazıda bu algoritmaların en basitinin simülasyonuyla ilgileneceğim.

Bu algoritmada metnin en başından başlanır ve harf harf kelime ve aranan kelime karşılaştırılır. Eğer karşılaştırılan harfler farklı ise aynı karşılaştırmaya metnin bir sonraki harfinden başlanır. Bu karşılaştırmalar ya metnin içinde bu kelime bulunana ya da metnin sonuna ulaşılana kadar devam edilir.

Simülasyon

Evrim ve genetik algoritmalara küçük bir giriş

Richard Dawkins, Kör Saatçi adlı kitabında bir programdan bahseder. Bu program rastgele değişimler ve rastgele olmayan seçimler sayesinde nesiller boyu işleyen bir algoritmanın tamamen rastgele şekilde işleyen bir mekanizmadan çok daha çabuk hedefe ulaşacağını gösteren bir deneydir.

Bu deneyde Dawkins ‘METHINKS IT IS LIKE A WEASEL’ cümlesini kullanır. Eğer bir maymun rastgele İngilizce alfabedeki 26 harfi ve boşluk karakterlerini kullanarak bu cümleyi yazmaya çalışırsa çok çok uzun zaman bu işle meşgul olurdu.

Dawkins, bunun yerine maymunun çalışma prensibinde hafif bir değişiklik yapılırsa çok ilginç bir sonuç çıkacağını söyler kitabında. Diyelim ki maymun yine rastgele 28 harflik (cümle 28 harf uzunluğunda) bir şey yazsın. Daha sonra bu cümleyi kopyalamaya başlasın ama bir farkla. Kopyalarken arada rastgele hatalar yapsın, yani bazı harfler kopyalarda değişsin (mutasyon). Daha sonra maymun o yazdığı ve kopyaladığı cümleler grubunda hedef cümleye en yakın cümleyi seçsin ve o ana kadar yaptığı adımları tekrarlasın. Böylece nesiller sonra maymun hedef cümleyi bulacaktır ve bu iş için gereken nesil sayısı tamamen rastgele seçim olan algoritmadan çok daha az olacaktır.

Bunu denemek için bir javascript simulasyonu programladım. Her nesildeki birey sayısını ve mutasyon oranını girdikten sonra ya animasyonlu ya da animasyonsuz çalıştırılabilir. Öncelikle animasyonsuz çalıştırılmasını öneririm. Böylece daha hızlı çalışacaktır ve daha kısa sürede bütün işlemlerin yaklaşık kaç nesil süreceği görülebilir. Bu esnada yukarıda nesil numaraları ve o nesildeki hedefe en yakın cümleyi görebilirsiniz.

Eğer animasyonla çalıştırılırsa maymunun yaptığı işlemleri ‘ağır çekimde’ görülebilir. Cümlelerdeki mutasyonlar, yani hatalı kopyalanan harfler kırmızı gösteriliyor. Ardından maymunun seçimi yeşil arkaplan rengiyle gösteriliyor. Bundan sonra o nesil komple siliniyor ve yerine maymunun seçtiği cümlenin tam kopyaları koyuluyor. Animasyon bu adımların tekrarlanmalarıyla devam ediyor. Küçük bir uyarı yapayım, bu adımlar çok yavaş gösterildiğinden bütün simulasyonu seyretmek çok zaman alacaktır.

Hedefe çabucak ulaşmak için kalabalık popülasyonlar seçmek daha iyi olacaktır. Animasyon kullanılmayacaksa 100 iyi bir popülasyon büyüklüğüdür. Animasyon için ise ne kadar küçükse o kadar iyi ama bu durumda da bütün simulasyon çok uzun sürecektir. Mutasyon değerini küçük tutmak iyidir. Örneğin 0.05 (Her harf yüzde beş ihtimalle değişebilir) yeterli bir değer. Aşağıdaki linkten simulasyon sayfasına ulaşabilirsiniz.

Gelincik programı

Fisher’in kaçış evrim modeli üzerine denemeler

Evrim teorisi temelde basit olmasına rağmen birçok durumda akılda canlandırmakta zor oluyor. Bu nedenle bu konuyu daha iyi anlayabilmek için elimden geldiğince simülasyonlar yazmaya karar verdim. Bu ilk sümülasyonda cinsel seçilim konusunda Fisher kaçış modelini denedim. Önce anladığım kadarıyla bu noktalara kısaca değineceğim ve sonra da simülasyonu sunacağım.

Evrimde doğal seçilimin yanında cinsiyetler arası seçilim de oldukça önemlidir. Hayatta kalabilen bir birey eğer çiftleşemezse genleri bir sonraki nesle aktarılamaz.

Bazı kuş türlerinde erkeklerde hayatta kalma şansını artırmaya yaramayacak büyüklükte kuyruklar vardır. Bu kuyruklar yardım etmediği gibi aynı zamanda yük de olmaktadır. Peki, o zaman nasıl bu kadar büyümüşler?

Ronald Fisher, 1930’da bu durumu açıklayabilecek bir model öne sürdü. Erkekteki süs özelliğini güçlü bir şekilde seçen dişi bu şekilde doğal seçilimin etkisini zayıflatabilirdi. Bu şekilde bu süs, süsün masrafı cinsel seçilimin getirisinden büyük olana kadar artabilir ya da büyüyebilir. Burada masraftan kasıt örneğin kuşun artık hiç uçamayacağı bir kuyruğa sahip olması olabilir. Bu durumda bu erkekler dişiler tarafından seçilecek olsa bile hayatta kalamadıklarından çiftleşme şansı bulamayacaklardır.

Fisher’in açıklaması için erkeklerdeki abartılı süs ve dişilerdeki bu süsü tercih etme genetik özellikler olmalı, yani genlerle nesilden nesile aktarılabilmeli. Gruptaki diğer bireylere göre ortaya çıkan bu iki ayrılık da (erkekteki süs gelişimi ve dişideki bu süsü seçme eğilimi) Fisher’e göre birbirlerini pozitif bir şekilde ilerleteceklerdir.

Süslü erkeği tercih eden bir dişinin dişi yavrusu olursa kendi tercih geni de yüzde elli ihtimalle bu yavruya geçecektir ve bu yavru da yüzde elli ihtimalle annesinin tercih özelliğini gösterecektir. Bu dişi yavru aynı şekilde babadan da büyük süs genini yüzde elli ihtimalle alacak. Her ne kadar kendisi büyük süs özelliğini göstermese de yine kendisi bu geni bir sonraki nesle aktarma şansını sürdürecektir. Aynı mantığı erkek yavru için de yürütebiliriz. Erkek yavru babadan aldığı büyük süs geninin etkisini gösterirken anneden aldığı büyük süs seçim genini de bir sonraki nesle aktaracaktır.

Aşağıdaki linkten bu modelin simülasyonuna erişebilirsiniz. Simülasyon animasyonsuz çalıştırıldığında sadece her nesilde kaç tane normal erkek (normal süse sahip), normal dişi (eş seçimini süs büyüklüğünden bağımsız yapan), farklı erkek (büyük süse sahip) ve farklı dişi (eş seçiminde büyük süsü tercih eden) birey olduğu hesaplanıyor. Bir sonraki nesli üretmek için o nesildeki bireyler seçim yöntemlerine göre birer eş seçiyor ve sonraki nesilde toplam popülasyon büyüklüğünde çocuk oluşana kadar ürüyorlar. Çocukların erkek veya dişi olması ya da babadan ve anneden hangi genlerin geleceği rastgele seçiliyor. Eş seçiminde monogami ya da poligami olması seçeneği de mevcut. Poligamide bir erkek birden fazla dişi ile çiftleşebiliyor. Burada çiftleşmeden kastım başarılı döllemedir, beraber olma sıklığı ya da çeşitliliği simülasyonda ele alınmamıştır. Eğer animasyon seçeneği kullanılırsa popülasyon büyüklüğünü küçük tutmak iyi olacaktır yoksa hem simülasyon çok uzun sürecek hem de popülasyon ekrana sığmayacaktır. Animasyon modunda bireyler dikdörtgen şeklinde gösterilmektedir. Erkek bireyler E, dişi bireyler de D harfi ile işaretlenir. Dikdörtgenlerin alt tarafında anne ve babadan geçen genler gösteriliyor. S geni, büyük süsü gösterirken s geni de normal süsü göstermektedir. Aynı şekilde T geni büyük süsü tercihi simgelerken t geni de rastgele tercih anlamına geliyor. Üremeye katılan çiftler animasyon sırasında yeşil gösteriliyor. Sonra bir alt satırda bu birleşmeden ortaya çıkan çocuklar yeni nesilde genlerle beraber gösteriliyor. Ardından dişi birey bu nesilde bir daha çiftleşemeyeceğinden kırmızıya dönüyor. Eğer ilişki durumu monogamiyse erkek birey de kırmızı oluyor. Poligami seçilmişse aynı erkek başka çiftleşmelerde de bulunabiliyor.

Üreme aşamasında şöyle bir algoritma kullandım. Seçilen çiftleşmelerden önce sırayla birer çocuk ürüyor. Ardından toplam nüfus istenen değere ulaşana kadar aynı çiftleşmelerden rastgele seçimler yapılıyor ve basla çocuklar da ürüyor. Animasyon sırasında ise bu iki kademe aynı anda oluyor gibi gösterilmekte.

Simülasyonlarda da görüldüğü gibi poligaminin yaygın olduğu popülasyonlarda aşırı süs ve bu süslerin tercih genleri daha hızlı yayılıyor.

Simülasyon

Bu simülasyonda daha başka özellikler de görmek isterseniz bunu yorum kısmında belirtebilirsiniz.