ΥΠΟΛΟΓΙΣΤΙΚΗ ΝΟΗΜΟΣΥΝΗ ΙΙ

 

4.     Αναλυση των Γενετικων Αλγοριθμων

 

Η θεωρητική θεμελίωση των Γ.Α. βασίζεται στην αναπαράσταση των λύσεων σαν δυαδικές συμβολοσειρές, καθώς και στην έννοια του σχήματος (schema) - μιας φόρμας (template) που επιτρέπει τον προσδιορισμό της ομοιότητας μεταξύ των χρωμοσωμάτων. Ένα σχήμα κατασκευάζεται εισάγοντας ένα αδιάφορο σύμβολο (don't care symbol) * στο αλφάβητο  των γονιδίων (). Ένα σχήμα αναπαριστά όλες τις συμβολοσειρές (ένα υπερεπίπεδο ή άλλο υποσύνολο του χώρου αναζήτησης), οι οποίες ταιριάζουν σε όλες τις θέσεις εκτός από αυτές με το αδιάφορο σύμβολο .

 

Για παράδειγμα, ας θεωρήσουμε τις συμβολοσειρές και τα σχήματα μήκους 10. Στο σχήμα  ταιριάζουν οι δύο συμβολοσειρές:

 

και στο σχήμα  ταιριάζουν οι τέσσερις συμβολοσειρές:

.

 

Φυσικά το σχήμα  αναπαριστά μία μόνο συμβολοσειρά, την  και το σχήμα  αναπαριστά όλες τις συμβολοσειρές μήκους . Είναι σαφές ότι κάθε σχήμα αναπαριστά  συμβολοσειρές, όπου  είναι ο αριθμός των αδιάφορων συμβόλων  στο σχήμα. Από την άλλη πλευρά, κάθε συμβολοσειρά μήκους  ταιριάζει σε  διαφορετικά σχήματα. Για παράδειγμα, ας θεωρήσουμε τη συμβολοσειρά . Αυτή η συμβολοσειρά ταιριάζει στα ακόλουθα  σχήματα:













.

Διαφορετικά σχήματα έχουν και διαφορετικά χαρακτηριστικά. Θα πρέπει να έχει ήδη γίνει σαφές ότι ο αριθμός των αδιάφορων συμβόλων  σε ένα σχήμα καθορίζει τον αριθμό των συμβολοσειρών που ταιριάζουν σε αυτό το σχήμα. Υπάρχουν δύο σημαντικά μεγέθη που χαρακτηρίζουν τα σχήματα: η τάξη (order) και το καθορισμένο μήκος (defining length). Το Αποτέλεσμα των Σχημάτων (Schema Result) θα διατυπωθεί με βάση τα μεγέθη αυτά.

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

 

,
,
,

 

έχουν τις ακόλουθες τάξεις:

  και  ,

 

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

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

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

 και  .

 

Φυσικά, ένα σχήμα με μια μοναδική σταθερή θέση έχει ορισμένο μήκος μηδέν.

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

 

Η διαδικασία εξέλιξης ενός Γ.Α. αποτελείται από τέσσερα επαναλαμβανόμενα βήματα:

1)       

2)        επέλεξε νέο (προσωρινό) πληθυσμό  από τον

3)        ανασυνδύασε τον

4)        εκτίμησε τον

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

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

 




















Έστω  ο αριθμός των συμβολοσειρών στον πληθυσμό τη στιγμή  που ταιριάζουν στο σχήμα . Για παράδειγμα, για το σχήμα

,

είναι , αφού υπάρχουν τρεις συμβολοσειρές (οι ,  και ), οι οποίες ταιριάζουν με το σχήμα . Η τάξη του  είναι  και το ορισμένο μήκος του είναι .

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

 

.

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

 

Μετά το βήμα της επιλογής, αναμένεται ότι  συμβολοσειρές θα ταιριάζουν με το σχήμα . Επειδή,

1)        για μια συμβολοσειρά που ταιριάζει με το σχήμα , η πιθανότητα επιλογής της είναι ,

2)        ο αριθμός των συμβολοσειρών που ταιριάζουν με το σχήμα  είναι  και

3)        ο αριθμός των επιλογών σε κάθε βήμα είναι ,

θα πρέπει να είναι σαφές ότι:

Αν λάβουμε υπ' όψη ότι η μέση απόδοση του πληθυσμού είναι , η παραπάνω σχέση ισοδυναμεί με την ακόλουθη:

 

.

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

Η μακροπρόθεσμη επίδραση της παραπάνω διαπίστωσης είναι η εξής: Αν υποθέσουμε ότι ένα σχήμα  βρίσκεται πάνω από τον μέσο όρο κατά % (δηλαδή ), τότε:

 και

με  για σχήματα πάνω από τον μέσο όρο και  για σχήματα κάτω από τον μέσο όρο.

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

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

.

Την ίδια στιγμή, η μέση απόδοση του πληθυσμού είναι:

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

 

.

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

Διαισθητικά, το σχήμα  αποτελεί ένα υποσχόμενο τμήμα του χώρου αναζήτησης και, για το λόγο αυτό, δειγματοληπτείται με εκθετικά αυξανόμενο τρόπο.

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

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

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

Μια οποιαδήποτε συμβολοσειρά του πληθυσμού, π.χ. η :

,

ταιριάζει σε  διαφορετικά σχήματα. Έστω τα ακόλουθα δύο σχήματα, στα οποία ταιριάζει η συμβολοσειρά αυτή:

 

       και
.

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

      και

θα έδινε:

    και
.

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

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

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

 

                                                                 (4.1)

και συνεπώς η πιθανότητα επιβίωσής του είναι:

                                                             (4.2)

Στο παράδειγμά μας, οι πιθανότητες αυτές για τα σχήματα  και  είναι:

 

,

οπότε το αποτέλεσμα της διασταύρωσης ήταν αναμενόμενο.

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

                                                       (4.3)

Επιστρέφοντας στο παράδειγμά μας, ισχύει ():

.

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

                                                       (4.4)

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

 

                             (4.5)

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

 

.

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

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

 

και το σχήμα :

.

Ας υποθέσουμε, ακόμα, ότι η συμβολοσειρά  υπόκειται σε μετάλλαξη. Στο παράδειγμα του Κεφαλαίου 3, η  μεταλλάχθηκε στην ένατη θέση και προέκυψε η:

 

,

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

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

 

                                                        (4.6)

Επειδή, όμως, , η πιθανότητα αυτή προσεγγίζεται από την:

 

                                                       (4.7)

Αναφερόμενοι και πάλι στο παράδειγμά μας με το σχήμα , και θεωρώντας

 

                                                                                                                           , έχουμε:

.

Επομένως, ο συνδυασμός των αποτελεσμάτων μας για την επιλογή, τη διασταύρωση και τη μετάλλαξη οδηγούν στην ακόλουθη σχέση:

 

                        (4.8)

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

Για το σχήμα :

.

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

Η παραπάνω ανάλυση και το αποτέλεσμα που περιγράφεται από τη σχέση (4.8) μπορεί να διατυπωθεί από το ακόλουθο συμπέρασμα (γνωστό ως Συμπέρασμα Σχημάτων).

 

 

ΑΡΧΗ ΚΕΦΑΛΑΙΟΥ