Max-sat problemi için metasezgisel ve hibrit yaklaşımlar (metasezgisel + matematiksel yöntemler)
Metaheuristic and hybrid approaches for the max-sat problem (metaheuristic + mathematical methods
Yazar: CANSU ÇINAR SİS
Danışman: DR. ÖĞR. ÜYESİ TOLGA AYDIN
Atatürk Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Yüksek Lisans, 2021
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control

Ö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.

Abstract:
Purpose: The aim of this study is to compare the results obtained from metaheuristic methods and hybrid methods in order to find the optimum result in Max-Sat problem and examine whether hybrid methods will be successful for such problems.
Method: In this study, firstly, different types of Max-Sat problem (Max-2Sat, Max-3Sat and Weighted Max-Sat) are solved by Simulated Annealing, Tabu Search and Genetic algorithms, which are metaheuristic methods. Later, a deterministic approach is applied to all 3 algorithms in the neighborhood finding phase and hybrid methods are developed in which metaheuristic and deterministic methods are used together.
Findings: As a result of the study, metaheuristic and hybrid algorithm results were recorded and the results obtained from metaheuristic methods and the results obtained from hybrid methods were compared with each other and with Eleventh Max-Sat Evaluations results. It has been observed that the algorithms developed with the hybrid approach are more successful than those developed with the metaheuristic approach. In addition, while 100% success is achieved by finding the optimum result in the literature with the Hybrid Tabu Search algorithm, the success of hybrid methods has been proven by obtaining even better results than the optimum result in the literature with the Hybrid Genetic Algorithm.
Results: It has been proven by experimental findings that the hybrid approach developed for the Max-Sat problem is more successful than the metaheuristic method. In addition, contrary to what was predicted, it was seen that the working times of hybrid methods are not much more than metaheuristic methods.