ΥΠΟΛΟΓΙΣΤΙΚΗ ΝΟΗΜΟΣΥΝΗ ΙΙ
2.2 Τα βασικα στοιχεια ενος απλου Γενετικου Αλγοριθμου
Στην ουσία, ένας τυπικός Γ.Α. περιλαμβάνει απλές λειτουργίες, που όμως κρύβουν μέσα τους μεγάλη ισχύ. Αυτός ο συνδυασμός απλοϊκότητας και ισχύος είναι το μεγαλύτερο θέλγητρο της τεχνικής τους. Στην παράγραφο αυτή παρουσιάζονται τα βασικά στοιχεία, που πρέπει να έχει ένας αλγόριθμος, ώστε να θεωρείται γενετικός και δίνεται ένα παράδειγμα που κάνει αντιληπτή την εφαρμογή της θεωρίας.
Αρχικά σε ένα Γ.Α. πρέπει να υπάρχουν στοιχεία που θα τον συνδέουν με το πρόβλημα που επιλύει. Η κωδικοποίηση και η αντικειμενική συνάρτηση επιτελούν αυτό το σκοπό και είναι "εκ των ων ουκ άνευ" συστατικά για ένα Γ.Α.
Η κωδικοποίηση αφορά ένα σύνολο πιθανών λύσεων του προβλήματος. Η αναπαράσταση των λύσεων πρέπει να γίνει με ένα μαθηματικό, φορμαλιστικό τρόπο, ώστε να είναι δυνατή η επεξεργασία από τον υπολογιστή. Εξ' άλλου, κωδικοποίηση υπάρχει και στο φυσικό μοντέλο (χρωμοσώματα) και μάλιστα, όλες οι αλλαγές που παρατηρούνται στους οργανισμούς γίνονται πάνω στα κωδικοποιημένα χαρακτηριστικά των χρωμοσωμάτων. Κύριος στόχος της κωδικοποίησης είναι να αναπαριστά με ικανοποιητικό τρόπο τα επιμέρους χαρακτηριστικά των λύσεων, ώστε να διευκολύνει τις επόμενες λειτουργίες του αλγορίθμου (κυρίως την επιλογή). Αποτέλεσμα της κωδικοποίησης πρέπει να είναι η ύπαρξη ομοιοτήτων ανάμεσα στα άτομα με σκοπό την κατάλληλη εκμετάλλευση τους, διότι οι ομοιότητες βοηθούν την κατεύθυνση του ψαξίματος.
Διάφορα είναι τα είδη της κωδικοποίησης που μπορούν να γίνουν από πρόβλημα σε πρόβλημα. Η πιο απλή είναι η κωδικοποίηση με δυαδικά ψηφία (bits): κάθε λύση αναπαρίσταται από μια δυαδική συμβολοσειρά (binary string) καθορισμένου μήκους. Πάντως, έχουν αναφερθεί ποικίλες μορφές κωδικοποιήσεων, που κάθε μια εξαρτάται από το υπό εξέταση πρόβλημα. Καμιά δεν είναι αποτελεσματική για όλα τα προβλήματα, ενώ είναι πιθανό ένα πρόβλημα να επιδέχεται περισσότερες από μια κωδικοποιήσεις. Το σίγουρο είναι ότι η κωδικοποίηση είναι ένα κρίσιμο βήμα στην εφαρμογή του Γ.Α. και αν δεν είναι προσεκτική, πιθανότατα θα αποβεί μοιραία για την επιτυχία του. Η καταλληλότητα της κωδικοποίησης εξαρτάται σε μεγάλο βαθμό από τη διαίσθηση και την πείρα του σχεδιαστή. Συμβαίνει μερικές φορές μάλιστα, προφανείς τρόποι κωδικοποίησης να είναι λίγο (ή και καθόλου) αποτελεσματικοί.
Κατά συνέπεια προκύπτει το κρίσιμο ερώτημα: ποιοι είναι οι παράγοντες που καθορίζουν το είδος της κωδικοποίησης που πρέπει να επιλεχθεί για ένα συγκεκριμένο πρόβλημα; Δεν υπάρχει ξεκάθαρη απάντηση που να καλύπτει όλες τις περιπτώσεις. Μερικές γενικού τύπου συμβουλές θα φανούν στην παραπέρα ανάπτυξη του θέματος.
Για παράδειγμα [19], έστω η
συνάρτηση , με
και
: ακέραιος. Ζητείται το μέγιστο της συνάρτησης στο πεδίο
ορισμού της. Για να λυθεί το πρόβλημα από ένα Γ.Α. πρέπει να επινοηθεί ένας
τρόπος κωδικοποίησης των πιθανών λύσεων. Ο πιο προφανής και τελικά, όπως θα
αποδειχθεί, πιο αποτελεσματικός τρόπος κωδικοποίησης είναι να αναπαρασταθεί η
κάθε λύση με μια δυαδική συμβολοσειρά μήκους 5, που αριθμητικά θα ισοδυναμεί μα
την αντίστοιχη δεκαδική τιμή της λύσης. Έτσι καλύπτεται όλο το πεδίο ορισμού
από τις
δυνατές συμβολοσειρές αυτού του είδους. Π.χ. η συμβολοσειρά
αντιστοιχεί, κατά τα γνωστά, στην τιμή
του δεκαδικού συστήματος. Συνήθως, σε προβλήματα
βελτιστοποίησης μαθηματικών συναρτήσεων, η δυαδική είναι η πιο βολική και πιο
αποδοτική κωδικοποίηση.
Το δεύτερο βασικό στοιχείο της σύνδεσης ενός Γ.Α. με το πρόβλημα που λύνει, είναι η αντικειμενική συνάρτηση. Αυτή παίρνει ως είσοδο μια αποκωδικοποιημένη συμβολοσειρά και επιστρέφει μια τιμή (συνήθως πραγματική), που είναι ανάλογη του πόσο καλά λύνει το πρόβλημα η συγκεκριμένη συμβολοσειρά. Η τιμή αυτή αποτελεί και τον καθοριστικό παράγοντα επιβίωσης και πολλαπλασιασμού ή όχι του ατόμου.
Η αντικειμενική συνάρτηση παίζει το ρόλο του περιβάλλοντος στο τεχνικό μοντέλο. Ουσιαστικά, είναι η μόνη πληροφορία που δέχεται ο αλγόριθμος για το πρόβλημα που λύνει. Είναι σημαντικό αυτή η συνάρτηση να είναι εύκολα υπολογίσιμη, ώστε να μην επιβραδύνει τους ρυθμούς της διαδικασίας.
Επιστρέφοντας στο παράδειγμα,
η συνάρτηση ικανότητας του προβλήματος μεγιστοποίησης είναι φανερό ότι πρέπει να
είναι η ίδια η , γιατί ουσιαστικά το ζητούμενο είναι η μεγιστοποίηση αυτής
της συνάρτησης. Έτσι σε κάθε λύση, δηλαδή σε κάθε πιθανή τιμή της μεταβλητής
, αντιστοιχεί μια τιμή ικανότητας ή απόδοσης (fitness
ή score), μια τιμή που αξιολογεί το πόσο καλή είναι η λύση για τη
μεγιστοποίηση της συνάρτησης και που, για αυτή την περίπτωση είναι η ίδια η
εικόνα της στην
.
Με τον καθορισμό της κωδικοποίησης και της αντικειμενικής συνάρτησης ορίζεται πλέον το πρόβλημα και ολοκληρώνεται το πρώτο στάδιο εφαρμογής ενός Γ.Α. Αξίζει να σημειωθεί η αυτονομία και ανεξαρτησία αυτού του σταδίου από τα επόμενα μέρη. Οι λειτουργίες που ακολουθούν από εδώ και πέρα δεν εξαρτώνται από το πώς γίνεται η αναπαράσταση των ατόμων στο τεχνητό περιβάλλον και με ποιο τρόπο αξιολογούνται οι ικανότητές τους. Αυτό είναι σπουδαίο χαρακτηριστικό, διότι επιτρέπει την διαπραγμάτευση πολλών προβλημάτων με μια απλή αλλαγή στην συνάρτηση ικανότητας, ίσως και στην κωδικοποίηση. Η φάση ορισμού της κωδικοποίησης και της αντικειμενικής συνάρτησης υπάρχουν πάντα σε κάθε Γ.Α. ανεξαρτήτως του προβλήματος.
Στο επόμενο στάδιο περιλαμβάνονται λειτουργίες που ανήκουν στη φάση τρεξίματος του Γ.Α.. Εδώ γίνεται ο κύριος όγκος της εργασίας και παράγεται το αποτέλεσμα της βελτιστοποίησης. Η δομή της λειτουργίας ενός Γ.Α. αποτελείται από τα παρακάτω βήματα:
1) Αρχικοποίηση (Initialization)
2) Αποκωδικοποίηση (Decoding)
3) Υπολογισμός ικανότητας (Fitness calculation ή evaluation)
4) Αναπαραγωγή (Reproduction)
I. Επιλογή (Selection)
II. Διασταύρωση (Crossover ή Μating)
III.Μετάλλαξη (Mutation)
5) Επανάληψη από το βήμα (2) μέχρι να ικανοποιηθεί το κριτήριο τερματισμού του Γ.Α.
Η αρχικοποίηση είναι το βήμα στο οποίο ορίζεται ο αρχικός πληθυσμός, πάνω στον οποίο θα λάβουν χώρα οι λειτουργίες του Γ.Α. Ο πληθυσμός αυτός διαλέγεται με τυχαίο τρόπο ανάμεσα σε όλες τις δυνατές τιμές των μεταβλητών του προβλήματος, ενώ το μέγεθός του ορίζεται από το χρήστη (συνήθως, όμως, εξαρτάται από τους πόρους τους που έχει στη διάθεσή του). Σε μερικές
μερικές υλοποιήσεις, η επιλογή των αρχικών σημείων γίνεται με ευρετικές μεθόδους, δίνοντας ένα εξ αρχής πλεονέκτημα στην αναζήτηση. Έστω στο παράδειγμά μας, ότι το μέγεθος του πληθυσμού είναι 4. Μένει να επιλεχτούν τυχαία τέσσερις συμβολοσειρές από τις 32 πιθανές. Αυτό μπορεί να γίνει με 20 διαδοχικές ρίψεις ενός τίμιου νομίσματος, ώστε να προκύψουν 4 συμβολοσειρές μήκους 5 η κάθε μία. Ένα πιθανό σενάριο θα μπορούσε να βγάλει τις συμβολοσειρές 01101, 11000, 01000 και 10011.
Σχήμα 2.1: Τα στάδια λειτουργίας ενός Γ.Α.
Αφού προκύψει η πρώτη γενιά, ο Γ.Α. εισέρχεται στο επαναληπτικό μέρος του. Ο πληθυσμός πρέπει να αξιολογηθεί, δηλαδή να μετρηθεί η ικανότητα επιβίωσης του κάθε ατόμου χωριστά. Για να συμβεί αυτό πρέπει να γίνει αποκωδικοποίηση χαρακτηριστικών και έπειτα υπολογισμός της απόδοσης των ατόμων. Ο παραλληλισμός με το φυσικό μοντέλο ίσως βοηθά στην κατανόηση αυτής της διαδικασίας: Στη φύση τα χρωμοσώματα ενός οργανισμού έχουν στα γονίδιά τους κωδικοποιημένα τα χαρακτηριστικά τους. Το σύνολο αυτής της κωδικοποιημένης γενετικής πληροφορίας ονομάζεται, όπως είπαμε, γονότυπος. Ο γονότυπος δεν είναι αντιληπτός με τις φυσικές αισθήσεις των έμβιων όντων. Αντίθετα, αντιληπτή γίνεται η αλληλεπίδραση του με το περιβάλλον, που έχει ως αποτέλεσμα την ορατή εμφάνιση των χαρακτηριστικών αυτών.
Ανάλογος είναι ο ρόλος της αποκωδικοποίησης στο τεχνητό μοντέλο. Εδώ το ρόλο του γονότυπου παίζει η δομή της συμβολοσειράς με τα δυαδικά ψηφία ως αντίστοιχο των γονιδίων. Ο φαινότυπος αναφέρεται στην παρατηρήσιμη εμφάνιση μιας συμβολοσειράς, δηλαδή στο πώς φαίνεται στο περιβάλλον της. Περιβάλλον όμως, θεωρείται η αντικειμενική συνάρτηση, άρα ο φαινότυπος μιας συμβολοσειράς αντιστοιχεί στην αποκωδικοποιημένη τιμή του, που ανήκει στο σύνολο ορισμού της αντικειμενικής συνάρτησης.
Σκοπός της λειτουργίας αξιολόγησης είναι να υπολογιστεί για κάθε άτομο του πληθυσμού η ικανότητα του για επιβίωση. Στη φύση οι ικανότητες των ατόμων δεν μπορούν να προσδιοριστούν με αυστηρό τρόπο. Είναι όμως καθορισμένες από το γενετικό υλικό των χρωμοσωμάτων τους. Εύκολα πάντως θα μπορούσε κανείς να ισχυριστεί, π.χ. για τα ζώα, ότι μεγαλύτερη τύχη για επιβίωση έχουν όσα μπορούν να ξεφεύγουν από άρπαγες, να αντέχουν σε αρρώστιες και γενικά να αντιπαρέρχονται τις όποιες αντιξοότητες παρουσιάζονται κατά τη διάρκεια της ζωής τους. Συνεπώς, ο υπολογισμός της ικανότητας είναι θεμελιώδης λειτουργία για το Γ.Α. Η εφαρμογή της είναι πολύ απλή (τουλάχιστον για απλά προβλήματα): για κάθε συμβολοσειρά του τρέχοντος πληθυσμού υπολογίζεται η απόδοσή της από την ήδη γνωστή αντικειμενική συνάρτηση. Σε πιο σύνθετα προβλήματα, ο υπολογισμός ικανότητας μπορεί να ισοδυναμεί με την εκτέλεση μιας εργαστηριακής προσομοίωσης.
Τη σκυτάλη στη συνέχεια παίρνει η σημαντικότερη λειτουργία του Γ.Α., η αναπαραγωγή. Εδώ λαμβάνει χώρα ο κύριος όγκος της εργασίας του αλγόριθμου. Η δομή της αναπαραγωγικής διαδικασίας είναι σύνθετη. Περιλαμβάνει τα εξής τρία μέρη: την επιλογή, τη διασταύρωση και τη μετάλλαξη.
Με την επιλογή, βρίσκει εφαρμογή στα πλαίσια του αλγόριθμου, ο νόμος της επιβίωσης του ικανότερου. Μέσω αυτής της διαδικασίας, καθορίζεται ποια άτομα από τον υπάρχοντα πληθυσμό θα έχουν την ευκαιρία να λάβουν μέρος στην αναπαραγωγή και να κληροδοτήσουν στην επόμενη γενιά μέρος ή το σύνολο των χαρακτηριστικών τους. Στόχος της λειτουργίας της επιλογής είναι να επιτρέπει εκθετική αύξηση των ικανοτέρων ατόμων και τελικά, μετά από αναπαραγωγή αρκετών γενεών, την επικράτησή τους. Ένας Γ.Α. χωρίς επιλογή στην αναπαραγωγική του διαδικασία ισοδυναμεί με τυχαίο ψάξιμο.
Υπάρχουν διάφοροι τρόποι υλοποίησης της επιλογής στα πλαίσια ενός Γ.Α. Δεδομένου όμως, ότι στη βασική μορφή του αλγορίθμου το μέγεθος του πληθυσμού από γενιά σε γενιά δεν αλλάζει, κάθε τεχνική επιλογής, για να δικαιώνει τον τίτλο της, οφείλει να δίνει με κάποιο τρόπο μεγαλύτερες πιθανότητες αναπαραγωγής σε άτομα που αξιολογούνται μέσα στο τεχνητό περιβάλλον ως τα πιο ικανά.
Ο τελεστής αναπαραγωγής μπορεί να εκφραστεί σε αλγοριθμική βάση, με πολλούς τρόπους. Ίσως ο ευκολότερος από αυτούς είναι η έκφραση μέσω μιας εξαναγκασμένης ρουλέτας, στην οποία κάθε συμβολοσειρά ενός πληθυσμού αντιπροσωπεύεται σε ένα μέρος της ρουλέτας, σε αναλογία με την απόδοσή της, όπως εισάγεται για πρώτη φορά στο κεφάλαιο 1 της αναφοράς [29]. Για να εξηγήσουμε τη χρήση της εξαναγκασμένης ρουλέτας, θεωρούμε τον πληθυσμό των τεσσάρων συμβολοσειρών, που έχουμε δημιουργήσει με τη ρίψη ενός νομίσματος 20 φορές. Έστω, ότι έχουμε μετρήσει την απόδοση (δηλαδή την τιμή της αντικειμενικής συνάρτησης), για κάθε συμβολοσειρά, όπως φαίνεται στον παρακάτω πίνακα 2.1:
Αριθμός Συμβολοσειράς |
Συμβολοσειρά |
Απόδοση |
Απόδοση % |
---|---|---|---|
1 |
01101 |
169 |
14.4 |
2 |
11000 |
576 |
49.2 |
3 |
01000 |
64 |
5.5 |
4 |
10011 |
361 |
30.9 |
Σύνολο |
|
1170 |
100.0 |
Πίνακας 2.1
Αθροίζοντας την απόδοση των τεσσάρων συμβολοσειρών παίρνουμε άθροισμα 1170. Το ποσοστό κάθε συμβολοσειράς στη συνολική απόδοση του πληθυσμού φαίνεται στην τελευταία στήλη του πίνακα. Αυτή η αντιστοιχία στην εξαναγκασμένη ρουλέτα γι’ αυτή τη γενιά αναπαραγωγής φαίνεται στο παρακάτω σχήμα 2.2.
Για να γίνει η αναπαραγωγή, στρίβουμε τη ρουλέτα τέσσερις φορές. Για το συγκεκριμένο πρόβλημα η συμβολοσειρά Νο.1 έχει απόδοση 169, η οποία αντιπροσωπεύει το 14.4% της συνολικής απόδοσης. Σαν αποτέλεσμα η συμβολοσειρά Νο.1 αντιστοιχεί στο 14.4 της επιφάνειας της ρουλέτας και σε κάθε στρίψιμο της ρουλέτας θα δώσει ως αποτέλεσμα αυτή τη συμβολοσειρά με πιθανότητα 0.144. Με αυτόν τον τρόπο, οι συμβολοσειρές που έχουν τη μεγαλύτερη απόδοση, θα έχουν μεγαλύτερο αριθμό αντιγράφων (απογόνων) στην επόμενη γενιά, ενώ αυτές που έχουν χαμηλή απόδοση δεν θα υπάρχουν. Όταν μια συμβολοσειρά επιλεγεί, δημιουργείται ένα ακριβές αντίγραφό της και μαζί με τα αντίγραφα άλλων συμβολοσειρών, που παράγονται με τον ίδιο τρόπο, δημιουργείται ένας νέος δοκιμαστικός πληθυσμός, ο οποίος θα υποστεί περισσότερες γενετικές διαδικασίες. Αυτός ο νέος πληθυσμός αναφέρεται στη διεθνή βιβλιογραφία και σαν δεξαμενή ζευγαρώματος (mating pool).
Σχήμα 2.2: Σχηματική αναπαράσταση της εξαναγκασμένης ρουλέτας.
Ο προσωρινός πληθυσμός που προέκυψε από τη διαδικασία της επιλογής πρέπει να περάσει από τη διαδικασία ζευγαρώματος για να πραγματοποιηθεί ένα είδος γονιμοποίησης, όπως συμβαίνει και στη φύση. Η νέα λοιπόν ομάδα ατόμων, που προέκυψε από την επιλογή, σχηματίζει με τυχαίο τρόπο ομάδες των δύο. Σε κάθε ομάδα, τα δύο μέλη παίρνουν μέρος σε μια απλή λειτουργία ανταλλαγής γενετικού υλικού που ονομάζεται διασταύρωση. Η διασταύρωση είναι μια απαραίτητη λειτουργία που συμβάλει αποφασιστικά στην επίδοση ενός Γ.Α. Εξ' αιτίας αυτής της σπουδαιότητας, έχει γίνει αρκετή έρευνα και έχουν επινοηθεί πολλοί τρόποι υλοποίησης της. Μερικοί μπορούν να εφαρμοστούν σε κάθε τύπο προβλήματος, ενώ άλλοι είναι πιο κατάλληλοι και εξειδικευμένοι για ειδικές περιπτώσεις. Στόχος της διασταύρωσης είναι η νέα γενιά που θα προκύψει μετά την εφαρμογή της να περιλαμβάνει άτομα που θα διαφέρουν από τους γονείς τους και θα φέρουν συνδυασμό των καλύτερων χαρακτηριστικών τους. Ερευνητές που ασχολούνται χρόνια με τους Γ.Α. υποστηρίζουν ότι αν αφαιρεθεί η διασταύρωση από έναν Γ.Α., τότε μειώνεται σημαντικά η απόδοσή του, αλλά αυτή δεν είναι μια άποψη με καθολική αποδοχή [19].
Ένα ενδεικτικό της χρησιμότητας της διασταύρωσης είναι η ανακατεύθυνση του ψαξίματος σε νέες "απάτητες" περιοχές του χώρου αναζήτησης. Έτσι διευρύνεται το πεδίο δράσης του αλγορίθμου και αυξάνουν οι πιθανότητες επιτυχίας του. Επίσης, τα νέα άτομα περιλαμβάνουν συνδυασμούς χαρακτηριστικών των γονέων τους και με αυτό τον τρόπο μπορούν να προκύψουν επιτυχημένοι συνδυασμοί υψηλής ικανότητας. Υπάρχει βέβαια το ενδεχόμενο, η διασταύρωση να δώσει χειρότερα παιδιά από τους γονείς, αλλά αυτά δεν θα έχουν μεγάλη πιθανότητα πολλαπλασιασμού στον επόμενο αναπαραγωγικό κύκλο, λόγω μικρής απόδοσης.
Στην πράξη, η διασταύρωση χρησιμοποιείται με παραμετροποιημένη μορφή, δηλαδή λαμβάνει χώρα με πιθανότητα που καθορίζεται από το σχεδιαστή του Γ.Α. Συνήθως, αυτή η πιθανότητα ποικίλει από πρόβλημα σε πρόβλημα, ενώ είναι δυνατό και να αλλάζει κατά το χρόνο τρεξίματος.
Τελευταία στον κύκλο αναπαραγωγικής διαδικασίας και ίσως λιγότερο σημαντική, αλλά πάντως χρήσιμη, είναι η μετάλλαξη. Είναι μια λειτουργία που όταν συμβαίνει αραιά στη φύση δρα βελτιωτικά για τους οργανισμούς και γενικά για την εξέλιξη της ζωής. Ανάλογος είναι ο ρόλος της και στα τεχνικά περιβάλλοντα. Η λειτουργία της είναι απλή: Ενεργεί σε ένα μόνο οργανισμό κάθε φορά. Καθώς αντιγράφονται δυαδικά ψηφία από τον γονέα στον απόγονο, επιλέγεται τυχαία με μικρή πιθανότητα, ένα ψηφίο και αντιστρέφεται (από 0 σε 1 ή το αντίστροφο). Είναι πολύ σημαντικό η πιθανότητα να πραγματοποιηθεί η μετάλλαξη να είναι αρκετά μικρή (περίπου μία μετάλλαξη σε κάθε χίλια ψηφία που αντιγράφονται), γιατί σε αντίθετη περίπτωση ο Γ.Α. εκφυλίζεται σε τυχαίο ψάξιμο.
Αν και υπάρχει κάποια σύγχυση για το ρόλο της μετάλλαξης, τόσο της φυσικής όσο και της τεχνητής, το σίγουρο είναι πως είναι απαραίτητη. Η μετάλλαξη λειτουργεί ως ασφαλιστική δικλείδα για τις περιπτώσεις όπου η επιλογή και η διασταύρωση χάσουν κάποιες πολύτιμες γενετικές πληροφορίες [21]. Όταν συμβαίνει, επιφέρει ποικιλία στον πληθυσμό, ανακατευθύνει την αναζήτηση και εξασφαλίζει ότι κανένα σημείο του χώρου αναζήτησης δεν αποκλείεται από τη διαδικασία του ψαξίματος.