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

Abstract

This thesis examines non deterministic polynomial problems in relation to the solutions proposed by Swarm Intelligence Algorithms. Many real life problems can be reduced to problems in the NP class and that is the reason they attract scientific interest. In this thesis, the problems that are examined are the Travelling Salesman Problem, the Vehicle Routing Problem, the Quadratic Assignment Problem in the form of the Linear Machine Layout Problem. These problems are approached with established methods like Simulated Annealing but also with the new methods of Ant Swarm Intelligence. The aim of the critical appraisal of the international journals and literature review is to select the best performing algorithms in relation to the above mentioned problems. Finally, a new Ant Swarm Intelligence algorithm is proposed.

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