MAX-SAT PROBLEMİ İÇİN METASEZGİSEL VE HİBRİT YAKLAŞIMLAR (METASEZGİSEL + MATEMATİKSEL YÖNTEMLER)

---

Tezin Türü: Yüksek Lisans

Tezin Yürütüldüğü Kurum: Atatürk Üniversitesi, Fen Bilimleri Enstitüsü, Bilgisayar Mühendisliği Anabilim Dalı, Türkiye

Tezin Onay Tarihi: 2021

Tezin Dili: Türkçe

Öğrenci: CANSU ÇINAR SİS

Danışman: Tolga Aydın

Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu

Özet:

Amaç: Bu çalışmanın amacı, Max-Sat probleminde optimum sonucu bulmak için metasezgisel yöntemler ile hibrit yöntemlerden elde edilen sonuçları karşılaştırıp bu tarz problemler için hibrit yöntemlerin başarılı olup olmayacağını incelemektir. Yöntem: Bu çalışmada ilk olarak Max-Sat probleminin farklı türleri (Max-2Sat, Max-3Sat ve Ağırlıklı Max-Sat) metasezgisel yöntemlerden olan Benzetilmiş Tavlama, Tabu Arama ve Genetik algoritmaları ile çözülmüştür. Daha sonra her 3 algoritmaya, komşuluk bulma aşamasında deterministik bir yaklaşım uygulanarak metasezgisel ve deterministik yöntemin bir arada kullanıldığı hibrit yöntemler geliştirilmiştir. Bulgular: Çalışma sonucunda metasezgisel ve hibrit algoritma sonuçları kaydedilip metasezgisel yöntemlerden elde edilen sonuçlar ile hibrit yöntemlerden elde edilen sonuçlar hem birbirleriyle hem de Eleventh Max-Sat Evaluations sonuçlarıyla karşılaştırılmıştır. Hibrit yaklaşım ile geliştirilen algoritmaların metasezgisel yaklaşım ile geliştirilenlere göre daha başarılı olduğu görülmüştür. Ayrıca Hibrit Tabu Arama algoritması ile literatürdeki optimum sonuç bulunarak %100 başarı sağlanırken Hibrit Genetik Algoritması ile literatürdeki optimum sonuçtan bile daha iyi sonuç elde edilerek hibrit yöntemlerin başarısı gözlemlenmiştir. Sonuç: Max-Sat problemi için geliştirilen hibrit yaklaşımın metasezgisel yönteme göre daha başarılı olduğu deneysel bulgular ile gözlemlenmiştir. Ayrıca öngörülenin aksine hibrit yöntemlerin çalışma sürelerinin metasezgisel yöntemlerden çok fazla olmadığı görülmüştür.