Αλγόριθμοι αποικίας μυρμηγκιών

Abstract

Το Κεφάλαιο 1, παρουσιάζει μία περίληψη της βελτιστοποίησης αποικίας μυρμηγκιών (ACO) - μία μεταευριστική εμπνευσμένη από τη συμπεριφορά πραγματικών μυρμηγκιών, μία μέθοδος επίλυσης δύσκολων προβλημάτων συνδυαστικής βελτιστοποίησης. Το Κεφάλαιο 2, παρουσιάζει ένα τρόπο να εκτείνουμε τον ACO σε συνεχή χωρία χωρίς να χρειαστεί να κάνουμε καμία κρίσιμη αλλαγή στη δομή του. Δηλώνουμε ότι ο ACO επεκτείνεται σε συνεχή χωρία από τον ACOR. Το Κεφάλαιο 3, παρουσιάζει στην ενότητα 3.1 έναν αλγόριθμο εμπνευσμένο από τα μυρμήγκια για βελτιστοποίηση σε συνεχείς χώρους αναζήτησης που βασίζεται στη παραγωγή τυχαίων διανυσμάτων με πολυμεταβλητή Γκαουσιαννή συνάρτηση πυκνότητας πιθανότητας. Ονομάζεται MACACO και συγκρίνεται με το Συνεχές Σύστημα Μυρμηγκιακής Αποικίας (CACS) και τη Βελτιστοποίηση Αποικίας Μυρμηγκιών στον Rn (ACOR). Στην ενότητα 3.2 περιγράφεται ένα σύστημα συνάθροισης φερομόνης (APS), το οποίο είναι μία επέκταση του ACO για συνεχή χωρία, χρησιμοποιώντας τη συλλογική συμπεριφορά των ατόμων που επικοινωνούν χρησιμοποιώντας φερομόνες συνάθροισης. Το APS δοκιμάστηκε σε αρκετές συναρτήσεις ελέγχου. Τα αποτελέσματα δείχνουν ότι το APS μπορεί να λύσει προβλήματα βελτιστοποιήσης πραγματικών παραμέτρων αρκετά καλά. Το Κεφάλαιο 4, παρουσιάζει στην ενότητα 4.1 κάποιες ιδιότητες σύγκλισης για μία κλάση από αλγορίθμους βελτιστοποίησης αποικίας μυρμηγκίων. Αποδεικνύεται επίσης, ότι μετά την εύρεση μίας βέλτιστης λύσης, χρειάζεται ένας πεπερασμένος αριθμός από επαναλήψεις για να αυξηθούν τα ίχνη φερομόνης που σχετίζονται με την εύρεση βέλτιστης λύσης περισσότερο από κάθε άλλο ίχνος φερομόνης. Στην ενότητα 4.2 παρουσιάζεται μία ανάλυση σύγκλισης του ACO σε παραπλανητικά προβλήματα.και αποδεικνύεται ότι ο ACO μπορεί να επιτύχει σύγκλιση προσβασιμότητας αλλά όχι ασυμπτωτική σύγκλιση για μία κλάση από πρώτης τάξης παραπλανητικά προβλήματα (FODS) χωρίς να υποθέσουμε μία ελάχιστη φερομόνη σε κάθε επανάληψη.