Ένας Απλός Γενετικός Αλγόριθμος

Χρησιμοποιώντας τον πληθυσμό του πίνακα να απαντήσετε στις παρακάτω ερωτήσεις και να συμπληρώσετε τον πίνακα:

	Άτομο	Ικανότητα	Πιθανότητα Επιλογής	Αναμενόμενος Αριθμός Αντιγράφων	Προσωρινός Πληθυσμός       *	Πληθυσμός μετά τη Διασταύρωηση **	Πληθυσμός μετά τη Μετάλλαξη (1η γενιά)
Α	11010	0.10
Β	01101	0.05
Γ	10101	0.25
Δ	00111	0.20
Ε	01110	0.40

* Σε παρένθεση να γράψετε σε ποιο άτομο του αρχικού πληθυσμού αντιστοιχεί, π.χ. 01101 (β).

** Σημειώστε στην προηγούμενη στήλη τα σημεία διασταύρωσης.

Α. (5/20) Να υπολογίσετε την πιθανότητα επιλογής κάθε ατόμου, χρησιμοποιώντας επιλογή εξαναγκασμένης ρουλέτας και τον αναμενόμενο αριθμό αντιγράφων κάθε ατόμου στην επόμενη γενιά και τις αθροιστικές πιθανότητες.

Β. (15/20) Να υπολογίσετε την επόμενη γενιά του πληθυσμού, για Pc=0.8 και Pm=0.25. Να χρησιμοποιήσετε τους παρακάτω τυχαίους αριθμούς:

0.9501    0.2311    0.6068    0.4860    0.8913    0.7621    0.4565    0.0185    0.8214    0.4447    0.6154    0.7919    0.9218     0.7382     0.1763    0.4057    0.9355    0.9169    0.4103    0.8936    0.0579    0.3529    0.8132    0.0099    0.1389    0.2028    0.1987    0.6030     0.8381    0.0196    0.6813      0.3795     0.83180    0.5028    0.7095     0.4966    0.8998     0.8216     0.6449   0.2897

Τα ζεύγη σχηματίζονται ανά δύο με βάση τη σειρά επιλογής



------------------------ΑΠΑΝΤΗΣΗ----------------------------------------------------------------------------------------

Ο υπολογισμός της πιθανότητάς επιλογής κάθε άτομο μπορεί να γίνει ευκολά, παρατηρούμε ότι εάν αθροίζουμε την ικανότητα το αποτέλεσμα είναι 1 δηλαδή 0,40+0,2+0,25+0,05+0,1=1.

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

	Άτομο	Ικανότητα	Πιθανότητα επιλογής	Αθροιστική πιθανότητα
Α	11010	0.10	0.10	0,10
Β	01101	0.05	0.05	0,15
Γ	10101	0.25	0.25	0,40
Δ	00111	0.20	0.20	0,60
Ε	01110	0.40	0.40	100

Μπορούμε να υπολογίσουμε τον αναμενόμενο αριθμό αντιγραφών κάθε ατόμου στην επόμενη γενιά.

Ο αρχικός πληθυσμός είναι 5 άτομα δηλαδή τα  5 άτομα είναι το 100 % του πληθυσμού

            Και το 10% του 5 είναι  10/100 * 5 =50/100 = 0,5 δηλαδή ο αναμμένος αριθμός είναι 0,5

Το ίδιο και για το Β άτομο δηλαδή το 0,05 του 5 είναι 5/100 * 5=0,25 δηλαδή για το Β ο αναμενόμενος αριθμός ατόμων είναι  0,25

Για το Γ είναι 25% και το 25% του 5 είναι 25/100 *5=125/100=1,25 άτομα δηλαδή για το Γ ο αναμενόμενος αριθμός ατόμων είναι 1,25

Για το Δ είναι το 20% και το 20% του 5 είναι 20/100 *5=100/100=1 άτομο δηλαδή για το Δ ο αναμενόμενος πληθυσμός είναι 1

Τέλος το Ε είναι  40% και το 40% του 5 είναι 40/100 * 5=200/100=2 δηλαδή ο αναμενόμενος πληθυσμός για τα ο Δ είναι 2.

Γ

	Άτομο	Ικανότητα	Πιθανότητα επιλογής	Αθροιστική πιθανότητα	Αναμενόμενος Αριθμός Αντιγράφων
Α	11010	0.10	0.10	0,10	0,5
Β	01101	0.05	0.05	0,15	0,25
Γ	10101	0.25	0.25	0,40	1,25
Δ	00111	0.20	0.20	0,60	1
Ε	01110	0.40	0.40	1	2

   

Β

Αρχικά θα υπολογίσουμε τον προσωρινό πληθυσμό  θα  χρησιμοποιήσουμε τους 5 πρώτους τυχαίους αριθμούς για να επιλέξουμε έναν άτομα αναλογία με τον αριθμό

Ο πρώτος τυχαίος αριθμός είναι 0,9501 που αντιστοιχεί  στο άτομο Ε  από τον πίνακα με τις αθροιστικές πιθανότητες συγκεκριμένα για το άτομα Ε ισχύει  0,60 < Ε≤ 1 .

Ο δεύτερος τυχαίος αριθμός είναι 0,2311 και επειδή 0,15 <Γ≤ 40  θα επιλέξουμε το Γ άτομο

Ο τρίτος τυχαίος αριθμός είναι 0,6068 και αντιστοιχεί στο Ε άτομο δηλαδή ισχύει  0,60 < Ε≤ 1 .

Ο τέταρτος αριθμός είναι 0,4860 και θα επιλεχθεί το Δ άτομο διότι ισχύει  0,40 <Δ≤ 0,60 .

Τέλος  το πέμπτος αριθμός είναι  0,8913 όπου θα επιλεχθεί Το άτομο Ε  επειδή ισχύει  0,60 < Ε≤ 1 .

Επομένως ο Προσωρινός πληθυσμός είναι

1.    Α’=01110 (ε)

2.    Β’=10101(γ)

3.    Γ’=01110(ε)

4.    Δ’=00111(δ)

5.    Ε’=01110(ε)

Συνεχίζουμε από το προσωρινό πληθυσμό θα επιλέξουμε με τα επόμενα  πέντε νούμερα  από την ρουλέτα για να δούμε εάν θα διασταυρωθούν. Έχουμε ότι η πιθανότητα διασταύρωσης είναι Pc=0,8  όταν ο αριθμός από την Ρουλέτα είναι μικρότερος από την πιθανότητα διασταύρωσης τότε θα πραγματοποιείται διασταύρωση διαφορετικά το άτομο θα περνά απευθείας .

Έχουμε για το Α’ ο αριθμός από την ρουλέτα είναι 0,7621<Pc=0,8 ) επομένως το άτομο Α΄ διαστρώνεται

Έπειτα για Το Β’ ο αριθμός από την ρουλέτα είναι 0,4565<Pc και το άτομο Β’ διασταυρώνεται

Το Γ΄ ο αριθμός από την ρουλέτα είναι 0,0185<Pc και το Γ΄ διασταυρώνεται

Το Δ΄ ο αριθμός από την ρουλέτα είναι 0,8214 >Pc το Δ’ δεν διασταυρώνεται

Τέλος το Ε’ και ο αριθμός από την ρουλέτα είναι  0,4447 και το Ε΄<Pc και το Ε΄ διασταυρώνεται.

Συνολικά έχουμε.

	Άτομο	Ικανότητα	Προσωρινός Πληθυσμός	Αριθμοί ρουλέτας	Διασταύρωση
Α	11010	0.10	01110 (ε)	0,7621	Ναι
Β	01101	0.05	10101(γ)	0,4565	Ναι
Γ	10101	0.25	01110(ε)	0,0185	Ναι
Δ	00111	0.20	00111(δ)	0,8214	Όχι
Ε	01110	0.40	01110(ε)	0,4447	Ναι

Δηλαδή θα διαστρωθεί  το Α’=01110 (ε) με το Β’=10101(γ)   και

Το  Γ’=01110(ε) με το  Ε’=01110(ε) δηλαδή το Γ΄ και το Ε΄ θα  διασταυρωθούν  (εάν και ίδια η διασταύρωση θα πραγματοποιηθεί )και Δ’=00111(δ) θα περάσει απευθείας.

Συνεχίζουμε με  την διασταύρωση του Α΄ και Β΄ για να βρούμε το σημείο διασταύρωσης θα χρησιμοποιήσουμε τον επόμενο αριθμό από την ρουλέτα και είναι 0,6154  .

Παρακάτω είναι ο πίνακας που αντιστοιχεί το σημείο κοπής  και την πιθανότητα του.

Σημείο	Πιθανότητα (αθροιστική)
1	0,25 πιθανότητα
2	0,50
3	0,75
4	1

0.5<3 sup="">ο

Σημείο κοπης≤0.75   το 0,6154 βρίσκεται στο 3 σημείο επομένως η διασταύρωση θα γίνει στο τρίτο σημείο. έχουμε

Α’=011  |10  ----à  011   01

Β’=101  |01 -----à  101   10

Και η διασταύρωση του Γ’=01110(ε) με το  Ε’=01110(ε)   θα γίνει με την βοήθεια της επομένης ρουλέτας που είναι ο αριθμός 0,7919 και η διασταύρωση θα γίνει στο 4 bit όμως το  Γ΄ και Ε΄ είναι ίσα έτσι θα περάσουν απευθείας .

Δηλαδή ο πληθυσμός μετά την διασταύρωση είναι

1.    Α’’=01101

2.    Β’’=10110

3.    Γ’’=01110

4.    Δ’’=00111

5.    Ε’’=01110

	Άτομο	Ικανότητα	Προσωρινός Πληθυσμός	Διασταύρωση	Πληθυσμός μετά τη Διασταύρωσή
Α	11010	0.10	01110 (ε)	Ναι	01101
Β	01101	0.05	10101(γ)	Ναι	10110
Γ	10101	0.25	01110(ε)	Ναι	01110
Δ	00111	0.20	00111(δ)	Όχι	00111
Ε	01110	0.40	01110(ε)	Ναι	01110

Τελειώνουμε με τον πληθυσμό μετά την μετάλλαξη

έχουμε 5 παιδιά και το κάθε ένα από αυτά έχει 5 bitsδηλαδή η μετάλλαξη μπορεί να συμβεί σε 5 * 5 =25 bits

Για κάθε bit του κάθε ατόμου θα συγκρίνουμε το νούμερο από την ρουλέτα με το Pm=0,25. Όταν η πιθανότητα μετάλλαξης είναι μεγαλύτερη από το νούμερο της ρουλέτας τότε στο bit αυτό θα γένετε μετάλλαξη.

Ξεκινάμε με το Α’’=01101 και τα νούμερα από την ρουλέτα .

1.)     0,9218

2.)    0,7382

3.)    0,1763

4.)    0,4057

5.)    0,9355

Το 3.) είναι 0,17>Pm=0.25 και θα γίνει μετάλλαξη στο 3 bit δηλαδή στο Α’’ το 3 bit από 1 θα γίνει 0 δηλαδή το Α’’’ θα είναι : Α’’’=01001.

Το  επόμενο είναι το Β’’=10110 και τα τυχαία νούμερα από την ρουλέτα είναι

1.       0,9169

2.       0,4103

3.       0,8936

4.       0,0579

5.       0,3529

Θα γίνει μετάλλαξη στο 4^ο bit διότι ο αριθμός είναι μικρότερος της Pm και το Β’’ θα γινει Β’’’=10100.

Στην συνέχεια Γ’’=01110 και τα τυχαία νούμερα

1.       0,8132

2.       0,0099

3.       0,1389

4.       0,2028

5.       0,1987

Θα γίνει μετάλλαξη στο 2^ο ,3^ο,4^ο,5^ο bit διότι οι αριθμοί από την ρουλέτα είναι μικρότεροι από το Pm και το Γ΄΄ θα γίνει Γ’’’=00001

Συνεχίζουμε με το Δ’’=00111 με τους επομένους 5 αριθμούς

1.       0,6030

2.       0,8381

3.       0,0196

4.       0,6813

5.       0,3795

Θα γίνει μετάλλαξη στο 3 bit και το Δ’ ’θα γίνει Δ’’’=00011

Τελειώνουμε με το Ε’’=01110 και οι τυχαίοι αριθμοί

1.       0,83180

2.       0,5028

3.       0,7095

4.       0,4966

5.       0,8998

Δεν θα γίνει μετάλλαξη.

Τώρα μπορούμε να συμπληρώσουμε τον αρχικό πίνακα. 

	Άτομο	Ικανότητα	Πιθανότητα Επιλογής	Αναμενόμενος Αριθμός Αντιγράφων	Προσωρινός Πληθυσμός       *	Πληθυσμός μετά τη Διασταύρωσή **	Πληθυσμός μετά τη Μετάλλαξη (1η γενιά)
Α	11010	0.10	0.10	0,5	01110 (ε)	01101	01001
Β	01101	0.05	0.05	0,25	10101(γ)	10110	10100
Γ	10101	0.25	0.25	1,25	01110(ε)	01110	00001
Δ	00111	0.20	0.20	1	00111(δ)	00111	00011
Ε	01110	0.40	0.40	2	01110(ε)	01110	01110