Νευρωνικά Δίκτυα Γράφων για την επίλυση του προβλήματος του περιπλανώμενου πωλητή : συνδυασμός μαθηματικού προγραμματισμού και μηχανικής μάθησης

Abstract

Η παρούσα διατριβή εξετάζει τη χρήση Νευρωνικών Δικτύων Γράφων (Graph Neural Networks - GNNs) για την επίλυση του κλασικού προβλήματος του Πλανόδιου Πωλητή (Traveling Salesman Problem - TSP). Το TSP αποτελεί ένα από τα σημαντικότερα προβλήματα συνδυαστικής βελτιστοποίησης και έχει χαρακτηριστεί ως NP-hard. Η μεθοδολογία που αναπτύχθηκε συνδυάζει κλασικές τεχνικές βελτιστοποίησης με σύγχρονες προσεγγίσεις μηχανικής μάθησης, αναδεικνύοντας τον ρόλο των Νευρωνικών Δικτύων Γράφων στη μοντελοποίηση δομών γράφων και στην επίλυση προβλημάτων συνδυαστικής φύσης. Ειδικότερα, η εφαρμογή Νευρωνικών Δικτύων Γράφων στο συγκεκριμένο πρόβλημα στοχεύει στην πρόβλεψη των ακμών που συνθέτουν τη βέλτιστη διαδρομή σε πλήρως συνδεδεμένους γράφους. Η εκπαίδευση και η αξιολόγηση μοντέλων Νευρωνικών Δικτύων Γράφων διεξάχθηκε με τη δημιουργία συνθετικών δεδομένων. Τα πειραματικά αποτελέσματα αναδεικνύουν ότι τα μοντέλα Νευρωνικών Δικτύων Γράφων μπορούν να εκπαιδευτούν αποτελεσματικά στα μοτίβα που αποτυπώνουν τις βέλτιστες λύσεις και να γενικεύσουν σε νέα παραδείγματα, γεγονός που επιβεβαιώνει τη δυναμική τους για την αντιμετώπιση πολύπλοκων προβλημάτων βελτιστοποίησης.