Using artificial intelligence and machine learning to solve NP-complete graph theory problems
NP-tam çizge teori problemlerinin çözümü için yapay zeka ve makine öğrenmesi kullanımı
- Tez No: 623715
- Danışmanlar: DR. ÖĞR. ÜYESİ KUTLUHAN EROL
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2020
- Dil: İngilizce
- Üniversite: İzmir Ekonomi Üniversitesi
- Enstitü: Lisansüstü Eğitim Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
Bilgisayar bilimi literatürü, lojistikten bilgi güvenliğine kadar bir çok alanda polinom zamanda çözümü bilinmeyen NP-tam problemlerle doludur. Bu tez, sezgisel arama literatüründen ve optimallik için çabalayan makine öğrenmesinden ilham alarak bu tür problemlerin hesaplama süresini iyileştirmeye çalışır. Yöntemimiz, sezgisel bir fonksiyon olarak Doğrusal Programlama (DP) yaklaşıklıkla birlikte A* Algoritmasının kullanılmasını içerir ve hem hesaplama yükü hem de arama alanı boyutunu azaltmak açısından DP sezgiselliğini geliştirmek için bir Sinir Ağı eğitimine yönelir. Yaklaşımımızı Gezgin Satıcı Problemi (GSP)'ni genişleten zengin bir çizge teori problemi olan All Colors Shortest Path (ACSP) bağlamında gösteriyoruz. Sonuçlarımız, sezgisel bir fonksiyon olarak DP kullanmanın, arama alanını yarı yarıya azaltırken, aynı zamanda da optimalliği koruduğunu göstermektedir. Bir sezgisel olarak DP'nin yerini alan Yapay Sinir Ağı'nı (YSA) eğitmek, hesaplama alanını altı kat azaltırken hesaplama yükünde yalnızca çok küçük bir oranda artış getirmektedir. A* algoritmasında kullanılan sezgisel fonksiyonun onanırlık özelliğini garanti edilmese de, deneysel olarak çoğunlukla optimal veya neredeyse optimal çözümler üretmektedir. Sonuçlarımız, hesaplama kaynaklarının kullanılabilirliği nedeniyle küçük problem boyutlarına dayanmakta olsa da gelecekteki daha büyük ölçekli çalışmalarda yaklaşımımızın uygulanabilirliğini belirlemek için yeterli olduğuna inanmaktayız.
Özet (Çeviri)
Computer science literature is abound with NP-complete problems with numerous practical applications ranging from logistics to information security. This thesis attempts to address such problems by drawing inspiration from heuristic search literature and machine learning, striving for optimality while improving computation time. Our approach involves utilizing A* Algorithm in conjunction with Linear Programming (LP) approximations as a heuristic function and proceeds to train a Neural Network to improve on the LP heuristic with respect to both computation overhead and reduction in search space size. We demonstrate our approach in the context of All Colors Shortest Path (ACSP), a rich graph theory problem that extends the Travelling Salesperson Problem (TSP). Our results indicate that using LP as a heuristic function reduces search space by half, while preserving optimality. Artificial Neural Network (ANN) train to replace LP as a heuristic does a much better job reducing the search space by six fold at a fraction of the computational overhead. While it is not guaranteed to be admissible, empirically it produces mostly optimal or almost optimal solutions. Note that our results are based on small problem sizes due to computational resource availability, but we believe they are sufficient to establish the viability of our approach for future studies of larger scale.
Benzer Tezler
- Makine öğrenmesi tabanlı karınca kolonisi optimizasyonu kullanarak araç rotalama
Vehicle routing using machine learning based ant colony optimization
SİNAN KAMİLÇELEBİ
Yüksek Lisans
Türkçe
2022
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKocaeli ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. SUHAP ŞAHİN
- Prediction of COVID 19 disease using chest X-ray images based on deep learning
Derin öğrenmeye dayalı göğüs röntgen görüntüleri kullanarak COVID 19 hastalığının tahmini
ISMAEL ABDULLAH MOHAMMED AL-RAWE
Yüksek Lisans
İngilizce
2024
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolGazi ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. ADEM TEKEREK
- Türk dili için konuşma üretme
Başlık çevirisi yok
NİHAL ALICI
Yüksek Lisans
Türkçe
1998
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiKontrol ve Bilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. EŞREF ADALI
- Para piyasasında banka dışı mali kesimde finansal farklılaşma: Factoring, forfaiting, leasing ve özel finans kurumları
Başlık çevirisi yok
MÜGEHAN ACARASLAN
- Elektrokardiyografi sinyallerinden aritmilerin yapay zeka destekli sınıflandırılması
Classification of arrhythmias based on artificial intelligence from electrocardiography signals
BÜŞRA ÜNLÜ
Yüksek Lisans
Türkçe
2024
Mühendislik BilimleriTobb Ekonomi ve Teknoloji ÜniversitesiBiyomedikal Mühendisliği Ana Bilim Dalı
PROF. DR. OSMAN EROĞUL