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ı: 52
Ö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
- 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
- Otonom robotlarda yapay sinir ağları ile navigasyon uygulaması
Navigation application on autonomous robots using artificial neural networks
ALPER HÜSEYİN DOĞAN
Yüksek Lisans
Türkçe
2023
Elektrik ve Elektronik Mühendisliğiİstanbul Üniversitesi-CerrahpaşaElektrik ve Elektronik Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ TARIK VELİ MUMCU
- İmalat sistemlerinin tasarlanması ve öncelik kurallarının belirlenmesinde yapay sinir ağlarının kullanılması
Başlık çevirisi yok
TARIK ÇAKAR
Doktora
Türkçe
1997
Mühendislik Bilimleriİstanbul Teknik Üniversitesiİşletme Mühendisliği Ana Bilim Dalı
PROF. DR. AYHAN TORAMAN
- Derin öğrenme modellerinin hücre veri seti üzerinde eğitilerek kıyaslanması ve mobil ortama uyarlanması
Comparision and mobile application of deep learning models trained on blood cell dataset
MEHMET YAVUZ
Yüksek Lisans
Türkçe
2020
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSakarya Uygulamalı Bilimler ÜniversitesiBiyomedikal Mühendisliği Ana Bilim Dalı
DOÇ. DR. MUSTAFA ZAHİD YILDIZ