Eξελικτικό αλγόριθμο που χρησιμοποιεί χρωμοσώματα

Θεωρείστε ένα εξελικτικό αλγόριθμο που χρησιμοποιεί χρωμοσώματα της μορφής: x = abcdefgh, με μήκος l=8 γονίδια. Κάθε γονίδιο μπορεί να είναι οποιοδήποτε ψηφίο από 0 έως 9. Έστω ότι η καταλληλότητα ενός ατόμου x υπολογίζεται από την συνάρτηση:

f (x) = (a + b) − (c + d) + (e + f ) − (g + h),

και έστω ότι ο αρχικός πληθυσμός αποτελείται από 4 άτομα με τα ακόλουθα χρωμοσώματα:

x₁ = 6 5 4 1 3 5 5 2

x₂ = 8 7 1 2 6 6 0 1

x₃ = 2 3 9 2 1 2 8 5

x₄ = 4 1 8 5 2 0 9 4

Α. (3/15): Να υπολογίσετε την καταλληλότητα κάθε ατόμου, (δείχνοντας όλες τις πράξεις), και να τα διατάξετε ως προς φθίνουσα απόδοση.

Β. (3/15) Να κάνετε τις παρακάτω διασταυρώσεις:

i)                              Διασταυρώστε τα δύο καλύτερα άτομα χρησιμοποιώντας διασταύρωση μονού σημείου, στο μεσαίο σημείο κοπής.

ii)                            Διασταυρώστε το 2^ο και 3^ο καλύτερο άτομο, χρησιμοποιώντας διασταύρωση διπλού σημείου (θέσεις κοπής η 2^η και η 6^η).

iii)                          Διασταυρώστε το 1^ο και το 3^ο καλύτερο άτομο, χρησιμοποιώντας ομοιόμορφη διασταύρωση:

Γ. (3/15) Υποθέστε ότι ο νέος πληθυσμός αποτελείται από τα 6 παιδιά που έχουν προκύψει από τις διασταυρώσεις της προηγούμενης ερώτησης. Να υπολογίσετε την καταλληλότητα του νέου πληθυσμού (δείχνοντας όλους τους υπολογισμούς). Έχει βελτιωθεί η συνολική απόδοση του πληθυσμού;

Δ. (3/15) Παρατηρώντας τη συνάρτηση καταλληλότητας και θεωρώντας ότι τα γονίδια μπορούν να είναι ψηφία από 0 έως 9, να βρείτε το χρωμόσωμα που αναπαριστά τη βέλτιστη λύση (δηλαδή που δίνει τη μέγιστη καταλληλότητα). Να βρείτε την τιμή της μέγιστης καταλληλότητας.

Ε. (3/15) Παρατηρώντας τον αρχικό πληθυσμό του αλγορίθμου, μπορείτε να πείτε αν είναι δυνατόν να βρει τη βέλτιστη λύση, χωρίς την εφαρμογή του τελεστή μετάλλαξης;
----------------ΑΠΑΝΤΗΣΗ-----------------------------------------------------------------------------------------------

Η καταλληλόλητα κάθε ατόμου υπολογίζεται από την συνάρτηση f(x) όπου

f (x) = (a + b) − (c + d) + (e + f ) − (g + h),

σε κάθε άτομο Χ θα υπολογίσουμε την τιμή. Τα άτομα είναι 4

x₁ = 6 5 4 1 3 5 5 2

x₂ = 8 7 1 2 6 6 0 1

x₃ = 2 3 9 2 1 2 8 5

x₄ = 4 1 8 5 2 0 9 4

Υπολογίζουμε για το x₁ = 6 5 4 1 3 5 5 2 είναι

f (x₁) = (6 + 5) − (4 + 1) + (3 + 5 ) − (5 + 2)=11-5-8+7=19-12=7

Υπολογίζουμε το x₂ =  8 7 1 2 6 6 0 1είναι

f (x₂) = (8 + 7) − (1 + 2) + (6 + 6 ) − (0 + 1)=15-3+12-1=27-4=23

Υπολογίζουμε το x₃ = 2 3 9 2 1 2 8 5             είναι

f (x₃) = (2 + 3) − (9 + 2) + (1 + 2 ) − (8 + 5)=5-11+3-13=8-24=-16

Υπολογίζουμε το x₄ = 4 1 8 5 2 0 9 4 είναι

f (x₄) = (4+ 1) − (8 + 5) + (2 + 0 ) − (9 + 4)=5-13+2-13=7-26=-19

Τώρα μπορούμε να διατάξουμε σε φθίνουσα σειρά.

f (x₂) =23

f (x₁) =7

f (x₃) = -16

f (x₄) = -19

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

f (x₂) =23 +20=43

f (x₁) =7 +20=27

f (x₃) = -16+20=4

f (x₄) = -19+20=1

προσθέσαμε 20 για να γίνει η F(x4) μονάδα για να έχει και αυτό το χρωμόσωμα την ευκαιρία να αναπαραχθεί  γιατί εάν ήταν μηδέν δεν θα επιλεγόταν.

Α.

i.)

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

Τα δυο καλυτέρα άτομα είναι το x2 = 8 7 1 2 6 6 0 1 και το x1 = 6 5 4 1 3 5 5 2 και θα διασταυρωθούν στο μεσαίο σημείο κοπής δηλαδή στο 4 σημείο . έχουμε

x2 = 8 7 1 2 | 6 6 0 1 x1 = 6 5 4 1 | 3 5 5 2

και τα παιδιά   Χ2_1= 8 7 1 2  3 5 5 2 >>>>>>   Χ2_2 =6 5 4 1 6 6 0 1

     

ii) Το δεύτερο καλύτερο άτομο και το τρίτο καλύτερο άτομο χρησιμοποιώντας διασταύρωση διάπλου σημείου (θέσεις 2^η και 6^η )

Το δεύτερο καλύτερο άτομο είναι το x₁ = 6 5 4 1 3 5 5 2 και το τρίτο καλύτερο είναι x₃ = 2 3 9 2 1 2 8 5 και θα γίνει διασταύρωση στην 2 και 6 θέση είναι

x1 = 6 5| 4 1 3 5|  5 2 x3 = 2 3| 92 1 2 | 8 5

και τα παιδιά   Χ2_3= 6 5 |92 1 2 |  5 2= Χ2_3= 65921252 >>>>>>   Χ2_4 =2 3|413 5| 8 5= Χ2_4 =2341358 5

iii) Το πρώτο καλύτερο άτομο είναι x2 = 8 7 1 2 6 6 0 1 και το 3^ο καλύτερο άτομο x₃ = 2 3 9 2 1 2 8 5

θα χρησιμοποιήσουμε ομοιόμορφη διασταύρωση  .

Για την ομοιόμορφή διασταύρωση θα χρησιμοποιήσουμε την μάσκα 10011010 και όταν η τιμή της μάσκας είναι 1 τότε  το πρώτο παιδί Χ2_5 παίρνει τιμή από το γονέα Χ1 ενώ όταν είναι 0 από το Χ3 και αντίστροφα το δεύτερο παιδί,  δηλαδή έχουμε

Mask=1 0 0 1 1 0 1 0 x2 =    8 7  1 2 6 6 0 1 x3 =    2 3  9 2 1 2 8 5

και τα παιδιά   Χ2_5= 8 3  9 2 6 2 0 5 >>>>>>                Χ2_6 =2 7  1 2 1 6 8 1

Γ.

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

Χ2_1= 87123552

Χ2_2 =65416601     

Χ2_3= 65921252

Χ2_4 =2341358 5

Χ2_5= 83926205

Χ2_6 =27121681                  

Υπολογίσουμε την καταλληλότατα των νέων  χρωμοσωμάτων

F(Χ2_1)= (8+7)-(1+2)+(3+5)-(5+2)=15-3+8-7=23-10=13

F(Χ2_1)= (6+5)-(4+1)+(6+6)-(0+1)=11-5+12-1=23-6= 17

F(Χ2_3)= (6+5)-(9+2)+(1+2)-(5+2)=11-11+3-7=3-7=-4

F(Χ2_4) =(2+3)-(4+1)+(3+5)-(8+ 5)=5-5+8-13=-5

F(Χ2_5)= (8+3)-(9+2)+(6+2)-(0+5)=11-11+8-5=3

F(Χ2_6) =(2+7)-(1+2)+(1+6)-(8+1)=9-3+7-9   =7-3=4     

Συνολική απόδοση είναι  13+17-4-5+3+4  =28     

Και η αποδόσεις των γονέων  είναι 

f (x₂) =23

f (x₁) =7

f (x₃) = -16

f (x₄) = -19

Συνολικά 23+7-16-19=-5

 Το πλήθος των παιδιών είναι 6 και το πλήθος των γονέων είναι 4 .

Η μέση απόδοση των παιδιών είναι 28/6=4,666

Και η μέση απόδοση των γονέων είναι -5/4=-1,25

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

Δ.

Η συνάρτηση ακαταλληλότητας είναι f (x) = (a + b) − (c + d) + (e + f ) − (g + h),

Και 9 ≤a,b,c,d,e,f,g,h ≥0 . Το καταλληλότερο άτομα είναι όπου η f είναι μέγιστη και επειδή η μεταβλητές της συνάρτησης f(x) είναι μόνο θετικοί πρέπει οι τιμές που αφαιρούμε να είναι οι μικρότερες δυνατές που είναι 0. Αντίθετα οι τιμές που προτίθενται πρέπει να είναι οι μεγαλύτερες δηλαδή 9. Συμπεραίνουμε ότι θα είναι

f (x)_max = (a + b)_max − (c + d)_min + (e + f )_max − (g + h)_min δηλαδή

f (x)_max = (9 + 9)     − (0 + 0)   +    (9 + 9 )    −  (0+ 0)  = 36

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

Χ_βελτ=99009900

Ε.

Ο αρχικός πληθυσμός είναι

x₁ = 6 5 4 1 3 5 5 2

x₂ = 8 7 1 2 6 6 0 1

x₃ = 2 3 9 2 1 2 8 5

x₄ = 4 1 8 5 2 0 9 4

Η βέλτιστη λύση είναι Χ_βελτ=99009900.

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

x₁ = 6

x₂ = 8

x₃ = 2

x₄ = 4

ενώ  το βέλτιστο είναι Χ_βελτ=9

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