Tez No	İndirme	Tez Künye	Durumu
623715		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ı Yazar:MUSTAFA KEMAL BİNLİ Danışman: DR. ÖĞR. ÜYESİ KUTLUHAN EROL Yer Bilgisi: İzmir Ekonomi Üniversitesi / Lisansüstü Eğitim Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control Dizin:	Onaylandı Yüksek Lisans İngilizce 2020 52 s.
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.
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.