Using artificial intelligence and machine learning to solve NP-complete graph theory problems

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ündeyalnı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.