Please use this identifier to cite or link to this item: https://hdl.handle.net/20.500.14365/122
Title: Using artificial intelligence and machine learning to solve NP-complete graph theory problems
Other Titles: NP-tam çizge teori problemlerinin çözümü için yapay zeka ve makine öğrenmesi kullanımı
Authors: Binli, Mustafa Kemal
Advisors: Erol, Kutluhan
Keywords: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol
Computer Engineering and Computer Science and Control
Publisher: İzmir Ekonomi Üniversitesi
Abstract: 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.
URI: https://tez.yok.gov.tr/UlusalTezMerkezi/TezGoster?key=Eb5EkakJlp3olBdo_wNEGUOOOnE3f5sMtjYhO5Dck7IQCQYK9Q8JyMumrKWPBCq5
https://hdl.handle.net/20.500.14365/122
Appears in Collections:Lisansüstü Eğitim Enstitüsü Tez Koleksiyonu

Files in This Item:
File SizeFormat 
243-623715.pdf4.56 MBAdobe PDFView/Open
Show full item record



CORE Recommender

Page view(s)

112
checked on Sep 30, 2024

Download(s)

38
checked on Sep 30, 2024

Google ScholarTM

Check





Items in GCRIS Repository are protected by copyright, with all rights reserved, unless otherwise indicated.