Αλγόριθμοι τεχνητής ευφυΐας σμήνους και εφαρμογές σε μη-ντετερμινιστικά πολυωνυμικά προβλήματα

Abstract

Η παρούσα διδακτορική διατριβή ασχολείται με τα Μη ντετερμινιστικά Πολυωνυμικά Προβλήματα και τις λύσεις που προτείνονται για αυτά από τους Αλγορίθμους Ευφυΐας Σμήνους. Προβλήματα με πλήθος εφαρμογών μπορούν να αναχθούν σε προβλήματα της κλάσης Νοn deterministic Polynomial και οι τροποποιήσεις τους με σκοπό να καλύψουν μεγαλύτερο εύρος εφαρμογών δείχνουν το ενδιαφέρον που έχουν προκαλέσει στη ερευνητική κοινότητα καθώς και την αντίστοιχη προσπάθεια που έχει γίνει για την επίλυση τους. Τα προβλήματα που ερευνήθηκαν στην παρούσα διατριβή όπως, το Πρόβλημα Περιοδεύοντος Πωλητή, το Πρόβλημα Δρομολόγησης Οχημάτων, το Πρόβλημα Τετραγωνικής Ανάθεσης υπό τη μορφή του Προβλήματος Γραμμικής Τοποθέτησης Μηχανών προσεγγίζονται με παλαιότερες μεθόδους, όπως της Προσομοιωμένης Ανόπτησης, αλλά και με νέους αλγορίθμους σμήνους ευφυΐας μυρμηγκιών. Γίνεται εκτενής έρευνα της διεθνούς αρθρογραφίας και βιβλιογραφίας με σκοπό την επιλογή των βέλτιστων αλγορίθμων και τη κατανόηση της συμπεριφοράς των αλγορίθμων σε σχέση με τα υπό έρευνα προβλήματα. Τέλος προτείνεται και ελέγχεται η απόδοση ενός νέου αλγορίθμου σμήνους ευφυΐας μυρμηγκιών.