Kombinatoryal optimizasyon problemlerinin çözümünde makine öğrenmesi temelli yaklaşımlar
Machine learning based approaches in combinatorial optimization problems
Yazar: DUYGU SELİN TURAN
Danışman: PROF. DR. BURAK ORDİN
Ege Üniversitesi / Fen Bilimleri Enstitüsü / Matematik Ana Bilim Dalı / Bilgisayar Bilimleri Bilim Dalı
Derece: Doktora, 2023
Konu: Matematik = Mathematics

Özet:
Kombinatoryal optimizasyon problemleri, sonlu bir olası çözümler kümesinden en iyi sonucu veren çözümün seçilmesi ile ilgilidir. Bu seçim için kesin çözüm veren yöntemler vardır ancak, problemin boyutu arttıkça polinom zamanda çözüm bulma işi zorlaşmaktadır. Bu nedenle, kombinatoryal optimizasyon problemlerinin çözümü için yaklaşık çözümler veren algoritmaların tasarlanması oldukça önemlidir.
Kombinatoryal optimizasyon problemlerinin çözümü için makine öğrenmesi ve veri madenciliği yöntemlerinin kullanımı son yıllarda giderek önem kazanmıştır. Çoğunlukla başlangıç çözümlerin seçimi, olası çözüm kümesinin daraltılması ve bir sonraki adımın tahmini gibi aşamalarda kullanılan bu yöntemlerin polinom zamanda yaklaşık çözümler bulması, bu alana ilgiyi arttırmıştır. Mevcut yöntemlerden biri olan kümeleme tekniği, veriler arası benzerlik/uzaklık bilgilerini kullanarak benzer verileri aynı kümede, benzer olmayan verileri farklı kümelerde gruplandırmayı amaçlar. Bu tez çalışmasında, Steiner ağaç problemi türlerinden biri olan graflarda Steiner ağaç problemi için kümeleme tekniği kullanılarak bir yaklaşık çözüm algoritması geliştirilmiştir. Tasarlanan yöntem, bir artımlı graf kümeleme algoritması ile Steiner noktaları belirleyerek problemi çözer. Önerilen yöntem C# ve C++ programlama dillerinde programlanmış ve SteinLib Testdata kütüphanesinden 36 veri seti ile hesaplama denemeleri yapılmıştır. Elde edilen sonuçlar, tasarlanan yöntemin ele alınan problemleri makul hata oranları ile çözdüğünü göstermektedir.

Abstract:
Combinatorial optimization problems is about choosing the best solution from a finite set of possible solutions. There are methods that give exact solutions for this selection, however, as the size of the problem increases, the task of finding a solution in polynomial time becomes more difficult. Therefore, it is very important to propose algorithms that give approximate solutions for the solution of combinatorial optimization problems.
The use of machine learning and data mining methods for the solution of combinatorial optimization problems has become increasingly important in recent years. The fact that these methods, which are mostly used in stages such as the selection of initial solutions, reducing the possible solution set and estimation of the next step, find approximate solutions in polynomial time, has increased the interest in this field. Clustering technique, which is one of these methods, aims to group similar data in the same cluster and dissimilar data in different clusters by using similarity/distance information between data. In this thesis, an approximate solution algorithm is proposed for the network Steiner tree problem, which is one of the Steiner tree problem types, by using the clustering technique. The designed method solves the problem by determining Steiner points with an incremental graph clustering algorithm. The proposed method was programmed in C# and C++ programming languages and computational experiments were made with 36 datasets from the SteinLib Testdata library. The obtained results show that the proposed method solves the problems with reasonable error rates.