Βελτιστοποίηση με πολλαπλά κριτήρια
αγγλικά : Swarm intelligence
γαλλικά :
γερμανικά :
Η νοημοσύνη σμήνους (swarm intelligence) είναι η συλλογική συμπεριφορά μη κατανεμημένων, αυτοοργανωμένων φυσικών ή τεχνητών συστημάτων. Η ιδέα εφαρμόζεται στον τομέα της τεχνητής νοημοσύνης. Ο όρος εισήχθη από τους Gerardo Beni και Jing Wang το 1989.[1] Η νοημοσύνη σμήνους είναι μια ιδιότητα συστημάτων που επιδεικνύουν συλλογικά ευφύη συμπεριφορά. Ένα σύστημα αντιπροσωπεύει μια οντότητα που ανιχνεύει το περιβάλλον προκειμένου να εκτελέσει μαι ενέργεια που έχει επιλέξει. Η κάθε οντότητα λειτουργεί αυτόνομα και προκύπτει μια συνολική συλλογική συμπεριφορά. Δεν παίρνουν οδηγίες από κανέναν, παίρνουν αποφάσεις και μέσα από απλούς κανόνες εμφανίζονται φαινόμενα (σμήνη πουλιών, κοπάδια ψαριών, άναμμα πυγολαμπίδων, τα μυρμήγκια υπολογίζουν βέλτιστες διαδρομές προς την τροφή τους, μέλισσες να ενημερώνουν τη κυψέλη για νέκταρ) τα οποία οδηγούνται μέσα από τη συλλογική συμπεριφορά και ευφυΐα.
Τα συστήματα νοημοσύνης σμήνους κατά κανόνα αποτελούνται από έναν πληθυσμό απλών, αυτόνομων πρακτόρων[2] ή διαμεσολαβητών (boids) που αλληλεπιδρούν μεταξύ τους και με το περιβάλλον τους σε τοπικό επίπεδο. Τα συστήματα είναι εμπνευσμένα από τη φύση και ειδικότερα από τα βιολογικά συστήματα. Οι πράκτορες ακολουθούν πολύ απλούς κανόνες, και παρόλο που δεν υπάρχει καμία συγκεντρωτική δομή ελέγχου να υπαγορεύει πως πρέπει να συμπεριφέρονται οι πράκτορες, τοπικές - και έως ένα βαθμό τυχαίες - αλληλεπιδράσεις μεταξύ τέτοιων πρακτόρων οδηγούν στην εμφάνιση μιας ευφυούς, καθολικής συμπεριφοράς, άγνωστης στους αυτόνομους πράκτορες. Φυσικά παραδείγματα της νοημοσύνης σμήνους περιλαμβάνουν τις αποικίες μυρμηγκιών, τα σμήνη πουλιών, τη βακτηριδιακή ανάπτυξη, τις αγέλες ή τα κοπάδια ζώων και τα κοπάδια ψαριών.
Η εφαρμογή των αρχών του σμήνους στα ρομπότ ονομάζεται ρομποτική σμήνους[3], ενώ ο όρος "νοημοσύνη σμήνους" αναφέρεται στο σύνολο των αλγορίθμων. Η πρόβλεψη σμήνους έχει χρησιμοποιηθεί στο πλαίσιο των προβλημάτων πρόγνωσης.
Ένα παράδειγμα νοημοσύνης σμήνους είναι σμήνη πουλιών κινούνται σαν ένα σώμα παρά του ότι αποτελούνται από πολλές ανεξάρτητες οντότητες. Αν παρατηρήσει κανείς τα πουλιά θα προσέξει ότι κινούνται σαν μια ομάδα με ένα κοινό προσανατολισμό. Αυτό το σύνολο που προκύπτει είναι μέσα από τη συνολική συμπεριφορά των πουλιών. Ένα πουλί βλέπει γύρω το περιβάλλον του και αναλόγως συνυπολογίζει σε σχέση με τα άλλα πουλιά για να πάρει τις δικές του αποφάσεις. Ο νόμος του Couzin[4] αναφέρει τρεις αρχές: αν ένα πουλί βρίσκεται μακριά από τα άλλα τότε καταλαβαίνει ότι πρέπει να αναπτύξει ταχύτητα αν όμως πλησιάζει πολύ σε ένα άλλο τότε καταλαβαίνει ότι θα συγκρουστεί και μειώνει την ταχύτητα του, να υπάρχει δηλαδή στο σμήνος μια συνοχή, αν βρει εμπόδιο το αποφεύγει, διαχωρίζεται από το σύνολο και ξανασμίγουν και τρίτο πρέπει να έχουν μια κοινή κατεύθυνση να ακολουθούν μια συγκεκριμένη πορεία. Αρχή της συλλογικής συμπεριφοράς είναι ότι τα πουλιά πάντα προσπαθούν να διατηρήσουν μια ελάχιστη απόσταση μεταξύ των ιδιών αλλά και των άλλων. Αυτός ο κανόνας έχει υψηλή προτεραιότητα και αντιστοιχεί στη συμπεριφορά των ζώων στη φύση.
Παραδείγματα Αλγορίθμων
Βελτιστοποίηση σμήνους σωματιδίων
Βελτιστοποίηση αποικίας μυρμηγκιών
Αλγόριθμος τεχνητής αποικίας μελισσών
Διαφορική εξέλιξη
Αλγόριθμος μελισσών
Τεχνητό ανοσοποιητικό σύστημα
Αλγόριθμος νυχτερίδων
Βελτιστοποίηση σμήνους πυγολαμπίδων
Βαρυτικός αλγόριθμος αναζήτησης
Αυτοκινούμενα σωματίδια
Στοχαστική αναζήτηση διάχυσης
Εφαρμογές
Οι τεχνικές που βασίζονται στην νοημοσύνη σμήνους μπορούν να χρησιμοποιηθούν σε διάφορες εφαρμογές. Ο στρατός των ΗΠΑ ερευνά τεχνικές σμήνους για τον έλεγχο τηλεκατευθυνόμενων οχημάτων. Ο Ευρωπαϊκός Οργανισμός Διαστήματος μελετά ένα σμήνος σε τροχιά για την αυτοσυναρμολόγηση και τη συμβολομετρία. Η NASA ερευνά τη χρήση της τεχνολογίας σμήνους για χαρτογράφηση των πλανητών. Σε μια μελέτη του 1992 από τους Anthony M. Lewis και George A. Bekey συζητάται το ενδεχόμενο χρησιμοποίησης νοημοσύνης σμήνους για τον έλεγχο nanobots μέσα στο ανθρώπινο σώμα, με σκοπό τη θανάτωση καρκινικών όγκων.[5] Αντίθετα οι al-Rifaie και Aber έχουν χρησιμοποιήσει τον αλγόριθμο SDS (Stochastic Diffusion Search) για να βοηθήσουν στον εντοπισμό όγκων.[6][7] Η νοημοσύνη σμήνους έχει επίσης εφαρμογές στην εξόρυξη δεδομένων.[8]
Δρομολόγηση με βάση τα μυρμήγκια
Η χρήση της νοημοσύνης σμήνους έχει επίσης διαπιστωθεί σε δίκτυα τηλεπικοινωνιών, με τη μορφή της δρομολόγησης των μυρμηγκιών. Οι πρώτοι που παρατήρησαν το θέμα αυτό ήταν οι Dorigo κ.ά και ο Hewlett Packard στα μέσα της δεκαετίας του 1990, με διάφορες παραλλαγές να εμφανίζονται από τότε. Βασικά χρησιμοποιείται ένας στοχαστικός πίνακας δρομολόγησης, επιβραβεύοντας/ενισχύοντας τη διαδρομή που διασχίζεται επιτυχώς από κάθε "μυρμήγκι" (μικρό πακέτο ελέγχου) που κατακλύζει το δίκτυο. Η ενίσχυση της διαδρομής προς τα εμπρός, η αντίστροφη κατεύθυνση αλλά και τα δύο αυτά γεγονότα ταυτόχρονα έχουν διερευνηθεί: η αντίστροφη ενίσχυση απαιτεί ένα συμμετρικό δίκτυο και ενώνει τις δύο κατευθύνσεις μαζί. Η ενίσχυση προς τα εμπρός επιβραβεύει μια διαδρομή πριν το αποτέλεσμα να είναι γνωστό. Δεδομένου ότι το σύστημα συμπεριφέρεται στοχαστικά και ως εκ τούτου στερείται επαναληψιμότητα, υπάρχουν μεγάλα εμπόδια για εμπορική ανάπτυξη. Τα μέσα μαζικής ενημέρωσης για κινητά και οι νέες τεχνολογίες έχουν τη δυνατότητα να αλλάξουν τα όρια για συλλογική δράση εξαιτίας της νοημοσύνης σμήνους (Rheingold:2002, P175).
Η χωροθέτηση των υποδομών μεταφοράς για τα ασύρματα δίκτυα επικοινωνίας είναι ένα σημαντικό πρόβλημα της μηχανικής που περιέχει ανταγωνιστικούς στόχους. Μια ελάχιστη επιλογή τοποθεσιών απαιτούνται για την επαρκή κάλυψη περιοχής για τους χρήστες. Ένας πολύ διαφορετικός αλγόριθμος της νοημοσύνης σμήνους εμπνευσμένος από τα μυρμήγκια, ο (SDS-Stochastic Diffusion Search), έχει χρησιμοποιηθεί με επιτυχία για να παρέχει ένα γενικό μοντέλο για το πρόβλημα αυτό. Έχει αποδειχθεί ότι ο αλγόριθμος SDS μπορεί να εφαρμοστεί για τον προσδιορισμό κατάλληλων λύσεων ακόμα και σε περιπτώσεις δύσκολων προβλημάτων.[9]
Ορισμένες αεροπορικές εταιρείες έχουν χρησιμοποιήσει επίσης δρομολόγηση βασισμένη σε μυρμήγκια στην ανάθεση αφίξεων αεροσκαφών στις πύλες του αεροδρομίου. Στις αερογραμμές "Southwest Airlines" ένα πρόγραμμα λογισμικού χρησιμοποιεί την νοημοσύνη σμήνους, βασιζόμενο στην ιδέα ότι μια αποικία μυρμηγκιών λειτουργεί καλύτερα από ένα και μόνο μυρμήγκι. Κάθε πιλότος λειτουργεί ως ένα μυρμήγκι που ψάχνει για την καλύτερη πύλη του αεροδρομίου. "Ο πιλότος μαθαίνει από την εμπειρία του τι είναι το καλύτερο γι' αυτόν, και αποδεικνύεται ότι αυτή είναι και η καλύτερη λύση για την αεροπορική εταιρεία" εξηγεί ο Douglas A. Lawson. Ως αποτέλεσμα, η «αποικία» των πιλότων πάντα κατευθύνεται σε πύλες που μπορούν να φτάσουν και να αναχωρήσουν γρήγορα. Το πρόγραμμα μπορεί ακόμα να προειδοποιήσει έναν πιλότο για εναλλακτικές επιλογές πυλών. "Μπορούμε να προβλέψουμε τι πρόκειται να συμβεί, οπότε έχουμε στη διάθεσή μας μια επιπλέον πύλη," εξηγεί ο Lawson.[10]
Προσομοίωση πλήθους
Οι καλλιτέχνες χρησιμοποιούν την τεχνολογία της νοημοσύνης σμήνους ως μέσο για τη δημιουργία πολύπλοκων διαδραστικών συστημάτων ή για την προσομοίωση πλήθους.
Η ταινία "Stanley and Stella in: Breaking the Ice" ήταν η πρώτη που κάνει χρήση της τεχνολογίας νοημοσύνης σμήνους για την απόδοση και την ρεαλιστική απεικόνιση των κινήσεων κοπαδιών ψαριών και σμηνών πτηνών με τη χρήση του συστήματος Boids. Επίσης η ταινία του Τιμ Μπάρτον "Batman Returns" έκανε χρήση της τεχνολογίας νοημοσύνης σμήνους για να δείξει τις κινήσεις της ομάδας νυχτερίδων. H τριλογία ταινιών "Άρχοντας των Δαχτυλιδιών" έκανε χρήση παρόμοιας τεχνολογίας, γνωστής ως MASSIVE, κατά τη διάρκεια σκηνών μάχης. Η τεχνολογία νοημοσύνης σμήνους είναι ιδιαίτερα ελκυστική επειδή είναι φθηνή, εύρωστη και απλή.
Αεροπορικές εταιρείες έχουν χρησιμοποιήσει την ίδια τεχνολογία για την προσομοίωση επιβατών κατά την επιβίβαση τους σε αεροπλάνο. Ο ερευνητής A. Douglas Lawson της εταιρίας Southwest Airlines κατάφερε να αναπτύξει μια προσομοίωση σε υπολογιστή που χρησιμοποιεί μόνο έξι κανόνες για τον υπολογισμό του χρόνου επιβίβασης, χρησιμοποιώντας διάφορες μεθόδους επιβίβασης.[11]
Κοινωνικά σμήνη
Με τη χρήση κατάλληλου λογισμικού, όπως για παράδειγμα την πλατφόρμα συλλογικής ευφυίας UNUM, δίκτυα κατανεμημένων χρηστών είναι δυνατόν να οργανωθούν σε «ανθρώπινα σμήνη» (αναφέρεται επίσης ως «κοινωνικά σμήνη»), υλοποιώντας συστήματα ελέγχου κλειστού βρόχου σε πραγματικό χρόνο. Όπως δημοσιεύθηκε από τον Rosenberg (2015), αυτά τα συστήματα ελέγχου πραγματικού χρόνου επιτρέπουν σε ομάδες συμμετέχοντων να συμπεριφέρονται ως μια ενιαία συλλογική νοημοσύνη.[12] Για παράδειγμα αφού συνδεθούν στην πλατφόρμα UNUM, ομάδες χρήστες μπορούν να απαντήσουν συλλογικά σε ερωτήσεις, να δημιουργήσουν ιδέες και να κάνουν προβλέψεις.[13] Προηγούμενα πειράματα δείχνουν ότι τα κοινωνικά σμήνη μπορούν να προβλέψουν καλύτερα από μεμονομένα άτομα διάφορες πτυχές του πραγματικού κόσμου.[14]
Τέχνη
Σε μελέτη των al-Rifaie κ.ά [15] έχουν χρησιμοποιηθεί επιτυχώς δύο αλγόριθμοι νοημοσύνης σμήνους - ο ένας μιμείται τη συμπεριφορά ενός είδους μυρμηγκιών (Leptothorax acervorum) κατά την αναζήτηση τροφής ( SDS) και ο άλλος μιμείται τη συμπεριφορά ενός σμήνους πουλιών (βελτιστοποίηση σμήνους σωματιδίων, PSO) - για να περιγράψουν μια νέα στρατηγική που αξιοποιεί τις ιδιότητες τοπικής αναζήτησης του αλγορίθμου PSO με τη γενική συμπεριφορά του αλγορίθμου SDS. Ο προκύπτον υβριδικός αλγόριθμος χρησιμοποιείται στο σχεδιασμό νέων σχεδίων από μια εικόνα εισόδου, αξιοποιώντας μια καλλιτεχνική τάση μεταξύ της τοπικής συμπεριφοράς του σμήνους πουλιών - στην προσπάθειά τους να ακολουθήσουν το σκίτσο εισόδου - και της καθολικής συμπεριφοράς των μυρμηγκιών κατά την αναζήτηση τροφής - στην προσπάθειά τους να ενθαρρύνει το σμήνος να εξερευνήσει νέες περιοχές του καμβά. Η «δημιουργικότητα» αυτού του υβριδικού συστήματος σμήνους έχει αναλυθεί σύμφωνα με την φιλοσοφική τάση "ρίζωμα" στην αλληγορία του Deleuze "Orchid and Wasp".[16]
Σε μια πιο πρόσφατη δουλειά των al-Rifaie κ.ά , "Swarmic Sketches and Attention Mechanism"[17], εισάγεται μια νέα προσέγγιση αναπτύσσοντας τον μηχανισμό της «προσοχής», προσασμόζοντας τον αλγόριθμο SDS σε επιλεγμένες λεπτομερείς περιοχές ενός ψηφιακού καμβά. Μόλις η προσοχή του σμήνους εφιστάται σε μια συγκεκριμένη γραμμή εντός του καμβά, η δυνατότητα του αλγορίθμου SPO χρησιμοποιείται για την παραγωγή ενός «σκίτσου σμήνους» της συγκεκριμένης γραμμής. Το σμήνος κινείται σε όλο το ψηφιακό καμβά σε μια προσπάθεια να αξιοποιήσει τον δυναμικό του ρόλο, όπου δίνεται προσοχή στις περιοχές με τις περισσότερες λεπτομέρειες. Έχοντας συσχετίσει τη διαδικασία του rendering με τις έννοιες της προσοχής, η απόδοση των συμμετεχόντων σμηνών, δημιουργεί ένα μοναδικό σκίτσο κάθε φορά που τα "καλλιτεχνικά σμήνη" ξεκινούν την ερμηνεία των γραμμών εισόδου του σχεδίου. Με άλλα λόγια, ενώ ο αλγόριθμος PSO είναι υπεύθυνος για τη διαδικασία της σχεδίασης. ο αλγόριθμος SDS ελέγχει την "προσοχή" του σμήνους.
Σε ένα παρόμοιο έργο, "Swarmic Paintings and Colour Attention" [18], μη-φωτορεαλιστικές εικόνες παράγονται χρησιμοποιώντας τον αλγόριθμο SDS , ο οποίος στην περίπτωση αυτή, είναι υπεύθυνος για τον έλεγχο του χρώματος.
Η «υπολογιστική δημιουργικότητα» των ανωτέρω αναφερθέντων συστημάτων εξετάζεται στα [15][19][20][21], μέσα από τις δύο προϋποθέσεις της δημιουργικότητας (δηλαδή την ελευθερία και τους περιορισμούς), χρησιμοποιώντας τις δύο γνωστές φάσεις της νοημοσύνης σμήνους, την εξερεύνηση και την εκμετάλλευση.
Δείτε επίσης
Τεχνητή νοημοσύνη
Παραπομπές
Beni, G., Wang, J. Swarm Intelligence in Cellular Robotic Systems, Proceed. NATO Advanced Workshop on Robots and Biological Systems, Tuscany, Italy, June 26–30 (1989)
«Wikipedia Autonomous agent».
«Wikipedia Swarm Robotics».
«Princeton Iain Couzin».
Lewis, M. A., and G. A. Bekey. (1992). «The Behavioral Self-Organization of Nanoagents Using Local Rules.». Proceedings of the 1992 IEEE/RSJ International Conference on Intelligent Agents and Systems.
al-Rifaie, M.M.; Aber, A. (2012). «Identifying metastasis in bone scans with Stochastic Diffusion Search». Proc. IEEE Information Technology in Medicine and Education, ITME 2012: 519–523..
al-Rifaie, Mohammad Majid, Ahmed Aber, and Ahmed Majid Oudah. "Utilising Stochastic Diffusion Search to identify metastasis in bone scans and microcalcifications on mammographs." In Bioinformatics and Biomedicine Workshops (BIBMW), 2012 IEEE International Conference on, pp. 280-287. IEEE, 2012.
Martens, D.; Baesens, B.; Fawcett, T. (2011). «Editorial Survey: Swarm Intelligence for Data Mining». Machine Learning 82 (1): 1–42.. doi:10.1007/s10994-010-5216-5.
Hurley, Steve, and Roger M. Whitaker. "An agent based approach to site selection for wireless networks." Proceedings of the 2002 ACM symposium on Applied computing. ACM, 2002.
"Planes, Trains and Ant Hills: Computer scientists simulate activity of ants to reduce airline delays". Science Daily. April 1, 2008. Retrieved December 1, 2010.
Miller, Peter (2011). The Smart Swarm: How to Work Efficiently, Communicate Effectively, and Make Better Decisions Using the Secrets of Flocks, Schools, and Colonies. Avery Trade. σελ. 304. ISBN 978-1-58333-428-7. line feed character in |title= at position 17 (βοήθεια)
«Human Swarms, a real - time paradigm for Collective I ntelligence» (PDF). line feed character in |title= at position 6 (βοήθεια)
«Swarms of Humans Power A.I. Platform : DNews». DNews. Ανακτήθηκε στις 28 Σεπτεμβρίου 2015.
http://unanimousai.com/swarms-are-smart-its-kinda-scary/
al-Rifaie, MM; Bishop, J.M.; Caines, S. (2012). "Creativity and Autonomy in Swarm Intelligence Systems". Cognitive Computing 4 (3): 320–331. doi:10.1007/s12559-012-9130-y
Deleuze G, Guattari F, Massumi B. A thousand plateaus. Minneapolis: University of Minnesota Press; 2004
al-Rifaie, Mohammad Majid, and John Mark Bishop. "Swarmic sketches and attention mechanism". Evolutionary and Biologically Inspired Music, Sound, Art and Design. Springer Berlin Heidelberg, 2013. 85-96
al-Rifaie, Mohammad Majid, and John Mark Bishop. "Swarmic paintings and colour attention". Evolutionary and Biologically Inspired Music, Sound, Art and Design. Springer Berlin Heidelberg, 2013. 97-108
al-Rifaie, Mohammad Majid, Mark JM Bishop, and Ahmed Aber. "Creative or Not? Birds and Ants Draw with Muscle." Proceedings of AISB'11 Computing and Philosophy (2011): 23-30
al-Rifaie, Mohammad Majid, Ahmed Aber and John Mark Bishop. "Cooperation of Nature and Physiologically Inspired Mechanisms in Visualisation." Biologically-Inspired Computing for the Arts: Scientific Data through Graphics. IGI Global, 2012. 31-58. Web. 22 Aug. 2013. doi:10.4018/978-1-4666-0942-6.ch003
al-Rifaie MM, Bishop M (2013) Swarm intelligence and weak artificial creativity. In: The Association for the Advancement of Artificial Intelligence (AAAI) 2013: Spring Symposium, Stanford University, Palo Alto, California, U.S.A., pp 14–19
Σχετική βιβλιογραφία
Swarm Intelligence: From Natural to Artificial Systems by Eric Bonabeau, Marco Dorigo and Guy Theraulaz. (1999) ISBN 0-19-513159-2, complete bibliography
Turtles, Termites, and Traffic Jams: Explorations in Massively Parallel Microworlds by Mitchel Resnick. ISBN 0-262-18162-2
Swarm Intelligence by James Kennedy and Russell C. Eberhart. ISBN 1-55860-595-9
Fundamentals of Computational Swarm Intelligence by Andries Engelbrecht. Wiley & Sons. ISBN 0-470-09191-6
Nanocomputers and Swarm Intelligence by Jean-Baptiste Waldner, ISTE, ISBN 9781847040022, 2007.
Miller, Peter (July 2007), «Swarm Theory», National Geographic Magazine, ανακτήθηκε στις 2011-05-23
Swarms and Swarm Intelligence by Michael G. Hinchey, Roy Sterritt, and Chris Rouff, Article at IEEE Computer Society
- "From Ants to People: an Instinct to Swarm" - NY Times, 11-13-07
Swarm Intelligence (Journal) Chief Editor: Marco Dorigo. Springer New York. ISSN 1935-3812 (Print) 1935-3820 (Online) [1]
Eva Horn, Lucas Marco Gisi (Ed.): Schwärme – Kollektive ohne Zentrum. Eine Wissensgeschichte zwischen Leben und Information, Bielefeld: transcript 2009. ISBN 978-3-8376-1133-5
L. Fisher, The Perfect Swarm : The Science of Complexity in Everyday Life, Basic Books, 2009.
Couzin (2009), Collective Cognition in Animals
Hellenica World - Scientific Library
Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License
