Σχηματισμός διαδρομών μυρμηγκιών για εύρεση συντομότερων μονοπατιών σε γενικούς γράφους
Loading...
Date
2023-07-06
Authors
Ταμπουρατζής, Παναγιώτης
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Το πρόβλημα εύρεσης συντομότερων διαδρομών απασχολεί την επιστήμη της Πληροφορικής από τις αρχές της. Είναι ένα από τα προβλήματα που απασχολούν και τους έμβιους οργανισμούς που έχουν αναπτύξει μηχανισμούς για λύνουν αυτό το πρόβλημα. Η παρούσα διπλωματική εργασία ασχολείται με την υλοποίηση κώδικα για πειραματική επαλήθευση της σύγκλισης αλγορίθμου που βασίζεται στον τρόπο δημιουργίας μονοπατιών από μυρμήγκια σε γενικούς γράφους καθώς και στην πειραματική επαλήθευση των αποτελεσμάτων της εργασίας «Finding Geodesics on graphs using reinforcement learning» [1]. Ο αλγόριθμος που απασχολεί αυτή την εργασία βασίζεται στην απόθεση φερομόνης από μυρμήγκια επί των μονοπατιών που ακολουθούν κατά την διαδικασία εύρεσης τροφής [1]. Έπειτα από μελέτη της εργασίας και σχετικής βιβλιογραφίας έγιναν αρχικά πειράματα για την επαλήθευση των θεωρητικών αποτελεσμάτων σε γράφους series-parallel και των 5 ακμών ρομβοειδή γράφο (5e Losange graph). Μετά την επαλήθευση των θεωρητικών αποτελεσμάτων, εκτελέστηκαν πειράματα αρχικά σε τυχαίους γράφους βάση του μοντέλου των Erdos- Renyi και στην συνέχεια, σε τυχαίους γράφους των οποίων η κατανομή βαθμού στους κόμβους ακολουθεί τον Νόμο Δύναμης (Power Law). Τέλος, ο αλγόριθμος εφαρμόστηκε σε πραγματικό δίκτυο που αναπαριστά τα αεροδρόμια και τις συνδέσεις τους στις Ηνωμένες Πολιτείες της Αμερικής (Η.Π.Α.). Τα αποτελέσματα φαίνονται ενθαρρυντικά για αυτού του είδους αλγορίθμους, όμως ο συγκεκριμένος αλγόριθμος δεν εμφανίζεται να είναι η καλύτερη επιλογή.
Description
Keywords
Διαδρομές μυρμηγκιών, Φερομόνη, Αλγόριθμοι εμπνευσμένοι από τη φύση, Σειρά παράλληλοι γράφοι, Εν σειρά εν παραλλήλω γράφοι