Kombinatoryal optimizasyon problemlerinin çözümünde makine öğrenmesi temelli yaklaşımlar
Machine learning based approaches in combinatorial optimization problems
- Tez No: 828500
- Danışmanlar: PROF. DR. BURAK ORDİN
- Tez Türü: Doktora
- Konular: Matematik, Mathematics
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2023
- Dil: Türkçe
- Üniversite: Ege Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Matematik Ana Bilim Dalı
- Bilim Dalı: Bilgisayar Bilimleri Bilim Dalı
- Sayfa Sayısı: 118
Ö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.
Özet (Çeviri)
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.
Benzer Tezler
- Data-driven operators for a hybrid evolutionary algorithm to solve multi-trip rich vehicle routing problem
Çok kullanımlı zengin araç rotalama probleminin melez evrimsel algoritma ile çözümlenmesinde veri güdümlü operatörlerin etkileri
DİLARA AYKANAT
Yüksek Lisans
İngilizce
2020
Endüstri ve Endüstri MühendisliğiBoğaziçi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ MUSTAFA GÖKÇE BAYDOĞAN
- Fake news classification using machine learning and deep learning approaches
Makine öğrenimi ve derin öğrenme yaklaşımlarını kullanarak sahte haber sınıflandırması
SAJA ABDULHALEEM MAHMOOD AL-OBAIDI
Yüksek Lisans
İngilizce
2023
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolGazi ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ TUBA ÇAĞLIKANTAR
- Akış tipi çizelgeleme problemlerinin çözümünde metasezgisel yaklaşımların karşılaştırmalı olarak analizi
A comparative analysis of metaheuristic approaches developed for solving flowshop scheduling problems
MURAT RUHLUSARAÇ
- Dinamik esnek atölye tipi çizelgeleme probleminin bakım kısıtları altında çözümü
Solution of dynamic flexible job shop scheduling under maintenance constraints
OLCAY KALAN
Doktora
Türkçe
2019
Endüstri ve Endüstri MühendisliğiÇukurova ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. CENK ŞAHİN
- Kombinatoryal optimizasyon problemlerinde arı sistemi yaklaşımı
Bee system approach for combinatorial optimization problems
PINAR ZARİF TAPKAN
Doktora
Türkçe
2010
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolErciyes ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. LALE ÖZBAKIR