Akademik Veri Yönetim Sistemi
Tezin Türü: Yüksek Lisans
Tezin Yürütüldüğü Kurum: Dokuz Eylül Üniversitesi, Fen Bilimleri Enstitüsü, Bilgisayar Bilimleri, Türkiye
Tezin Onay Tarihi: 2017
Tezin Dili: Türkçe
Öğrenci: MEHMET GENCER
Danışman: Murat Erşen Berberler
Özet:
NP-Zor karmaşıklık sınıfına ait çizge problemlerinden biri olan Maksimum Bağımsız Küme (MIS) ile günlük hayatta sıklıkla görüntü işleme, harita işaretleme, moleküler biyoloji, zaman çizelgesi planlama(scheduling), vs. gibi alanlarda sıklıkla karşılaşılır. Bu çalışmada MIS problemine birden fazla uygun çözümün aynı anda oluşturulup kontrol edilebildiği meta sezgisel yöntemlerden birisi olan genetik algoritmalar yardımıyla kısa sürelerde optimuma yakın kalitede çözümler aranmıştır. Literatürdeki çalışmaların büyük bölümünden farklı olarak genetik algoritmanın başlangıç popülasyonu, rastgele belirlenmeyip çeşitli sezgisel yaklaşımlarla oluşturulmuştur. Farklı sezgisel yaklaşımlar ve bu yaklaşımların optimum değer bulamadığı ters örnekler incelenmiş, sezgisel yaklaşımların çözüme ulaşma olasılığı kaydırma operatörü yardımıyla farklı çözümler üretilerek arttırılmıştır. Burada kaydırma operatörü ile kastedilen yapı tepe derecelerine göre sıralı vektör üzerinde farklı çözümleri elde edebilmek için permütasyon uzayının küçük bir alt kümesinin seçilmesidir. Ayrıca çözüm uzayını etkin bir şekilde tarayabilmek amacıyla problemin boyutuna bağlı olarak büyüklüğü değişen başlangıç popülasyonu kullanılmıştır. Algoritma C dilinde kodlanmış olup farklı ayrıt yoğunluklarına sahip rastgele oluşturulmuş problemler üzerinde hesaplama denemeleri yapılmıştır. Çalışma zamanı ve amaç fonksiyonunun değerleri açısından algoritmanın verimli olduğu gözlenmiştir. Oluşturulan problemler klasik genetik algoritma ile de çözülerek, başarım oranları ve çözüm zamanları incelenmiş, sezgisel yaklaşımın etkisini gözlemlemek amacıyla bir biri ile karşılaştırılmıştır.