Γενετικοί Αλγόριθμοι

Τι είναι αυτό;

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

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

Προγραμματισμός σε υπολογιστή

Ο ψευδοκώδικας είναι:

1. Αρχικοποίηση: Πολύ συχνά αυτές θα έχουν τυχαίες τιμές.
2. Αξιολόγηση: Η βαθμολογία θα είναι ένας αριθμός που δείχνει πόσο καλά η λύση αυτή λύνει το πρόβλημα.
3. Τα ακόλουθα βήματα εκτελούνται μέχρι να εκπληρωθεί η απαίτηση για διακοπή:
1. Επιλογή: Επιλογή των λύσεων/ατόμων για την επόμενη επανάληψη
2. Ανασυνδυασμός: Συνδυάστε τις λύσεις που επιλέχθηκαν
3. Μετάλλαξη: Αλλαγή τυχαία των νεοδημιουργηθέντων λύσεων
4. Αξιολόγηση: Εφαρμόστε τη συνάρτηση καταλληλότητας, βλέπε βήμα 2.
5. Εάν δεν ικανοποιείται η απαίτηση για διακοπή, ξεκινήστε εκ νέου με το βήμα επιλογής.

Παράδειγμα

Η παραπάνω περιγραφή είναι αφηρημένη. Ένα συγκεκριμένο παράδειγμα βοηθάει.

Εφαρμογές

Σε γενικές γραμμές

Οι γενετικοί αλγόριθμοι είναι καλοί στην επίλυση προβλημάτων που περιλαμβάνουν χρονοπρογραμματισμό και προγραμματισμό. Έχουν επίσης εφαρμοστεί στη μηχανική. Χρησιμοποιούνται συχνά για την επίλυση προβλημάτων συνολικής βελτιστοποίησης.

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

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

Στο Εγχειρίδιο σχεδίασης αλγορίθμων, ο Skiena συμβουλεύει να μην χρησιμοποιούνται γενετικοί αλγόριθμοι για οποιαδήποτε εργασία: "Είναι αρκετά αφύσικο να μοντελοποιούμε εφαρμογές με όρους γενετικών τελεστών όπως η μετάλλαξη και η διασταύρωση σε συμβολοσειρές bit. Η ψευδοβιολογία προσθέτει άλλο ένα επίπεδο πολυπλοκότητας ανάμεσα σε εσάς και το πρόβλημά σας. Δεύτερον, οι γενετικοί αλγόριθμοι χρειάζονται πολύ μεγάλο χρονικό διάστημα σε μη τετριμμένα προβλήματα. [...] Η αναλογία με την εξέλιξη -όπου η σημαντική πρόοδος απαιτεί [sic] εκατομμύρια χρόνια- μπορεί να είναι αρκετά κατάλληλη. [...] Ποτέ δεν αντιμετώπισα κάποιο πρόβλημα όπου οι γενετικοί αλγόριθμοι μου φάνηκαν ο σωστός τρόπος για να το αντιμετωπίσω. Επιπλέον, δεν έχω δει ποτέ κανένα υπολογιστικό αποτέλεσμα που να έχει αναφερθεί με τη χρήση γενετικών αλγορίθμων που να με έχει εντυπωσιάσει θετικά. Μείνετε στην προσομοιωμένη ανόπτηση για τις ανάγκες σας σε ευρετικές αναζητήσεις βουντού".

Επιτραπέζια παιχνίδια

Τα επιτραπέζια παιχνίδια αποτελούν ένα πολύ σημαντικό μέρος του τομέα των γενετικών αλγορίθμων που εφαρμόζονται σε προβλήματα θεωρίας παιγνίων. Μεγάλο μέρος των πρώτων εργασιών για την υπολογιστική νοημοσύνη και τα παιχνίδια κατευθύνθηκε προς τα κλασικά επιτραπέζια παιχνίδια, όπως το tic-tac-toe,^[3] σκάκι και ντάμα.^[4] Τα επιτραπέζια παιχνίδια μπορούν πλέον, στις περισσότερες περιπτώσεις, να παιχτούν από έναν υπολογιστή σε υψηλότερο επίπεδο από τους καλύτερους ανθρώπους, ακόμη και με τεχνικές τυφλής εξαντλητικής αναζήτησης. Το γκο αποτελεί σημαντική εξαίρεση σε αυτή την τάση και μέχρι στιγμής έχει αντισταθεί στην επίθεση των μηχανών. Οι καλύτεροι παίκτες του Γκο από υπολογιστή παίζουν τώρα στο επίπεδο ενός καλού αρχάριου.^[5][6] Η στρατηγική του Γκο λέγεται ότι βασίζεται σε μεγάλο βαθμό στην αναγνώριση προτύπων και όχι μόνο στη λογική ανάλυση, όπως στο σκάκι και σε άλλα παιχνίδια που δεν εξαρτώνται από τα κομμάτια. Ο τεράστιος αποτελεσματικός παράγοντας διακλάδωσης που απαιτείται για την εύρεση λύσεων υψηλής ποιότητας περιορίζει σημαντικά την προοπτική που μπορεί να χρησιμοποιηθεί σε μια αναζήτηση ακολουθίας κινήσεων.

Παιχνίδια υπολογιστών

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

Οι γενετικοί αλγόριθμοι απαιτούν τα ακόλουθα μέρη:

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

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

Περιορισμοί

Υπάρχουν περιορισμοί στη χρήση ενός γενετικού αλγορίθμου σε σύγκριση με εναλλακτικούς αλγορίθμους βελτιστοποίησης:

• Η επαναλαμβανόμενη αξιολόγηση συναρτήσεων καταλληλότητας για πολύπλοκα προβλήματα είναι συχνά το πιο περιοριστικό τμήμα των τεχνητών εξελικτικών αλγορίθμων. Η εύρεση της βέλτιστης λύσης σε πολύπλοκα προβλήματα απαιτεί συχνά πολύ ακριβές αξιολογήσεις συναρτήσεων καταλληλότητας. Σε προβλήματα του πραγματικού κόσμου, όπως προβλήματα δομικής βελτιστοποίησης, μια απλή αξιολόγηση συνάρτησης μπορεί να απαιτεί αρκετές ώρες έως αρκετές ημέρες πλήρους προσομοίωσης. Οι τυπικές μέθοδοι βελτιστοποίησης δεν μπορούν να αντιμετωπίσουν τέτοιους τύπους προβλημάτων. Συχνά είναι απαραίτητη η χρήση προσεγγίσεων, καθώς ο υπολογισμός της ακριβούς λύσης διαρκεί πολύ μεγάλο χρονικό διάστημα. Οι γενετικοί αλγόριθμοι συνδυάζουν μερικές φορές διαφορετικά μοντέλα προσέγγισης για την επίλυση πολύπλοκων προβλημάτων της πραγματικής ζωής.
• Οι γενετικοί αλγόριθμοι δεν κλιμακώνονται καλά. Δηλαδή, όταν ο αριθμός των στοιχείων που εκτίθενται στη μετάλλαξη είναι μεγάλος, συχνά παρατηρείται εκθετική αύξηση του μεγέθους του χώρου αναζήτησης. Αυτό καθιστά εξαιρετικά δύσκολη τη χρήση της τεχνικής σε προβλήματα όπως ο σχεδιασμός μιας μηχανής, ενός σπιτιού ή ενός αεροπλάνου. Για να χρησιμοποιηθούν οι γενετικοί αλγόριθμοι με τέτοια προβλήματα, πρέπει να αναλυθούν στην απλούστερη δυνατή αναπαράσταση. Για το λόγο αυτό, βλέπουμε εξελικτικούς αλγορίθμους να κωδικοποιούν σχέδια για πτερύγια ανεμιστήρων αντί για κινητήρες, σχήματα κτιρίων αντί για λεπτομερή κατασκευαστικά σχέδια και αεροτομές αντί για ολόκληρα σχέδια αεροσκαφών. Το δεύτερο πρόβλημα πολυπλοκότητας είναι το ζήτημα του τρόπου προστασίας των τμημάτων που έχουν εξελιχθεί ώστε να αντιπροσωπεύουν καλές λύσεις από περαιτέρω καταστροφική μετάλλαξη, ιδίως όταν η αξιολόγηση της καταλληλότητάς τους απαιτεί να συνδυάζονται καλά με άλλα τμήματα.
• Η "καλύτερη" λύση είναι μόνο σε σύγκριση με άλλες λύσεις. Κατά συνέπεια, το κριτήριο διακοπής δεν είναι σαφές σε κάθε πρόβλημα.
• Σε πολλά προβλήματα, οι γενετικοί αλγόριθμοι έχουν την τάση να συγκλίνουν σε τοπικά βέλτιστα ή ακόμη και σε αυθαίρετα σημεία αντί για το παγκόσμιο βέλτιστο του προβλήματος. Αυτό σημαίνει ότι ο αλγόριθμος δεν "ξέρει πώς" να θυσιάσει τη βραχυπρόθεσμη καταλληλότητα για να κερδίσει τη μακροπρόθεσμη καταλληλότητα. Η πιθανότητα να συμβεί αυτό εξαρτάται από τη μορφή της συνάρτησης καταλληλότητας: ορισμένα προβλήματα διευκολύνουν την εύρεση του παγκόσμιου βέλτιστου, ενώ άλλα μπορεί να διευκολύνουν τη συνάρτηση να βρει τα τοπικά βέλτιστα. Το πρόβλημα αυτό μπορεί να μειωθεί με τη χρήση μιας διαφορετικής συνάρτησης καταλληλότητας, την αύξηση του ρυθμού μετάλλαξης ή με τη χρήση τεχνικών επιλογής που διατηρούν έναν ποικιλόμορφο πληθυσμό λύσεων. Μια συνήθης τεχνική για τη διατήρηση της ποικιλομορφίας είναι η χρήση μιας "ποινής θέσης" (niche penalty): σε κάθε ομάδα ατόμων με επαρκή ομοιότητα (ακτίνα θέσης) προστίθεται μια ποινή, η οποία θα μειώσει την εκπροσώπηση της ομάδας αυτής στις επόμενες γενιές, επιτρέποντας τη διατήρηση άλλων (λιγότερο όμοιων) ατόμων στον πληθυσμό. Αυτό το τέχνασμα, ωστόσο, μπορεί να μην είναι αποτελεσματικό, ανάλογα με το τοπίο του προβλήματος. Μια άλλη πιθανή τεχνική θα ήταν να αντικαταστήσετε απλώς μέρος του πληθυσμού με τυχαία παραγόμενα άτομα, όταν το μεγαλύτερο μέρος του πληθυσμού είναι πολύ παρόμοιο μεταξύ του. Η ποικιλομορφία είναι σημαντική στους γενετικούς αλγορίθμους (και στον γενετικό προγραμματισμό), επειδή η διασταύρωση ενός ομοιογενούς πληθυσμού δεν δίνει νέες λύσεις. Στις στρατηγικές εξέλιξης και στον εξελικτικό προγραμματισμό, η ποικιλομορφία δεν είναι απαραίτητη λόγω της μεγαλύτερης εξάρτησης από τη μετάλλαξη.
• Η λειτουργία σε δυναμικά σύνολα δεδομένων είναι δύσκολη, καθώς τα γονιδιώματα αρχίζουν να συγκλίνουν από νωρίς προς λύσεις οι οποίες μπορεί να μην ισχύουν πλέον για μεταγενέστερα δεδομένα. Έχουν προταθεί διάφορες μέθοδοι για να διορθωθεί αυτό με την αύξηση της γενετικής ποικιλομορφίας με κάποιο τρόπο και την αποτροπή της πρόωρης σύγκλισης, είτε αυξάνοντας την πιθανότητα μετάλλαξης όταν η ποιότητα της λύσης πέφτει (που ονομάζεται ενεργοποιημένη υπερμετάλλαξη), είτε εισάγοντας περιστασιακά εντελώς νέα, τυχαία παραγόμενα στοιχεία στη γονιδιακή δεξαμενή (που ονομάζονται τυχαίοι μετανάστες). Και πάλι, οι στρατηγικές εξέλιξης και ο εξελικτικός προγραμματισμός μπορούν να εφαρμοστούν με τη λεγόμενη "στρατηγική κόμματος", στην οποία οι γονείς δεν διατηρούνται και οι νέοι γονείς επιλέγονται μόνο από τους απογόνους. Αυτό μπορεί να είναι πιο αποτελεσματικό σε δυναμικά προβλήματα.
• Οι γενετικοί αλγόριθμοι δεν μπορούν να επιλύσουν αποτελεσματικά προβλήματα στα οποία το μόνο μέτρο καταλληλότητας είναι ένα μοναδικό μέτρο σωστού/λάθους (όπως τα προβλήματα αποφάσεων), καθώς δεν υπάρχει τρόπος σύγκλισης στη λύση (δεν υπάρχει λόφος για να ανέβουμε). Σε αυτές τις περιπτώσεις, μια τυχαία αναζήτηση μπορεί να βρει μια λύση το ίδιο γρήγορα με έναν ΓΑ. Ωστόσο, εάν η κατάσταση επιτρέπει την επανάληψη της δοκιμής επιτυχίας/αποτυχίας δίνοντας (ενδεχομένως) διαφορετικά αποτελέσματα, τότε ο λόγος των επιτυχιών προς τις αποτυχίες παρέχει ένα κατάλληλο μέτρο καταλληλότητας.
• Για συγκεκριμένα προβλήματα βελτιστοποίησης και περιπτώσεις προβλημάτων, άλλοι αλγόριθμοι βελτιστοποίησης μπορεί να είναι πιο αποτελεσματικοί από τους γενετικούς αλγορίθμους όσον αφορά την ταχύτητα σύγκλισης. Οι εναλλακτικοί και συμπληρωματικοί αλγόριθμοι περιλαμβάνουν στρατηγικές εξέλιξης, εξελικτικό προγραμματισμό, προσομοιωμένη ανόπτηση, προσαρμογή κατά Gauss, αναρρίχηση σε λόφους, και νοημοσύνη σμήνους (π.χ.: βελτιστοποίηση αποικίας μυρμηγκιών, βελτιστοποίηση σμήνους σωματιδίων) και μεθόδους που βασίζονται στον ακέραιο γραμμικό προγραμματισμό. Η καταλληλότητα των γενετικών αλγορίθμων εξαρτάται από το μέγεθος της γνώσης του προβλήματος- για καλά γνωστά προβλήματα υπάρχουν συχνά καλύτερες, πιο εξειδικευμένες προσεγγίσεις.

Ιστορία

Το 1950, ο Άλαν Τούρινγκ πρότεινε μια "μηχανή μάθησης" η οποία θα ήταν παράλληλη με τις αρχές της εξέλιξης. Η προσομοίωση της εξέλιξης στον υπολογιστή ξεκίνησε ήδη από το 1954 με το έργο του Nils Aall Barricelli, ο οποίος χρησιμοποιούσε τον υπολογιστή στο Ινστιτούτο Προηγμένων Μελετών στο Princeton του New Jersey. Η δημοσίευσή του το 1954 δεν έτυχε ευρείας προσοχής. Από το 1957, ο Αυστραλός ποσοτικός γενετιστής Άλεξ Φρέιζερ δημοσίευσε μια σειρά εργασιών σχετικά με την προσομοίωση της τεχνητής επιλογής οργανισμών με πολλαπλούς τόπους που ελέγχουν ένα μετρήσιμο χαρακτηριστικό. Από αυτές τις απαρχές, η προσομοίωση της εξέλιξης σε υπολογιστή από βιολόγους έγινε πιο συνηθισμένη στις αρχές της δεκαετίας του 1960, και οι μέθοδοι περιγράφηκαν στα βιβλία των Fraser και Burnell (1970) και Crosby (1973). Οι προσομοιώσεις του Fraser περιλάμβαναν όλα τα βασικά στοιχεία των σύγχρονων γενετικών αλγορίθμων. Επιπλέον, ο Hans-Joachim Bremermann δημοσίευσε μια σειρά εργασιών στη δεκαετία του 1960 που επίσης υιοθέτησε έναν πληθυσμό λύσεων σε προβλήματα βελτιστοποίησης, ο οποίος υφίσταται ανασυνδυασμό, μετάλλαξη και επιλογή. Η έρευνα του Bremermann περιελάμβανε επίσης τα στοιχεία των σύγχρονων γενετικών αλγορίθμων. Άλλοι αξιοσημείωτοι πρώτοι πρωτοπόροι είναι οι Richard Friedberg, George Friedman και Michael Conrad. Πολλές πρώιμες εργασίες αναδημοσιεύονται από τον Fogel (1998).

Παρόλο που ο Barricelli, σε εργασία που ανέφερε το 1963, είχε προσομοιώσει την εξέλιξη της ικανότητας να παίζει ένα απλό παιχνίδι, η τεχνητή εξέλιξη έγινε μια ευρέως αναγνωρισμένη μέθοδος βελτιστοποίησης ως αποτέλεσμα της εργασίας των Ingo Rechenberg και Hans-Paul Schwefel τη δεκαετία του 1960 και στις αρχές της δεκαετίας του 1970 - η ομάδα του Rechenberg ήταν σε θέση να επιλύει πολύπλοκα προβλήματα μηχανικής μέσω στρατηγικών εξέλιξης. Μια άλλη προσέγγιση ήταν η τεχνική εξελικτικού προγραμματισμού του Lawrence J. Fogel, η οποία προτάθηκε για τη δημιουργία τεχνητής νοημοσύνης. Ο εξελικτικός προγραμματισμός αρχικά χρησιμοποιούσε μηχανές πεπερασμένων καταστάσεων για την πρόβλεψη του περιβάλλοντος και χρησιμοποιούσε τη μεταβολή και την επιλογή για τη βελτιστοποίηση των λογικών πρόβλεψης. Οι γενετικοί αλγόριθμοι έγιναν ιδιαίτερα δημοφιλείς μέσω του έργου του John Holland στις αρχές της δεκαετίας του 1970, και ιδίως του βιβλίου του Adaptation in Natural and Artificial Systems (1975). Το έργο του προήλθε από μελέτες κυτταρικών αυτομάτων, που διεξήχθησαν από τον Holland και τους φοιτητές του στο Πανεπιστήμιο του Michigan. Ο Holland εισήγαγε ένα τυποποιημένο πλαίσιο για την πρόβλεψη της ποιότητας της επόμενης γενιάς, γνωστό ως θεώρημα σχήματος του Holland. Η έρευνα στους ΓΑ παρέμεινε σε μεγάλο βαθμό θεωρητική μέχρι τα μέσα της δεκαετίας του 1980, όταν πραγματοποιήθηκε το Πρώτο Διεθνές Συνέδριο για τους Γενετικούς Αλγορίθμους στο Πίτσμπουργκ της Πενσυλβάνια.