δείτε την πρωτότυπη σελίδα τεκμηρίου στον ιστότοπο του αποθετηρίου του φορέα για περισσότερες πληροφορίες και για να δείτε όλα τα ψηφιακά αρχεία του τεκμηρίου*
Συγκριτική μελέτη αλγορίθμων νοημοσύνης σμήνους (Swarm Intelligence) σε προβλήματα βελτιστοποίησης
Ο Μαθηματικός Προγραμματισμός προσφέρει διάφορες μεθόδους επίλυσης προβλημάτων βελτιστοποίησης, οι οποίες εγγυώνται την εύρεση της βέλτιστης λύσης του προβλήματος. Ωστόσο, ο χρόνος που απαιτείται για την εύρεση της βέλτιστης λύσης αυξάνεται εκθετικά όσο αυξάνονται οι μεταβλητές απόφασης του προβλήματος. Αυτό έχει ως αποτέλεσμα να διερευνώνται μέθοδοι επίλυσης με μικρότερο υπολογιστικό χρόνο. Οι νοήμονες αλγόριθμοι που είναι εμπνευσμένοι από την φύση αποτελούν μεθόδους που η δομή τους τούς επιτρέπει να βρίσκουν μία υποβέλτιστη λύση σε προβλήματα βελτιστοποίησης μεγαλύτερης πολυπλοκότητας σε σημαντικά μικρότερο χρόνο σε σχέση με τον Μαθηματικό Προγραμματισμό, ο οποίος παραμένει ένα δυνατό εργαλείο επίλυσης. Μία κατηγορία νοημόνων αλγορίθμων βελτιστοποίησης αποτελούν οι αλγόριθμοι που είναι εμπνευσμένοι από τη φύση και κατ’ επέκταση ονομάζονται Αλγόριθμοι Εμπνευσμένοι από την Φύση.
Η παρούσα διπλωματική εργασία μελετάει αλγόριθμους της συγκεκριμένης κατηγορίας και πιο συγκεκριμένα εκείνους που ανήκουν στην υπο-κατηγορία αυτής, που ονομάζεται Νοημοσύνη Σμήνους (Swarm Intelligence). Στη Νοημοσύνη Σμήνους κατατάσσονται οι αλγόριθμοι που έχουν αναπτυχθεί βασιζόμενοι στην συλλογική συμπεριφορά των μελών μεγάλων ομάδων έμβιων όντων (όπως σμήνη, αγέλες, κοπάδια κλπ.). Ο πρώτος και πιο γνωστός αλγόριθμος αυτής της κατηγορίας είναι η Βελτιστοποίηση Σμήνους Σωματιδίων (Particle Swarm Optimization) που έχει εμπνευστεί από τον συγχρονισμένο τρόπο πτήσης των πτηνών. Η δημοφιλία που απέκτησε, λόγω της απλότητάς του και άρα της ευκολίας να αναπτυχθεί από άλλους ερευνητές, είχε ως αποτέλεσμα να παρουσιαστούν πολλοί παρόμοιοι αλγόριθμοι, για τους οποίους ισχυρίζονται οι συγγραφείς τους ότι προσομοιώνουν διάφορους τρόπους συλλογικής νοημοσύνης που συναντώνται στα ζώα.
Λόγω του ολοένα αυξανόμενου πλήθους νέων τέτοιου τύπου αλγορίθμων που παρουσιάζονται τα τελευταία χρόνια, η παρούσα εργασία μελετάει 23 επιλεγμένους αλγόριθμους Νοημοσύνης Σμήνους. Η επιλογή αυτών των αλγορίθμων έγινε με βάση ομοιότητες που παρατηρούνται στη δομή και στο μαθηματικό φορμαλισμό τους, σε σύγκριση με τη Βελτιστοποίηση Σμήνους Σωματιδίων. Πέραν αυτής της σύγκρισης, γίνεται επίσης σύγκριση σε πρακτικό επίπεδο, που επιτυγχάνεται με την εφαρμογή των αλγορίθμων σε επιλεγμένα προβλήματα βελτιστοποίησης από το χώρο της μηχανικής. Απώτερος σκοπός αυτής της σύγκρισης είναι η ανάδειξη της/των πιο αποδοτικής/-ών μεθόδων, αλλά και η απάντηση στο ερευνητικό ερώτημα που τέθηκε εξ’ αρχής: «συνεισφέρουν στην επίλυση ενός προβλήματος (από πλευράς απόδοσης ή προσέγγισης του προβλήματος) όλοι αυτοί οι αλγόριθμοι ή τελικά η Βελτιστοποίηση Σμήνους Σωματιδίων έχει την επικρατούσα απόδοση;».Τα προβλήματα που επιλέχθηκαν για την παραπάνω μελέτη είναι δύο κατηγοριών. Στην πρώτη κατηγορία κατατάσσονται τα προβλήματα μηχανικού, όπως είναι ο σχεδιασμός μιας συγκολλημένης δοκού με το ελάχιστο δυνατό κόστος, ο σχεδιασμός μειωτή ταχύτητας με ελαχιστοποιημένο όγκο γραναζιών και αξόνων μετάδοσης και ο σχεδιασμός ελατηρίου, που θα υποβληθεί σε εφελκυσμό/θλίψη, με το ελάχιστο δυνατό βάρος. Στην δεύτερη κατηγορία συναντώνται συναρτήσεις ελέγχου αποδοτικότητας, που προτάθηκαν στη σειρά διεθνών συνεδρίων με κριτές, «Congress on Evolutionary Computation». Οι εν λόγω συναρτήσεις χαρακτηρίζονται είτε από πλήθος περιορισμών είτε από μεγάλο πλήθος διαστάσεων.
Στο πειραματικό μέρος της παρούσας εργασίας, οι συγκρινόμενοι αλγόριθμοι αξιολογούνται με βάση το συνολικό χρόνο εκτέλεσής του, την καλύτερη λύση που βρήκαν, την εφικτότητα των λύσεων που βρίσκουν (δηλαδή αν η λύση παραβιάζει ή όχι κάποιους περιορισμούς του προβλήματος) και της επανάληψης στην οποία βρέθηκε η καλύτερη λύση (σύγκλιση ή convergence).
*Η εύρυθμη και αδιάλειπτη λειτουργία των διαδικτυακών διευθύνσεων των συλλογών (ψηφιακό αρχείο, καρτέλα τεκμηρίου στο αποθετήριο) είναι αποκλειστική ευθύνη των αντίστοιχων Φορέων περιεχομένου.
Βοηθείστε μας να κάνουμε καλύτερο το OpenArchives.gr.
Πανεπιστήμιο Αιγαίου
