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

 

5.13     Συστηματα Διασταυρωσης

 

Η ενότητα αυτή βασίζεται ως επί το πλείστον στην εργασία των Y. Rabani, Y. Rabinovich και A. Sinclair [57], η οποία συνέβαλε σημαντικά στην μελέτη των Μη Γραμμικών Δυναμικών Συστημάτων (Non Linear Dynamical Systems) από υπολογιστική άποψη, δίνοντας έμφαση σε γενετικά συστήματα. Πιο συγκεκριμένα, ανέλυσαν διεξοδικά μία κλάση Δευτεροβάθμιων Δυναμικών Συστημάτων (Quadratic Dynamical Systems), που χρησιμοποιείται ευρύτατα σα μοντέλο για τον πληθυσμό ενός Γ.Α. Τα συστήματα αυτά περιγράφουν μία διαδικασία κατά την οποία σχηματίζονται με τυχαίο τρόπο ζευγάρια, τα οποία ζευγαρώνουν με διασταύρωση. Δηλαδή, η δομή των συστημάτων αυτών περιλαμβάνει μόνο δύο από τα βήματα ενός κλασσικού Γ.Α., που είναι τα εξής:

 

·           Επιλογή

·           Διασταύρωση

 

Όλα τα άτομα του πληθυσμού που επιλέχθηκαν κατά τη διαδικασία της επιλογής, θα συμμετάσχουν σε διασταύρωση, δηλαδή ο νέος πληθυσμός θα αποτελείται από τα παιδιά των ατόμων του προηγούμενου πληθυσμού. Γι' αυτό το λόγο, αυτά τα γενετικά συστήματα ονομάζονται Συστήματα Διασταύρωσης (Crossover Systems). Η εξελικτική διαδικασία σε ένα Σύστημα Διασταύρωσης (Σ.Δ.) έχει ως εξής:

 

1)      Αρχικοποίηση του πληθυσμού.

2)      Επιλογή ατόμων με ομοιόμορφη κατανομή για διασταύρωση.

3)      Σχηματισμός ζευγαριών από τα άτομα αυτά και διασταύρωσή τους.

4)      Επανάληψη των βημάτων 1 και 2 ως ότου ικανοποιηθεί το κριτήριο τερματισμού.

 

Στο [57] αναλύεται ο ρυθμός σύγκλισης (convergence rate) των συστημάτων αυτών προς την μόνιμη κατάσταση, καθώς επίσης και η δομή (structure) των ατόμων του πληθυσμού μόνιμης κατάστασης (stationary population).

 

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

Τα γραμμικά δυναμικά συστήματα -με την μορφή διεργασιών διακλάδωσης (branching processes) και αλυσίδων Markov (Markov chains)- είχαν, και εξακολουθούν να έχουν ως σήμερα, πολύ σημαντική επίδραση στο σχεδιασμό αλγορίθμων, γεγονός που είχε σαν αποτέλεσμα την "εντατική" έρευνα πάνω στα συστήματα αυτά, που με τη σειρά της κατέληξε στην πλήρη μαθηματική ανάλυση των συστημάτων αυτών [2,34,46]. Αντίθετα, η μελέτη των μη γραμμικών δυναμικών συστημάτων, παρ' ότι αυτά διαθέτουν μεγαλύτερη ισχύ από τα γραμμικά αντίστοιχά τους, βρίσκεται ακόμη σε πολύ πρώιμο στάδιο.

 

Πολλά μη γραμμικά δυναμικά συστήματα μπορούν να αναλυθούν σαν Δευτεροβάθμια Δυναμικά Συστήματα (Δ.Δ.Σ.)[1]. Έστω  ένα σύνολο "τύπων". Συχνά, οι τύποι καλούνται καταστάσεις (states), οπότε το  είναι ο χώρος των καταστάσεων (state space). Έστω  η κατανομή πιθανότητας στο σύνολο . Επιπλέον, ας ορίσουμε σαν  την πιθανότητα ο τύπος  τη χρονική στιγμή .

 

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

                      (5.1)

 

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

.

Θα πρέπει επίσης να σημειώσουμε ότι οι αλυσίδες Markov αποτελούν ειδική περίπτωση της σχέσης (5.1), αφού σε αυτές υπάρχει ένας μόνο "πατέρας", δηλαδή από μία κατάσταση μεταβαίνουμε σα κάποια άλλη (δεν υπάρχει αλληλεπίδραση με άλλη κατάσταση):

.

Ακολουθούν δύο χρήσιμοι ορισμοί:

Ορισμός 5.1. Η πιθανότητα  καλείται συμμετρική (symmetric), αν και μόνο αν  .

Ορισμός 5.2. Η πιθανότητα  καλείται απεριοδική (aperiodic), αν και μόνο αν , .

 

Στο [25] έχει αποδειχθεί το ακόλουθο θεώρημα:

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

Για το ρυθμό σύγκλισης αποδεικνύεται στο [57] ότι είναι πολύ μικρός σε σχέση με το χώρο των καταστάσεων, δηλαδή μπορούμε να πούμε ότι τα συστήματα διασταύρωσης έχουν την ιδιότητα της γρήγορης σύγκλισης (mixing time property).

 

Έστω ο ακόλουθος ορισμός:

Ορισμός 5.3. Ένας πληθυσμός  έχει πλήρη υποστήριξη (full support), εάν , .

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

 


[1] Οι Rabani, Rabinovich και Sinclair απέδειξαν αρχικά ότι ένα Δ.Δ.Σ. περιορισμένου πληθυσμού μπορεί να προσομοιώσει ικανοποιητικά ένα Σύστημα Διασταύρωσης.

 

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