Genetik Algoritmalarda Injection Yaklaşımı ile Genetik Çeşitliliğin Korunması

“Genetik Algoritmalarda “Injection” Yaklaşımı ile Genetik Çeşitliliğin Korunması” başlıklı çalışma Mustafa ORAL ve Serkan KARTAL tarafından hazırlanmış olup 11-13 Mayıs 2016 günlerinde Tokat/TÜRKİYE’de düzenlenen EEB 2016 Elektrik-Elektronik ve Bilgisayar Sempozyumu’nda sunulmuştur.

Popülasyon çeşitliliğinin kaybedilmesi ve zamanından önce yerel en iyi çözüme yakınsanması popülasyon tabanlı sürü zekası algoritmalarının en temel problemlerinden birini oluşturmaktadır.

Popülasyon tabanlı sürü zekası algoritmalarının çalışması süresince belirli aralıklarla, popülasyona farklı yöntemlerle elde edilmiş yeni bireylerin eklenmesi çeşitliliğe fayda sağlayabilmektedir. Amaç, algoritmanın yerel en iyi çözüme takılmasının önüne geçilerek, genel en iyi çözüme daha kolay bir şekilde ulaşmasını hedeflemektir.

Popülasyon tabanlı sürü zekası algoritmalarının performansını etkileyen en önemli iki faktör sırası ile başlangıç popülasyonun oluşturulması ve çeşitliliğin jenerasyonlar boyunca korunmasıdır.

Injection(Enjeksiyon) metodu nedir? Nasıl uygulanır?

Injection metodu ile, her jenerasyon sonunda, popülasyonda bulunan belirli bir oranda birey yok edilerek, yerine rastgele oluşturulmuş yeni bireyler popülasyona eklenmektedir. Böylece, hem var olan bireylerle daha iyiye doğru evrimleşme işlemi gerçekleşirken, hem de yeni bireylerin popülasyona eklenmesi ile genetik çeşitlilik korunmuş olmaktadır.

Crowding(Kalabalık) metodu nedir? Nasıl uygulanır?

Popülasyon çeşitliliğinin korunması için öne sürülen yaklaşımlardan birisi “crowding” tir. Bu yaklaşıma göre ilk olarak popülasyon alt popülasyonlara ayrılmakta ve oluşturulan yeni bireyler bu alt popülasyona eklenmektedir. Eklenme sırasında alt popülasyonda bulunan ve yeni eklenen bireye en çok benzeyen birey çıkarılmaktadır. Alt popülasyonun büyüklüğü “crowding factor” parametresi ile belirlenmektedir [DeJong, K. A., “An analysis of the behavior of a class of genetic adaptative systems”, Ph.D. dissertation, Univ. of Michigan, Ann Arbor, 1975.].

Hamming mesafesi ölçümü ile popülasyon çeşitliliğinin ölçülmesi ve benzer bireylerin yok edilmesi metodu nedir? Nasıl uygulanır?

Bir sonraki jenerasyon için popülasyon oluşturulurken, çocukların oluşturduğu yeni popülasyon ile anne-babaların oluşturduğu eski popülasyon harmanlanmaktadır. Bu işlem sırasında, her iki popülasyon birleştirilmekte, ancak birbirine benzer olan bireyler yok edilerek, yalnızca farklı bireylerin oluşturduğu yeni bir popülasyon elde edilmektedir. Bireylerin benzerlikleri Hamming mesafesi ile ölçülmektedir. Bu yöntemi kullanan çalışmalar;

1-SHIMODAIRA, H.,. “A Diversity Control Oriented Genetic Algorithm”, Second International Conference on Genetic Algorithms in Engineering Systems, 444-449, 1997.
2-Mauldin, M.. “Maintaining genetic diversity in genetic search”, National Conference on Artificial Intelligence, 247-250, 1984.

Hamming mesafesi bilgisayar bilimlerinde aynı uzunluktaki iki dizgi (string) arasında, birbirine dönüşmesi için gerekli olan yer değiştirme sayısını verir. Yani basitçe bir dizginin diğer dizgiden ne kadar farklı olduğunu gösterir.

Örneğin aşağıda bazı dizgiler arasındaki hamming mesafesi verilmiştir:

100011101 <-> 100101101 = 2
düğün <-> düşün = 1

Ranked Space(Sıralanmış Uzay) metodu nedir? Nasıl uygulanır?

Ranked Space(Sıralanmış Uzay) metodunda çeşitlilik seçilim işlemi sırasında bireylerin seçilim şansına etki ederek korumaktadır. Bu metod ile seçilim işlemi sırasında iki farklı sıra puanı (rank score) hesaplanmaktadır. Bunlardan birincisi uygunluk (fitness) değerine bağlı olarak verilen sıra puanı, ikincisi ise farklılığa bağlı olarak verilen sıra puanıdır. Her iki puanın toplamı ise bireylerin seçilim puanlarını oluşturmaktadır. Böylece farklılığı yüksek olan bireylerin de seçilim şansı arttırılarak, çeşitlilik korunmaya çalışılmaktadır.

Sharing metodu nedir? Nasıl uygulanır?

Aynı yapıya sahip olan bireylerin seçilim şansları benzer birey sayısına bölünmektedir. Bu işlem sonunda benzer bireylerin seçilim şansları azaltılarak tüm popülasyonun benzer bireylerden oluşmasının önüne geçilmektedir. Böylece farklı özelliklerdeki bireylerin seçilim şansı artmakta
ve çeşitlilik kısmen korunabilmektedir. İlgili çalışma: [P., Snijders, “Incorporating frequency dependent selection and sexual selection in genetic algorithms”, Master Thesis 33 pages, 2005.]

Çalışmayı indirmek için:

genetik_algoritmalarda_injection_yaklasimi_ile_genetik_cesitliligin_korunmasi