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

 

Γενετικοι Τελεστες

 

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

Σχήμα 3.2: Η κατανομή τεσσάρων ατόμων στη ρουλέτα σύμφωνα με την απόδοσή τους

 

Για τη διαδικασία επιλογής ενός νέου πληθυσμού χρησιμοποιείται μια ρουλέτα με σχισμές (slotted roulette wheel). Η επιλογή γίνεται με βάση την απόδοση κάθε χρωμοσώματος, δηλαδή όσο καλύτερο είναι κάποια χρωμόσωμα τόση μεγαλύτερη πιθανότητα έχει ώστε να επιλεγεί. Τα χρωμοσώματα τοποθετούνται στη ρουλέτα σε σχέση πάντα με την απόδοσή τους (χρωμοσώματα με μεγάλη απόδοση κατέχουν μεγαλύτερο ποσοστό της ρουλέτας). Μια τέτοια ρουλέτα για πληθυσμό τεσσάρων ατόμων φαίνεται στο σχήμα 3.2.

Η κατασκευή μιας τέτοιας ρουλέτας γίνεται ως εξής:

 

·           Υπολογίζουμε την απόδοση  για κάθε χρωμόσωμα .

 

·           Υπολογίζουμε τη συνολική απόδοση του πληθυσμού .

 

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

·           Τέλος, υπολογίζουμε τη συσσωρευμένη (cumulative) πιθανότητα  για κάθε χρωμόσωμα : .

 

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

Πιο συγκεκριμένα, ακολουθούμε τα εξής βήματα:

1.         Επιλέγουμε τυχαία έναν αριθμό  μεταξύ 0 και 1.

2.         Αν , τότε επιλέγουμε το πρώτο χρωμόσωμα , διαφορετικά επιλέγουμε το  (), έτσι ώστε .

 

Η μορφή του καινούριου πληθυσμού των τεσσάρων ατόμων που αναφέραμε προηγουμένως μετά από την επιλογή της ρουλέτας θα είναι η εξής:

 

Σχήμα 3.3: Η κατανομή των τεσσάρων ατόμων μετά την επιλογή της ρουλέτας

 

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

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

·           Επιλέγουμε τυχαία έναν αριθμό  μεταξύ 0 και 1.

·           Αν , επιλέγουμε το χρωμόσωμα για διασταύρωση.

 

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

 και

αντικαθίστανται από το ζευγάρι απογόνων:

 και
.

 

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

·           Επιλέγουμε τυχαία έναν αριθμό  μεταξύ 0 και 1.

·           Αν , τότε αντιστρέφουμε το δυαδικό ψηφίο.

 

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

 


Ασκηση 1η:

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

α) 1ος Γονιός: 0 1 1 0 1, 2ος Γονιός: 1 1 0 0 0.

β) 1ος Γονιός: 1 1 0 0 0, 2ος Γονιός: 1 0 0 1 1.

 

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

 

Λύση


Ασκηση 2η:

Για έναν πληθυσμό με μέγεθος 100 και μήκος χρωμοσώματος 42 ποιος είναι ο αναμενόμενος αριθμός των ψηφίων που θα υποστούν μετάλλαξη, αν  ηπιθανότητα μετάλλαξης παίρνει τις τιμές 0.1, 0.01 και 0.001;

Υπόδειξη: Ανατρέξτε στην παραπάνω υποενότητα για τον τύπο υπολογισμού του αριθμού των ψηφίων που θα υποστούν μετάλλαξη.

 

 Λύση


 

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