Άσκηση 14η

 

Δίνεται ο εξής πληθυσμός συμβολοσειρών τη γενιά 0: 11011, 01011, 11001, 10111

και η εξής αντικειμενική συνάρτηση:  , όπου το bi είναι το i-οστό δυαδικό ψηφίο (το πρώτο δυαδικό ψηφίο έχει δείκτη i=0).

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

0.25, 0.73, 0.15, 0.52, 0.81, 0.65

Θεωρήστε ότι:

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

2.       Πιθανότητα μετάλλαξης ίση με 0.

3.       Η επιλογή των ατόμων που θα συμμετέχουν στη διασταύρωση γίνεται με βάση τον τελεστή επιλογής και τους τυχαίους αριθμούς που προέκυψαν από τη γεννήτρια τυχαίων αριθμών. Ο τελεστής διασταύρωσης  είναι μονού σημείου με πιθανότητα διασταύρωσης 1.0, με το σημείο διασταύρωσης να επιλέγεται τυχαία ανάμεσα στα τέσσερα πιθανά σημεία διασταύρωσης κάθε συμβολοσειράς. Με βάση κάποιο τυχαίο αριθμό τα σημεία διασταύρωσης θα επιλέγονται από τα αριστερά προς τα δεξιά με ίδια πιθανότητα και για τα τέσσερα πιθανά σημεία (0.25 για κάθε πιθανή θέση). Δηλαδή εάν ο τυχαίος αριθμός είναι ο 0.45 το σημείο διασταύρωσης θα είναι ανάμεσα στο δυαδικό ψηφίο 1 και το δυαδικό ψηφίο 2 (το πιο αριστερό ψηφίο έχει αριθμό 0).

4.       Και τα δύο παιδιά που προκύπτουν από μία διασταύρωση προστίθενται στον πληθυσμό της επόμενης γενιάς, επομένως μόνο δύο διασταυρώσεις χρειάζονται για να δημιουργηθεί ο πληθυσμός της γενιάς 1 από τον πληθυσμό της γενιάς 0.

Να υπολογίσετε τα ακόλουθα:

1.       Την απόδοση της αντικειμενικής συνάρτησης για κάθε άτομο του πληθυσμού στις γενιές 0 και 1.

2.       Την μέση απόδοση του πληθυσμού στις γενιές 0 και 1.

3.       Τη ρουλέτα που χρησιμοποιείτε για την επιλογή των ατόμων από τη γενιά 0. Να φαίνεται καθαρά το ποσοστό που αντιστοιχεί σε κάθε άτομο του αρχικού πληθυσμού.

4.       Τον πληθυσμό των ατόμων στη γενιά 1.

5.       Τον αριθμό των ατόμων του πληθυσμού που ανήκουν στα σχήματα 1###1 και ##01# στην γενιά 0 και στη γενιά 1.

6.    Τη μέση απόδοση των παραπάνω σχημάτων στη γενιά 0 και στη γενιά 1.

 


Λύση:

 

Η γενιά 0 αποτελείται από τα χρωμοσώματα: v1=11011, v2=01011, v3=11001, v4=10111.

Η απόδοση για κάθε ένα από τα άτομα της γενιάς 0 είναι:

 

 

 

 

Η συνολική απόδοση του πληθυσμού είναι: F(0)=2+1+3+4=10

Η μέση απόδοση του πληθυσμού στη γενιά 0 είναι:

 

Η πιθανότητα επιλογής κάθε ατόμου είναι:

, , ,

 

Επομένως, η ρουλέτα που χρησιμοποιείται για την επιλογή τους είναι:

 

Η συσσωρευμένη πιθανότητα για κάθε άτομο είναι:

, , ,

 

Έστω ότι αρχίζει η διαδικασία επιλογής. Ο πρώτος τυχαίος αριθμός είναι ο 0.25, επομένως το πρώτο άτομο που επιλέγεται για την 1η γενιά είναι το v2 αφού .Ο επόμενος τυχαίος αριθμός είναι ο 0.73, άρα επιλέγεται το v4.

Ο τρίτος τυχαίος αριθμός είναι ο 0.15 επομένως έχουμε διασταύρωση μονού σημείου των v2 και v4 μετά το δυαδικό σημείο 0, δηλαδή:

 

Στη συνέχεια επιλέγεται το v3 αφού ο επόμενος αριθμός είναι ο 0.52. Τέλος, επιλέγεται το v4 αφού ο πέμπτος αριθμός είναι ο 0.81.

Ο τελευταίος τυχαίος αριθμός είναι ο 0.65 επομένως έχουμε διασταύρωση μονού σημείου των v3 και v4 μετά το δυαδικό σημείο 3, δηλαδή:

 

Η απόδοση για κάθε ένα από τα άτομα της γενιάς 1 είναι:

F(00111)=3, F(11011)=2, F(11011)=2, F(10101)=5.

Η συνολική απόδοση του πληθυσμού στην 1η γενιά είναι: F(1)=3+2+2+5=12

Η μέση απόδοση του πληθυσμού στη 1η γενιά είναι:

 

Παρατηρούμε ότι σε σύγκριση με τη μέση απόδοση του πληθυσμού στη γενιά 0 έχουμε μία αύξηση της τάηεως του 0.5, δηλαδή του 20%.

 

Στο σχήμα 1###1 ανήκουν οι συμβολοσειρές:

Γενιά 0: 11011, 11001, 10111.

Γενιά 1: 11011, 11011, 10101.

 

Στο σχήμα ##01# ανήκουν οι συμβολοσειρές:

Γενιά 0: 11011, 01011.

Γενιά 1: 11011, 11011.

 

Οι μέσες αποδόσεις των σχημάτων είναι οι εξής:

Σχήματα

Γενιά 0

Γενιά 1

1###1

(2+3+4)/3=3

(2+2+5)/3=3

##01#

(2+1)/2=1.5

(2+2)/2=2