Genetik algoritmalarda mutasyon çaprazlama ve bellek mekanizmalarının etkileri ve iyileştirilmesi / Hanife Usta; Danışman İlyas Eminoğlu
Abstract
Bu tez çalışmasında; çaprazlama ve mutasyon işlemcilerinden esinlenerek ortaya çıkmış, biyolojik kökenli optimizasyon yöntemi olan genetik algoritma (GA) incelenmiştir. Çalışmada ilk olarak genetik algoritmanın tanımı, çalışma şekli ele alınmış ve kullanılan çaprazlama, mutasyon işlemcilerinin etkileri ayrıntılı olarak incelenmiştir. Ayrıca fonksiyon optimizasyonu için kaynaklarda sık kullanılan tek ve çok amaçlı yapay test fonksiyonlarına yer verilmiştir.Genetik algoritmalar topluluk tabanlı ve çok adımlı olmakla birlikte, kullandıkları matematiksel araçlar/işlemciler açısından bakıldığında yapısı karmaşık değildir. Temel itibariyle GA da en az bir amaç fonksiyonu, seçme mekanizması, çaprazlama ve mutasyon işlemcileri bulunur. Genetik algoritmada genelde ilk topluluk rasgele oluşturulur. En iyiyi bulmak ve iyi bir yakınsama elde etmek için topluluk üzerinde genetik işlemler uygulanır. Önceden belirlenen adım sayısına ulaşınca veya hata belli bir ön tanımdan küçükse işlem sona erdirilir. Bu çalışmada GA'nın hesapsal olarak adım adım nasıl çalıştığı ve nasıl çözüm üretebildiği, karmaşık olmayan bir optimizasyon problemi üzerinde gösterilmiştir. GA da kullanılan işlemcilerin (mutasyon/çaprazlama) algoritma üzerindeki etkileri işlemcilerin olasılık değerleri değiştirilerek irdelenmiştir.Genetik algoritmalar çok değişkenli problemlerin optimizasyonu amacıyla kullanılan sezgisel yöntemdir. Rasgele sayı üretimine dayalı olarak çözümler üreten genetik algoritmalar N defa çalıştırıldıklarında aynı sonucu üretmeyebilirler. GA da seçilen bireylerin bir nesilden diğer nesile nasıl aktarıldığını belirleyen çaprazlama ve mutasyon işlemcilerinin olasılık güdümlü çalışması; topluluğun bir nesilden bir sonraki nesile olan değişiminin izlenmesini zorlaştırmaktadır. Bu tez çalışmasında topluluğun dinamik davranışlarını incelemek amacıyla eldeki problem izlenebilir boyuta düşürülmektedir. Bu tezde amaçlanan bir birey çiftinin çaprazlama ve mutasyon işlemcileri altında nasıl davrandığını modellemek ve bu modelden elde edilecek veriler ışığında topluluğun genel davranışı hakkında geçerli bir modele/yaklaşıma ulaşmak istenmektedir. GA da mevcut sıralama yöntemleri bireylerin sayısal gövdelerinin farklılığını dikkate almadan sıralama yapmaktadır. Klasik GA da yüksek puanlı bireylerin seçilme olasılığı yüksektir, bu da yüksek puanlı ve nispeten benzer sayısal gövdeli bireylerin seçilmesiyle sonuçlanmaktadır. Elde edilen benzetim sonuçlarında; yüksek puanlı ve sayısal gövde itibariyle birbirine benzemeyen bireylerin, bir başka deyişle yüksek puanlı, farklı bireylerin yeni çözümler üretme olasılığının fazla olduğu gözlenmiştir Genetik algoritmada bellek (elitizm) mekanizması, üretilen iyi çözümlerin saklanması ve bir sonraki nesle aktarılması işlevini yerine getirdiğinden GA'nın çözüm üretme kabiliyetini arttırmaktadır. Klasik GA'daki bellek mekanizması topluluktaki en iyi bireylerin bir kısmını veya tamamını bir sonraki topluluğa aktarmaktadır. Bu çalışmada genetik algoritmanın performansını arttırmak amacıyla bellek mekanizmasında değişikliğe gidilmiştir. Her adımda elde edilen en iyi birey/bireyler genetik işlemciler (çaprazlama/mutasyon) ile uyarılarak bir sonraki topluluğa aktarılır. Yapılan benzetim çalışmalarında her adımda elde edilen en iyi bireylerden daha iyi bireylerin elde edilebileceği gösterilmiştir. Bellek mekanizmasında önerilen ve denenen iyileştirme yöntemi kaynaklarda mevcut bellek mekanizmalı tüm genetik algoritmalara rahatlıkla uygulanabilir ve bu tezin önemli bir çıktısıdır.
