Geri Dön

Kombinatoryal optimizasyon problemlerinin çözümünde makine öğrenmesi temelli yaklaşımlar

Machine learning based approaches in combinatorial optimization problems

  1. Tez No: 828500
  2. Yazar: DUYGU SELİN TURAN
  3. Danışmanlar: PROF. DR. BURAK ORDİN
  4. Tez Türü: Doktora
  5. Konular: Matematik, Mathematics
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2023
  8. Dil: Türkçe
  9. Üniversite: Ege Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Matematik Ana Bilim Dalı
  12. Bilim Dalı: Bilgisayar Bilimleri Bilim Dalı
  13. 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

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

    İngilizce

    2020

    Endüstri ve Endüstri MühendisliğiBoğaziçi Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ MUSTAFA GÖKÇE BAYDOĞAN

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

    İngilizce

    2023

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolGazi Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ TUBA ÇAĞLIKANTAR

  3. 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Ç

    Yüksek Lisans

    Türkçe

    Türkçe

    2012

    İşletmeErciyes Üniversitesi

    İşletme Ana Bilim Dalı

    DOÇ. DR. MEHMET S. İLKAY

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

    Türkçe

    2019

    Endüstri ve Endüstri MühendisliğiÇukurova Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DOÇ. DR. CENK ŞAHİN

  5. Kombinatoryal optimizasyon problemlerinde arı sistemi yaklaşımı

    Bee system approach for combinatorial optimization problems

    PINAR ZARİF TAPKAN

    Doktora

    Türkçe

    Türkçe

    2010

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolErciyes Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. LALE ÖZBAKIR