Maksimum klik problemi için algoritmik yaklaşımlar
Yükleniyor...
Tarih
2019
Yazarlar
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Ege Üniversitesi, Fen Bilimleri Fakültesi
Erişim Hakkı
info:eu-repo/semantics/openAccess
Özet
Maksimum Klik Problemi; yöneylem araştırması alanında çok çalışılan ve NP-Tam sınıfına ait teorik çizge optimizasyon problemidir. Problem, birçok alanda yaygın bir uygulama alanına sahiptir. Ayrıca problem birçok çizge kuramı problemi ile yakın bir ilişki içerisindedir. Bu yüzden maksimum klik problemi bilgisayar bilimleri alanında önemli bir role sahiptir. Bu tezde, maksimum klik problemi araştırılmış, problem için literatürde var olan çözüm yöntemleri incelenmiş ve bu problem için yeni bir hibrit genetik algoritma önerilmiştir. Önerilen algoritma Java dilinde kodlanmış, DIMACS ve BHOSLIB kütüphane örnekleri üzerinde test edilerek, literatürdeki benzer çalışmalar ile karşılaştırılmıştır. Hesaplama sonuçları önerilen algoritmanın etkinliğini göstermektedir.
The Maximum Clique Problem is much studied graph theory optimization problem in operation research field, and it belongs to the class of NP-Complete. The problem has widespread field of application in many areas. Besides, the problem is closely related to many graph theory problems. Thus, the maximum clique problem plays an important role in computer science field. In this thesis, the maximum clique problem is studied, the solution approaches for the problem in literature are investigated and a new hybrid genetic algorithm have been proposed for the problem. The proposed algorithm has been implemented in Java and has been tested on the DIMACS and BHOSLIB benchmark instances, the results have been compared with similar studies the literature works. The experimental results show that proposed algorithm is effective.
The Maximum Clique Problem is much studied graph theory optimization problem in operation research field, and it belongs to the class of NP-Complete. The problem has widespread field of application in many areas. Besides, the problem is closely related to many graph theory problems. Thus, the maximum clique problem plays an important role in computer science field. In this thesis, the maximum clique problem is studied, the solution approaches for the problem in literature are investigated and a new hybrid genetic algorithm have been proposed for the problem. The proposed algorithm has been implemented in Java and has been tested on the DIMACS and BHOSLIB benchmark instances, the results have been compared with similar studies the literature works. The experimental results show that proposed algorithm is effective.
Açıklama
Anahtar Kelimeler
Maksimum Klik Problemi, Cizge Kuramı, Optimizasyon Problemleri, Sezgisel Algoritmalar, Hibrit Genetik Algoritmalar, Maximum Clique Problem, Graph Theory, Optimization Problems, Heuristic Algorithms, Hybrid Genetic Algorithms
