Σχηματισμός διαδρομών μυρμηγκιών για εύρεση συντομότερων μονοπατιών σε γενικούς γράφους
| datacite.contributor.RelatedPerson | Μακρής, Χρήστος | |
| datacite.contributor.Supervisor | Τσίχλας, Κωνσταντίνος | |
| dc.contributor.author | Ταμπουρατζής, Παναγιώτης | |
| dc.contributor.other | Tampouratzis, Panagiotis | |
| dc.date.accessioned | 2023-07-07T09:01:38Z | |
| dc.date.available | 2023-07-07T09:01:38Z | |
| dc.date.issued | 2023-07-06 | |
| dc.degree | graduateThesis | |
| dc.description.abstract | Το πρόβλημα εύρεσης συντομότερων διαδρομών απασχολεί την επιστήμη της Πληροφορικής από τις αρχές της. Είναι ένα από τα προβλήματα που απασχολούν και τους έμβιους οργανισμούς που έχουν αναπτύξει μηχανισμούς για λύνουν αυτό το πρόβλημα. Η παρούσα διπλωματική εργασία ασχολείται με την υλοποίηση κώδικα για πειραματική επαλήθευση της σύγκλισης αλγορίθμου που βασίζεται στον τρόπο δημιουργίας μονοπατιών από μυρμήγκια σε γενικούς γράφους καθώς και στην πειραματική επαλήθευση των αποτελεσμάτων της εργασίας «Finding Geodesics on graphs using reinforcement learning» [1]. Ο αλγόριθμος που απασχολεί αυτή την εργασία βασίζεται στην απόθεση φερομόνης από μυρμήγκια επί των μονοπατιών που ακολουθούν κατά την διαδικασία εύρεσης τροφής [1]. Έπειτα από μελέτη της εργασίας και σχετικής βιβλιογραφίας έγιναν αρχικά πειράματα για την επαλήθευση των θεωρητικών αποτελεσμάτων σε γράφους series-parallel και των 5 ακμών ρομβοειδή γράφο (5e Losange graph). Μετά την επαλήθευση των θεωρητικών αποτελεσμάτων, εκτελέστηκαν πειράματα αρχικά σε τυχαίους γράφους βάση του μοντέλου των Erdos- Renyi και στην συνέχεια, σε τυχαίους γράφους των οποίων η κατανομή βαθμού στους κόμβους ακολουθεί τον Νόμο Δύναμης (Power Law). Τέλος, ο αλγόριθμος εφαρμόστηκε σε πραγματικό δίκτυο που αναπαριστά τα αεροδρόμια και τις συνδέσεις τους στις Ηνωμένες Πολιτείες της Αμερικής (Η.Π.Α.). Τα αποτελέσματα φαίνονται ενθαρρυντικά για αυτού του είδους αλγορίθμους, όμως ο συγκεκριμένος αλγόριθμος δεν εμφανίζεται να είναι η καλύτερη επιλογή. | |
| dc.description.translatedabstract | The problem of finding shortest paths has been a concern of Computer Science since its beginnings. It is one of the problems that concern living organisms that have developed mechanisms to solve this problem. This thesis deals witη an implementation for experimental verification of the convergence of an algorithm inspired by the way ants create paths, as well as the experimental verification of the results of the work "Finding Geodesics on graphs using reinforcement learning" [1]. The algorithm proposed in this work is based on the deposition of pheromone by ants on the paths they follow during the process of finding food [1]. After studying the work and related literature, initial experiments were conducted to verify the theoretical results in series-parallel graphs and the 5-edge lozenge graph (5e Losange graph). After verifying the theoretical results, experiments were first performed on random graphs based on the Erdos-Renyi model and then on random graphs whose degree distribution in the nodes follows the Power Law. Finally, the algorithm was applied to a real network representing airports and their connections in the United States of America (USA). The results look encouraging but the implemented algorithm does not appear to be the best choice for the shortest paths problem. | |
| dc.identifier.uri | https://hdl.handle.net/10889/25431 | |
| dc.language.iso | el | |
| dc.rights | CC0 1.0 Universal | * |
| dc.rights.uri | http://creativecommons.org/publicdomain/zero/1.0/ | * |
| dc.subject | Διαδρομές μυρμηγκιών | |
| dc.subject | Φερομόνη | |
| dc.subject | Αλγόριθμοι εμπνευσμένοι από τη φύση | |
| dc.subject | Σειρά παράλληλοι γράφοι | |
| dc.subject | Εν σειρά εν παραλλήλω γράφοι | |
| dc.subject.alternative | Ant trail formation | |
| dc.subject.alternative | Pheromones | |
| dc.subject.alternative | Nature inspired algorithms | |
| dc.subject.alternative | Series parallel graphs | |
| dc.subject.alternative | Series parallel graphs | |
| dc.title | Σχηματισμός διαδρομών μυρμηγκιών για εύρεση συντομότερων μονοπατιών σε γενικούς γράφους | |
| dc.title.alternative | Ant trail formation for finding shortest paths in general graphs |
Files
Original bundle
1 - 1 of 1
Loading...
- Name:
- Σχηματισμός διαδρομών μυρμηγκιών για εύρεση συντομότερων μονοπατιών σε γενικούς γράφους - διπλωματική εργασία Ταμπουρατζή Παναγιώτη.pdf
- Size:
- 2.36 MB
- Format:
- Adobe Portable Document Format
License bundle
1 - 1 of 1
No Thumbnail Available
- Name:
- license.txt
- Size:
- 5.02 KB
- Format:
- Item-specific license agreed upon to submission
- Description: