Αλγόριθμοι βελτιστοποίησης αποικιών των μυρμηγκιών

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια

Οι αλγόριθμοι βελτιστοποίησης με βάση την λειτουργία των αποικιών των μυρμηγκιών μελετούνται από την Επιστήμη Υπολογιστών και την περιοχή της Επιχειρησιακής Έρευνας. Πρόκειται για μια πιθανολογική τεχνική για την επίλυση υπολογιστικών προβλημάτων τα οποία αφορούν στην εύρεση βέλτιστων μονοπατιών σε γράφους. Ο συγκεκριμένος αλγόριθμος ανήκει στην οικογένεια των αλγορίθμων "Αποικιών μυρμηγκιών" και στην κατηγορία μεθόδων γνωστές ως "Μέθοδοι Ευφυίας Σμήνους", αποτελεί δε μια μετα-ευριστική βελτιστοποίηση.

Ο αλγόριθμος αυτός προτάθηκε αρχικά μέσα από τη διδακτορική διατριβή του Marco Dorigo το 1992. Είναι ο πρώτος αλγόριθμος που αποσκοπεί στην αναζήτηση μιας βέλτιστης διαδρομής σε ένα γράφο με βάση την συμπεριφορά των μυρμηγκιών που αναζητούν μια διαδρομή από την αποικία προς την τροφή τους. Η αρχική αυτή ιδέα διαφοροποιήθηκε και επεκτάθηκε ώστε να υπηρετήσει την επίλυση μιας ευρύτερης κατηγορίας υπολογιστικών προβλημάτων, έχοντας σαν αποτέλεσμα την δημιουργία αρκετών προβλημάτων τα οποία βασίζονται στις διαφορετικές πτυχές της συμπεριφοράς των μυρμηγκιών.

Σύγκριση φυσικών μυρμηγκιών σε σχέση με τα ψηφιακά μυρμήγκια[Επεξεργασία | επεξεργασία κώδικα]

Ας συγκρίνουμε τα διάφορα χαρακτηριστικά των φυσικών μυρμηγκιών σε σχέση με τα ψηφιακά μυρμήγκια παρακάτω :

(1)Το μονοπάτι που ενώνει τη φωλιά με τη τροφή στα φυσικά μυρμήγκια , στα ψηφιακά μυρμήγκια πρόκειται για ένα γράφημα Κόμβων και Συνδέσεων .

(2) Η φερομόνη που αφήνουν τα φυσικά μυρμήγκια όταν πάνε να βρουν τροφή και που όπως είδαμε εξατμίζεται , στα ψηφιακά μυρμήγκια , αντιστοιχεί στις διάφορες θέσεις με αριθμητικές πληροφορίες , δίνοντας μας όλα τα πιθανά μονοπάτια του συστήματος . Στα μονοπάτια που δεν ικανοποιούν το σύστημα υπάρχει αρνητική αντίδραση (εξάτμιση) .

Ο αλγόριθμος ACO βρίσκει τις καλύτερες λύσεις που κατασκευάστηκαν από προηγούμενες επαναλήψεις. Συγκεκριμένα σε κάθε σύνθεση του γράφου αντιστοιχεί μια μεταβλητή ( τεχνητή φερομόνη) και ανάλογα πόσο καλύτερη είναι η λύση, τόσο περισσότερη είναι η τεχνητή φερομόνη. Στο τέλος που θα έχουμε όλες τις πιθανές λύσεις , θα δούμε την ποσότητα της τεχνητής φερομόνης ώστε να δούμε πια είναι η βέλτιστη.

Όμως υπάρχουν κάποια στοιχεία που δεν συναντούμε στα φυσικά μυρμήγκια , αλλά υπάρχουν στα συστήματα πολλαπλών πρακτόρων στα ψηφιακά μυρμήγκια . Αυτά είναι η μνήμη, οι περισσότεροι αισθητήρες, ο διακριτός χώρος και χρόνος, η εναπόθεση φερομόνης σε διαφορετικές χρονικές στιγμές,(αφού τα ψηφιακά μυρμήγκια αφήνουν τη φερομόνη όταν ολοκληρώσουν τις κινήσεις τους , σε αντίθεση με τα φυσικά που την αφήνουν συνέχεια) και τέλος χρησιμοποιούνται αλγόριθμοι για τη βελτίωση της απόδοσης του συστήματος.

Κύριες Μορφές Αλγορίθμου[Επεξεργασία | επεξεργασία κώδικα]

Αρκετοί αλγόριθμοι βασισμένοι στη λειτουργία των αποικιών μυρμηγκιών έχουν προταθεί στη βιβλιογραφία. Παρακάτω, εκτός των άλλων, αναφέρονται ο πρωτότυπος Ant System, και οι δύο πλέον επιτυχημένες παραλλαγές του, MAX-MIN Ant System και Ant Colony System.

  • Ant System (AS). Είναι ο πρώτος ACO αλγόριθμος που προτάθηκε στη βιβλιογραφία[1]. Το κύριο χαρακτηριστικό του είναι ότι, σε κάθε επανάληψη, οι ποσότητες φερορμόνης ενημερώνονται από όλα τα μυρμήγκια που έχουν καταφέρει, στην επανάληψη αυτή, να κατασκευάσουν μία λύση.
  • MAX-MIN Ant System (MMAS). Ο αλγόριθμος[2] αυτός είναι μια βελτίωση του αρχικού Ant System. Χαρακτηριστικά στοιχεία του είναι ότι μόνο το "καλύτερο" μυρμήγκι ενημερώνει τα μονοπάτια φερομόνης και ότι η ποσότητα της φερομόνης είναι περιορισμένη από άνω και κάτω όρια. Τα όρια αυτά συνήθως καθορίζονται εμπειρικά και αφορούν το συγκεκριμένο προς επίλυση πρόβλημα.
  • Ant Colony System (ACS). Η πιο ενδιαφέρουσα συμβολή του ACS[3] είναι η εισαγωγή της τοπικής ενημέρωσης φερομόνης. Η ενημέρωση αυτή εκτελείται από όλα τα μυργμήγκια σε κάθε βήμα του αλγορίθμου. Το κάθε μυρμήγκι ενημερώνει μόνο την τελευταία ακμή που έχει ακολουθήσει. Ο κύριος στόχος, της τοπικής ενημέρωσης, είναι να διαφοροποιηθεί η αναζήτηση η οποία πραγματοποιείται από τα μυρμήγκια, που ακολουθούν, κατά τη διάρκεια μιας επανάληψης. Με τη μείωση της συγκέντρωσης φερομόνης τα επόμενα μυρμήγκια ενθαρρύνονται να επιλέξουν άλλες ακμές και, ως εκ τούτου, να παράγουν διαφορετικές λύσεις. Με τον τρόπο αυτό έχουμε πλουραλισμό λύσεων κατά τη διάρκεια μιας επανάληψης.
  • Elitist Ant System
  • Rank-based Ant System (ASrank). Όλες οι λύσεις κατατάσσονται ανάλογα με το μήκος τους. Η ποσότητα της φερομόνης που εκκρίνεται σταθμίζεται με βάση το μέγεθος της διαδρομής, έτσι ώστε λύσεις με μικρότερες διαδρομές να έχουν περισσότερη φερομόνη από τα αυτές με μεγαλύτερες διαδρομές.
  • Continuous Orthogonal Ant Colony (COAC). Ο μηχανισμός φερομόνης COAC επιτρέπει στα μυρμήγκια να αναζητήσoυν λύσεις συνεργατικά και αποτελεσματικά. Χρησιμοποιούν μια ορθογωνική μέθοδο σχεδίασης που καθιστά εφικτή την εξερεύνηση επιλεγμένων περιοχών του πεδίου ορισμού γρήγορα και αποτελεσματικά, με ενισχυμένη δυνατότητα αναζήτησης σε ολόκληρο το πεδίο ορισμού και ακρίβεια. Αυτή η ορθογωνική μέθοδος σχεδίασης μπορεί επίσης να επεκταθεί και σε άλλους αλγόριθμους βελτιστοποίησης.
  • Recursive Ant Colony Optimization. Πρόκειται για μια αναδρομική μορφή συστήματος που διαχωρίζει ολόκληρο το πεδίο ορισμού (τομέα) σε επιμέρους τμήματα όπου λύνει το πρόβλημα-στόχο του κάθε επιμέρους τμήματος. Τα αποτελέσματα από τα επιμέρους τμήματα συγκρίνονται και μερικά από τα καλύτερα αποτελέσματα προωθούνται στο επόμενο επίπεδο.Τα επιμέρους τμήματα που ανήκουν στα επιλεγμένα καλύτερα αποτελέσματα διαιρούνται και πάλι. Η διαδικασία αυτή επαναλαμβάνεται μέχρι να καταλήξουμε σε αποτέλεσμα της επιθυμητής ακρίβειας. Αυτή η μέθοδος έχει δοκιμαστεί σε κακές περιπτώσεις γεωφυσικών προβλημάτων και δουλεύει καλά.

Εφαρμογή αλγορίθμου[Επεξεργασία | επεξεργασία κώδικα]

Ο πρώτος αλγόριθμος ονομάζεται Ant System και έχει ως στόχο να λύσει το πρόβλημα του πλανόδιου πωλητή που αποσκοπεί στην εύρεση της βέλτιστης διαδρομής. Ο γενικός αλγόριθμος είναι απλός και μελετά ένα σύνολο από μυρμήγκια που κάνουν κυκλικές διαδρομές κατά μήκος των πόλεων. Το μυρμήγκι επιλέγει να πάει σε μια πόλη με βάση ορισμένους κανόνες:

  1. Θα πρέπει να επισκεφτεί κάθε πόλη μόνο μια φορά;
  2. Μια μακρινή πόλη έχει λιγότερες πιθανότητες να επιλεγεί;
  3. Αν η ποσότητα φερομόνης σε μια πόλη είναι έντονη τότε η πιθανότητα να επιλεγεί η πόλη είναι μεγαλύτερη;
  4. Με την ολοκλήρωση της διαδρομής η κατάθεση φερομόνης δείχνει αν η διαδρομή είναι σύντομη;

Έστω ότι έχουμε τις πιο πάνω διαδρομές ποια θα πρέπει να ακολουθήσω; Η απάντηση θα καθοριστεί από τα στοιχεία της λύσης του αλγορίθμου. Ο αλγόριθμος πληροφορείται στο τέλος της κάθε επανάληψης ποιες είναι οι συνδέσεις που κατασκευάζουν τα μυρμήγκια σε κάθε επανάληψη έτσι ώστε σε επόμενες να δοθεί κάποια προτίμηση από τον αλγόριθμο. Για κάθε σύνδεση (i,j) στο γράφημα συνδέεται με μια μεταβλητή τη φερομόνη. Η ποσότητα της φερομόνης είναι ανάλογη της χρησιμότητας της σύνδεσης. Όσο μεγαλύτερη η ποσότητα φερομόνης μιας υποψήφιας λύσης τόσο μεγαλύτερη είναι η πιθανότητα να επιλεγεί. Όταν ένα μυρμήγκι ανανεώνει την ποσότητα φερομόνης στις συνδέσεις μιας λύσης τότε έχει κατασκευαστεί η συγκεκριμένη λύση στο γράφημα. Άρα, γενικότερα για τη λύση στο πρόβλημα της εύρεσης του συντομότερου μονοπατιού προς την τροφή, ένα μυρμήγκι εξετάζει την ποσότητα φερομόνης που χαρακτηρίζει την κάθε σύνδεση και που θα επηρεάσει την απόφαση του.

Οι αλγόριθμοι βελτιστοποίησης αποικιών έχουν εφαρμοστεί σε πολλά προβλήματα συνδυαστικής βελτιστοποίησης, όπως η δρομολόγηση οχημάτων. Έχει επίσης χρησιμοποιηθεί για την παραγωγή βέλτιστων λύσεων στο πρόβλημα του πλανόδιου πωλητή. Έχουν ένα πλεονέκτημα σε σχέση με άλλους αλγορίθμους όσον αφορά την αναδιάταξη και την αλλαγή στο γράφημα: ο αλγόριθμος μπορεί να λειτουργεί συνεχώς και να προσαρμοστούν αλλαγές σε πραγματικό χρόνο. Αυτό είναι ενδιαφέρον όσον αφορά τη δρομολόγηση του δικτύου και συστήματα αστικών μεταφορών.

Παραπομπές[Επεξεργασία | επεξεργασία κώδικα]

  1. M. Dorigo, V. Maniezzo, and A. Colorni, “Positive feedback as a search strategy,” Dipartimento di Elettronica, Politecnico di Milano, Italy, Tech. Rep. 91-016, 1991.
  2. T. Stutzle and H.H. Hoos, “MAX–MIN Ant System,” Future Generation Computer Systems, vol. 16, no. 8, pp. 889–914, 2000.
  3. M. Dorigo and L.M. Gambardella, “Ant Colony System: A cooperative learning approach to the traveling salesman problem,” IEEE Transactions on Evolutionary Computation, vol. 1, no. 1, pp. 53–66, 1997.

Βιβλιογραφία[Επεξεργασία | επεξεργασία κώδικα]