Yazan : Şadi Evren ŞEKER

Türkçe kaynaklarda, Memetik Algoritma olarak da geçmektedir. Sanırım isimlendirme konusundaki tartışmalar hiç bitmeyecek ama ben Taklitçi algoritmalar demeyi tercih ediyorum. Bunun sebebi İngilizce Memetic kelimesinin kökünün “meme” kelimesi ve “meme” kelimesinin etimolojik kökünün de “mimic” kelimesi olmasıdır. Mimic kelimesi ise buradaki kullanımı anlamıyla taklit kelimesi ile karşılanabilir. Aslında meme kelimesi tam olarak toplumda veya genlerde olan değişimi ifade etmektedir. Bu anlamda değişimsel algoritmalar ismi de verilebilir. Ancak burada değişimin şekillerinden bahsetmek gerekir. Memetic Algorithms terimi ile kast edilen değişim daha çok evrimsel bir değişimdir (evolutionary). Bu anlamda evrimsel değişimlerde taklit esastır. Yani Memetik algoritmalarda çıkan her yeni sonuç (nesil) daha önceki gruptan (atalarında) bir benzerlik taşır. Tamamen bağımsız, tamamen yeni, daha önce hiç olmayan bir değer elde etmek mümkün değildir. Zaten bu yüzden memetic algorithms ismi kullanılmıştır ve bence bu durumu Türkçe de karşılayan en güzel terim Taklitçi Algoritmalardır.

Gelelim taklitçi algoritmaların ne olduğuna. Aslında yukarıda biraz giriş yaptık ama tam olarak, bilgisayar bilimlerinde, yapay zeka çalışmalarının altında geçmektedir. Gruplandırma olarak evrimsel algoritmaların (evolutionary algorithms) bir çeşidi olarak kabul edilebilirler.

Darwin’in evrim teorisinden esinlenilmiştir ve bir toplumdaki değişim (veya göç) ve bir gendeki değişim (veya karışım) esas alınarak kurulmuştur.

Bu yazıyı okuyanların, tam bu adımda, değişim ile neyin kast edildiğini daha iyi anlayabilmesi için, evrimsel algoritmalar (evolutionary algorithms) başlıklı yazıyı okumalarında yarar vardır.

Kısaca evrim teorisinde bulunan RAST GELE seçim ki buna doğal seçim (doğal seleksiyon) ismi de verilmektedir ve yine RAST GELE eşleşme ve kalıtım (inheritance) gibi özellikleri temel alır.

Taklitçi algoritmaların gelişiminde ve günümüzdeki kullanımlarına ulaşmalarında bir kaç aşamadan bahsetmek mümkündür.

Birinci seviyede üç temel adımdan bahsedilebilir:

  1. Toplumdan rast gele bir seçim

  2. Bu seçilen bireyler üzerinde evrimsel bir işlemin (operator) uygulanması

  3. İstatistiksel yöntemlerle bu yeni nesil üzerinden öğrenme çabası

Örneğin, sitede bu tip problemleri anlatırken sıkça kullandığım, klasik bir problemimiz olan zaman çizelgelemesi (time tabling) problemini ele alalım. Bir haftalık program yapmak istiyoruz ve bu programın günde 8 saatten haftada 40 saatlik bir dizilime sahip olmasını bekliyoruz. Problemi basitleştirmek için, elimizde de 40 saatlik yerleştirilecek ders olsun. Basit bir hesapla 40 saatin birbirinden farklı 40! kadar dizilimi bulunur. Bütün bu ihtimallerin hesaplanması yerine bir taklitçi algoritma kullanmaya karar verdik. Aşağıdaki adımları izleyebiliriz:

Öncelikle rast gele dağılıma sahip 10 program hazırlayalım. (Muhtemelen çözüm bulacak kadar şanslı değiliz, çözüm bulma ihtimalimiz 10 / 40! )

Sonra taklitçi algoritmamızı uygulamaya başlayalım:

  1. Üretilen 10 farklı programdan 2 tanesini seçelim

  2. Bu seçilen 2 programdan birincisini pazartesi ve salı dizilimini, diğerinin çarşamba, perşembe ve cuma dizilimlerini alıp yeni bir program elde edelim. (Burada bir evrimsel işlem olan (evolutionary operator) çarpazlama (crossover) kullanılmıştır.

Bu aşamada 1. ve 2. adımlar istenildiği kadar tekrarlanabilir. Yani algoritmamızın ne kadar hızlı olmasını istiyorsak o kadar fazla nesil üretmemiz mümkün.

  1. Çıkan bu yeni neslin ne kadar sonuca yakın olduğuna bakarak bir yorum yapabiliriz.

Yukarıda anlatılan ilk yaklaşım daha da iyileştirilerek ikinci aşamada çoklu-taklit (multi-meme) veya hiper sezgisel (hyper heuristic) yaklaşımlar kullanılmıştır. Örneğin yukarıdaki aynı problem ve aynı algoritmanın bu aşamadaki hali aşağıdaki gibi olabilir:

  1. Üretilen 10 farklı programdan 2 tanesini seçelim

  2. Bu seçilen 2 programdan birincisini pazartesi ve salı dizilimini, diğerinin çarşamba, perşembe ve cuma dizilimlerini alıp yeni bir program elde edelim. (Burada bir evrimsel işlem olan (evolutionary operator) çarpazlama (crossover) kullanılmıştır.

  3. Tam bu aşamada hangi bireylerin (meme) hangi atalardan geldiğinin takibi yapılır.

  4. Çıkan bu yeni neslin ne kadar sonuca yakın olduğuna bakarak bir yorum yapabiliriz.

  5. İlave olarak çıkan bireylerde istenilen neticeye göre düzenlemeler yapılabilir. Örneğin bir takım kalıtım fonksiyonlarının uygulanması gibi.

  6. Neticede bireylerin soyuna göre bir rekabet kurulabilir. Geldikleri atalarına göre soy ağaçlarının takibi ve daha üstün ırkların elde edilmesi hedeflenebilir. Bu yaklaşım, sezgi üstü bir yaklaşım (meta-heuristic) olarak kabul edilebilir.

Yukarıdaki bu yaklaşımın biraz daha geliştirilmesi mümkündür. Örneğin bir kural tabanı (rule-base) tanımlayarak istenilen neticeye ulaşma hızlandırılabilir. Bu kural tabanında, istenilen sonuca yönelik olarak bir bireyin taşıması gereken özellikler belirtilip, bu özelliğe sahip bireylerin seçilmesi ve hatta daha da ileri gidilerek bu bireylerin her evrim seviyesinde rast gele üretilmesi mümkündür. Ayrıca bu gelişmiş taklitçi algoritma yaklaşımında, nesiller arasında benzerlik gösteren genlerin yakalanması ve bu genlerin iyileştirme amacıyla kullanılması da mümkündür.


Yorumlar

  1. hakan saribiyik

    Merhaba,
    Burada anlatılan daha çok genetik algoritmalara uyuyor bence. Benim yıllar önce okuduğum ve bu sıralar tekrar elime aldığım Susan Blackmore un The Meme Machine, 1999 baskısında farklı anlatıyordu. Uzun zaman once okudugum icin tekrar okumaya başladım, okuduktan sonra daha net ifade edebilirim ne demek istediğimi.

    selamlar

    Hakan

  2. Şadi Evren ŞEKER Article Author

    sanırım yorumunuz, kısaca gene ve meme arasındaki farka dayanıyor. Bilebildiğim kadarıyla bu konu oldukça tartışmaya açık. Kabaca, gen, biyolojik olarak nesilden nesile aktarılan bazı özellikleri ifade ediyor. Genelde bu aktarım düşey boyuttadır. Yani yukarıdan aşağıya doğru aktarılmaktadır. İstisnai olarak yatay hareketin varlığından da söz edenler oluyor (tam olarak hakim olmamakla birlikte virüslerle veya salgın hastalıklarla aynı nesildeki bireyler arasında gen alışverişi olması mümkün gibi görülüyor).
    Buna karşılık meme tanımı, kültürel bir kavram ve insan sosyal yapısına ve kültürüne ait özellikler taşıyor. Örneğin bir düşüncenin nesilden nesile aktarılması veya bir nesildeki bireyler arasında yayılması memetik bir yaklaşım gibi duruyor.
    Elbette farklı disiplinlerde tartışmalara sebep olan bu fark, bilgisayar bilimlerine gelindiğinde ve algoritma olarak incelendiğinde genetic algorithm ve memetic algorithm farkı sorgulandığında, kısaca yukarıdaki yazıda bulunan 3. adımdadır. Yani evrimsel algoritmanın uygulanması sonucunda (veya çeşitli evrimsel algoritma fonksiyonlarının uygulanması sonucunda) çıkan bireyin, diğer nesiller üzerinde etki etmesi.
    Burada bir tartışma başlatmak veya konuyu saptırmak niyetinde değilim ama sadece daha iyi anlaşılsın diye aşağıdaki görüşü ele alalım:
    “Ben bir bireyim ve sadece kendi genimi kopyalamak için varım. Kendi genim ne kadar kötü veya iyi olursa olsun benim için önemli değil sonraki nesillere aktarmak benim görevim. Amacım başkasının genini veya toplumun menfaati olan geni veya gelecek için en mantıklı olan geni değil sadece kendi genimi yaşatmak.”
    Yukarıdaki yaklaşım, genelde biyolojik olarak gen kopyalanmasının temelini oluştururken, memetik yaklaşımda kişiler başkalarının fikirlerini veya kültürlerini taşıyabilir, sonraki nesillere aktarabilir veya yayabilir.
    Hızlı bir literatür taraması ile, özet olarak iki yaklaşım arasındaki farkı açıklayan bir makaleye ulaşabildim ( atıf:”A Comparison between Memetic algorithm and Genetic algorithm for the cryptanalysis of Simplified Data Encryption Standard algorithm”, International Journal of Network Security & Its Applications (IJNSA), Vol.1, No 1, April 2009, Poonam Garg)

    “Genetic algorithms are a population-based Meta heuristics. They have been successfully applied to many
    optimization problems. However, premature convergence is an inherent characteristic of such classical
    genetic algorithms that makes them incapable of searching numerous solutions of the problem domain. A
    memetic algorithm is an extension of the traditional genetic algorithm. It uses a local search technique to
    reduce the likelihood of the premature convergence. ”

    Yukarıdan da anlaşılacağı üzere, iki yaklaşım arasındaki en temel farkın, genetik algoritmalardaki “erken yakınsama” (premature convergence) probleminin çözümü için memetik algoritmalardaki yerel arama (local search) olduğu anlaşılabilir.

  3. Can Barış

    Merhaba,

    Bu yararlı siteyi kurup yönettiğiniz için teşekkür ederim. Matematik Mühendisliği mezunuyum ve Yazılım Mühendisi olarak çalışıyorum. Çalıştığım bu büyük kuruluşta bir veri filtreleme sistemi yapmak istiyoruz. Projeyi matematik kökenim de olduğu için ben üstleniyorum. Bu konuda nasıl bir metodoloji izlemem gerektiği hakkında fikrinizi almak için yazıyorum.

    İstenilen şu; biri tarafından düzenli olarak girilen kurallar olacak ve bu kurallar her yeni obje için kontrol edilecek. Objeden kastım, nesne-yönelimli programlamadaki herhangi bir nesne ile birebirdir. Özetle, veritabanımda bulunan belli formattaki bir dizi verinin (kaydın veya sınıfın da diyebiliriz) örnekleri (instance) için tek tek daha önce yazılmış kurallar işlenip bir puanlama yapılacaktır. Hangi kuraldan geçiyor, hangisinden kalıyor tarzında bir işleyiş ile ilerlemesini düşünüyorum.

    Soruma gelelim, önce modelimde şunlar var demiştim: 1.Objem 2.Kurallarım 3.Kural Kümelerim. Bu kuralların birbirinden haberdar olmasını ve her bir kuralın çıktısına göre belki es geçeceği kuralları da bilerek performansı yüksek tutmayı hedefliyorum. Keza, yine belli kuralların ortak kullanılarak Kural Kümeleri içinde yer alabilmesini ve Kural Kümeleri üzerinden kontrolleri yapmayayı amaçlıyorum.

    Bu bağlamda, decision tree mantığından ziyade graph teorisi daha mantıklı geldi. Çünkü kuralların hangi sırada olması gerektiğine de kendilerinin karar vermesi gerekirken, birbirlerinden haberdar olup kendi uzaylarında bu objeyi belli bir mantıkla birbirlerine de paslayabilmeleri gerekiyor.

    Java ile yazmaya çalıştığım bu uygulamanın iskeletine, hangi metodolojileri okuyup uyarlayıp izleyebileceğime, yapay zekayı kural mantığına nası oturtabileceğime, son olarak bu mantık tabanının nasıl modellenmesi gerektiğine dair bir fikriniz varsa ve paylaşırsanız çok minnettar olurum.

    Bilgi ve tecrübenizle en azından beni doğru bir yolda yönlendirebileceğinizi öngörüyor ve buna istinaden yazıyorum.

    Şimdiden değerli vaktiniz için teşekkür ederim. Sevgi ve saygılarımla,
    Can
    javaguncem.blogspot.com

  4. Şadi Evren ŞEKER Article Author

    Öncelikle siteye gösterdiğiniz ilgi için teşekkür ederim.

    Genelde sizin durumunuzda olduğu gibi büyük ölçekli projelerde kararı uzaktan vermek çok zor.
    İkinci paragrafta anlattığınız kural uygulaması için genelde kural tabanlı sistemler (rule based) kullanılabilir. Ancak sizinki kural tabanlı sistemlerden çok skorlamaya benziyor. Yani filitrelerinize yakalandıkça puanlanmalı gibi sanki.

    4. paragrafta bahsettiğiniz durum itibariyle probleminiz, constraint programminge kaymış oluyor. Zaten bu yaklaşım bir graph theory uygulamasıdır ve sizin kurallarınız birbirine bağlı şekilde etkileşir. En kolay uygulamalarından birisi kiriş şartı (arc constraint)‘tir ve sitede bir zamanlar 4 vezir problemi için nasıl uygulanacağını yayınlamıştım. Kurallarınız arasındaki bağlantıyı belirleyerek problemin çözümünde birisinin diğerleri etkilemesini sağlayabilirsiniz. Bu programlama mantığını uygulayan hazır paket yazılımlar da bulunuyor.

    başarılar

Şadi Evren ŞEKER için bir cevap yazın Cevabı iptal et

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir