Αποκωδικοποίηση των Αξιοσημείωτων Αλγορίθμων των Μυρμηγκιών

Τα μυρμήγκια είναι ικανά να κάνουν αξιοσημείωτα επιτεύγματα συντονισμού. Μπορούν να χαράξουν περίπλοκα μονοπάτια μέσα στη ζούγκλα, να χτίσουν εξελιγμένες δομές και να προσαρμόσουν μοτίβα αναζήτησης τροφής για να ταιριάζουν στο περιβάλλον τους, όλα αυτά χωρίς παραγγελίες από μια κεντρική πηγή. Η Deborah Gordon, βιολόγος στο Πανεπιστήμιο του Στάνφορντ, ελπίζει να αποκαλύψει τους απλούς κανόνες που παράγουν περίπλοκα μοτίβα από απλές μεμονωμένες ενέργειες.

Ιδιαίτερα τα μυρμήγκια υπερέχουν στη συλλογική αναζήτηση, προσαρμόζοντας αυτόματα τη στρατηγική αναζήτησής τους για να καλύπτουν αποτελεσματικά μεγάλες περιοχές του εδάφους. Ο Γκόρντον έχει βρει παραλληλισμούς μεταξύ των αλγορίθμων που χρησιμοποιούν οι αποικίες μυρμηγκιών για αναζήτηση τροφής και των ανθρωπογενών αλγορίθμων που αποτελούν τη βάση του Διαδικτύου. Δεδομένου του χρόνου που τα μυρμήγκια λύνουν αυτού του είδους τα προβλήματα, η Gordon ελπίζει ότι θα ανακαλύψει νέους αλγόριθμους που τελικά θα κάνουν τα υπολογιστικά δίκτυα μεγάλης κλίμακας φθηνότερα και πιο αποτελεσματικά.

Quanta συναντήθηκε με τον Γκόρντον σε ένα συνέδριο κοινωνικών εντόμων στο Cold Spring Harbor της Νέας Υόρκης, λίγο πριν φύγει για ένα ταξίδι στο Μεξικό για να μελετήσει αλγόριθμους δρομολόγησης σε δενδρόβια μυρμήγκια. Ακολουθεί μια επεξεργασμένη και συνοπτική έκδοση της συνομιλίας.

QUANTA MAGAZINE:Πώς ξεκίνησες να ενδιαφέρεσαι για τα μυρμήγκια;

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

Μελετάτε τις ίδιες αποικίες μυρμηγκιών στην Αριζόνα για 30 χρόνια. Αυτή ήταν η πρόθεσή σας από την αρχή;

Όχι. Όταν ξεκίνησα για πρώτη φορά, με ενδιέφερε η ποικιλία μεταξύ των αποικιών, έτσι σημείωσα τις αποικίες για να ξέρω πότε κοίταζα την ίδια την επόμενη χρονιά. Παρατήρησα ότι μερικές αποικίες γίνονταν μεγαλύτερες από χρόνο σε χρόνο, έτσι έμαθα πώς μεγαλώνει μια αποικία. Σε εκείνο το σημείο, κανείς δεν ήξερε πόσο καιρό θα μπορούσε να ζήσει μια αποικία μυρμηγκιών θεριστών. Γύριζα για να ελέγξω τις αποικίες κάθε χρόνο — πέρασαν πέντε χρόνια και μετά δέκα. Τότε δεν είχα άλλη επιλογή από το να συνεχίσω.

Τι σας έχει εντυπωσιάσει περισσότερο στα μυρμήγκια;

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

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

Για τα μυρμήγκια θεριστών, μάθαμε ότι ένα μυρμήγκι αποφασίζει αν θα βγει από τη φωλιά και θα βρει τροφή χρησιμοποιώντας τον ρυθμό με τον οποίο συναντά τα μυρμήγκια που έρχονται με τροφή. Είναι μια μορφή θετικής ανατροφοδότησης. Όσο πιο γρήγορα τα μυρμήγκια έρχονται με φαγητό, τόσο περισσότερα μυρμήγκια βγαίνουν έξω. Κάθε μυρμήγκι αποφασίζει μόνο όταν ο ρυθμός αλληλεπίδρασής του είναι αρκετά υψηλός για να σβήσει. Συνολικά, αυτό το σύστημα επιτρέπει στην αποικία να ρυθμίζει τη δραστηριότητα αναζήτησης τροφής, έτσι ώστε τα μυρμήγκια να μην βγαίνουν εκτός αν υπάρχει αρκετή τροφή για να το κάνει να αξίζει τον κόπο.

Ονομάσατε τον αλγόριθμο μυρμηγκιών συγκομιδής "anternet". Γιατί;

Συνεργάστηκα με τον Balaji Prabhakar, έναν συνάδελφο στο Stanford, για να καταλάβω τον αλγόριθμο που χρησιμοποιούν τα μυρμήγκια θεριστών για να ρυθμίσουν την αναζήτηση τροφής. Επισήμανε ότι ο αλγόριθμος είναι παρόμοιος με το Πρωτόκολλο Ελέγχου Μετάδοσης, το οποίο ρυθμίζει την κυκλοφορία δεδομένων στο Διαδίκτυο για να διασφαλίσει ότι τα δεδομένα δεν σβήνουν εκτός εάν υπάρχει αρκετό εύρος ζώνης. Και τα δύο συστήματα χρησιμοποιούν απλή, τοπική ανατροφοδότηση για τη ρύθμιση της δραστηριότητας. Νομίζω ότι ίσως μπορέσουμε να βρούμε άλλους αλγόριθμους που χρησιμοποιούν τα μυρμήγκια για την επίλυση προβλημάτων μηχανικής που δεν έχουμε σκεφτεί ακόμα. Με ενδιαφέρει η ιδέα ότι η εξέλιξη μπορεί να παράγει διαφορετικούς αλγόριθμους σε διαφορετικά συστήματα για την επίλυση των ίδιων προβλημάτων.

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

Από την προοπτική της εξέλιξης, η αποικία είναι πραγματικά το άτομο, γιατί είναι η αποικία που αναπαράγεται. Τα μυρμήγκια δεν κάνουν περισσότερα μυρμήγκια, οι αποικίες κάνουν περισσότερες αποικίες. Επομένως, αν σκεφτούμε πώς εξελίσσεται η συμπεριφορά των μυρμηγκιών, πρέπει να δούμε τις αποικίες.

Πώς οι αποφάσεις που λαμβάνονται από μεμονωμένα μυρμήγκια αλλάζουν τη συμπεριφορά της αποικίας στο σύνολό της;

Στην έρημο, το νερό είναι ένας σημαντικός περιορισμός. Τα μυρμήγκια χάνουν νερό μόνο που βρίσκονται έξω και τριγυρίζουν. Αλλά παίρνουν το νερό τους από τους σπόρους που τρώνε, επομένως πρέπει να ξοδεύουν νερό για να πάρουν νερό. Κανένα μεμονωμένο μυρμήγκι δεν παίρνει την απόφαση να εξοικονομήσει νερό και να μείνει σπίτι. Αλλά μικρές διαφορές στον τρόπο με τον οποίο τα μυρμήγκια αντιδρούν στις αλληλεπιδράσεις μπορεί να προσθέσουν μεγάλες διαφορές στον τρόπο με τον οποίο οι αποικίες αναζητούν τροφή, κάτι που με τη σειρά του επηρεάζει τον αριθμό των αποικιών που έχουν απογόνους. Βρήκαμε ότι η φυσική επιλογή ευνοεί τις αποικίες που εξοικονομούν νερό. Το ονομάζω «τα ανταμοιβές της αυτοσυγκράτησης». Νομίζω ότι αυτή είναι η πρώτη μελέτη που μπόρεσε να παρακολουθήσει την εξέλιξη της συλλογικής συμπεριφοράς σε έναν φυσικό πληθυσμό ζώων. Μια απλή, τοπική συμπεριφορά — πώς αντιδρούν τα μυρμήγκια όταν το ένα συναντά το άλλο — επιλέγεται λόγω του αποτελέσματος για ολόκληρη την αποικία.

Έχει δημιουργήσει άλλους αλγόριθμους η εξέλιξη;

Συνεργάζομαι με έναν άλλο επιστήμονα υπολογιστών για τα δίκτυα δρομολόγησης που χρησιμοποιούν τα μυρμήγκια. Τα είδη των δενδρωδών μυρμηγκιών στο Μεξικό ακολουθούν πολύ περίπλοκα μονοπάτια μέσα από το κουβάρι των δέντρων και των αμπελιών και άλλης βλάστησης που συνδέει φωλιές και πηγές τροφής. Τα μονοπάτια σπάνε συνέχεια, για παράδειγμα όταν ένα κλαδάκι κουμπώνει ή ένα ζώο διασχίζει το μονοπάτι. Αλλά ο αυτοκινητόδρομος επισκευάζεται εύκολα. Πώς βρίσκουν μια νέα διαδρομή τόσο γρήγορα — στην κλίμακα των λεπτών — όταν υπάρχουν τόσες πολλές διαφορετικές επιλογές; Πιστεύουμε ότι χρησιμοποιούν μια στρατηγική που δεν ακολουθεί τη συντομότερη διαδρομή, αλλά αποκαθιστά τη διαδρομή πολύ γρήγορα και διατηρεί τη ροή σε εξέλιξη. Κατά κάποιο τρόπο έχουν θυσιάσει αυτό που πιστεύουμε ως αποτελεσματικότητα για την ανθεκτικότητα. Πιστεύουμε ότι έχουμε ένα μοντέλο που έχει νόημα και το δοκιμάζουμε στην επιτόπια εργασία.

Πώς μπορεί να είναι σημαντικό αυτό στους υπολογιστές;

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

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

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

Πώς αλλάζουν οι αποικίες μυρμηγκιών με την πάροδο του χρόνου;

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

Είμαστε περιτριγυρισμένοι από γιγάντια δίκτυα - το Διαδίκτυο, οι εγκέφαλοί μας - και αυτό με έκανε να ενδιαφερθώ για άλλα συστήματα. Πώς κλιμακώνεται η συμπεριφορά ενός δικτύου καθώς μεγαλώνει;

Πώς γίνεται η κλίμακα;

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

Εξερευνάτε επίσης πώς τα μυρμήγκια μοιάζουν με τους νευρώνες.

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

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

Μόνο 50 από τα περίπου 14.000 είδη μυρμηγκιών έχουν ποτέ μελετηθεί. Είναι πιθανό ότι εάν μελετήσουμε νέα είδη, θα αποκαλύψουμε νέους αλγόριθμους. Δημιουργήσαμε ένα μικρό κιτ για να δουν οι μαθητές πώς διαφορετικά είδη μυρμηγκιών κάνουν συλλογική αναζήτηση. Εάν τα παιδιά το δοκιμάσουν με διαφορετικά είδη, πιθανότατα θα κάνουν ανακαλύψεις για είδη που κανείς δεν έχει δει ποτέ.